Welfenlab - Leibniz 
                        Universitšt Hannover Welfenlab Leibniz Universitšt Hannover

Exact and Approximate Geodesics on Meshes

Pawel Gardzinski, Welfenlab, Seminar

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

Top | Last Change 17.08.2011 | Editorial Responsibility 
| Imprint | © FG Graphische Datenverarbeitung