Computing Approximate Geodesic on Triangular Mesh

摘要

A robust algorithm for computing approximate geodesic on triangular mesh by minimizing an energy function defined for piecewise linear path is proposed. Firstly, in order to avoid local minima, a good initial approximate geodesic is provided by Dijkstra's algorithm that is applied to a weighted graph constructed on triangular mesh. Then, the Polak-Ribiere-Polyak conjugate gradient method is chosen to minimize the energy function. Finally, this piecewise linear path achieved is considered as an approximate geodesic between two arbitrary points on mesh. The result of experiment indicates that this algorithm has good stability and high efficiency, thus quite suitable for the geodesic computation of large scale mesh models.