几何立体图形光顺算法的研究与比较∗

苏 刚 胡新荣 李佳黎 尹 汪 赵红杏

（武汉纺织大学数学与计算机学院 武汉 430073）

1 引言

由多边形面片组建的几何立体图形虽然具有规则的网格结构，可以用来表示复杂的三维实体，但所构成的表面不够光滑，不能满足实际应用的要求，所以需要对多边形网格进行光滑处理。网格光顺可以有效解决三维几何实体表面的光滑问题。当前主要网格光顺算法有四类，分别是拉普拉斯平滑法、曲率均匀法、能量法、曲面细分技术［1］。其中，曲面细分技术是通过用低分辨率的控制网格和定义在控制网格上的细分规则来表示光滑曲面。细分曲面造型技术规则简单，拓扑适应能力强，因而在曲面设计加工中得到了广泛应用。三角形网格细分曲面方法具有稳定性好、不受网格拓扑限制的优点，可以对任意拓扑网格进行曲面造型，其递归结构与小波和多分辨率分析有着密切联系［2］。正是由于三角形网格细分曲面的特点，用三角网格来表示模型各个曲面，不仅可以获得较好的视觉效果，并能通过控制模型中三角面片的数量来得到不同需求的三维网格模型［3］。

本文着重介绍了Loop细分法、Butterfly细分法、Sqrt3细分法、PN-triangle细分法4种曲面细分算法的原理，并用程序实现了这4种曲面细分算法。程序通过读取三维网格数据，并借助openGL平台将其显示。同时，实验通过选择相同的三维网格模型来测试并对比这4种细分算法在处理网格模型时，细分曲面与原始网格曲面的逼近程度，细分曲面的质量，细分算法运行复杂度等性能指标。从细分算法原理上比较并分析了这四种细分算法，最后总结出这四种细分算法的特点和适用范围。

2 典型三角网格细分算法

2.1 Loop细分算法

Loop细分曲面方案是Utah大学的Loop在1987年的硕士论文种提出的一种基于三角形控制网格的细分曲面算法，是目前应用最为广泛的算法之一［4-5］。Loop细分具有细分规则简单，光滑性好特点，但是细分曲面会产生较大的收缩。Loop细分算法是一种实现简单的逼近细分算法，对原有特征尤其尖锐特征的保持能力较弱。Loop细分在正则点处可以达到C2连续，在奇异点处达到C1连续。Loop细分曲面方案采用三角形分裂模式产生新的网格拓扑结构。设给定一个初始网格，经过i次Loop细分之后，其网格顶点记为vi的邻域有n个共边顶点=（j=1，2，…，n），第i+1次细分后，新网格顶点记为vi+1，它的邻域有n个共边顶点（j=1，2，…，n），具体几何点的产生规则如下。

1）内部奇点产生规则，如图1（a）所示，设有两个三角形（V0，V1，V2）和（V0，V1，V3），共享边为V0V1，则V0V1新顶点的位置为

2）内部偶点产生规则，如图1（b）所示，设V的边临点 V0，V1，…，Vn-1，n=|VE|，相应顶点的位置为

3）边界奇点，如图1（c）所示：

4）边界偶点，如图1（d）所示：

2.2 Butterfly细分算法

Butterfly细分曲面方案是由Dyn，Gregory和Levin于1990年提出的。Butterfly细分法是一种定义在三角网格上的细分曲面方案［6～7］，属于插值的面分裂方法，其细分极限曲面在正则点处达到C1连续，在奇异点处只能达到C0连续。后来Zorin对Butterfly细分曲面方案进行了研究［8～9］，并对其算法进行了改进，使得可以在任意三角网格上生成C1连续的曲面。改进Butterfly细分模式几何规则如图2所示，图a是具有规则邻接点的内部奇点，图b是具有非规则邻接点的奇点，图c为边界奇点。由于该算法属于插值类型，上一细分级别的所有控制点都位于曲面上，因此偶点不需要重新计算，只要计算奇点即可。

图1 Loop细分模式几何规则

图2 改进Butterfly细分模式几何规则

规则1：当网格边的两个端点都是规则点，即阶为6的端点时，细分面具如图2（a）所示，各权值设置为

规则2：当网格的一个端点是阶为6的规则点，而另一端点为非规则点（阶n不为6），则细分面具如图2（b）所示，细分规则由非规则顶点以及它的邻接点决定，其中各邻接点的权重系数如下：

规则3：细分边2个端点都为奇异点时，则先对每一个奇异点利用规则2得到2个新顶点，然后取平均值作为当前细分边生成的顶点。

规则4：细分边为边界边时，如图2（c）所示，则插入点的计算公式为

2.3 Sqrt3细分算法

Sqrt3细分方案是由Kobbelt在2000年提出的一种逼近型、面分裂的三角网格细分方案［10～11］，该细分曲面方案能有效缓解面片增长速度。Sqrt3采用一种全新的顶点插入和分裂方式，每次细分时，在每个三角形面插入一个新顶点，新顶点与原三角形的三个顶点相连，然后去掉原三角形的内部边，这样使得三角形面的个数增加3倍，细分过程如图3所示。Sqrt3细分法使得三角形增加缓慢，不会出现尖锐三角形，并且连续性自动保留，适用于局部性适应性细分。

设新顶点（V-vertex）：顶点v相邻顶点为v0，v1，v2，…，vn-1，则（V-vertex）顶点Vv由下面的公式计算：

新面点（F-vertex）：设三角形的三个顶点为v0，v1，v2，新插入的（F-vertex）VF由下面的公式计算：

图3 Sqrt3细分过程

2.4 PN-triangle细分算法

近年来，随着GPU运算能力的不断增强，人们在GPU上实现曲面细分技术方向上进行了大量的研究工作。Vlachos、Jorg Peters、Chas Boyd等提出的Curved Point Normal三角形（PN-tringle）细分算法［12～14］，根据顶点位置和法向信息对三角形面片内部进行独立的双三次Bezier曲面插值，在不考虑几何拓扑关系情况下，对每个patch进行均匀细化，实现满足视觉需求的几何模型平滑绘制，它适合硬件加速处理，并在实时精细渲染中得到了广泛应用。PN-triangle三角形细分算法能够将原始粗糙三角形网格生成光滑连续表面，针对参数三角形区域，其Bezier细化方程定义为

其中（u，v，w）是在该三角形中定点的重心坐标形式，且u+v+w=1。如图4所示，输入单一基三角形，获取法线控制点nijk和顶点控制点bijk，根据内部和边界细化因子执行细化过程，得到插值后的光滑网格顶点布局。PN三角形的生成只依赖于基三角形的顶点位置和法向量，适合应用在基于GPU的三角形细化渲染管线中。

图4 PN-triangle细化过程

3 细分算法比较分析

3.1 实验过程

实验选取维纳斯头部三角网格模型来进行测试，初始维纳斯三角网格模型具有498个顶点，992个三角形面。该实验目的是用Loop细分法，改进Butterfly细分法，Sqrt3细分法及PN-triangle细分法分别对相同模型进行细分测试，比较不同细分算法细分曲面与原始网格的逼近程度，细分曲面质量以及细分算法复杂度等方面的性能指标。实验通过OpenGL平台显示各细分算法的细分效果，如图5所示，为初始网格模型经过细分算法处理得到第一次细分和第二次细分后的曲面细分效果图。同时，实验统计了四种不同细分算法完成每次细分所使消耗的时间，如表1所示。

图5 维纳斯模型曲面细分效果图

表1 曲面细分算法运行效率分析表

3.2 实验分析及改进方法

通过以上实验，经过对比可以分析出，各细分算法在曲面细分方面各有所长。第一，在细分曲面和控制网格的逼近程度方面，改进Butterfly算法和PN-triangle算法具有突出表现，而改进Butterfly算法作为一种插值型细分算法，由此可以说明插值型细分算法比逼近型细分算法生成的曲面更加接近控制网格，并且连续性越低，曲面越靠近控制网格，这符合插值型细分算法的特点。第二，在细分曲面质量方面，Loop细分曲面方案生成曲面质量较高，但细分曲面会产生较大的收缩性，产生的曲面会出现不对称现象。第三，在算法实现复杂度方面，通过表2可以得出，经过第一次细分及第二次细分时，各曲面细分算法运行效率相当，在第三次细分时，Sqrt3细分算法运行效率较高，其中Loop细分和改进Butterfly细分每次细分三角形个数将增加4倍，由此说明Sqrt3细分算法使三角形面片增长速度仅为每次3倍，不仅大幅度减少了新生三角形的数量，同时提高了运行效率和分辨率。其中PN-triangle是基于GPU管线和图形库（DirectX 11）技术前提下实现的［15］，细分产生的三角形由GPU进行运算，其细分的结果在渲染管道内传输，几乎不需要额外显存空间，由此，本实验忽略计算PN-triangle细分算法的运算时间。考虑到GPU运算的高并行和快速性，PN-triangle曲面细分相对其它传统细分算法更有空间和时间上的优势。PN-triangle不仅对现有的模型没有更多的要求，而且效率很高，可以应用于实时性要求较高的程序中。

4 结语

本文着重介绍了4种典型三角网格细分算法，并通过程序实现了这四种算法，最后通过实验结果对比各曲面细分算法在细分方面的不同优势。除本文着重阐述的4种三角网格细分算法外，还有其它三角网格细分算法也具有重要的研究意义，如三重细分、混合细分、4-8细分等曲面细分算法，在此不一一详述。曲面细分在涉及理论和实际的应用领域有着广泛的应用。随着计算机图形学及相关领域学者和研究人员对曲面细分技术研究的不断深入，细分曲面理论和技术将不断得到完善。同时，细分曲面融入各种曲面造型系统与其它类型的曲面相融合是当前曲面造型的发展趋势。目前，虽然可以实现创建曲率连续的曲面，但创建更高阶连续曲面的算法还待进一步研究。除此之外，对细分曲面控制，编辑还比较困难，如何处理网格细分速度和曲面质量的关系还有待深入研究［16～18］。随着GPU计算能力的不断增强以及GPU并行计算技术的日益成熟，如何利用现代GPU有效的生成和处理细分曲面成为近年来非常热门的研究方向之一。