三角网格模型上任意两点间的近似最短路径算法研究

摘要：

提出一种任意三角网格模型上两点间的近似最短路径算法.该算法首先将三角网格模型表示为带权图结构,然后用Dijkstra算法计算带权图中两顶点间的最短路径,并将其作为网格模型上该两点间最短路径的初始近似.通过不断地迭代对相关三角形边进行自适应细分,并构造每次细分后新的带权图,从而对网格模型上的两点间最短路径进行迭代逼近.该算法效率高,可以很好地控制精度,适用于大型三角网格模型两点间最短路径寻找.文中还讨论了该算法在任意三角网格模型区域划分中的应用.

关键词：计算机图形学、三角网格模型、近似最短路径

所属期刊栏目：15

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

资助基金：国家自然科学基金60273097;江苏省自然科学基金BK2001408;南京航空航天大学校科研和教改项目S0272-054

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

页数：共6页

页码：592-597