摘要
为了提高曲面上任意两点间近似最短路径的计算效率,提出了求解曲面上任意两点间近似最短路径的算法,该算法首先利用三角形网格模型表示曲面,并形成相应的带权图结构,然后采用FSPA(快速最短路径法)动态计算带权图上两点的最短路径,再通过迭代细分最短路径周围的三角形网格上的边,最后由这些边构造新的子图来不断逼近曲面上两点间的最短路径。为验证该算法效果,还给出了该算法两个应用实例。应用结果表明,该算法效率高,容易实现,并可用网格尺寸和细分参数γ来控制近似精度。
A new algorithm is proposed for calculating the approximate shortest path on curve surface which can be represented by a triangle mesh model and form a weighted graph.This method mainly use FSPA(faster shortest path algorithm) to calculate shortest path on weighted graph on the basis of edge subdivision technology.By iteratively subdividing triangle edge that adjoins the shortest path and constructing new subgraph,a shortest path of high approximation accuracy can be achieved.The algorithm is efficient and easy to be implemented.The approximation accuracy can be improved by adjusting the mesh size and edge subdivision parameter γ.Two applications of the algorithm are demonstrated.
出处
《中国图象图形学报》
CSCD
北大核心
2005年第7期900-904,共5页
Journal of Image and Graphics
基金
国家高技术研究发展计划"863"项目(2002AA336120)
关键词
曲面
三角形网格模型
最短路径
curve surface,triangle mesh model,shortest path
