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

施逸飞,熊岳山,朱晨阳,施 鹏

(国防科学技术大学计算机学院高性能计算国家重点实验室,长沙410073)

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

施逸飞,熊岳山,朱晨阳,施 鹏

(国防科学技术大学计算机学院高性能计算国家重点实验室,长沙410073)

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

测地线;三角网格;空间单元划分;A*算法;虚拟肝脏手术;触觉交互设备

1 概述

计算三角网格模型表面两点间的测地线是计算几何中的一个基础性问题,被广泛应用于计算机图形学、地理信息系统、机器人学、虚拟现实、虚拟手术等领域,有重要的理论意义与应用价值。

目前已有多种针对三角网格模型的测地线算法,可分为2类:(1)计算三角网格上一点与其他所有点之间的测地线算法;(2)计算给定两点间的测地线算法。……