Approximate Shortest Path on Triangular Mesh Surface

The triangle mesh model is represented by a weighted graph structure and Dijkstra’s algorithm is used to calculate the shortest path between two points on the graph.By iteratively subdividing the related triangle edges and constructing new weighted graph,the shortest path between points on the graph finally approaches the shortest path on the mesh surface.The algorithm is highly efficient,and quite suitable for the shortest path finding of large scale models.Application of the algorithm in model segmentation is also demonstrated.