US Patent 10255716 Multi-resolution tiled 2.5D delaunay triangulation stitching

In an example embodiment, a technique is provided for reconstructing a coherent tiled mesh surface that preserves the 2.5D Delaunay property. A spatial index is built for 2.5D data, the spatial index including nodes that correspond to a plurality of tiles of the 2.5D data. A 2.5D Delaunay triangulation algorithm is applied to data of nodes of the spatial index to create a plurality of independent mesh surfaces that each correspond to a tile. The plurality of independent mesh surfaces are stitched together to form the coherent tiled mesh surface. After a coherent mesh surface for a level of detail (LOD) is created, it is determined whether a new level of detail (LOD) is required. If so, one or more independent mesh surfaces that have the new LOD are created and stitching is repeated. Finally, a coherent multi-resolution tiled mesh surface is output.