Technical Papers

Date/Time: 04 – 13 December 2020
All presentations are available in the virtual platform on-demand.

Lecturer(s):
Nicholas Sharp, Carnegie Mellon University, United States of America
Keenan Crane, Carnegie Mellon University, United States of America

Bio:

Description: This paper describes a new approach to computing exact geodesics on polyhedral surfaces. The basic idea is to perform edge flips, in the same spirit as the classic Delaunay flip algorithm. As a natural byproduct of this process, one also obtains a triangulation containing the shortened paths as edges. More precisely, given a path as a sequence of mesh edges, we transform it into a locally shortest geodesic path while avoiding self-crossings (i.e., we find a geodesic in the same isotopy class). Implementation amounts to a simple subroutine that flips edges to create a shorter path within their local neighborhood. The method is guaranteed to produce an exact geodesic path in a finite number of operations; practical runtimes are on the order of a few milliseconds, even for meshes with millions of faces. It is easily applied to cases beyond simple paths, including closed loops, curve networks, and multiply-covered curves. The method is well-suited for applications in geometry processing: it guarantees that curves do not cross, a necessary property when straightening region boundaries or cut networks, and furthermore it yields an intrinsic triangulation which includes the geodesic curves as edges, extending the idea of a \emph{constrained Delaunay triangulation} to curved surfaces. Evaluation on large datasets indicates that the method is both efficient and robust even for challenging models with low-quality triangulations. We explore how the curves and triangulations produced by the method facilitate a variety of tasks in digital geometry processing such as straightening cuts and segmentation boundaries, computing geodesic Bézier curves, and providing accurate boundary conditions for PDEs.