Computer Science Thesis Oral
— 12:00pm
Location:
In Person and Virtual - ET
-
Traffic21 Classroom, Gates Hillman 6501 and Zoom
Speaker:
MARK GILLESPIE
,
Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://markjgillespie.com/
Evolving Intrinsic Triangulations
This thesis presents algorithms and data structures for performing robust computation on surfaces that evolve over time. Throughout scientific and geometric computing, surfaces are often modeled as triangle meshes. However, finding high-quality meshes remains a challenge because meshes play two distinct and often-conflicting roles: defining both the surface geometry and a space of functions on that surface.
One solution to this dilemma, which has proven quite powerful in recent years, is the use of intrinsic triangulations to decouple these two concerns. The key idea is that given a triangle mesh representing an input surface, one can find many alternative triangulations which encode the exact same intrinsic geometry but offer alternative function spaces to work in. This technique makes it easy to find high-quality intrinsic triangle meshes, sidestepping the tradeoffs of classical mesh construction. However, the fact that intrinsic triangulations exactly preserve the input geometry—one of the central benefits of the technique—also makes it challenging to apply to surfaces whose geometry changes over time.
In this thesis we relax the assumption of exact geometry preservation, allowing the intrinsic perspective to be applied to time-evolving surfaces. We take as examples the problems of mesh simplification and surface parameterization. In the case of mesh simplification, we provide a general-purpose data structure for intrinsic triangulations which share only the topological class of the input surface, but may feature different geometry. In the case of surface parameterization, we build more efficient data structures and algorithms for the special case where the geometry changes conformally, using a connection between discrete conformal maps and hyperbolic geometry. In both cases, we find that the intrinsic perspective leads to simple algorithms which are still robust and efficient on a variety of examples.
Thesis Committee: Keenan Crane (Chair)
James McCann
Ioannis Gkioulekas
Boris Springborn (Technische Universität Berlin)
In Person and Zoom Participation. See announcement.