Fast exact and approximate geodesics on meshes

DSpace/Manakin Repository

Fast exact and approximate geodesics on meshes

Citable link to this page


Title: Fast exact and approximate geodesics on meshes
Author: Gortler, Steven; Surazhsky, Vitaly; Surazhsky, Tatiana; Kirsanov, Danil; Hoppe, Hugues

Note: Order does not necessarily reflect citation order of authors.

Citation: Surazhsky, Vitaly, Tatiana Surazhsky, Danil Kirsanov, Steven J. Gortler, and Hugues Hoppe. 2005. Fast exact and approximate geodesics on meshes. In Proceedings of the 32nd annual conference on computer graphics and interactive techniques (SIGGRAPH 2005), July 29-31, 2005, Los Angeles, Calif., ed. Hart, John C., 553-560. New York, N.Y.: ACM Press. Also published as ACM Transactions on Graphics 24 (3): 553-560.
Full Text & Related Files:
Abstract: 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.
Published Version:
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search