四种逼近型细分算法对比研究及应用

Comparative Research and Application of Four Approximation Subdivision Algorithms

摘要: 曲面细分作为生成平滑表面的重要手段，已广泛应用于计算机图形学。在实体建模中，多边形网格虽然可以表示物体形状，但在实际采样中由于采样的不均匀性或物体的遮挡等导致获得的初始网格不够光滑，难以表达曲面的真实形状，而曲面细分可以有效解决网格光滑问题。近年来，有些逼近型细分算法，在经典算法的基础上通过改变细分规则，实现了某些效果或者控制了网格的数量，但是其应用的广泛性和普适性较低。本文选取了经典的逼近型Catmull-Clark细分法、Doo-Sabin细分法、Loop细分法和√3细分法进行了对比实验，并阐述了各细分算法的适用范围。此外，基于贪婪算法对采集到的真实数据进行重建，得到初始三角网格；然后，根据细分算法特点，采用Loop细分对初始三角网格进行细分，最后得到光顺的细分曲面。

Abstract: As an important means of generating smooth surfaces, surface subdivision has been widely used in computer graphics. In solid modeling, although the polygon mesh can represent the shape of the object, the initial mesh obtained in actual sampling is not smooth enough due to the unevenness of the sampling or the occlusion of the object, and it is difficult to express the true shape of the surface. Surface subdivision can effectively solve the problem of mesh smoothness. In recent years, some approximation subdivision algorithms have achieved certain specific effects or controlled the number of grids by changing subdivision rules on the basis of classic algorithms, but their application versatility and universality are low. This paper selects the classic approximation Catmull-Clark subdivision, Doo-Sabin subdivision, Loop subdivision and Sqrt3 subdivision for comparative experiments, and explains the applicable scope of each subdivision algorithm. In addition, based on the greedy algorithm, the collected real data is reconstructed to obtain the initial triangle mesh; then, according to the characteristics of the subdivision algorithm, the loop subdivision algorithm is used to subdivide the initial triangle mesh, and finally a smooth subdivision surface is obtained. As an important means of generating smooth surfaces, surface subdivision has been widely used in computer graphics.

1. 引言

细分曲面以一个给定的相对粗糙的初始多边形网格作为输入数据，根据相应的细分规则，通过迭代细化过程，生成顶点稠密的控制网格，同时细分表面也变得更加平滑。由于其理想的属性，例如多分辨率，局部可控性，仿射不变性和全局连续性等，使得细分曲面已广泛应用于许多领域 [1]，例如计算机图形，计算机动画和曲面模型构建等。

迄今为止，已经提出了许多不同的方法，根据细分曲面与控制网格的关系，可以将细分方法分为两类，即逼近型细分和插值型细分。经典的插值型细分是在每次细分操作后始终在精炼网格中包含旧顶点，其中最经典的是Butterfly细分算法 [2] 及其改进算法 [3] 都属于此类，该方法生成的极限曲面将包含所有原始顶点。文献 [4] 提出了一种基于局部细化操作的四边形网格统一插值细分算法。文献 [5] 提出了一种混合非均匀递归细分方案，以支持等几何分析，并提高了收敛速度。典型的逼近型细分算法有Catmull-Clark细分 [6]、Doo-Sabin细分 [7]，Loop细分 [8] 以及 $\sqrt{3}$ 细分 [9]。其中Loop细分和 $\sqrt{3}$ 细分是较为常见的三角形网格细分，而Catmull-Clark、Doo-Sabin细分则是常见的四边形网格细分。在此基础上，一些学者对逼近型曲面细分方法进行了进一步的研究。文献 [10] 通过修改细分规则，拓展了Doo-Sabin细分，使其适用于具有尖锐特征的曲面。文献 [11] 通过专用内核替换，优化了算法的性能。文献 [12] 通过改变细分准则来提高算法的效率。文献 [13] 通过插值曲面法向量来提高曲面的光顺性。

虽然改进的逼近型细分算法众多，但经典细分方法因其几何规则、拓扑规则以及理论相对简单且容易控制，所以得到了广泛的应用。因此，本文重点介绍了四种逼近细分算法，通过实际应用，对其细分效果进行了分析讨论。

2. 细分算法原理

2.1. Catmull-Clark细分

Catmull-Clark细分作为双三次B样条的扩展，是一种四边形网格的近似细分，通过将每个面分为四个子面来生成新的控制网格，其由新面点、新边点和新顶点构成。采用Catmull-Clark细分算法得到的曲面在规则点处具有 $c^2$，在不规则点处 $c^1$ 连续。

2.1.1. 几何规则

设每个面细分所产生的新面点为F-点，每个边生成的新边点为E-点，每个点生成的新顶点为V-点，则Catmull-Clark曲面细分的几何规则如下：

1) F-点：设四边形网格的4个原顶点为 $v_1$ 、 $v_2$ 、 $v_3$ 、 $v_4$ 如图1(a)所示，则每个面上控制点的几何平均即为F-点，可表示为：

$v_F=\frac{1}{4}\left(v_1+v_2+v_3+v_4\right)$ (1)

2) E-点：设2个网格公共边的顶点为 $v_0$ 、 $v_1$，其他顶点为 $v_2$ 、 $v_3$ 、 $v_4$ 、 $v_5$ 如图1(b)所示，则公共边上的两个点和两个面控制点的几何平均即为新边点E-点，可表示为：

$v_E=\frac{3}{8}\left(v_0+v_1\right)+\frac{1}{16}\left(v_2+v_3+v_4+v_5\right)$ (2)

边界情况：对于边界边如图1(d)所示，设原顶点为 $v_0$ 、 $v_1$，则

$v_E=\frac{1}{2}\left(v_0+v_1\right)$ (3)

(a) F-点 (b) E-点 (c) V-点 (d) 边界E-点 (e) 边界V-点

Figure 1. Surface subdivision geometric rules of Catmull-Clark

图1. Catmull-Clark曲面细分几何规则

3) V-点：设图1(c)中网格原顶点为 $v_1$， $v_2$， $v_3$， $\cdots$， $v_{2i\pm 1}\left(i=0,1,2,\cdots ,n\right)$，则新顶点V-点可表示为：

$v_V={\alpha }_n+\frac{{\beta }_n}{n}{\displaystyle \underset{i=0}{\overset{2n-1}{\sum }}{v}_{2i}}+\frac{{\gamma }_n}{n}{\displaystyle \underset{i=0}{\overset{2n-1}{\sum }}{v}_{2i+1}}$ (4)

式中： $v_{2i}$ 为与原控制点共边的相邻顶点， $v_{2i\text{+}1}$ 是同一四边形的对角点。系数 ${\beta }_n=\frac{3}{2n}$， ${\gamma }_n=\frac{1}{4n}$，

${\alpha }_n=1-{\beta }_n-{\gamma }_n$。

边界情况：v是边界点，与其相邻的两个边界点为 $v_0$ 、 $v_1$ 如图1(e)所示，则新边界点为：

$v_V=\frac{1}{8}\left(v_0+v_1\right)+\frac{3}{4}v$ (5)

2.1.2. 拓扑规则

Catmull-Clark细分的拓扑规则如图2所示。其中图2(a)为原始网格，按照曲面细分几何规则生成新面点F-点、新边点E-点和新顶点V-点，依次将每个面的F-点连接到该面中每条边的E-点，然后将新顶点V-点连接相邻的E-点，由此生成一个新的加密网格如图2(b)所示，至此完成一次细分。循环上述计算，形成不断细分的网格。

(a) 原始网格 (b) 细分后网格

Figure 2. Topological structure of Catmull-Clark subdivision

图2. Catmull-Clark细分拓扑结构

2.2. Doo-Sabin细分

1) 几何规则：对于初始控制网格 $M^k$，其中任意一个多边形 $P^k$ 的顶点 $V_i^k\left(0\le i\le n\right)$，细分后对应的多边形为 $P^{k\text{+}1}$，每个顶点 $V_i^{k+1}$ ：

$V_i^{k+1}={\displaystyle \underset{j=1}{\overset{n}{\sum }}{\omega }_{ij}}{V}_j^k\left(j=0,\cdots ,n\right)$ (6)

其中

${\omega }_{ij}=\{\begin{array}{l}\frac{1}{4n}\left(n+5\right),i=j\\ \frac{1}{4n}\left(3+2cod\left(2\pi \left(i-j\right)/n\right)\right),i\ne i\end{array}\left(i=1,2,\cdots ,n-1\right)$ (7)

2) 拓扑规则

A：对初始控制网格 $M^k$ 的每个顶点 $V_i^k$ 采用上式(6)生成新的顶点 $V_i^{k+1}$ ；

B：依次连接控制网格 $M^k$ 的每个面中的所有新生成的顶点 $V_i^{k+1}$ 得到F-面；

C：依次连接控制网格 $M^k$ 的每个边两边面所对应的新顶点 $V_i^{k+1}$ 得到E-面；

D：依次连接控制网格 $M^k$ 的每个点新生成点的顶点 $V_i^{k+1}$ 得到V-面。

Doo-Sabin细分拓扑结构如图3 [14] 所示。

(a) 原始网格 (b) 细分后结果 (c) F-面 (d) E-面 (e) V-面

Figure 3. Topological structure of Doo-Sabin subdivision

图3. Doo-Sabin细分拓扑结构

2.3. Loop细分

2.3.1. 几何规则

设每条边上插入的新顶点为E-点，由原顶点生成顶点为V-点，则：

1) V-点：对于内部顶点v，与其相邻的顶点为 $v_0,v_1,\cdots ,v_{n-1}$，则V-点由原顶点和其邻域内的顶点加权求和，可表示为：

$v_v=\left(1-n\beta \right)v_0+\beta {\displaystyle \underset{i=1}{\overset{n}{\sum }}{v}_i}$ (8)

其中，系数 $\beta$ 由如下公式定义：

$\beta =\{\begin{array}{l}\frac{3}{16},k=3;\\ \beta =\frac{1}{n}\left[\frac{5}{8}-{\left(\frac{3}{8}+\frac{1}{4}\cos \frac{2\pi }{n}\right)}^2\right]\left(n>3\right),k>3.\end{array}$ (9)

2) E-点：对于内部边，设2个三角形的公共边所对应的顶点为 $v_0$ 、 $v_1$，其他顶点为 $v_2$ 、 $v_3$，则E-点为：

$v_E=\frac{3}{8}\left(v_0+v_1\right)+\frac{1}{8}\left(v_2+v_3\right)$ (10)

边界E-点和边界V-点同Catmull-Clark细分。

Loop曲面细分几何规则如图4 [15] 所示。

(a) 内部E-点 (b) 内部V-点 (c) 边界E-点 (d) 边界V-点

Figure 4. Surface subdivision geometric rules of Loop

图4. Loop曲面细分几何规则

2.3.2. 拓扑规则

按照上述细分的几何规则，将每次细分后得到新顶点和新边点连接，生成新的拓扑结构和控制网格，拓扑规则如图5所示：

(a) 原始网格 (b) 细分后网格

Figure 5. Topological structure of Loop subdivision

图5. Loop细分拓扑结构

2.4. $\sqrt{3}$ 细分

以上介绍的三种细分方法，每细分一次后的面片数是上一次的4倍，而 $\sqrt{3}$ 细分是细分后的面片数是原来的3倍的细分，该细分方法增长速度较小，其几何规则和拓扑规则如下：

2.4.1. 几何规则

(1) F-点：设原面片3顶点为 $v_1$， $v_2$， $v_3$，则新插入的中心点F-点为：

$V_F=\frac{1}{3}\left(v_1+v_2+v_3\right)$ (11)

(2) V-点：设与原顶点v相邻的顶点为 $v_1$， $v_2$， $v_3$， $\cdots$， $v_{n-1}$，则新顶点 $V_v$ 为：

$V_v=\left(1-a_n\right)v+\frac{a_n}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{v}_i}$ (12)

其中， $a_n$ 的求解公式如下：

$a_n=\frac{1}{9}\left(4-2\cos \frac{2\pi }{n}\right)$ (13)

2.4.2. 拓扑规则

每次细分后，三角形生成一个F-点和V-点，分别连接F-点及其三个V-点，之后去掉原三角形的内部边，则得到网格数量为细分前3倍的新网格，其拓扑规则如图6所示：

(a) 初始网格 (b) 去掉原边界 (c) 细分一次后

Figure 6. Topological structure of $\sqrt{3}$ subdivision

图6. $\sqrt{3}$ 细分拓扑结构

3. 对比实验与讨论分析

本文在Intel(R) Core(TM) i5-4200U CPU，1.6 GHz，安装内存(RAM) 8 GB，window7 64位操作系统配置环境下，利用Visual studio 2015实现了四种细分算法。本文选取Pig模型和Cross模型进行算法的对比，并采用实际风机数据进行Loop细分。

3.1. 对比结果分析

1) 逼近程度：上述几种算法都是逼近式细分，其中Catmull-Clark细分、Loop细分和 $\sqrt{3}$ 细分是面分裂细分，而Doo-Sabin细分是逼近型的点分裂模式。就逼近程度来说，从图7~10可以看出，经过相同的细分次数，Doo-Sabin细分相比于Catmull-Clark和Loop细分更加逼近于初始控制网格，尤其是在网格变化剧烈的地方，如Cross的拐角处。

(a) Cross模型 (b) 细分一次 (c) 细分两次 (d) 细分三次 (e) 细分四次

Figure 7. Surface subdivision process and result of Cross model by Catmull-Clark

图7. Cross模型Catmull-Clark细分过程及结果

(a) Cross模型 (b) 细分一次 (c) 细分两次 (d) 细分三次 (e) 细分四次

Figure 8. Surface subdivision process and result of Cross model by Doo-Sabin

图8. Cross模型Doo-Sabin细分过程及结果

(a) Cross模型 (b) 细分一次 (c) 细分两次 (d) 细分三次 (e) 细分四次

Figure 9. Surface subdivision process and result of Cross model by Loop

图9. Cross模型Loop细分过程及结果

(a) Cross模型 (b) 细分一次 (c) 细分两次 (d) 细分三次 (e) 细分四次

Figure 10. Surface subdivision process and result of Cross model by $\sqrt{3}$

图10. Cross模型 $\sqrt{3}$ 细分过程及结果

2) 细分曲面的质量：Catmull-Clark细分是针对于四边形网格的细分，故对初始模型为四边形网格的模型有较好的效果，如图7(e)所示。如下图11(b)、图11(c)和图12(a)所示，Catmull-Clark、Doo-Sabin细分算法对原始网格为三角形的Pig模型进行细分，相比于Loop细分其光顺性较差。从图12、图13的细节信息可以看出经过相同次数的细分后，Loop细分后模型的质量更高。而对于任意网格都可以转化为三角形网格，因此Loop细分算法适用范围较广。

(a) Pig原始网格 (b) Catmull-Clark细分四次 (c) Doo-Sabin细分四次

Figure 11. Surface subdivision result of Pig model by Catmull-Clark and Doo-Sabin

图11. Pig模型Catmull-Clark和Doo-Sabin细分结果

(a) Loop四次细分 (b)脚部细节 (c) 耳部细节 (d) 眼部细节

Figure 12. The Loop subdivision effect diagram of the Pig model and its detailed display

图12. Pig模型的Loop细分效果图及其细节展示

(a) $\sqrt{3}$ 四次细分(b) 脚部细节(c) 耳部细节(d) 眼部细节

Figure 13. The $\sqrt{3}$ subdivision effect diagram of the Pig model and its detailed display

图13. Pig模型的 $\sqrt{3}$ 细分效果图及其细节展示

3) 细分的复杂度：对比Loop细分和 $\sqrt{3}$ 细分应用于Cross和Pig模型的效果，从图9、图10可以看出，细分相同的次数后， $\sqrt{3}$ 细分得到的网格较稀疏。在前三次细分时，Loop细分和 $\sqrt{3}$ 细分在运行效率上相当，而在第四次细分时， $\sqrt{3}$ 细分算法的运行效率明显较高。Pig模型的初始点数为：468，初始网格数为：927。从表1也可看出，Loop细分算法细分一次，三角网格面片的数量是上次的4倍，而 $\sqrt{3}$ 细分算法细分一次后三角形的数量是细分前3倍，这不仅大幅度减少了新增三角形的数量，同时也提高了细分的效率。

根据上述的讨论，我们应从初始网格形状、细分曲面的质量和细分曲面的数量三方面来选择一个最合适的细分方法。如果初始网格为四边形，则可以选择Catmull-Clark细分或Doo-Sabin细分算法，如若是三角形网格则选择Loop细分或 $\sqrt{3}$ 细分算法；如若要求细分后的面片数较少，则可以选择 $\sqrt{3}$ 细分算法；如果要求细分后的光顺性较好，则可以选择Loop细分或Catmull-Clark细分。

Table 1. The running time, the number of output points and triangles of the Pig model after subdivision four times

表1. Pig模型细分四次的运行时间、细分后的输出点数、面片数

3.2. Loop细分算法应用于真实数据

本实验对贵州大学的风机进行数据采集，并截取底部部分数据。因栅栏的遮挡，点云数据存在缺陷和不均匀性，点云数据如图14(a)所示。通过贪婪算法 [16] 建模后，模型表面存在凹凸不平的现象，并且在点云缺失部分，重建出的表面呈现局部平面，结果如图14(b)所示。由上述可知，Loop细分算法针对三角形网格，生成的曲面质量较高，因此本文选用Loop细分算法对建模后的初始网格进行细分，来消除上述现象，结果如图14(c)所示。细分后的风机底部更加光顺，凹凸不平的现象消失，由于数据缺失而导致的局部平面，在细分后更接近于曲面。

(a) 原始点云 (c) Loop细分

Figure 14. Loop subdivision of wind turbine model

图14. 风机模型的Loop细分

4. 结论

在实际应用中，通过细分算法将低分辨率的初始网格转换为光顺的表面。本文系统的阐述了四种经典细分算法，分别对不同的模型进行对比实验，并从逼近程度、细分曲面的质量和细分的复杂度三个方面进行了算法的分析，来探究各个算法的适用情况。之后，根据各细分算法的特点，选取Loop细分应用于实际数据，得到了光顺性较好的结果。研究发现：Doo-Sabin细分的逼近程度较好；四边形网格Catmull-Clark细分质量较高，而对于三角形的初始网格，Loop细分算法的光顺性较好； $\sqrt{3}$ 细分后网格的数量较其他算法较少。

基金项目

国家自然科学基金(31700385)。

NOTES

^*通讯作者。