Multi-resolution tiled 2.5D delaunay triangulation stitching

A method for reconstructing a coherent tiled mesh surface, comprising:

• building, by a software process executing on an electronic device, a spatial index for 2.5D data, the spatial index including nodes that correspond to a plurality of tiles of the 2.5D data;
• applying a 2.5D Delaunay triangulation algorithm to data of nodes of the spatial index to create a plurality of independent mesh surfaces that each correspond to a tile;
• stitching, by the software process, the plurality of independent mesh surfaces together to form the coherent tiled mesh surface, the stitching, for each independent mesh surface, including:
• removing boundary triangles and triangles influenced by neighboring tiles, wherein triangles influenced by neighboring tiles include triangles whose circumcircle intersects the tile's boundaries,
• triangulating points of removed triangles with a set of constraints that include constraints from neighboring tiles, to produce a context, and
• merging the context and the remaining triangles of the independent mesh surface, to produce a stitched mesh surface;
• and
• outputting the coherent tiled mesh surface.

An electronic device comprising:

• a display screen;
• a processor;
• and
• a memory coupled to the processor configured to store tiles of 2.5D data and instructions of a coherent tiled mesh creation process, the instructions executable on the processor and when executed operable to:
• access the tiles of a 2.5D data,
• apply a 2.5D Delaunay triangulation algorithm to data of each tile to create a plurality of independent mesh surfaces that each correspond to a tile,
• stitch the plurality of independent mesh surfaces together to form a coherent tiled mesh surface, at least in part, by removing boundary triangles and triangles influenced by neighboring tiles from the independent mesh surface wherein triangles influenced by neighboring tiles include triangles whose circumcircle intersects the tile's boundary, triangulating points of removed triangles with constraints, merging the context and the remaining triangles of the independent mesh surface to produce a stitched mesh surface, and cutting the stitched mesh surface resulting from the merging to the tile's boundaries, and
• display the coherent tiled mesh surface on the display screen.

A non-transitory electronic device-readable medium having executable instructions stored thereon, the instructions when executed on one or more processing units operable to:

• apply a 2.5D Delaunay triangulation algorithm to a plurality of tiles of the 2.5D data to create a plurality of independent mesh surfaces that each correspond to a tile;
• stitch, by the software process, the plurality of independent mesh surfaces together to form a coherent tiled mesh surface, the stitching, for each independent mesh surface including:
• removing boundary triangles and triangles influenced by neighboring tiles from the independent mesh surface,
• compute a polygon surrounding all the remaining triangles of the independent mesh surface,
• triangulating points of removed triangles with a set of constraints that include constraints from neighboring tiles to produce a context, wherein the constraints used in the triangulating points of removed triangles include the computed polygon as a void constraint, and
• merging the context and the remaining triangles of the independent mesh surface, to produce a stitched mesh surface;
• and
• output the coherent tiled mesh surface.

A non-transitory electronic device-readable medium having executable instructions stored thereon, the instructions when executed on one or more processing units operable to:

• apply a 2.5D Delaunay triangulation algorithm to a plurality of tiles of the 2.5D data to create a plurality of independent mesh surfaces that each correspond to a tile;
• stitch, by the software process, the plurality of independent mesh surfaces together to form a coherent tiled mesh surface, the stitching, for each independent mesh surface, including:
• removing boundary triangles and triangles influenced by neighboring tiles from the independent mesh surface, wherein triangles influenced by neighboring tiles include triangles whose circumcircle intersects the tile's boundary,
• triangulating points of removed triangles with a set of constraints that include constraints from neighboring tiles, to produce a context, and
• merging the context and the remaining triangles of the independent mesh surface, to produce a stitched mesh surface;
• and
• output the coherent tiled mesh surface.