31:T679,md`# MARTINI: Real-Time RTIN Terrain Mesh To **render terrain in 3D**, you need a **triangular mesh** — a set of 3D triangles representing the surface. The easiest way to get one from height data is a uniform grid (two triangles per pixel), but that's _a lot_ of triangles. For fast rendering, we want to reduce this amount by adapting the mesh to the surface — using bigger triangles in relatively smooth areas, and smaller ones where there's a lot of detail. One such approach, [proposed by Will Evans et al. in 1997](https://www.cs.ubc.ca/~will/papers/rtin.pdf), is called **Right-Triangulated Irregular Networks**, or **RTIN**. An RTIN mesh consists of only right-angle triangles, which makes it less precise than Delaunay-based TIN meshes, requiring more triangles to approximate the same surface. But RTIN has two significant advantages: 1. The algorithm generates a **hierarchy of all approximations** of varying precisions — after running it once, you can quickly retrieve a mesh for any given level of detail. 2. It's very fast, making it viable for **client-side meshing** from raster terrain tiles. Surprisingly, I haven't found any prior attempts to do it in the browser. So let me present you a client-side terrain mesh generation code I called **MARTINI**: [**M**apbox](https://www.mapbox.com)'s **A**wesome **R**ight-**T**riangulated **I**rregular **N**etworks **I**mproved! It will live as an open source library at [github.com/mapbox/martini](https://github.com/mapbox/martini). Drag and zoom the terrain visualization below, and drag the slider to adjust mesh precision in real time. Then we'll dive into how this works. `32: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; }33:T47c,viewof mesh_creation={ replay; await visibility(); const size = Math.min(width, 512); const ratio = size / tileSize; const ctx = DOM.context2d(size, size, 2); ctx.fillStyle = 'white'; ctx.fillRect(0, 0, size, size); ctx.globalAlpha = 0.5; ctx.drawImage(terrainViz, 0, 0, size, size); ctx.globalAlpha = 1; function drawLine(ax, ay, bx, by, color) { ctx.beginPath(); ctx.moveTo(ax * ratio, ay * ratio); ctx.lineTo(bx * ratio, by * ratio); ctx.strokeStyle = color; ctx.stroke(); } function* split(ax, ay, bx, by, cx, cy) { const mx = (ax + bx) >> 1; const my = (ay + by) >> 1; if (Math.abs(ax - cx) + Math.abs(ay - cy) > 1 && errors[my * (tileSize + 1) + mx] > 100) { drawLine(mx, my, cx, cy, 'red'); yield ctx.canvas; yield* split(cx, cy, ax, ay, mx, my); yield* split(bx, by, cx, cy, mx, my); drawLine(mx, my, cx, cy, 'black'); } } drawLine(0, 0, tileSize, tileSize, 'red'); yield* split(0, 0, tileSize, tileSize, tileSize, 0, 0); yield* split(tileSize, tileSize, 0, 0, 0, tileSize, 0); drawLine(0, 0, tileSize, tileSize, 'black'); }34:T4a1,md`Note that **for this demo's purposes**, we allocate maximum possible vertex/index buffers at the beginning, and only update the index array and draw range on precision change; in real world apps, the approach would be different since we wouldn't need to update the mesh of a tile as often, and would instead only upload the vertices and indices used in the mesh, reducing the load on the GPU. This is reflected in the [actual library](https://github.com/mapbox/martin), where mesh retrieval routine generates an array of vertices that are only used in that mesh (avoiding duplicate vertices), and triangles referencing it. ## Thanks! Thank you for reading! Feel free to reach out to me [on Twitter](https://twitter.com/mourner) with comments & questions, check out [the repository](https://github.com/mapbox/martin) (very much a work in progress), and stay tuned for more cool stuff while we explore the 3D space! P.S. Originally I named this project MARTIN, completely forgetting there's an [existing awesome Mapbox-related open source project](https://martin.urbica.co) with the same name! After embarassing myself, I had to hastily rename this to MARTINI to save face. 😅 `35:[] 2f:{"title":"MARTINI: Real-Time RTIN Terrain Mesh","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1433,"value":"viewof location = html``;","pinned":false,"hidden":false,"mode":"ojs"},{"id":864,"value":"viewof viz=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 maxTriangles = tileSize * tileSize * 2;\n return md`Generated ${numTriangles} (${(100 * numTriangles / maxTriangles).toFixed(2)}%) triangles at ${maxError.toFixed(1)}m error from a ${tileSize}×${tileSize}px tile.`\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":220,"value":"viewof mesh={\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":1073,"value":"md`For demo purposes, we render the 3D viz above in a way where the triangles would be clearly visible, but with proper lighting and shading, the terrain would look smooth. Also, it's exaggerated by a factor of ${terrainExaggeration} to make it more prominent.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":704,"value":"md`## Preparing Height Data\n\nLet's get a sample elevation data from a [Mapbox Terrain-RGB](https://docs.mapbox.com/help/troubleshooting/access-elevation-data/#mapbox-terrain-rgb) ${tileSize}×${tileSize} raster tile:\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 = fetchImage(`https://a.tiles.mapbox.com/v4/mapbox.terrain-rgb/${location}.png?access_token=${mapboxToken}`)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1209,"value":"tileSize = tileImg.width","pinned":false,"hidden":false,"mode":"ojs"},{"id":1195,"value":"md`Then we'll decode it into a grid of height values in meters:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":28,"value":"terrain = {\n const ctx = DOM.context2d(tileSize, tileSize, 1);\n ctx.drawImage(tileImg, 0, 0);\n const data = ctx.getImageData(0, 0, tileSize, tileSize).data;\n\n const terrain = new Float32Array(gridSize * gridSize);\n \n // decode terrain values\n for (let y = 0; y < tileSize; y++) {\n for (let x = 0; x < tileSize; x++) {\n const k = (y * tileSize + x) * 4;\n const r = data[k + 0];\n const g = data[k + 1];\n const b = data[k + 2];\n terrain[y * gridSize + x] = (r * 256 * 256 + g * 256.0 + b) / 10.0 - 10000.0;\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":71,"value":"terrainViz = drawGrid(terrain)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1124,"value":"md`The RTIN algorithm works on grids of the size _(2^k+1)_ × _(2^k+1)_ — that's why we add 1-pixel borders on the right and bottom. On interactive maps, this property would also help us stitch the tiles together for seamless terrain.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1031,"value":"gridSize = tileSize + 1","pinned":false,"hidden":false,"mode":"ojs"},{"id":709,"value":"md`## Generating RTIN Hierarchy\n\nThe RTIN algorithm generates an error map — a grid of error values that will guide subsequent mesh retrieval by indicating whether to split a certain triangle in the middle given its height error value in that position. It looks like this:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":206,"value":"{\n const canvas = drawGrid(errors, 0.1, 0.85);\n canvas.style.width = Math.min((canvas.width * 2), width, 514) + 'px';\n return canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":924,"value":"md`The idea is to start with the smallest triangles, calculating the approximation error for each, and then propagate that error to parent triangles (keeping track of maximum error), repeating the process until we reach the top two triangles and have a full error map.\n\nThe way we accumulate errors from child triangles makes the resulting meshes conformal — meaning there are no T-junctions, and consequently no gaps in the mesh.\n\nThe algorithm has an _O(numPixels)_ computational complexity and takes just **40 lines of code**, and runs in about **20ms** on my laptop:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":36,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":727,"value":"md`## Retrieving a Mesh\nTo retrieve a mesh from an RTIN hierarchy, we start with two big triangles and recursively subdivide them when they don't approximate the underlying surface well enough according the error map. This is essentially a depth-first search in an implicit binary tree of triangles, and takes _O(numTriangles)_ steps, resulting in nearly instant mesh generation. \n\nHere's a visualization of mesh retrieval for a 100 meters error:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1273,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":1277,"value":"viewof replay = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":1286,"value":"md`And here's the code for updating the mesh of the actual 3D terrain visualization at the top of the notebook:`","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 return geometry;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1052,"value":"$34","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":1222,"value":"mapboxToken = 'pk.eyJ1IjoibW91cm5lciIsImEiOiJWWnRiWG1VIn0.j6eccFHpE3Q04XPLI7JxbA'","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"},{"id":22,"value":"import {fetchImage} from '@mbostock/cross-origin-images'","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}