三种经典网格细分算法的研究与分析

三种经典网格细分算法的研究与分析

摘要:曲面造型方法由于其局部性好、计算量小、算法简中、响应速度高等优点.

已经广泛应用于计算机图形学、CAGD、计算机动画以及虚拟现实领域。网格细分是一种离散造型方法.可以从数字化仪等设备直接获得数据。介绍了近年来提出的

一些细分算法.对其中几种比较经典的算法进行了简中的分类和比较，论述了各自

的适用范围。

关键词:细分逼近插值

中图法分类号:TP391 文献标识码:A

0 引言

细分思想的产生可以追溯到二十世纪40年代末50年代初，当时G. de Rham

使用“砍角算法”描述光滑曲线的生成。细分曲线中常用的许多算法均是砍角算法。1974年，Chaikin在研究曲线的快速绘制时把离散细分的概念引入到图形学

界:1978年Catmnll和Clark[1]以及Doo和Sabin[2]分别发表了一篇在图形学领域具有里程碑意义的论文，也就是图形学界推崇的Catmul- Clark算法和Doo -Sabin算法，标志着网格细分方法研究的真正开始:1987年，Loop在他的硕士论文中提出

了Loop[3]细分策略，细分造型方法的实质是通过对初始控制点或者初始网格进行一系列的细化过程，细化的极限生成所需要的曲线或者曲面。细分造型方法与传

统样条、代数方法、变分造型等方法相比，在执行效率、任意拓扑结构、细分曲

面特征以及复杂几何形状等方面都有其独特的优势。

1 网格细分算法的分类及比较

1.1 概念与术语定义1 对于四边形网格M中的任一顶点v，如果v为内部顶

点且价不等于4或v为边界顶点且价不等于3 或2，则称v为奇异顶点。非奇异

顶点称为正则顶点。

定义2 权图(Masks)表示旧控制点计算新控制点规则的映射，其中新控制点在

映射中用黑点表示，在每个旧控制点旁边的数字代表细分系数。

定义3 奇点(Odd Vertices)是在每一级细分中，按照某种细分规则所有新生成

的点.在三角网格中，奇点也就是边点，实际上是将每条边的中点作为一个新点重

新计算新的位置所得到的点.

定义4 偶点是在每一级细分中，所有从上一级控制点继承得到的点.

定义5 某顶点的价(Valence)是指与该顶点通过公共边相连的顶点个数.

定义6 在一个网格中，如果的一条边只属于一个面，称这条边为边界边(boundary edge):如果一个顶点属于边界边则称此顶点为边界顶点(或边界点，boundary vertex):至少包含一个边界顶点的面称为边界面(boundary face)。非边界

的边、顶点和面分别称为内部边(internal edge)、内部顶点(internal vertex)和内部

面(internal face)

1.2 细分算法的分类一般情况卜，对几何网格细分算法的分类包括以下四个标

准:①生成网格的类型(三角网格和四角网格)；②细分规则的类型(面分裂和点分裂)；③算法是逼近型还是插值型；④规则曲面的极限曲面光滑性(C1，C2等)。

在现有的典型细分算法中，面分裂的细分方法，实际上就是一种1- 4的细分

策略，对于三角网格，在每一次细分过程中，保留每个三角网格中所有旧控制点

的同时，在网格的每条边上插入新点并两两相连，然后与旧控制点一起得到四个

新的三角网格；对于四角网格，除了在网格的每条边上插入新点外，还需要在网

格中间另外插入一个新点并与另外四条边上的新点相连，从而得到四个新的四角

网格。点分裂细分方法则是一种1-N的细分策略，N为该点的Valence，每个顶点将分裂为N个新顶点，然后按照一定的规则将新顶点重新连接组成新的网格。

1.3 几种经典细分算法的介绍与比较在细分算法中比较具有代表性的包括

Loop算法、Doo- Sabin算法以及Catmull- Clark算法下面对这几种细分算法分别介

绍并进行比较。

1.3.1 Loop算法 Loop细分算法是Loop于1987年在其硕士论文中提出的一种

逼近型三角形面分裂细分算法。它是基于B样条的一种策略，应用于规则网格时

可以产生C2连续的曲面，在非正规点处则可达到C1连续。Loop细分策略的权图如图1所示，其中图1(a)为内部的奇点，图1 (b)为内部的偶点，图1(c)为边界或

褶皱上的奇点，图1(d)为边界或褶皱上的偶点。显然对边界与褶皱采用特殊的规

则实际上产生的是一条三次样条曲线。

1.3.2 Catmull-Clark(C-C)算法 C-C算法是一种基于张量积双三次样条的逼近型四边形面分裂细分策略，该策略除了在非正规点处仅C1连续外可以达到处处C2连续，其细分规则源于双三次B样条的细分权图

利用权A可以得到和旧控制网格中每个点相对应的新控制点；权B则生成对

应于每条边的新点；而权C生成的新点与控制网格中的每个面相对应。这三种新

生成的点分别称为V(Vertex)型点，E(Edge)型点和F(Face)型点。显然，V型点是Odd点，E型点和F型点是Even点，F型点为其控制多边形的质心；E型点则取

该边端点以及两个相邻多边形质心的平均值；V型点的计算相对复杂，它取决于

该点的Valence，而边界与褶皱上的细分规则与Loop格式相同，图3是Catmull-Clark算法的权图。

1.3.3 Doo-Sabin算法该算法从概念与原理上在几种细分算法中最简单，它是

一种基于四边形的点分裂细分策略，仅使用一个权图就可以定义该策略.Doo-Sabin算法实际上是从Chaikin快速曲线生成算法的思想推广而来的一种生成光滑

曲面的方法，生成的曲面可以达到C1 连续. 从细分规则可以看出，细分后顶点的

度均为4，非四边形而的个数是细分前非四边形的个数加定点度不为4的顶点数，且在细分过程中，始终保持不变。此外，细分在极限情形时，某个原始多边形的

细分极限趋向于该原始多边形的中心，所以极限曲面插值于多边形的中心，利用

这个性质可以在产品设计中用来控制细分的极限曲面。

2 结束语

上面介绍了三种经典细分算法的概念、光滑性以及细分规则，它们都是基于

常规格式的细分算法，其中Loop格式是基于几何三角网格的，Catmnll-Clark和Doo-Sabin算法是基于四角网格的细分方法，对于Loop格式、以及Catmnll-Clark

两种面分裂细分算法，在算法的实现过程中需要以某个面为单位进行递归细分，

其关键是根据算法的细分规则为每个面上各个点建立有序邻接表，但是有序邻接

表的构造比较复杂，而且在细分的实现过程中会出现重复绘制的情况，因此这种

通过有序邻接表来实现递归细分的方法效率不高，Doo-Sabin细分算法是一种点

分裂细分策略，能够有效地将逼近算法和插值算法结合起来发挥两者的优势是一

个不错的选择，这也将是我们今后的一个研究重点。

参考文献：

[1]Catmull E， Clark J. Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes [J].Computer Aided Design， 1978，10(6):350-355.

[2]Doo D， Sabin M. Analysis of the Behaviour of Recursive Division Surfaces Near Extraordinary [J].ComputerAidedDesign，1978， 10(6):356-360.