作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 图形图像处理 • 上一篇    下一篇

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

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

  1. (国防科学技术大学计算机学院高性能计算国家重点实验室,长沙410073)
  • 收稿日期:2013-10-21 出版日期:2014-11-15 发布日期:2014-11-13
  • 作者简介:施逸飞(1991 - ),男,硕士,主研方向:计算机图形学,虚拟现实;熊岳山,教授、博士、博士生导师;朱晨阳、施 鹏,硕士。
  • 基金资助:
    国家自然科学基金资助项目(61379103,61202333,61303185);高等院校博士点专项基金资助项目(20104307110003)。

Improved Surface Approximate Geodesic Algorithm on Triangle Mesh

SHI Yifei,XIONG Yueshan,ZHU Chenyang,SHI Peng   

  1. (State Key Laboratory of High Performance Computing,School of Computer,National University of Defense Technology,Changsha 410073,China)
  • Received:2013-10-21 Online:2014-11-15 Published:2014-11-13

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

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

Abstract: 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. Ex perimental 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.

Key words: geodesic, triangle mesh, division of space unit, A? algorithm;virtual liver surgery, haptic interface device

中图分类号: