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 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.Fundamental 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.

Key words: mesh segmentation, fundamental group, the tree of shortest paths, dual graph, maximum spanning tree

摘要： 提出一种有效的三角网格模型分割方法。用Dijkstra算法求出三角网格模型上任意给定一个基点到其余顶点的最短路径树;求出该模型对偶图的最大生成树，且对偶图的边与该最短路径树的边不相交;找出该模型上所有既不属于最短路径树也不和最大生成树相交的边，这些边分别与最短路径树组成的最短环集合就是给定基点处的基本群，沿着这些最短环就可以把网格分割成一个拓扑同胚于圆盘的区域。实验结果表明，该分割方法可以快速、有效地实现网格的分割。

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