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.
PDF, 16MB
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
Unlike an ordinary triangle mesh (top), an intrinsic triangulation (bottom) can include edges that take any straightest path between vertices. However, each region bounded by three edges can still be unfolded into a single planar triangle.
Our signpost data structure stores the direction and distance to each neighbor, making triangulations easy to update and to query on-demand.
Intrinsic versions of classic algorithms yield high quality triangulations for any mesh. We can obtain a Delaunay triangulation without increasing the vertex count (top right), achieve lower angle bounds (bottom left), or balance angles and triangle areas (bottom right).
As in the Euclidean case, we find that intrinsic Delaunay refinement can achieve a minimum angle bound of 30°, even on challenging models.
Our signpost data structure makes it easy to implement an intrinsic version of optimal Delaunay triangulation (iODT), which provides an excellent balance between element size and angle distribution while exactly preserving the input geometry.
Our data structure allows planar computational geometry algorithms to be easily translated into the polyhedral setting. Here we apply a classic Euclidean algorithm for Steiner tree approximation to find shorter cuts through polyhedral surfaces.
Even for domains with large, flat regions, solving a Poisson equation is about twice as accurate with an intrinsic triangulation. Rows show two refinements, with matching element counts in the last three columns.
Working with intrinsic triangulations allows one to accurately and efficiently approximate the exact polyhedral distance using PDE based methods like the heat method.
Intrinsic AMR allows extremely accurate computations of standard kernels from geometry processing with very few elements. Left: harmonic Green's function. Right: short time heat kernel. Performing uniform iDR to achieve the same accuracy requires 18x and 54x as many vertices, respectively.
Mappings computed on low-quality meshes can exhibit flipped triangles, as shown here for a harmonic mapping (left). An iDT guarantees the map is flip-free (center), and AMR intelligently reduces distortion (right).
Our signpost data structure is also well suited for tangent vector field processing. Here we draw streamlines of the vector field with smallest Dirichlet energy ED (showing vectors in the inset); using an intrinsic triangulation yields a much smoother field.
Intrinsic triangulations that satisfy the Delaunay condition help prevent flips in tangent direction fields. Here we compute the smoothest field interpolating given vectors at the boundary.
Flipping to the intrinsic Delaunay triangulation and extracting the edge crossings in the overlay mesh is extremely efficient with the signpost data structure. Prior methods update the overlay mesh every flip, while our approach reads it off after the fact.
Left: an extrinsic Delaunay triangulation which preserves geometry requires dramatically more vertices. Center: the intrinsic Delaunay triangulation requires no additional elements. Right: Even a modest number of additional intrinsic vertices can dramatically increase element quality.
A mechanical part (left) is made Delaunay with extrinsic splits and simplifications (center), or with intrinsic flips (right). For an equal number of elements, the extrinsic method loses important geometric detail, whereas the intrinsic triangulation exactly preserves the given shape.
An intrinsic edge can cross an extrinsic edge many times, as seen with this increasingly “twisted” cube. Rather than track these crossings explicitly, we introduce an implicit encoding that has constant size.