基于顶点法向量约束的Catmull-Clark细分插值方法①

林传銮

(福州墨尔本理工职业学院 计算机与文化创意系,福州 350108)

引言

曲面细分技术是计算机辅助几何设计(Computer Aided Geometric Design,简称CAGD)和计算机图形学(Computer Graphics,简称CG)的研究热点,该研究成果已经在曲面造型、几何设计和处理、动画软件等方面上广泛应用[1].

给定一个由初始控制顶点构成的网格,细分规则是根据相应的几何规则和拓扑规则,在原有的网格上插入新的顶点,通过不断的重复细分规则,最终生成一个网格可表示为实体或极限曲面[2,3].根据细分曲面是否通过初始控制顶点可以将细分方法分为两类,分别是逼近型细分和插值型细分[4],逼近型细分生成的极限曲面相对于初始控制网格会收缩,但是极限曲面光顺性较好,相较于逼近型细分,插值型细分则要求极限曲面通过初始控制网格,但光顺性不如逼近型细分.典型的基于四边形网格的逼近型细分代表有Catmull-Clark[5]细分,生成的极限曲面在规则点处C2连续,不规则点处C1连续.典型的插值型细分代表有蝶型细分方法(Butterfly Subdivision),后来又由Kobbelt等[6]作了改进,改进的细分方法可以在任意拓扑网格上实现C1连续.插值型细分方法得到的极限曲面虽然不会收缩,但是极限曲面可能产生不必要的扭曲,并且对锐利形状的初始网格更加敏感,容易产生效果比较差的曲面.

实际应用当中常常要求极限曲面可以通过初始控制顶点,如何生成极限曲面既光顺,又能实现插值初始控制网格成为近年来计算机辅助几何设计研究的一个热点,其中 Hoppe[7],Nasri[8],Brunet[9]以及 Halstead[10]等提出全局优化方法构造出线性方程组反解控制顶点实现插值,Zheng和Cai[11]提出一种用两步 Catmull-Clark细分方法构造插值曲面,上述方法都需求解线性方程组,对稠密的控制网格难以处理.随着B样条曲线渐进迭代逼近(Progressive Iterative Approximation,简称PIA)方法在曲面细分研究方面的推广,Chen等[12]提出了Catmull-Clark细分的渐进迭代插值方法,上述方法缺少调整曲面造型的自由度.Lin和Pan等[13,14]通过两步细分的方法提出了基于形状控制的插值型 Loop细分和Catmull-Clark 细分,Guo等[15]提出基于渐进插值的 Catmull-Clark 双正交细分小波及其应用,分析了该算法具有较高的效率和稳定性,以上方法同时实现了插值和形状控制,但对于初始控制网格中存在着尖锐的顶点,仍缺少某些细节特征的处理,生成的细分曲面效果不够理想.

近年来,Catmull-Clark细分建模方法的应用越来越广泛.Bénard等[16]利用Catmull-Clark细分实现了计算具有精确拓扑的光顺曲面轮廓.Wei等[17]提出了拓展截断层次的Catmull-Clark细分方法,改进了曲面的局部特征.Wang等[18]利用参数化的二阶Bezier生成插值型Catmull-Clark细分曲面.实际建模当中,细分曲面的形状控制起着重要作用,法向量可以量化的表示模型的某些细节特征,是曲面形状控制的重要因素,因此插值法向量对于曲面形状控制有着重要意义,Halstead[10]提出了Catmull-Clark细分的顶点法向量的计算方法,为了使应用渐进迭代方法生成的Catmull-Clark细分曲面既能实现形状控制,又能插值法向量,本文在文献[19]的基础上提出一种基于顶点法向量约束的两步Catmull-Clark细分插值算法,插值目标是给定一个闭合的初始四边形网格其中为顶点集,为边集,控制顶点相应的法向量,生成的极限曲面插值初始网格中的顶点集和相应的法向量.

1 顶点法向量插值条件

本文讨论定义在闭合的四边形网格上的Catmull-Clark细分,几何规则是计算在细分过程中产生的新顶点(分别是新面点F点,新边点E点,新顶点V点),每一次细分后生成的新顶点的拓扑连接规则都保持一致.为了分析一个顶点周围的极限曲面,引入两个矩阵来描述局部的细分过程,分别是顶点的1-领域顶点组成的列矩阵和相应的细分矩阵.为网格中n个顶点中的一个对应1-领域顶点组成的列矩阵在一次细分后生成的相应列矩阵可以通过线性运算求得,方矩阵为Catmull-Clark细分矩阵由四边形网格组成的闭合初始网格相应的Catmull-Clark细分矩阵为:

整个细分过程可以表示为对初始控制顶点重复左乘细分矩阵,因此,存在一当i趋于无穷大时，为极限曲面.

Halstead通过对Doo-Sabin细分进行分析获得细分矩阵与极限曲面的性质,可以推广到Loop细分与Catmull-Clark细分,同时给出了的左特征向量与极限法向量的关系,从而推导出极限顶点法向量的计算方法.

引理1[10].初始控制网格上的任一顶点,该顶点1-领域顶点集为以及相应的局部细分矩阵为,它会收敛到顶点上特征值为1的特

2 两步Catmull-Clark细分插值方法

两步Loop细分插值方法在文献[19]中第一次被提出,本文提出的方法是给定一个初始控制网格,通过两步Catmull-Clark细分插值方法使得生成的极限曲面S∞插值于初始控制顶点V={v1，v2，...，vm}和相应的法向量N={N1，N2，...，Nm}.两步Catmull-Clark细分方法中第一步是对初始控制网格M0进行一次改造型Catmull-Clark插值细分[14]得到新的控制网格,然后对新的控制网格生成极限曲面,调整新顶点位置,生成控制网格; 第二步是调整新边点和新面点位置.经过以上两步Catmull-Clark细分可以生成,其中调整新顶点是为了实现插值初始控制顶点,调整新边点和新面点是为了实现插值法向量.重复上述过程会得到一系列网格时,极限曲面插值初始网格上的控制顶点和法向量.两步Catmull-Clark细分规则中的第一步分为两个步骤,第一个步骤是对初始控制网格进行一次改造型Catmull-Clark插值细分得到新的控制网格.具体的第一个步骤:

1) 拓扑规则与传统的Catmull-Clark细分方法保持不变;

2) 几何规则中,新边点和新面点与传统的Catmull-Clark细分方法保持不变.新顶点的取法修改为:

3 插值法向量分析

要证明第2节给出的两步Catmull-Clark细分的初始控制顶点法向量插值,就是要确定差向量,从而获得相应的法向量插值于给定的法向量.

这里采用拉格朗日乘子法求解上述问题,引入两个拉格朗日乘子都为标量.相应的目标函数为:

由于本文讨论闭合的四边形网格上的 Catmull-Clark 细分,则网格上每个顶点的度因此通过三角函数的运算得出推导出:

得到新边点和新面点的差向量为:

4 实验结果与分析

本文利用 Visual Studio 2012 和 CSGL 实现了基于顶点法向量约束的两步Catmull-Clark细分插值方法.本文给出了4个四边形网格模型的例子,各个顶点处形状控制参数值都取其中标记红色的顶点为初始网格对应的顶点.例1为正方体网格,实验结果见图1,例2为圆环形网格,实验结果见图2,例3为圆锥形网格,实验结果见图3,例4为正方体与球形,实验结果见图4,图中(a)表示初始控制网格,(b)表示Catmull-Clark细分2次,(c)表示改造型Catmull-Clark细分2次,(d)表示本文基于顶点法向量约束的两步Catmull-Clark细分2次.从实验结果看,本文给定的方法生成的曲面插值于初始控制网格和给定的法向量,方法简单,曲面造型效果良好.

图1 基于顶点法向量约束的两步Catmull-Clark细分插值方法(正方体形)

图2 基于顶点法向量约束的两步Catmull-Clark细分插值方法(圆环形)

图3 基于顶点法向量约束的两步Catmull-Clark细分插值方法(圆锥形)

图4 基于顶点法向量约束的两步Catmull-Clark细分插值方法(正方体与球形)

5 结语

本文提出了一种基于顶点法向量约束的两步Catmull-Clark细分插值方法,该方法在改造型 Catmull-Clark 细分规则基础上结合初始控制顶点法向量的约束实现对 Catmull-Clark 细分生成曲面的插值,引入拉格朗日乘子法求出乘子,从而求出差向量实现插值法向量.该方法同时具有形状调整和插值法向量两个特性,丰富了细分曲面造型的形状控制方法.本文方法只研究了实验图形的效果,还可以继续研究细分的精度和效率.