Fast exact and approximate geodesics on meshes
By Vitaly Surazhsky, Tatiana Surazhsky, D. Kirsanov, Steven J. Gortler, Hugues Hoppe. ACM Transactions on Graphics, 2005
583 citations recorded by the source corpus.
The computation of geodesic paths and distances on triangle meshes is a common operation in many computer graphics applications. We present several practical algorithms for computing such geodesics from a source point to one or all other points efficiently. First, we describe an implementation of the exact "single source, all destination" algorithm presented by Mitchell, Mount, and Papadimitriou (MMP). We show that the algorithm runs much faster in practice than suggested by worst case analysis. Next, we extend the algorithm with a merging operation to obtain computationally efficient and accurate approximations with bounded error. Finally, to compute the shortest path between two given points, we use a lower-bound property of our approximate geodesic algorithm to efficiently prune the frontier of the MMP algorithm. thereby obtaining an exact solution even more quickly.
Subfields: Computational Mechanics, Computer Graphics and Computer-Aided Design
View Paper: https://www.semanticscholar.org/paper/964bb0a429620e33ebdec1a029849b24b12dddbe
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
- Keenan Crane
- Yonghuai Liu
- A. David Marshall
- Hongwei Lin
- Zhi-Quan Cheng
- Paul L. Rosin
- Shuming Gao
- Max Wardetzky
In Computer Graphics and Computer-Aided Design
- Keenan Crane
- Hongwei Lin
- Paul L. Rosin
- Shuming Gao
- Max Wardetzky
- Wei Zhao
- Frank C. Langbein
- Xianfang Sun
Citations in the corpus
- A robust hole-filling algorithm for triangular mesh (2007, methodology): “In this work, Surazhsky’s method [21] is applied to compute geodesic distance between two vertices on a mesh.”
- Geodesics in heat: A new approach to computing distance based on heat flow (2012, methodology): “In particular we used the state-of-the-art fast marching implementation of Peyré and Cohen [2005] and the exact implementation of Kirsanov [Surazhsky et al. 2005].”
- Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid (2013, background): “The geodesic distance is often found by solving the eikonal equation and wavefront propagation [85].”