三角网格模型的基本群分割 - 计算机工程与应用.PDFVIP

180 2011 ，47 （32） Computer Engineering and Applications 计算机工程与应用 三角网格模型的基本群分割 1 2 范媛媛 ，杨 斌 1 2 FAN Yuanyuan ，YANG Bin 1.滁州学院 数学系，安徽 滁州 239000 2.滁州学院 计算机科学与技术系，安徽 滁州 239000 1.Department of Mathematics ，Chuzhou University ，Chuzhou ，Anhui 239000 ，China 2.Department of Computer Science Technology ，Chuzhou University ，Chuzhou ，Anhui 239000 ，China FAN Yuanyuan ，YANG Bin.Triangular mesh segmentation based on fundamental group.Computer Engineering and Ap- plications ，2011 ，47 （32 ）：180-182. Abstract ：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 ob- tained 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.Fundamental group at given basepoint is the set of shortest loops consisting of the tree of short- est paths and these edges ，and then mesh can be cut into one topological disk along these loops.The result of experiment in- dicates that the method can quickly and efficiently cope with mesh segmentation. Key words ：mesh segmentation ；fundamental group ；the tree of shortest paths ；dual graph ；maximum spanning tree 摘 要：提出一种有效的三角网格模型分割方法。用Dijkstra 算法求出三角网格模型上任意给定一个基点到其余顶点的最短路 径树；求出该模型对偶图的最大生成树，且对偶图的边与该最短路径树的边不相交；找出该模型上所有既不属于最短路径树也不 和最大生成树相交的边，这些边分别与最短路径树组成的最短环集合就是给定基点处的基本群，沿着这些最短环就可以把网格 分割成一个拓扑同胚于圆盘的区域。实验结果表明，该分割方法可以快速、有效地实现网格的分割。 关键词：网格分割；基本群；最短路径树；对偶图；最大生成树 DOI ：10.3778/j.issn. 1002-8331.2011.32.052 文章编号：1002-8331（2011 ）32-0180-03 文献标识码：A 中图分类号：TP391.41 1 引言