孔令德， 康鳳娥

(1. 太原工業(yè)學(xué)院計(jì)算機(jī)工程系, 山西太原 030008; 2.太原工業(yè)學(xué)院電子工程系, 山西太原 030008)

0 引言

NURBS曲面是在de Boor三次樣條曲面插值的基礎(chǔ)上， 加入了張量積曲面定義的一種曲面， 其在構(gòu)造CAGD曲面中較為常見[1]， 其形狀都是矩形域的. 隨著CAGD曲面的應(yīng)用范圍不斷擴(kuò)大， 單個(gè)矩形域已不能滿足實(shí)際建模的需求， 特別是在CG動(dòng)畫制作的領(lǐng)域， 前期的曲面拼接技術(shù)與裁剪技術(shù)在復(fù)雜CG模型中的構(gòu)建是不容易實(shí)現(xiàn)的. 因此， 筆者提出了細(xì)分曲面技術(shù). 細(xì)分曲面不需要切割、不需要關(guān)節(jié)連接的特性可以解決曲面裁剪與拼接的問題. 它可以在任意拓?fù)渚W(wǎng)格上構(gòu)造光滑的表面.

最早的細(xì)分算法是圖形藝術(shù)家Chaikin在1974年CAGD國際會(huì)議上提出的、 用于快速生成一條光滑的曲線的多邊形割角算法[2]. 1978年， Catmull 和Clark 提出了CatmullClark細(xì)分曲面， 是對(duì)任意拓?fù)渚W(wǎng)格上的三階齊次B樣條曲面的擴(kuò)展[3]. 同年， Doo 和Sabin 也提出了Doo Sabin細(xì)分曲面， 是對(duì)任意拓?fù)渚W(wǎng)格上雙均勻B樣條曲面的擴(kuò)展[4]. 這兩種細(xì)分曲面的提出標(biāo)志著這一新曲面形式的出現(xiàn). 1987年， Loop將四次三項(xiàng)樣條推廣到任意的三角網(wǎng)格上， 構(gòu)建出了基于三角網(wǎng)格的Loop細(xì)分曲面[5]. 在三角網(wǎng)格方面， Dyn和Levine則利用四點(diǎn)插值的細(xì)分方法， 構(gòu)建了基于三角網(wǎng)格插值的蝶形曲面(Buterfly surface)[6]. 1998年， Sederberg、Zheng和Sewell等人將節(jié)點(diǎn)距方法引入細(xì)分曲面構(gòu)建中， 獲得了兩種非均勻有理細(xì)分曲面——廣義的CatmullClark細(xì)分曲面(NURCCs)和廣義的Doo-Sabin細(xì)分曲面[7]. 2003年， Sederberg、Zheng和Bakenov等人利用T控制點(diǎn)改善了NURCCs， 在T-NURCCs中實(shí)現(xiàn)局部插入T控制點(diǎn)方法[8]. Stam給出了Catmull-Clark細(xì)分曲面精確的計(jì)算方法， 實(shí)現(xiàn)通過細(xì)分曲面可以精確計(jì)算為任意參數(shù)的參數(shù)曲面[9].

細(xì)分曲面理論在學(xué)術(shù)界不斷地深化與完善， 細(xì)分曲面作為CG動(dòng)畫制作的一種有效的曲面造型方法也在商業(yè)界不斷被使用. 許多三維建模系統(tǒng)， 如開源軟件Brand、Pixar公司的Renderman和FEDES Effice公司的Houdini， 已經(jīng)在其建模系統(tǒng)中添加了細(xì)分曲面技術(shù). 細(xì)分曲面技術(shù)已經(jīng)成為CG動(dòng)畫制作的行業(yè)標(biāo)準(zhǔn).

本文根據(jù)細(xì)分曲面的原理， 給定了一個(gè)初始的多邊形網(wǎng)格信息， 并通過定義細(xì)分規(guī)則不斷在已有網(wǎng)格上插入新的控制頂點(diǎn)， 然后將多邊形網(wǎng)格多次進(jìn)行細(xì)化， 最后得到了一張具有光滑連續(xù)性的曲面.

1 曲面建模相關(guān)技術(shù)

1.1 NURBS曲線曲面

NURBS是一種非均勻有理B樣條(Non-Uniform Rational B-Spline)， 是幾何建模領(lǐng)域一種建模方式. 1946年Schoenberg提出了B樣條的理論[10]， B樣條方法具有建模的許多優(yōu)勢(shì)， 其缺點(diǎn)是不能適應(yīng)初等曲面的要求， 而NURBS方法很好地解決了這一問題[11].

一條k次NURBS曲線可以表示為一分段有理多項(xiàng)式矢函數(shù)

(1)

式(1)中wi(i=0,1,…,n)被稱為權(quán)重或權(quán)重因子(權(quán)重)， 它們分別與控制點(diǎn)di(i=0,1,…,n)相對(duì)應(yīng)， 一個(gè)控制頂點(diǎn)對(duì)應(yīng)著一個(gè)權(quán)因子. 首末權(quán)因子要求大于0， 其余大于或等于零. 同時(shí)要求順序k個(gè)權(quán)因子不能同時(shí)為零. 由控制頂點(diǎn)di連接起來組成NURBS的控制多邊形.Ni,k(u)是k次規(guī)范B樣條基函數(shù)， 和B樣條一樣， 是由節(jié)點(diǎn)矢量U-[u0,u1,…um+k+1]按德布爾-考克斯遞推公式?jīng)Q定的[12-13]. 實(shí)際應(yīng)用中， 將NURBS開曲線節(jié)點(diǎn)矢量兩端節(jié)點(diǎn)的重復(fù)度取為k+1， 即u0=u1=…uk，un+1=un+2=…un+k+1. 曲線定義域常取為u∈[uk,un+1]=[0,1].

在U方向和V方向， 使用NURBS曲線的方法， 構(gòu)造一張NURBS曲面， 一張k×l次NURBS曲面， 其曲面可以表示為

(2)

(2)中， (u,v)∈[0,1]×[0,1]，wij是控制權(quán)因子， 規(guī)定四角頂點(diǎn)處使用正權(quán)因子， 即w00、wm0、w0n、wmn>0， 其余wij≥0且順序k×l個(gè)權(quán)因子不同時(shí)為零. 控制頂點(diǎn)dij(i=0,1,…,m)(j=0,1,…n)按矩陣排列， 形成一個(gè)m×n的控制網(wǎng)格. 和B樣條一樣， 一個(gè)頂點(diǎn)dij對(duì)應(yīng)一個(gè)控制權(quán)因子wij. NURBS曲面的Ni,k(u)(i=0,1,…,m)和Nj,l(v)(j=0,1,…,n)分別為u向k次和v向l次的規(guī)范B樣條基. 它們分別由u向和v向的節(jié)點(diǎn)矢量U=[u0,u1,…,um+k+1]與V=[v0,v1,…,vn+l+1]按de Boor-Cox遞推公式?jīng)Q定.

1.2 幾種細(xì)分建模技術(shù)

常用細(xì)分算法有Catmull-Clark細(xì)分、Loop細(xì)分、蝶型細(xì)分、Doo-Sabin 細(xì)分、T樣條細(xì)分等.

(1)Catmull-Clark雙三次B樣條細(xì)分

Catmull-Clark的細(xì)分算法是基于雙三次B樣條的計(jì)算機(jī)圖形細(xì)分建模技術(shù)， 是一種光滑表面細(xì)分曲面建模的算法. 它由Edwin Catmull和Jim Clark在1978 年設(shè)計(jì)， 并將雙三次均勻B樣條曲面推廣到任意拓?fù)浣Y(jié)構(gòu)層面上.

(2)Loop細(xì)分

Loop細(xì)分是由Charles Loop于1987年為三角網(wǎng)格開發(fā)的近似細(xì)分規(guī)則[14]. 它被劃分成1～4個(gè)三角形， 每個(gè)邊都通過計(jì)算生成一個(gè)新的頂點(diǎn)， 并且每個(gè)原始頂點(diǎn)被更新.

(3)蝶形細(xì)分

Dyn、Gregory和Levin首先提出了蝶形插值細(xì)分的算法[4]， 細(xì)分算法可以在規(guī)則區(qū)域獲得光順次序但是邊緣的平滑度降低， 連接到一個(gè)點(diǎn)的邊緣的數(shù)量被稱為奇點(diǎn)附近的點(diǎn)的人類程度. 如果一個(gè)內(nèi)點(diǎn)的人度不為6或者一個(gè)邊緣點(diǎn)的人度不為4， 則稱這樣的點(diǎn)為奇異點(diǎn)， 否則稱為規(guī)則點(diǎn)[15]. Denis Zorin改進(jìn)了Dyn、Gregory和Levin的細(xì)分規(guī)則[16]， 他在奇異點(diǎn)周圍定義了新細(xì)分的規(guī)則， 使得細(xì)分面片在奇異點(diǎn)周圍也具有光滑的連續(xù)性. 但是他的算法在用于處理一般的三維網(wǎng)格的時(shí)候， 細(xì)分出來的面片效果很差， 達(dá)不到設(shè)計(jì)人員的要求， 究其原因是細(xì)分面片的光順性很差， 進(jìn)而嚴(yán)重影響了細(xì)分面片的視覺效果.

(4)Doo-Sabin 細(xì)分

Doo-Sabin細(xì)分算法是二次均勻B樣條曲面二分技術(shù)的推廣， 它由Daniel Doo和Malcolm Sabin于1978年開發(fā)[17]. 與Loop細(xì)分算法相比， Doo-Sabin細(xì)分算法的控制網(wǎng)格是四邊形.

(5)T樣條細(xì)分

Sederberg等人提出了T樣條的局部細(xì)分算法[18-19]. T樣條局部細(xì)分的思想是在T網(wǎng)格插入一個(gè)或多個(gè)控制點(diǎn)而不改變T樣條的曲面形狀. 因?yàn)椴迦胍粋€(gè)控制點(diǎn)到T網(wǎng)格中必須伴隨著將節(jié)點(diǎn)插入到相鄰的混合函數(shù)中， 這一方法被稱為局部節(jié)點(diǎn)插入. .

2 NURBS插入節(jié)點(diǎn)細(xì)分規(guī)則

結(jié)合前述對(duì)細(xì)分建模的研究和實(shí)踐， 本文選擇NURBS插入節(jié)點(diǎn)技術(shù)作為實(shí)現(xiàn)曲面細(xì)分建模.

2.1 NURBS曲線插入一個(gè)節(jié)點(diǎn)

在NURBS的曲線中插入一個(gè)節(jié)點(diǎn)， 即在NURBS曲線定義域的某段節(jié)點(diǎn)區(qū)間插入一個(gè)節(jié)點(diǎn)u∈[ui,ui+1]?[uk,un+1]， 則新節(jié)點(diǎn)的矢量為

U=[u1，u1, …,ui,u,un+1, …,un,un+k+1]

重新進(jìn)行編號(hào)后變?yōu)?/p>

(3)

(4)

公式(4)中r參數(shù)代表將要插入的節(jié)點(diǎn)u在原節(jié)點(diǎn)矢量U中已經(jīng)存在的個(gè)數(shù).

2.2 NURBS曲線重復(fù)插入同一個(gè)節(jié)點(diǎn)

在節(jié)點(diǎn)矢量中重復(fù)插入l次同一節(jié)點(diǎn)u， 即在節(jié)點(diǎn)矢量中插入重節(jié)點(diǎn). 而將要插入的節(jié)點(diǎn)u在原節(jié)點(diǎn)矢量U中已經(jīng)存在的個(gè)數(shù)為r， 也就是已有ui=ui-1=…=ui-r+1， 要求r+l≤k. 這時(shí)新的節(jié)點(diǎn)矢量

2.3 NURBS曲面插入節(jié)點(diǎn)

NURBS樣條曲面由節(jié)點(diǎn)矢量U和V決定，U=[u0,u1,…,um+k+1]，V=[v0,v1,…,vn+l+1].

i=(0,1,…,m+1)，j=(0,1,…,n+1).

則新的NURBS曲面表示如下：

(5)

式(5)中(u,v)∈[0,1]×[0,1]， NURBS曲面中在同一位置重復(fù)插入同一節(jié)點(diǎn)的算法和NURBS曲線的也是一樣.

3 細(xì)分建模技術(shù)設(shè)計(jì)實(shí)現(xiàn)

3.1 整體架構(gòu)設(shè)計(jì)

本文選擇Visual Studio 2015作為應(yīng)用程序開發(fā)工具， 使用Qt作為圖形用戶界面應(yīng)用程序開發(fā)框架. 在軟件中實(shí)現(xiàn)了NURBS細(xì)分建模的功能.NURBS曲面三維建模的流程圖如圖1所示.

圖1 物體建模的流程圖

開發(fā)的系統(tǒng)主要功能界面如圖2所示.

圖2NURBS曲面細(xì)分建模系統(tǒng)主界面

3.2 模塊功能設(shè)計(jì)

首先加載圖片文件， 并對(duì)圖片中的物體進(jìn)行描邊. 描邊完成之后獲得描邊數(shù)據(jù),然后進(jìn)行細(xì)分建模， 加載圖片建模的界面如圖3所示.

3.3 細(xì)分建模的主要算法

令inTime 為細(xì)分次數(shù)， Vertices為控制頂點(diǎn)， _W為權(quán)因子. 節(jié)點(diǎn)矢量細(xì)分算法、插入節(jié)點(diǎn)后計(jì)算新頂點(diǎn)算法的偽碼如下:

圖3 加載圖片建模的界面

(1)節(jié)點(diǎn)矢量的細(xì)分算法

SubdivideCurveKnots

for uTimes←0 to Number of Subdivisions

for indexJ←K to length[Vertices]

node← (Node[indexJ + 1] - Node[indexJ]) / 2.0

insert new node to Node Vector

Sort ,Getting the position of new node in the Node Vector

Generating new vertex data with newNode Vector

(2)節(jié)點(diǎn)矢量的細(xì)分后計(jì)算新頂點(diǎn)的算法

CurveKnotInsertVertex

position←the position of new nodes in the Node Vector

inInsertKnot ← new node value

for j ← position- K + 1 to position+1

numerator←inInsertKnot - Node[j]

denominator←Node[j + K+ 1] - Node[j]

aj← 0.0

if (0 == numerator or 0 == denominator)

aj←0.0

aj←numerator / denominator

Vertices[j]←aj * W[j] * Vertices[j] + (1 - aj) * W[j - 1] * W[j - 1]

W[j] ← aj * W[j] + (1 - aj) * W[j - 1]

Vertices[j] ← Vertices[j] / W[j]

for j ← inIndex + 1 to length[Vertices]

Vertices[j] ←Vertices[j - 1]

W[j] ← W[j - 1]

4 細(xì)分建模過程實(shí)現(xiàn)效果

正方體細(xì)分過程實(shí)現(xiàn)的效果如圖4～圖7所示， 通用物體細(xì)分實(shí)現(xiàn)的過程效果如圖8～圖11所示.

圖4 細(xì)分零次

圖5 細(xì)分一次

圖6 細(xì)分二次

圖7 細(xì)分四次

圖8 細(xì)分零次

圖9 細(xì)分一次

圖10 細(xì)分二次

圖11 細(xì)分四次

5 結(jié)語

曲面細(xì)分能在原始模型頂點(diǎn)數(shù)據(jù)的基礎(chǔ)上， 計(jì)算生成多倍的頂點(diǎn)， 新頂點(diǎn)與原始頂點(diǎn)構(gòu)成的曲面依然保持其幾何性質(zhì). 與計(jì)算機(jī)圖形學(xué)中的紋理映射模擬真實(shí)的畫面效果不同， 細(xì)分的畫面效果等同于建模的時(shí)候直接設(shè)計(jì)出來的， 但數(shù)據(jù)量、處理時(shí)間也相對(duì)增大. 但是該方法數(shù)值計(jì)算穩(wěn)定， 算法簡單， 并可部分細(xì)分， 與NURBS曲面相比， 它更適合于CG動(dòng)畫和雕刻曲面的設(shè)計(jì).