自由曲线曲面的任意次非均匀细分

郑辑涛;秦开怀

【摘 要】提出一种有效的建模自由曲线曲面的非均匀细分算法.首先在节点插入技术基础上推导出任意次自由曲线的非均匀细分规则,然后把它推广到张量积曲面得到任意次自由曲面的非均匀细分规则,最后对奇异点附近曲面采用类Doo-Sabin和Catmull-Clark的细分规则,从而使该算法可以实现建模任意次具有任意拓扑基网格的非均匀细分曲面.此外,该方法也实现了对传统细分格式的统一,例如,当次数为2并采用均匀节点矢量便转化为Doo-Sabin细分,当次数为3并采用均匀节点矢量便转化为Catmull-Clark细分.%In this paper, a new recursive non-uniform subdivision approach for modeling free-form curves and surfaces was presented. Based on the knot insertion technique, the non-uniform subdivision rules were provided for modeling arbitrarydegree curves and surfaces of arbitrary topology with non-uniform knot intervals. In particular, this approach generalized the traditional uniform subdivisions, such as Doo-Sabin and Catmull-Clark subdivision. 【期刊名称】《计算机应用》 【年(卷),期】2011(031)001 【总页数】5页(P53-57)

【关键词】非均匀;细分曲面;非均匀有理B样条 【作 者】郑辑涛;秦开怀

【作者单位】清华大学计算机科学与技术系,北京,100084;空军第四飞行学院飞行干部进修系,石家庄,050071;清华大学计算机科学与技术系,北京,100084 【正文语种】中 文 【中图分类】TP391 0 引言

在计算机辅助设计(Computer Aided Design,CAD)和相关的数字几何设计领域,非均匀有理 B样条(Non Uniform Rational B-Spline,NURBS)已经成了人所共知的基本造型工具。实践中,NURBS的基网格需要具有矩形拓扑并且难于处理任意拓扑复杂模型的建模。细分曲面技术的出现有效地解决了这个问题,它可以处理具有任意拓扑的曲面。

在曲线曲面的表示方面,基于细分的建模方法可以追溯到 Chaikin的角切割算法[1],极限情况下 Chaikin的算法生成均匀的二次B样条曲线。此后,Doo等人[2]和Catmull等人[3]分别把细分格式从曲线拓展到具有任意初始拓扑的自由曲面。对于规则网格,Doo-Sabin细分生成均匀双二次 B样条曲面,Catmull-Clark细分生成均匀双三次B样条曲面。因此,它们分别是对具有任意拓扑初始控制网格的双二次和双三次B样条曲面的扩展。由于细分曲面对初始控制网格没有限制的优点,近年来各种细分技术被广泛研究提出并逐渐成为计算机动画、曲线曲面造型、数字几何处理等领域的重要工具。例如常见的还有、4-8细分[8]、Loop细分[9]、Butterfly细分[10]等。但是上述这些细分格式是建立在等距节点矢量或均匀 B样条基础之上的,与非均匀B样条相比,显然在几何建模的灵活性和通用性方面尚有差距。因此基于 NURBS的非均匀细分方法尚需进行深入研究。

非均匀细分由于其依赖于非均匀的节点矢量以及其实现上的复杂性,长期以来没有

得到广泛研究。早在 20世纪 90年代,Qu等人[11]首次从离散 B样条推导出自由曲线的非均匀细分算法。此后,Sederberg等人[12]为多边形网格中的每一个边赋予一个节点距,从而研究了非均匀二次和三次的细分方法,但他们并没有推广到任意次曲面。值得注意的是,Schaefer和Cashman在建立非均匀细分规则中做出了各自的贡献。Schaefer等人[13]扩展了 Lane-Riesenfeld细分算法并且提出了一个任意次B样条的细分算法,但该算法由于不具有对称性而难于推广到曲面。Cashman等人[14-15]同样提出了一个基于Lane-Riesenfeld细分算法的非均匀细分格式,此方法用 blossom来表达,由于他们在处理张量积曲面时遇到困难,不仅没有推广到曲面,也没能给出一个形式化的表达形式,特别是对奇异点的处理也是一个难题。

本文基于节点插入技术[16]提出了一个新的非均匀细分算法,建立了非均匀细分格式。其特点是:

1)对于规则网格,应用非均匀节点矢量生成非均匀 B样条曲线曲面。

2)能够处理任意拓扑的模型,生成任意次的曲线或曲面,包括奇异点。特别是对均匀的节点矢量,当次数为 2时生成 Doo-Sabin曲面,当次数为 3时,生成 Catmull-Clark曲面。

难点在于建立非均匀节点矢量和细分格式之间的关系以及奇异点附近细分格式的处理。

1 B样条曲线的非均匀细分 1.1 二、三次非均匀细分

为了得到非均匀细分算法,首先在任意两个初始节点之间插入新节点。假设初始节点矢量和控制点如下:

当次数 d=2时,插入一个新节点ti∈ [ui,ui+1]后,新的节点矢量和控制点如下:

其中,箭头所指的元素是新插入的节点和控制点。为了细分原始控制多边形,应该在任意两个旧的节点参数之间插入。即:

其中新控制顶点的计算请参考Boehm节点插入算法[16]。

插入完成后,节点矢量的长度增加,重新编号后节点矢量和控制点分别为:

应用 Boehm节点插入,可得新控制点的计算公式:

从式(1)中可以看出,每个新的控制顶点依赖于两个相邻的旧控制点。类似于 Chaikin的角切割算法,不同之处在于平均加权系数不是常数而是依赖于非均匀节点矢量。所以可以看做是 Chaikin角切割算法的非均匀版本。

二次 B样条非均匀细分的拓扑规则如图 1所示。其中实心点表示第K层的控制点,空心点表示经过一次细分后第K+1层的控制点。 图1 二次 B样条细分的拓扑规则

当所有节点距都相等并且令θi=0.5,则二次非均匀细分退化为 Chaikin角切割算法:

当 B样条曲线次数d=3时,插入新节点后,利用 Boehm节点插入方法可得三次非均匀细分格式:

其中,其拓扑规则如图 2所示。实心点属于第 K层,空心点属于第K+1层。由公式和拓扑规则可以看出上述细分规则的第一步是更新第K层的控制点,第二步是插入新的控制点。

图2 三次 B样条细分的拓扑规则

1.2 任意次曲线的非均匀细分

同样的方法,可得曲线的任意次非均匀细分规则。 假设给定第K层的控制点和节点矢量:

对于 d次B样条曲线,细分前的层次为K,经过一次细分,得到第K+1层的节点矢量和控制点。

细分后控制点集为:

应用Boehm节点插入,可得任意次非均匀细分格式:

因此给定次数d,通过式(2)迭代计算直到j=0便得到任意次细分格式,并且 p0 i是原始控制点,即 p0 i=Pi(Pi∈ PK)。此外,从任意次非均匀细分格式,可以得出更一般的结论。

1)当次数d为偶数时,细分的拓扑规则都同d=2的情况,如图 1。细分的结果在任意两个原始控制点间产生两个新控制点。这和Chaikin角切割算法的拓扑规则也是一致的。因此,偶次非均匀细分可以看做Chaikin方法的非均匀版本。

2)当次数 d为奇数时,细分的拓扑规则都同d=3的情况,如图 2。此外,奇次非均匀细分包括两个不同的步骤,第一步是更新原始控制点,第二步是在任意两个原始控制点间插入一个新控制点。

3)虽然奇次和偶次细分分别具有相同的拓扑规则,但随着次数的增加,仿射变换的节点支撑区间将随之增大。

三次 B样条曲线非均匀细分的例子如图 3所示,这里非均匀节点矢量通过弦长参数化求得。从图中可以看出,与均匀细分相比,非均匀细分生成的曲线更加忠实于原始

控制多边形,而且非均匀细分曲线可以通过调整节点参数方便地进行形状修改。 图3 三次 B样条细分曲线 2 任意次非均匀细分曲面 2.1 规则拓扑的非均匀细分

把上述非均匀细分算法推广到任意次具有规则拓扑的张量积曲面是很自然的事,只需在两个方向上分别使用一维非均匀细分算法。具体描述如下。 给定二维规则控制多边形 PK和对应的节点矢量UK和V K,即:

对于任意次数 d,假设细分前层次为 K,细分后为 K+1。首先在 u和 v两个方向上插入新节点得到新的节点矢量:

式中 θi∈ [0,1]和 φi∈ [0,1]分别为 u向和 v向非均匀节点插入系数。分别在u和v方向执行 Boehm算法,假设先对任意常量参数 v,执行节点插入,得到中间结果 Pu:

式(3)中。随后再对任意常量 u执行节点插入,得到细分后的控制多边形网格。可以证明交换 u和v的顺序结果相同。

式中 p v,0i,j表示 Pu中的点,即式(4)描述了任意次规则多边形的细分算法,给定初始控制多边形,通过细分可以计算任意次光滑的张量积曲面。 2.2 双二次和双三次非均匀细分

作为例子,本文给出双二次和双三次细分格式。另d=2,代入式(4)可得双二次细分公式如下:

双二次非均匀细分的拓扑规则如图 4所示,其中实心点表示细分前的控制多边形,空

心点表示细分后的控制多边形。从图中可以看出,其拓扑规则与Doo-Sabin细分相同。区别在于非均匀细分的平均加权系数不是常量而是取决于非均匀节点矢量。当节点矢量U和V均匀分布时,双二次非均匀细分转化为传统的Doo-Sabin细分。 另d=3,代入上面任意次张量积曲面细分通用格式(4),可得双三次细分公式如下:

其中加权系数 λi,μi和ηi很容易由 2.1节中公式得到,这里不再一一列出。 虽然随着次数的增加,加权系数会越来越复杂,但是仍然满足仿射变换的性质:

读者可以任给一组节点矢量,计算系数α,β后代入上式自行验证。

双三次非均匀细分的拓扑规则如图 5所示,同样实心点表示细分前的原始控制网格,空心点表示细分后的控制网格。从图中可以看出规则区域的拓扑规则同传统的Catmull-Clark细分,而且当节点矢量均匀分布时,细分格式将转化为Catmull-Clark细分。

图4 双二次非均匀细分的拓扑规则 图5 双三次非均匀细分的拓扑规则

此外对于任意次非均匀细分,可以得到如下结论:当次数为偶数,拓扑规则同 Doo-Sabin细分,如图 4所示;当次数为奇数,拓扑规则同 Catmull-Clark细分,如图 5所示;区别在于非均匀细分的权因子取决于非均匀节点矢量。 2.3 具有奇异点的任意拓扑的非均匀细分

如果一个面具有四条边,即矩形面,则称为规则面;如果一个顶点的价为 4,则称为规则点,否则称为奇异点。具有规则点和规则面的控制网格我们称为规则拓扑。上述非均匀细分仅能处理规则网格,为了能够处理具有奇异点的任意拓扑网格,本文借鉴了传统的 Doo-Sabin和 Catmull-Clark中的思想。

对于偶数次细分,经过一次细分,所有顶点的价都为 4,称为规则点。但对于非规则面

上点的计算,可以采用Doo-Sabin细分的处理方法,细分模板如图6(a)所示。规则如下:

对于奇数次细分,由于其拓扑规则同Catmull-Clark细分,经过一次细分后,所有的面都成为规则面,奇异点的数量保持不变。奇异点附近的细分由于其不规则性不能得到标准的NURBS曲面,受 Catmull-Clark细分启发,本文用奇异点附近点的仿射变换来表示。图 6(b)和(c)分别给出了价为 3和 5的计算模板,其中箭头表示局部计算边点的方向。得到边点和面点后,可以用奇异点周围相邻的面点和边点更新奇异点。本文用 α(n)表示奇异点 v的系数,用β(n)表示与 v邻接的边点的系数,用 γ(n)表示与 v邻接的面点的系数。这些系数应满足仿射变换的性质:

对于具有任意拓扑的网格,可以先进行一次细分,这样所有面均为矩形规则面。 图6 不规则网格的模板 3 结果分析

部分非均匀细分的实验结果如图 7和图 8所示。

Ruibin[11]只能处理自由曲线;Stam[17]算法虽然是用来处理细分曲线曲面的,但只能处理均匀节点情况;Cashman[15]提出了一个处理任意次B样条曲线的非均匀细分算法,由于其算法是从Lane-Fiesenfeld算法演绎而来,需要首先重复控制点然后做d-1次光滑,因此其时间复杂度是O(dn);本文提出的任意次非均匀细分算法仅需两步,时间复杂度为O(2n)。相比 Cashman的方法,本文方法更容易处理具有奇异点的任意拓扑网格,而且由于本文算法有清晰的解析表示,也容易扩展到任意拓扑的张量积曲面。同文献[17]中方法可以证明,本文方法生成的曲面除了有限的不规则点外为 Cd-1连续,而在奇异点附近奇次和偶次情况,本文分别采用类Catmull-Clark和Doo-Sabin细分方法,因此满足 C1连续。

4 结语

本文从非均匀 B样条曲线基于 Boehm节点插入技术提出一个全新的非均匀细分算法,并推广到张量积 B样条曲面和具有任意拓扑曲面。

给出了一个基于 B样条的任意次的细分规则,并且统一了传统的均匀细分规则。在理论上,本文方法与NURBS是一致的。给出了一个非均匀细分曲线曲面的建模方法,与传统均匀细分格式相比,计算新节点时的仿射变换系数依赖于非均匀节点矢量,因此建模过程中可以通过调整节点矢量来修改曲线或曲面,表现出更强的灵活性。 图7 原始模型集合 1 图8 原始模型集合 2 参考文献:

[1] CHAIKIN G.An algorithm for high-speed curve generation[J].Computer Graphics and Image Processing,1974,3(4):346-349.

[2] DOO D,SABIN M.Behavior of recursive division surfacesnear extraordinary points[J].Computer-Aided Design,1978,10(6):356-360. [3] CATMULL E,CLARK J.Recursively generated B-spline surfaces on arbitrary topological meshes[C]//Computer-Aided Design,1978,10(6):350-355.

[4] LI G,MAW,BAOH.2-subdivision for quadrilateral meshes[J].The Visual Computer,2004,20(2/3):180-198.

[5] LIG,MA W,BAO H.Interpolatory 2-subdivision surfaces[C]//Proceedings of the Geometric Modeling and Processing.Washington,DC:IEEE Computer Society,2004:185-194.

[6] KOBBELT L.3-subdivision[C]//Proceedings of ACM SIGGRAPH Computer Graphics.New York:ACM,2000:103-112.

[7] LABISK U,GREINER G.Interpolatory 3-subdivision[J].Computer Graphics Forum,2000,19(3):131-138.

[8] VELHO L,ZORIN D.4-8 Subdivision[J].Computer Aided Geometric Design,2001,18(5):397-427.

[9] LOOPCT.Smooth subdivision surfaces based on triangles[D].Salt Lake City:The University of Utah,1987.

[10] DYN N,LEVINE D,GREGORY J A.A butterfly subdivision scheme for surface interpolation with tension control[J].ACM Transactions on Graphics,1990,9(2):160-169.

[11] QU R,GREGORY J.A subdivision algorithm for non-uniform B-splines[C]//Approximation Theroy,Spline Functions and Application.Berlin:Springer,1992:423-436.

[12] SEDERBERG T W,ZHENG J,SEWELL D,et al.Non-uniform recursive subdivision surfaces[C]//Proceedings of the ACM SIGGRAPH Computer Graphics.New York:ACM,1998:387-394.

[13] SCHAEFER S,GOLDMAN R.Non-uniform subdivision for B-splines of arbitrary degree[J].Computer Aided Geometric Design,2009,26(1):75-81 [14] CASHMAN T J,DODGSON N A,SABIN M A.Non-uniform B-spline subdivision using refine and smooth[C]//12th IMA Conference on the Mathematicsof Surfaces.Berlin:Springer,2007:121-137.

[15] CASHMAN T J,DODGSON N A,SABIN M A.A symmetric,non-uniform,refine and smooth subdivision algorithm for general degree B-splines[J].Computer Aided Geometric Design,2009,26(1):94-104.

[16] BOEHM W.Inserting new knots into B-spline curve[J].Computer-Aided

Design,1980,12(4):199-201.

[17] STAM J.On subdivision schemes generalizing uniform B-spline surfaces of arbitrary degree[J].Computer Aided Geometric Design,2001,18(5),383-396.