Exact and Approximate Geodesics on Meshes
Pawel Gardzinski, Welfenlab,
The computation of geodesic paths and distances on triangle meshes is a common operation in many computer graphics applications. I will present several practical algorithms for computing such geodesics from a source point to one or all other points efficiently.
First, I will describe an implementation of the exact ‚Äúsingle source, all destination‚ÄĚ algorithm presented by Mitchell, Mount, and Papadimitriou (MMP). I will show that the algorithm runs much faster in practice than suggested by worst case analysis.
I will also show an algorithm (by V. And T. Surazhsky, D. Kirsanov, Steven J. Gortler and H. Hoppe) extended with a merging operation to obtain computationally efficient and accurate approximations with bounded error.
Finally, to compute the shortest path between two given points, I will show how the authors used a lower-bound property of their approximate geodesic algorithm to efficiently prune the frontier of the MMP algorithm, thereby obtaining an exact solution even more quickly.
Contact: Alexander Vais