Fast exact and approximate geodesics on meshes
ACM Trans. Graphics (SIGGRAPH), 24(3), 2005.
Efficient computation of shortest paths and distances on triangle meshes.
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.
This computation of geodesic distances is used to improve the texture atlas parameterizations produced by
See Bommes and Kobbelt
for an interesting extension to compute geodesics from more general (non-point) sources.
ACM Copyright Notice
Copyright by the Association for Computing Machinery, Inc. Permission to make digital or
hard copies of part or all of this work for personal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the
full citation on the first page. Copyrights for components of this work owned by others than ACM must be
honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to
redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications
Dept, ACM Inc., fax +1 (212) 869-0481, or email@example.com. The definitive version of this paper can be
found at ACM's Digital Library http://www.acm.org/dl/.