You can find geodesic paths in triangle meshes by just flipping edges

• Published in: ACM transactions on graphics 2020-11, Vol.39 (6), p.1-15, Article 249
• Main Authors: Sharp, Nicholas, Crane, Keenan
• Format: Article
• Language: English
• Subjects: Computer graphics; Computing methodologies; Shape modeling
• ISSN: 0730-0301; 1557-7368
• DOI: 10.1145/3414685.3417839

This paper introduces a new approach to computing geodesics on polyhedral surfaces---the basic idea is to iteratively perform edge flips, in the same spirit as the classic Delaunay flip algorithm. This process also produces a triangulation conforming to the output geodesics, which is immediately useful for tasks in geometry processing and numerical simulation. More precisely, our FlipOut algorithm transforms a given sequence of edges into a locally shortest geodesic while avoiding self-crossings (formally: it finds a geodesic in the same isotopy class). The algorithm is guaranteed to terminate in a finite number of operations; practical runtimes are on the order of a few milliseconds, even for meshes with millions of triangles. The same approach is easily applied to curves beyond simple paths, including closed loops, curve networks, and multiply-covered curves. We explore how the method facilitates tasks such as straightening cuts and segmentation boundaries, computing geodesic Bézier curves, extending the notion of constrained Delaunay triangulations (CDT) to curved surfaces, and providing accurate boundary conditions for partial differential equations (PDEs). Evaluation on challenging datasets such as Thingi10k indicates that the method is both robust and efficient, even for low-quality triangulations.