CMU-CS-21-132.pdf (17.17 MB)
Download file

Intrinsic Triangulations in Geometry Processing

Download (17.17 MB)
thesis
posted on 16.12.2021, 22:25 by Nicholas SharpNicholas Sharp
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.

Funding

NSF Graduate Research Fellowship

History

Date

01/08/2021

Degree Type

Dissertation

Department

Computer Science

Degree Name

  • Doctor of Philosophy (PhD)

Advisor(s)

Keenan Crane

Usage metrics

Exports