Keenan Crane

CARNEGIE MELLON UNIVERSITY

Navigating Intrinsic Triangulations

SIGGRAPH 2019 / ACM Transactions on Graphics 2019

We present a data structure that makes it easy to run a large class of algorithms from computational geometry and scientific computing on extremely poor-quality surface meshes. Rather than changing the geometry, as in traditional remeshing, we consider *intrinsic triangulations* which connect vertices by straight paths along the exact geometry of the input mesh. Our key insight is that such a triangulation can be encoded implicitly by storing the direction and distance to neighboring vertices. The resulting *signpost data structure* then allows geometric and topological queries to be made on-demand by tracing paths across the surface. Existing algorithms can be easily translated into the intrinsic setting, since this data structure supports the same basic operations as an ordinary triangle mesh (vertex insertions, edge splits, *etc.*). The output of intrinsic algorithms can then be stored on an ordinary mesh for subsequent use; unlike previous data structures, we use a constant amount of memory and do not need to explicitly construct an *overlay mesh* unless it is specifically requested. Working in the intrinsic setting incurs little computational overhead, yet we can run algorithms on extremely degenerate inputs, including all manifold meshes from the *Thingi10k* data set. To evaluate our data structure we implement several fundamental geometric algorithms including intrinsic versions of Delaunay refinement and optimal Delaunay triangulation, approximation of Steiner trees, adaptive mesh refinement for PDEs, and computation of Poisson equations, geodesic distance, and flip-free tangent vector fields.

Presentation

Teaser Video

navigating-intrinsic-triangulations-demo—C++ implementation and simple interactive demo of intrinsic Delaunay triangulation and intrinsic Delaunay refinement (with visualization via Polyscope).

This work was supported by a Packard Fellowship, NSF Award 1717320, an NSF Graduate Research Fellowship, a Kortschak Scholars Graduate Fellowship, and gifts from Autodesk, Adobe, and Facebook.

Supplemental

Supplemental Material — additional details about efficient implementation and adaptive mesh refinement.

@article{Sharp:2019:NIT,
author = {Nicholas Sharp and Yousuf Soliman and Keenan Crane},
title = {Navigating Intrinsic Triangulations},
journal = {ACM Trans. Graph.},
volume = {38},
number = {4},
year = {2019},
publisher = {ACM},
address = {New York, NY, USA},
}

Figures