Abstract: To reduce time cost of computing all pairs shortest path on triangular mesh，a parallel approximate geodesic path algorithm base on local-subdivision algorithm is presented.Two pairs initial shortest path is computed by using matrix-multiplication parallel shortest path algorithm and adopting source-partition method to map sub-mesh data for every processor.Then all processors subdivide edges of owned pairs’ initial shortest path neighborhood triangular faces concurrently，and get a new approximate shortest path base on this subdivision graph at last.The experimental results show that using this parallel approximate shortest path algorithm can reduce computing time efficiently and improve computing efficiency greatly.

Key words: triangular mesh, approximate geodesic path, parallel algorithm, local-subdivision

摘要： 为降低求解三角网格表面任意两点间近似测地线长度和路径问题的时间开销，提出一种基于局部细分法的并行近似测地线算法。采用类矩阵乘最短路径并行算法求解点对间初始最短路径，并用源分割法映射子网格数据；所有处理器并行执行，对其所拥有点对之间的初始最短路径周围三角面片上的边进行细分操作；最后基于局部细化后的细分图并行，求得所有点对间的近似测地线长度和路径。实验结果表明，该并行近似测地线算法能够有效降低求解该类问题的计算时间，计算效率大大提高。

关键词: 三角网格, 近似测地线, 并行算法, 局部细分法