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

摘要：

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

关键词：测地线、三角网格、空间单元划分、A?算法、虚拟肝脏手术、触觉交互设备

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61379103,61202333,61303185;高等院校博士点专项基金资助项目20104307110003。

在线出版日期：2014-12-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：225-228,249