30:T6fe,errors = { const errors = new Float32Array(gridSize * gridSize); const numSmallestTriangles = tileSize * tileSize; const numTriangles = numSmallestTriangles * 2 - 2; // 2 + 4 + 8 + ... 2^k = 2 * 2^k - 2 const lastLevelIndex = numTriangles - numSmallestTriangles; // iterate over all possible triangles, starting from the smallest level for (let i = numTriangles - 1; i >= 0; i--) { // get triangle coordinates from its index in an implicit binary tree let id = i + 2; let ax = 0, ay = 0, bx = 0, by = 0, cx = 0, cy = 0; if (id & 1) { bx = by = cx = tileSize; // bottom-left triangle } else { ax = ay = cy = tileSize; // top-right triangle } while ((id >>= 1) > 1) { const mx = (ax + bx) >> 1; const my = (ay + by) >> 1; if (id & 1) { // left half bx = ax; by = ay; ax = cx; ay = cy; } else { // right half ax = bx; ay = by; bx = cx; by = cy; } cx = mx; cy = my; } // calculate error in the middle of the long edge of the triangle const interpolatedHeight = (terrain[ay * gridSize + ax] + terrain[by * gridSize + bx]) / 2; const middleIndex = ((ay + by) >> 1) * gridSize + ((ax + bx) >> 1); const middleError = Math.abs(interpolatedHeight - terrain[middleIndex]); if (i >= lastLevelIndex) { // smallest triangles errors[middleIndex] = middleError; } else { // bigger triangles; accumulate error with children const leftChildError = errors[((ay + cy) >> 1) * gridSize + ((ax + cx) >> 1)]; const rightChildError = errors[((by + cy) >> 1) * gridSize + ((bx + cx) >> 1)]; errors[middleIndex] = Math.max(errors[middleIndex], middleError, leftChildError, rightChildError); } } return errors; }31:[] 2e:{"title":"Мартуни: использование MARTINI в нашем рельефе","cells":[{"id":0,"value":"md`# Мартуни: использование MARTINI в нашем рельефе`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1578,"value":"Ну вот я нашел MARTINI :boozy-artist: \n\nПакетик интересен тем, что размер получаемого меша практически сравним по размеру с нашими тайлами рельефа, а значит использование этого меша в качестве тайлов рельефа в теории возможно.\n\nО принципах работы этого пакетика лучше всего почитать в прообразе данного нотебука, написанного Агафонкиным https://observablehq.com/@mourner/martin-real-time-rtin-terrain-mesh\n\nПакет работает на базе некой \"Правосторонней нерегулярной триангуляции\" о которой можно почитать в пейпере: https://www.cs.ubc.ca/~will/papers/rtin.pdf Вкратце, это такой Дуглас-Пекер, но для 3D.","pinned":false,"hidden":false,"mode":"md"},{"id":1609,"value":"### Подводные камни\n\nКуда же без них. При объединении тайлов меша потребуется дополнительный код, который бы \"сшивал\" меш в единое целое.\n\nИ еще будет достаточно проблематично получить нужное значение высоты в конкретной точке в JS. Придется или городить структуру данных или лазить в GPU за высотой.","pinned":false,"hidden":false,"mode":"md"},{"id":1588,"value":"## Адрес тайла:","pinned":false,"hidden":false,"mode":"md"},{"id":1548,"value":"viewof location = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":864,"value":"renderer.domElement","pinned":false,"hidden":false,"mode":"ojs"},{"id":310,"value":"viewof maxError = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":556,"value":"{\n const numTriangles = updatedGeometry.drawRange.count / 3;\n const indicesCount = updatedGeometry.drawRange.count;\n const maxTriangles = tileSize * tileSize * 2;\n return md`Сгенерировано ${numTriangles} (${(100 * numTriangles / maxTriangles).toFixed(2)}%) треугольников с ошибкой ${maxError.toFixed(1)}м из тайла размером ${tileSize}×${tileSize}px. \n\nРазмер тайла ${(indicesCount * 2 / 1024).toFixed(3)}КиБ`\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":220,"value":"{\n const size = Math.min(width, 640);\n const ratio = size / tileSize;\n const ctx = DOM.context2d(size, size, 2);\n \n ctx.fillStyle = 'white';\n ctx.fillRect(0, 0, size, size);\n\n ctx.globalAlpha = 0.4;\n ctx.drawImage(terrainViz, 0, 0, size, size);\n ctx.globalAlpha = 1;\n \n ctx.lineWidth = 0.5;\n ctx.beginPath();\n\n function split(ax, ay, bx, by, cx, cy) {\n const mx = (ax + bx) >> 1;\n const my = (ay + by) >> 1;\n\n if (Math.abs(ax - cx) + Math.abs(ay - cy) > 1 && errors[my * (tileSize + 1) + mx] > maxError) {\n ctx.moveTo(mx * ratio, my * ratio);\n ctx.lineTo(cx * ratio, cy * ratio);\n split(cx, cy, ax, ay, mx, my);\n split(bx, by, cx, cy, mx, my);\n }\n }\n \n ctx.moveTo(0, 0);\n ctx.lineTo(ratio * tileSize, ratio * tileSize);\n \n split(0, 0, tileSize, tileSize, tileSize, 0, 0);\n split(tileSize, tileSize, 0, 0, 0, tileSize, 0);\n \n ctx.stroke();\n \n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":704,"value":"md`## Подготовка данных высоты\n\nВысота берется из наших тайлов рельефа, а затем декодируется нашим декодером\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":741,"value":"tileCoord = location.split('/').map(Number)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1192,"value":"tileImg = fetch(`https://tileserver.web-staging.2gis.ru/v2/ald?ts=relief_hd&x=${tileCoord[1]}&y=${tileCoord[2]}&z=${tileCoord[0]}`)\n .then(r => r.arrayBuffer())","pinned":true,"hidden":false,"mode":"ojs"},{"id":1209,"value":"tileSize = (tileImg.byteLength / 2) ** 0.5","pinned":false,"hidden":false,"mode":"ojs"},{"id":1195,"value":"md`Ниже происходит декодирование в высоты в метрах:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":28,"value":"terrain = {\n const terrain = new Float32Array(gridSize * gridSize);\n const tileData = new Uint8Array(tileImg);\n \n for (let y = 0; y < tileSize; y++) {\n for (let x = 0; x < tileSize; x++) {\n const index = x + y * tileSize;\n const height = tileData[index] + tileData[tileSize ** 2 + index] * 256 - 10000;\n terrain[y * gridSize + x] = height;\n }\n }\n // backfill right and bottom borders\n for (let x = 0; x < gridSize - 1; x++) {\n terrain[gridSize * (gridSize - 1) + x] = terrain[gridSize * (gridSize - 2) + x];\n }\n for (let y = 0; y < gridSize; y++) {\n terrain[gridSize * y + gridSize - 1] = terrain[gridSize * y + gridSize - 2];\n }\n return terrain;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1616,"value":"terrainViz = drawGrid(terrain)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1031,"value":"gridSize = tileSize + 1","pinned":false,"hidden":false,"mode":"ojs"},{"id":36,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":777,"value":"updatedGeometry = {\n let i = 0;\n const indices = geometry.index.array;\n \n function processTriangle(ax, ay, bx, by, cx, cy) {\n // middle of the long edge\n const mx = (ax + bx) >> 1;\n const my = (ay + by) >> 1;\n\n if (Math.abs(ax - cx) + Math.abs(ay - cy) > 1 && errors[my * gridSize + mx] > maxError) {\n // triangle doesn't approximate the surface well enough; split it into two\n processTriangle(cx, cy, ax, ay, mx, my);\n processTriangle(bx, by, cx, cy, mx, my);\n\n } else {\n // add a triangle to the final mesh\n indices[i++] = ay * gridSize + ax;\n indices[i++] = by * gridSize + bx;\n indices[i++] = cy * gridSize + cx;\n }\n }\n\n processTriangle(0, 0, tileSize, tileSize, tileSize, 0);\n processTriangle(tileSize, tileSize, 0, 0, 0, tileSize);\n \n geometry.index.needsUpdate = true;\n geometry.setDrawRange(0, i);\n renderer.render(scene, camera);\n\n console.log(indices, i);\n \n return geometry;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":883,"value":"md`## Three.js terrain setup`","pinned":false,"hidden":false,"mode":"ojs"},{"id":993,"value":"geometry = {\n const geometry = new THREE.BufferGeometry();\n\n const vertices = new Float32Array(gridSize * gridSize * 3);\n const indices = new Uint32Array(tileSize * tileSize * 6);\n let index = 0;\n\n for (let y = 0; y <= tileSize; y++) {\n for (let x = 0; x <= tileSize; x++) {\n const i = y * gridSize + x;\n vertices[3 * i + 0] = x / tileSize - 0.5;\n vertices[3 * i + 1] = 0.5 - y / tileSize;\n vertices[3 * i + 2] = terrain[i] / metersPerPixel / tileSize * terrainExaggeration;\n\n indices[index++] = i + 1;\n indices[index++] = i;\n indices[index++] = i + gridSize;\n indices[index++] = i + 1;\n indices[index++] = i + gridSize;\n indices[index++] = i + gridSize + 1;\n }\n }\n \n geometry.addAttribute('position', new THREE.BufferAttribute(vertices, 3));\n geometry.setIndex(new THREE.BufferAttribute(indices, 1));\n geometry.computeVertexNormals();\n \n return geometry;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":763,"value":"camera = {\n const camera = new THREE.PerspectiveCamera(45, Math.min(width, 640) / height, 0.1, 1000);\n camera.position.set(0.2, -0.7, 0.9);\n camera.up.set(0, 0, 1);\n camera.lookAt(new THREE.Vector3(0, 0, 0));\n return camera;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":766,"value":"scene = {\n const scene = new THREE.Scene();\n scene.background = new THREE.Color(0x333333);\n const material = new THREE.MeshNormalMaterial({flatShading: true, side: THREE.DoubleSide});\n const mesh = new THREE.Mesh(geometry, material);\n mesh.name = 'terrain';\n scene.add(mesh);\n return scene;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":769,"value":"renderer = {\n const renderer = new THREE.WebGLRenderer({antialias: true});\n const controls = new THREE.OrbitControls(camera, renderer.domElement);\n invalidation.then(() => (controls.dispose(), renderer.dispose()));\n renderer.setSize(Math.min(width, 640), height);\n renderer.setPixelRatio(devicePixelRatio);\n controls.addEventListener(\"change\", () => renderer.render(scene, camera));\n renderer.render(scene, camera);\n return renderer;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":756,"value":"height = 420","pinned":false,"hidden":false,"mode":"ojs"},{"id":584,"value":"md`## Other stuff`","pinned":false,"hidden":false,"mode":"ojs"},{"id":957,"value":"terrainExaggeration = 1.5","pinned":false,"hidden":false,"mode":"ojs"},{"id":934,"value":"metersPerPixel = {\n const [z, x, y] = tileCoord;\n const numTiles = Math.pow(2, z);\n const lat = 2 * Math.atan(Math.exp((1 - 2 * (y + 0.5) / numTiles) * Math.PI)) - Math.PI / 2;\n return 40075016.7 * Math.cos(lat) / numTiles / tileSize;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":181,"value":"drawGrid = (data, cutoff = 1.0, max = 1.0) => {\n const size = Math.sqrt(data.length);\n const ctx = DOM.context2d(size, size, 1);\n ctx.canvas.style.imageRendering = 'pixelated';\n if (!ctx.canvas.style.imageRendering) ctx.canvas.style.imageRendering = 'crisp-edges';\n const imgData = ctx.getImageData(0, 0, size, size);\n const minZ = data.reduce((a, b) => Math.min(a, b));\n const maxZ = data.reduce((a, b) => Math.max(a, b));\n \n for (let y = 0; y < size; y++) {\n for (let x = 0; x < size; x++) {\n const k = y * size + x;\n const [r, g, b] = turbo(Math.min(max, max * Math.min((data[k] - minZ) / (maxZ - minZ), cutoff) / cutoff));\n imgData.data[4 * k + 0] = r;\n imgData.data[4 * k + 1] = g;\n imgData.data[4 * k + 2] = b;\n imgData.data[4 * k + 3] = 255;\n }\n }\n ctx.putImageData(imgData, 0, 0);\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"turbo = (x) => [\n 34.61 + x * (1172.33 - x * (10793.56 - x * (33300.12 - x * (38394.49 - x * 14825.05)))),\n 23.31 + x * (557.33 + x * (1225.33 - x * (3574.96 - x * (1073.77 + x * 707.56)))),\n 27.2 + x * (3211.1 - x * (15327.97 - x * (27814 - x * (22569.18 - x * 6838.66))))\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":1059,"value":"md`## Imports`","pinned":false,"hidden":false,"mode":"ojs"},{"id":753,"value":"THREE = {\n const THREE = window.THREE = await require(\"three@0.107.0/build/three.min.js\");\n await require(\"three@0.107.0/examples/js/controls/OrbitControls.js\").catch(() => {});\n return THREE;\n}","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}