基于顶点局部特征度的网格模型分割算法

摘 要：网格模型的简化要兼顾保持细节特征和快速这两个基本原则，而对网格模型进行分割可以有效提高模型简化效率。提出了一种基于顶点局部特征度的网格模型分割算法。分割时，网格模型要求分割成大小适中、密度差异相对明显的连续区域，区域边缘平滑，且所有三角形均属于某个区域。通过引入顶点局部特征度的概念对区域生长算法进行了改进。

关键词关键词：网格模型；顶点局部特征度；区域分割；区域生长

DOIDOI：10.11907/rjdk.161477

中图分类号：TP312

文献标识码：A ：1672-7800（2016）008-0021-02

0 引言

所谓网格模型区域分割，就是对网格模型按照拓扑特征或者几何特征进行分割，获得一组有一定外观意义、若干相互连通的子网格的操作，包括区域生长法、层次聚类法和迭代聚类法等。

区域生长法可以生成满足网格某一特征的区域，实现模型简化的目的。本文研究了一种改进的区域生长算法，首先提出了顶点的局部特征度概念，采用一种简单的计算方法近似估值顶点曲率，设定顶点局部特征度的阈值作为生长条件对不平滑区域进行平滑处理。

1 顶点局部特征度

对于大多数三维网格模型来说，不同细节部位具有不同的分辨率，因而其复杂程度也是不同的。例如，模型中的棱边、凹痕、尖端、褶皱等关键区域的曲率较大，其它区域的曲率相对较小。常见的三维网格模型是由点、边、面分段组合而成的线性曲面，无法用传统的二次求导方法来计算其曲率，只能人为定义求取某点处曲率的近似估值。本文采用相对简便的方法计算顶点的局部特征度，作为该点曲率的近似估值来反映网格模型某点位置的不平整程度。在不增加计算复杂度的前提下，本文将顶点的局部特征度定义如下：

2 区域预分割

网格模型的区域分割要服务于三角形网格模型简化需要：首先分割区域比较大（也不宜过大）， 太小的区域很难控制简化过程，太大的区域使得分割意义大打折扣；分割区域的边缘不平滑也给模型的简化处理带来麻烦， 所以三角形网模型的区域分割遵从以下原则[5]：①将网格模型尽可能分割成大小适中且连续的区域；②各个区域的三角形网格稠密程度区分明显；③分割区域的边缘平滑；④不存在任何三角形不属于任何区域问题。

本文采用区域生长法进行区域扩展以便分割出连续区域。采用区域生长法进行分割要处理好3个问题：①如何选取种子；②如何设定生长准则；③如何设定终止条件。这3个问题处理不好会直接影响到区域生长效果，进而影响模型简化质量。

如何选择种子是区域生长的关键。三角网格模型可以采用顶点、边或三角形作为种子生长，本文着重研究顶点作为种子的情况。如图1（a）所示，顶点P1是区域中正在生长的种子顶点，那么凡是以P1为顶点的三角形都是生长区域的一部分。然后判断任意一个与该顶点P1相邻的顶点Pi是否满足生长准则条件。若顶点Pi 满足生长准则条件， 则将以Pi为顶点的生长区域扩展为区域生长的一部分， 如图1（b）所示。

初始种子的选择决定区域生长的形状，本文采用的方法是：重复选取没有被分割区域具有顶点的局部特征度极大值的顶点作为初始种子。这样可将所有棱边、凹痕、尖端、褶皱等区域都按照顶点的局部特征度大小先后进入扩展区域，以减少这些区域出现在分割边缘。

生长准则的选择会影响区域生长趋势，为了对网格模型的三角形疏密程度进行区域划分，本文采用顶点局部特征度作为区域生长的判定条件，对于满足判定条件的进行区域生长，不满足则终止生长。若顶点P1和顶点 Pi的局部特征度满足生长某个阈值， 便可将Pi 的相邻三角形扩展到区域中。生长准则规定为：

其中， Ri、 R1分别表示顶点Ri和R1的局部特征度， RVthod是生长阈值， 它的大小选择根据实际情况而定。对于平滑区域，RVthod可选择较小值；对于局部特征度较大的区域，RVthod可适度增大。

3 区域平滑处理

经过预分割后的区域存在不连通及区域边缘不平滑，会给后续简化带来很大麻烦，所以在预分割后，需要进行平滑处理，本文采用区域填充法处理。边缘不平滑区域包含的顶点所在三角形数目和该顶点所在三角形数目的比大于1/2，我们将该顶点所在三角形全部填充到这个边缘不平滑区域，处理步骤如下：

首先，统计顶点vi所在三角形数目N，统计这些三角形中属于区域As的数目Ns；然后判断：如果顶点vi满足NsN>1/2，就将vi所在的N个三角形全部填充到区域As中。最后判断区域As是否连通，如果不连通就重新执行该操作；如果连通，则操作结束。

4 基于顶点的局部特征度网格分割算法过程

（1）将所有顶点加入顶点数组Q，并计算网格模型每个顶点的局部特征度值。

（2）遍历数组Q， 选择具有局部特征度极大值的顶点作为初始种子，即若顶点v满足：对vn∈Nv有∑vi∈S且v≠viUv>∑vi∈SUvn，则v为区域生长初始种子，将顶点v保存起来以备后续传输使用。从数组Q中删除顶点v，将区域a加入到区域数组A。

（3）选择合适的顶点局部特征度阈值。（4）从初始种子开始，向满足生长准侧的区域进行扩张，每扩展一个顶点，从数组Q中删除该顶点。如果数组Q中还有顶点未被扩展， 则转步骤（2），否则继续。（5）如果数组A为空，算法结束。否则遍历区域数组A找到不连通区域As，从数组A中删除As。

（6）统计顶点vi所在三角形数目N，统计这些三角形中属于区域As的数目Ns。（7）如果顶点vi满足：NsN>1/2（5）

则将顶点vi所在的所有三角形都填充到区域As之中。（8）如果区域As已经连通， 并且边缘已经达到平滑程度， 则转步骤（5），否则， 转步骤（6）。

5 实验结果

实验环境：CPU Intel（R） Core（TM） 2 Duo，内存 2G，代码在Windows 7系统VS2013和OpenGL下编写完成。本算法部分实验结果如图2、图3所示。

从实验结果可以看出，模型的分割区域比较好地保留了局部细节特征，而且分割区域中不存在不连通区域，区域边缘基本平滑，证明了本文算法的有效性。

6 结语

本文提出了一种基于顶点的局部特征度区域生长算法，算法通过对顶点的局部特征度阈值设定，作为区域生长准则的判定条件，决定区域生长中所需要的区域形状，对网格模型进行分割，并对预分割后产生的不平滑边界采用区域填充法进行处理。最后获得大小适中、密度差异相对明显的连续区域。区域边缘平滑，且所有三角形均属于某个区域。

参考文献：

[1] 孙晓鹏，李华.三维网格模型的分割及应用技术综述[J].计算机辅助设计与图形学学螅2005，17 （8 ）：1647-1655.

[2] MANGAN A， WHITAKER R. Partitioning 3D surface watershed segmentation[J].IEEE Transactions on Vieualization and Computer Graphics，1999，5（4）：308-321.

[3] GARLAND M.WILLMOTT A， HECKBERT P. Hierarchical face clustering on polygonal surfaces[C].Proceedings of ACM Symposium on Interactive 3D Graphics，New York，2001.

[4] LLOYD S. Least square quantization in PCM[J] .IEEE Transactions on Information Theory，1982，28（2）：129-137.

[5] 全红艳，张田文，董宇欣.一种基于区域分割的几何模型简化方法[J].计算机学报，2006，29（10）： 1834-1842.