Integer Coordinates for Intrinsic Geometry Processing
ACM Transactions on Graphics (SIGGRAPH Asia 2021)
Mark Gillespie Carnegie Mellon University
Nicholas Sharp Carnegie Mellon University
Keenan Crane Carnegie Mellon University
This paper describes a numerically robust data structure for encoding intrinsic triangulations of polyhedral surfaces. Many applications demand a correspondence between the intrinsic triangulation and the input surface, but existing data structures either rely on floating point values to encode correspondence, or do not support remeshing operations beyond basic edge flips. We instead provide an integer-based data structure that guarantees valid correspondence, even for meshes with near-degenerate elements. Our starting point is the framework of normal coordinates from geometric topology, which we extend to the broader set of operations needed for mesh processing (vertex insertion, edge splits, etc.). The resulting data structure can be used as a drop-in replacement for earlier schemes, automatically improving reliability across a wide variety of applications. As a stress test, we successfully compute an intrinsic Delaunay refinement and associated subdivision for all manifold meshes in the Thingi10k dataset. In turn, we can compute reliable and highly accurate solutions to partial differential equations even on extremely low-quality meshes.
This work was supported by a Packard Fellowship, NSF Award 1717320, DFG TRR 109, an NSF Graduate Research Fellowship, and gifts from Autodesk, Adobe, and Facebook.
@article{Gillespie:2021:ICI, author = {Gillespie, Mark and Sharp, Nicholas and Crane, Keenan}, title = {Integer Coordinates for Intrinsic Geometry Processing}, journal = {ACM Trans. Graph.}, volume = {40}, number = {6}, year = {2021}, publisher = {ACM}, address = {New York, NY, USA}, url = {}, doi = {10.1145/3478513.3480522}, }
Selected Figures