基于曲率的三角网格模型分割算法

摘 要本文围绕三角网格模型分割技术展开研究，主要针对具有非规则任意边界的三维网格模型，以曲面曲率为特征采用区域生长算法进行三角网格模型的分割。提出了一种基于曲率的网格分割算法。本文所用的分割算法是基于面的方法，把曲率小于某一阈值的顶点视为非曲率突变点，从一组种子点开始，进行区域生长，即把非曲率突变点的邻接三角片加入当前正在进行生长的曲面，直到周围邻域全是曲率突变点为止，生长结束。

【关键词】三角网格模型 曲面分割 离散曲率 区域生长

1 引言

随着三维扫描技术和计算机图形学的发展以及三维模型数量的快速增加，三角网格模型分割技术已经成为近年来的一个热门研究课题，并广泛地应用于计算机图形学的许多领域，如计算机动画、三维变形、网格压缩、纹理映射等。

本文主要研究基于离散曲面曲率的三角网格模型的分割技术。利用离散曲面高斯曲率和平均曲率的计算公式。以顶点的曲率阈值为生长原则，利用区域生长算法实现了三角网格模型的分割。本文以曲率为分割依据，利用区域生长算法进行三角网格模型分割。从一组“种子点”开始，进行“区域生长”，找出具有相似特征的点，即曲率较小的点，构成一个曲面片，直至周围邻域没有特征一致的点“生长”才结束，即周围所有的点都是曲率突变点，这些曲率突变点也即面片的边界点。

2 三角网格模型介绍

三角网格模型是由三维空间中的三角形通过边和顶点连接而成的分片线性的曲面，其中每条边最多包含在两个三角形中。定义三角网格M=（n，k），其中n={V1，V2，...，}，Vi∈R3，表示M中的顶点在三维空间中的位置；k是一单纯复合型，包含顶点集{1，2，...，n}及其非空子集，表示顶点间的连接相互关系。三角网格M中的点、边、面是k的一组单纯形，可分别记作：

点：V={i}∈k

边：E=（i，j）∈k

面：F={i，j，k}∈k

点的邻域如图1所示。

对于任意的顶点V，其领域关系有：

（1）1环邻域顶点的集合，即与V相邻的m个邻点，记为NV（i）={Vj，Vj+1，...，Vj+m-1}。

（2）邻边集合，即有一个顶点为V的边的集合，记为NE（i）={Ej，Ej+1，...，Ej+m-1}。

（3）邻接三角片集合，即有一个顶点为V的三角片的集合，记为NF（i）={Fj，Fj+1，...，Fj+m-1}。

（4）2环邻域顶点集合，即为其1环领域顶点的1环领域顶点，其邻接三角片与V的邻接三角片有公共边，但其本身与 无公共边。记为N2V（i）={Vk，Vk+1，...，Vk+l-1}。

3 三角网格分割的相关概念

三角网格分割（简称网格分割），是指根据一定的几何和拓扑特征，分解成一组数目有限、各自具有简单形状意义的、且各自连通的子网格片的工作。

令S为网格的顶点集、边集或者面片集。对于网格模型M的分割定义：将S分割为k个不相交的子集。即

（1）

（2）

4 算法基本思想

（1）通过拟合三角网格模型任意顶点的局部二次曲面，求出任意顶点的曲率，找出三角网格模型所有的曲率突变点，即曲率绝对值大于某一给定阈值的点。

（2）从三角网格模型的任意一个非曲率突变点（曲率小于给定阈值的点）出发进行深度优先遍历搜索，若搜索到的网格顶点是非边界点，则将其邻接三角片加入到当前正在进行生长的曲面片中，否则访问下一个邻接点，直到当前曲面片的所有边界点都是曲率突变点为止，则当前面片的区域生长过程完成。再选取另一个未访问过的非曲率突变点，将其作为种子点生长下一个曲面片。当所有的网格顶点都访问完毕，则网格模型的分割也就完成。

5 算法的描述

5.1 算法步骤

步骤1：置网格顶点的索引v=1；转步E2。

步骤2：选取种子点。若索引为v的顶点P（v）未曾被访问过，即访问数组visited[v]==false，则将其作为新的曲面片进行区域生长的种子点，转步骤4。否则转步骤3。

步骤3：顶点索引v=v+1；若v小于模型的顶点数，则转步骤2；否则转步骤9。

步骤4：面片初始化。给新的曲面片分配必要的内存空间，初始化某些变量。将新的曲面片结点插入模型的曲面片链表中。转步骤5。

步骤5：区域生长。置索引为v的当前生长点P（v）的访问标志为真，即 visited[v]=true；将P（v）的邻接三角片加入到当前曲面片集合中。若P（v）为非曲率突变点，转步骤6。

步骤6：，置j=0；转步骤7。

步骤7：搜索当前生长顶点P（v）的1环邻域顶点索引w=ver.vertices_1[j]；若索引为w的顶点P（w）未被访问过，以P（w）作为新的种子点进行生长，转步骤5；否则转步骤8。

步骤8：j=j+1；若j< P（v）.numvertices_1（生长顶点P（v）的一环邻域顶点数组），转步骤7；否则，当前曲面片生长完毕，转步骤3。

步骤9：模型分割完毕，算法结束。

5.2 实验结果

在Windows平台上，基于OpenGL和VC++实现了本文的三角网格模型分割算法，下面是本文算法的实验结果。

（1）模型初始化结果。

（2）当曲率阈值为6.25，指定三角片数目为800，平均法向量夹角为46度时经过算法分割以后的结果如图3所示。

（3）大象模型初始化结果。

（4）当曲率阈值为6.25，指定三角片数目为800，平均法向量夹角为46度时经过算法分割以后的结果如图5所示。

（指导教师：李群辉）

参考文献

[1]杨楠，校江超，王明海.基于三角网格模型的法矢及曲率估算[J].现代制造工程，2010（03）：104-107.

[2]全红艳，张田文.基于区域生长的网格模型分割技术[J].计算机辅助设计与图形学学报，2006，18（07）：1011-1016.

[3]汪俊，周来水，安鲁陵，谭昌柏.基于网格模型的一种新的区域分割算法[J].中国机械工程，2005，16（09）：796-800.

[4]曹彩霞，董洪伟，丁金仲.基于区域生长的网格模型分割[J].计算机工程与应用，2008，44（31）.

作者单位

长安大学 陕西省西安市 710018