Exact and Approximate Geodesics on Meshes

Pawel Gardzinski, Welfenlab, Seminar
02/2011

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.

Kontakt: Alexander Vais