Mapbox introduces MARTINI, a client-side terrain mesh generation code

Two days ago, Vladimir Agafonkin, an engineer at Mapbox introduced client-side terrain mesh generation code, called MARTINI, short for ‘Mapbox’s Awesome Right-Triangulated Irregular Networks Improved’. It uses a Right-Triangulated Irregular Networks (RTIN) mesh, which consists of big right-angle triangles to render smooth and detailed terrain in 3D. RTIN has two advantages such as:

• The algorithm generates a hierarchy of all approximations of varying precision, thus enabling quick retrieving.
• It is very fast making it feasible for client-side meshing from raster terrain tiles.

In a blog post, Agafonkin demonstrates a drag and zoom terrain visualization for users to adjust mesh precision in real time. The terrain visualization also displays the number of triangles generated with an error rate.

Image Source: Observable

How does the RTIN Hierarchy work

Mapbox’s MARTINI uses the RTIN algorithm which has a size of (2k+1) x (2k+1) grids, “that’s why we add 1-pixel borders on the right and bottom”, says Agafonkin. The RTIN algorithm initiates an error map where a grid of error values guides the following mesh retrieval. The error map indicates the user if a certain triangle has to be split or not, by taking the height error value into account.

The RTIN algorithm first calculates the error approximation of the smallest triangles, which is then propagated to the parent triangles. This process is repeated until the top two triangles’ errors are calculated and a full error map is produced. This process results in zero T-junctions and thus no gaps in the mesh.

Image Source: Observable

For retrieving a mesh, RTIN hierarchy starts with two big triangles, which is then subdivided to approximate, according to the error map. Agafonkin says, “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.”

Users have appreciated the Mapbox’s MARTINI demo and animation presented by Agafonkin in the blog post.

A user on Hacker News says, “This is a wonderful presentation of results and code, well done! Very nice to read.”

Another user comments, “Fantastic. Love the demo and the animation.”

Another comment on Hacker News reads, “This was a pleasure to play with on an iPad. Excellent work.”

For more details on the code and algorithm used in Mapbox’s MARTINI, check out Agafonkin’s blog post.

Read Next

Introducing Qwant Maps: an open source and privacy-preserving maps, with exclusive control over geolocated data

Top 7 libraries for geospatial analysis

Using R to implement Kriging – A Spatial Interpolation technique for Geostatistics data