Nicholas Sharp

Intrinsic Triangulations in Geometry Processing Degree Type: Ph.D. in Computer Science
Advisor(s): Keenan Crane
Graduated: August 2021

Abstract:

This thesis treats the theory and practice of intrinsic triangulations, and their use in 3D mesh processing algorithms. As geometric data becomes more ubiquitous in applications ranging from scientific computing to augmented reality to machine learning, there is a pressing need to develop algorithms that work reliably on low-quality data. Intrinsic triangulations provide a powerful framework for these problems, by decoupling the mesh used to encode geometry from the one used for computation. The basic shift in perspective is to encode the geometry of a mesh not with ordinary vertex positions, but instead with only edge lengths.

The contributions of this thesis begin with new data structures for richly encoding intrinsic triangulations, which support new operations necessary for applications while remaining efficient and robust. Using these data structures, we describe a wide variety of mesh processing operations on intrinsic triangulations, including powerful retriangulation schemes with strong guarantees. Additionally, we demonstrate how intrinsic triangulations can be used for tasks beyond retriangulation, introducing a new flip-based algorithm for computing geodesic paths on surfaces. Finally, we present a generalization of intrinsic triangulations, to offer the same benefits for less-structured data such as nonmanifold meshes and point clouds. Throughout, we show applications to problems in geometry processing, where intrinsic triangulations lend much-needed automatic robustness to tasks including parameterization, vector field processing, spectral methods, and more.

Thesis Committee:
Keenan Crane (Chair)
Ioannis Gkioulekas
Anupam Gupta
Maks Ovsjanikov (École Polytechnique)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Geometry processing, discrete differential geometry, numerical computing