NURBS曲面細分建模技術的研究與實現

孔令德， 康鳳娥

(1. 太原工業學院計算機工程系, 山西太原 030008; 2.太原工業學院電子工程系, 山西太原 030008)

0 引言

NURBS曲面是在de Boor三次樣條曲面插值的基礎上， 加入了張量積曲面定義的一種曲面， 其在構造CAGD曲面中較為常見[1]， 其形狀都是矩形域的. 隨著CAGD曲面的應用范圍不斷擴大， 單個矩形域已不能滿足實際建模的需求， 特別是在CG動畫制作的領域， 前期的曲面拼接技術與裁剪技術在復雜CG模型中的構建是不容易實現的. 因此， 筆者提出了細分曲面技術. 細分曲面不需要切割、不需要關節連接的特性可以解決曲面裁剪與拼接的問題. 它可以在任意拓撲網格上構造光滑的表面.

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

細分曲面理論在學術界不斷地深化與完善， 細分曲面作為CG動畫制作的一種有效的曲面造型方法也在商業界不斷被使用. 許多三維建模系統， 如開源軟件Brand、Pixar公司的Renderman和FEDES Effice公司的Houdini， 已經在其建模系統中添加了細分曲面技術. 細分曲面技術已經成為CG動畫制作的行業標準.

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

1 曲面建模相關技術

1.1 NURBS曲線曲面

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

一條k次NURBS曲線可以表示為一分段有理多項式矢函數

(1)

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

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

(2)

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

1.2 幾種細分建模技術

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

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

Catmull-Clark的細分算法是基于雙三次B樣條的計算機圖形細分建模技術， 是一種光滑表面細分曲面建模的算法. 它由Edwin Catmull和Jim Clark在1978 年設計， 并將雙三次均勻B樣條曲面推廣到任意拓撲結構層面上.

(2)Loop細分

Loop細分是由Charles Loop于1987年為三角網格開發的近似細分規則[14]. 它被劃分成1～4個三角形， 每個邊都通過計算生成一個新的頂點， 并且每個原始頂點被更新.

(3)蝶形細分

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

(4)Doo-Sabin 細分

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

(5)T樣條細分

Sederberg等人提出了T樣條的局部細分算法[18-19]. T樣條局部細分的思想是在T網格插入一個或多個控制點而不改變T樣條的曲面形狀. 因為插入一個控制點到T網格中必須伴隨著將節點插入到相鄰的混合函數中， 這一方法被稱為局部節點插入. .

2 NURBS插入節點細分規則

結合前述對細分建模的研究和實踐， 本文選擇NURBS插入節點技術作為實現曲面細分建模.

2.1 NURBS曲線插入一個節點

在NURBS的曲線中插入一個節點， 即在NURBS曲線定義域的某段節點區間插入一個節點u∈[ui,ui+1]?[uk,un+1]， 則新節點的矢量為

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

重新進行編號后變為

(3)

(4)

公式(4)中r參數代表將要插入的節點u在原節點矢量U中已經存在的個數.

2.2 NURBS曲線重復插入同一個節點

在節點矢量中重復插入l次同一節點u， 即在節點矢量中插入重節點. 而將要插入的節點u在原節點矢量U中已經存在的個數為r， 也就是已有ui=ui-1=…=ui-r+1， 要求r+l≤k. 這時新的節點矢量

2.3 NURBS曲面插入節點

NURBS樣條曲面由節點矢量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曲面中在同一位置重復插入同一節點的算法和NURBS曲線的也是一樣.

3 細分建模技術設計實現

3.1 整體架構設計

本文選擇Visual Studio 2015作為應用程序開發工具， 使用Qt作為圖形用戶界面應用程序開發框架. 在軟件中實現了NURBS細分建模的功能.NURBS曲面三維建模的流程圖如圖1所示.

圖1 物體建模的流程圖

開發的系統主要功能界面如圖2所示.

圖2NURBS曲面細分建模系統主界面

3.2 模塊功能設計

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

3.3 細分建模的主要算法

令inTime 為細分次數， Vertices為控制頂點， _W為權因子. 節點矢量細分算法、插入節點后計算新頂點算法的偽碼如下:

圖3 加載圖片建模的界面

(1)節點矢量的細分算法

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)節點矢量的細分后計算新頂點的算法

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 細分建模過程實現效果

正方體細分過程實現的效果如圖4～圖7所示， 通用物體細分實現的過程效果如圖8～圖11所示.

圖4 細分零次

圖5 細分一次

圖6 細分二次

圖7 細分四次

圖8 細分零次

圖9 細分一次

圖10 細分二次

圖11 細分四次

5 結語

曲面細分能在原始模型頂點數據的基礎上， 計算生成多倍的頂點， 新頂點與原始頂點構成的曲面依然保持其幾何性質. 與計算機圖形學中的紋理映射模擬真實的畫面效果不同， 細分的畫面效果等同于建模的時候直接設計出來的， 但數據量、處理時間也相對增大. 但是該方法數值計算穩定， 算法簡單， 并可部分細分， 與NURBS曲面相比， 它更適合于CG動畫和雕刻曲面的設計.