Fast exact and approximate geodesics on meshes
View/ Open
Author
Surazhsky, Vitaly
Surazhsky, Tatiana
Kirsanov, Danil
Hoppe, Hugues
Note: Order does not necessarily reflect citation order of authors.
Published Version
https://doi.org/10.1145/1073204.1073228Metadata
Show full item recordCitation
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.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.Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:2640598
Collections
- FAS Scholarly Articles [18292]
Contact administrator regarding this item (to report mistakes or request changes)