改进的三角网格表面近似测地线算法

Improved Surface Approximate Geodesic Algorithm on Triangle Mesh

三角网格表面的测地线计算问题可转化为三角网格表面两点间的最短路径计算问题，为了快速地计算三角网格表面测地线，提出一种基于缩小最短路径搜索区域的三角网格表面近似测地线算法。将三角网格沿坐标系三坐标轴方向进行空间单元划分，使用A？算法求出两点间的最短路径盒子序列，进而得到新的搜索区域，计算三角网格上两点间的最短路径，迭代细分最短路径邻域内的边以构造新的网格求解测地线。实验结果表明，该算法能够快速准确地计算出三角网格表面任意两点间的近似测地线，有效解决大型三角网格上最短路径计算速度慢的问题，计算速度较改进前的算法提高了10倍~59倍。将该算法应用到虚拟肝脏手术系统的区域标定中，可满足虚拟场景中对计算实时性和效果真实性的要求。

The computation of approximate geodesics algorithm on triangle mesh can be transformed to the computation of the shortest path on triangle mesh. In order to figure out the geodesics on triangle mesh efficiently, an improved approximate geodesics algorithm is presented. A weighted graph is constructed by splitting triangle mesh along the Cartesian coordinate axes,thus the shortest path on lattice can be computed by A＊algorithm and a new region of search can be defined. The neighboring edges of the shortest path are iteratively subdivided to construct a new weighted graphs to approach the geodesic. Experimental results show the improved algorithm can figure out the geodesics precisely and efficiently . The speed up ratio of the algorithm range is increased between 10 and 59 . A region labeling method on virtual liver surgery based on the improved algorithm is also proposed,which can meet the computational real-time and quality requirements of virtual scene.