三角网格模型的基本群分割  

Triangular mesh segmentation based on fundamental group

作　　者：范媛媛[1] 杨斌[2] 

机构地区：[1]滁州学院数学系,安徽滁州239000 [2]滁州学院计算机科学与技术系,安徽滁州239000

出　　处：《计算机工程与应用》2011年第32期180-182,共3页Computer Engineering and Applications

基　　金：国家自然科学基金No.60873175;安徽省教育厅自然科学基金(No.KJ2010B423;No.KJ2011Z284)~~

摘　　要：提出一种有效的三角网格模型分割方法。用Dijkstra算法求出三角网格模型上任意给定一个基点到其余顶点的最短路径树;求出该模型对偶图的最大生成树,且对偶图的边与该最短路径树的边不相交;找出该模型上所有既不属于最短路径树也不和最大生成树相交的边,这些边分别与最短路径树组成的最短环集合就是给定基点处的基本群,沿着这些最短环就可以把网格分割成一个拓扑同胚于圆盘的区域。实验结果表明,该分割方法可以快速、有效地实现网格的分割。An effective method of triangular mesh segmentation is proposed.The tree of shortest paths on triangular mesh from a given base point to every other vertex is calculated using Dijkstra algorithm.Then maximum spanning tree can be obtained in dual graph of this mesh, and these edges of dual graph don＇t intersect an arbitrary edge in the tree of shortest paths obtained.These edges on mesh which neither belong to the tree of shortest paths nor intersect the edges of maximum spanning tree can be found.Ftmdamental group at given basepoint is the set of shortest loops consisting of the tree of shortest paths and these edges, and then mesh can be cut into one topological disk along these loops.The result of experiment indicates that the method can quickly and efficiently cope with mesh segmentation.

关 键 词：网格分割 基本群 最短路径树 对偶图 最大生成树 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]