Differential Geometry and Shape Analysis - Mathematical Tools for Shape Analysis and Description - page 27

Figure 4.1: e distance measured along X between p and q is the same as the distance along Y
between p

0

and q

0

.

4.1.1 COMPUTING GEODESICS ON MESHES
e computation of geodesic paths and distances on triangle meshes has been largely explored in
the literature [ 29 , 162 , 191 ].
In Mitchell et al. [ 143 ], the authors presented an algorithm able to exactly determine the
shortest path between a source and a destination on an arbitrary (possibly non-convex) polyhedral
surface. e path is constrained to lie on the surface, and distances are measured according to the
Euclidean metric. However, the worst-case complexity is O.n 2 log n/ . ¹
A popular approximation of the geodesic distance is obtained using the well-known Dijk-
stra algorithm [ 50 ]. In this case, the triangle mesh is modeled as a weighted directed graph whose
nodes are the vertices of the mesh and the arcs correspond to the edges. en, the shortest dis-
tance from a vertex to others is approximated by walking throughout the network starting from a
source node. e shortest distance depends on the choice of the metric along the arcs (Euclidean
or other cost methods). e algorithm iteratively decreases estimates on the shortest paths of
non-processed vertices, which are stored in a priority queue. In each iteration of the algorithm,
the closest unprocessed vertex from the source is extracted from the priority queue and processed
by relaxing all its incident edges. When the algorithm starts, the length of the shortest path is
overestimated and in each iteration, a shorter path is found. e algorithm ends when all nodes
have been visited. e Dijkstra algorithm is computationally efficient ( O.n log n/ ) but it is con-
strained to pass through nodes and edges of the mesh. As a variation of the Dijkstra algorithm,
Hilaga et al. [ 102 ] proposed to improve the approximation of the path by considering as edges of

¹An implementation of this method is available in the MATLAB central repository, at the address: http://www.mathwork
s.com/matlabcentral/fileexchange/18168-exact-geodesic-for-triangular-meshes and is also available in C
language at http://code.google.com/p/geodesic/