林傳鑾

(福州墨爾本理工職業(yè)學院 計算機與文化創(chuàng)意系,福州 350108)

引言

曲面細分技術(shù)是計算機輔助幾何設(shè)計(Computer Aided Geometric Design,簡稱CAGD)和計算機圖形學(Computer Graphics,簡稱CG)的研究熱點,該研究成果已經(jīng)在曲面造型、幾何設(shè)計和處理、動畫軟件等方面上廣泛應(yīng)用[1].

給定一個由初始控制頂點構(gòu)成的網(wǎng)格,細分規(guī)則是根據(jù)相應(yīng)的幾何規(guī)則和拓撲規(guī)則,在原有的網(wǎng)格上插入新的頂點,通過不斷的重復細分規(guī)則,最終生成一個網(wǎng)格可表示為實體或極限曲面[2,3].根據(jù)細分曲面是否通過初始控制頂點可以將細分方法分為兩類,分別是逼近型細分和插值型細分[4],逼近型細分生成的極限曲面相對于初始控制網(wǎng)格會收縮,但是極限曲面光順性較好,相較于逼近型細分,插值型細分則要求極限曲面通過初始控制網(wǎng)格,但光順性不如逼近型細分.典型的基于四邊形網(wǎng)格的逼近型細分代表有Catmull-Clark[5]細分,生成的極限曲面在規(guī)則點處C2連續(xù),不規(guī)則點處C1連續(xù).典型的插值型細分代表有蝶型細分方法(Butterfly Subdivision),后來又由Kobbelt等[6]作了改進,改進的細分方法可以在任意拓撲網(wǎng)格上實現(xiàn)C1連續(xù).插值型細分方法得到的極限曲面雖然不會收縮,但是極限曲面可能產(chǎn)生不必要的扭曲,并且對銳利形狀的初始網(wǎng)格更加敏感,容易產(chǎn)生效果比較差的曲面.

實際應(yīng)用當中常常要求極限曲面可以通過初始控制頂點,如何生成極限曲面既光順,又能實現(xiàn)插值初始控制網(wǎng)格成為近年來計算機輔助幾何設(shè)計研究的一個熱點,其中 Hoppe[7],Nasri[8],Brunet[9]以及 Halstead[10]等提出全局優(yōu)化方法構(gòu)造出線性方程組反解控制頂點實現(xiàn)插值,Zheng和Cai[11]提出一種用兩步 Catmull-Clark細分方法構(gòu)造插值曲面,上述方法都需求解線性方程組,對稠密的控制網(wǎng)格難以處理.隨著B樣條曲線漸進迭代逼近(Progressive Iterative Approximation,簡稱PIA)方法在曲面細分研究方面的推廣,Chen等[12]提出了Catmull-Clark細分的漸進迭代插值方法,上述方法缺少調(diào)整曲面造型的自由度.Lin和Pan等[13,14]通過兩步細分的方法提出了基于形狀控制的插值型 Loop細分和Catmull-Clark 細分,Guo等[15]提出基于漸進插值的 Catmull-Clark 雙正交細分小波及其應(yīng)用,分析了該算法具有較高的效率和穩(wěn)定性,以上方法同時實現(xiàn)了插值和形狀控制,但對于初始控制網(wǎng)格中存在著尖銳的頂點,仍缺少某些細節(jié)特征的處理,生成的細分曲面效果不夠理想.

近年來,Catmull-Clark細分建模方法的應(yīng)用越來越廣泛.Bénard等[16]利用Catmull-Clark細分實現(xiàn)了計算具有精確拓撲的光順曲面輪廓.Wei等[17]提出了拓展截斷層次的Catmull-Clark細分方法,改進了曲面的局部特征.Wang等[18]利用參數(shù)化的二階Bezier生成插值型Catmull-Clark細分曲面.實際建模當中,細分曲面的形狀控制起著重要作用,法向量可以量化的表示模型的某些細節(jié)特征,是曲面形狀控制的重要因素,因此插值法向量對于曲面形狀控制有著重要意義,Halstead[10]提出了Catmull-Clark細分的頂點法向量的計算方法,為了使應(yīng)用漸進迭代方法生成的Catmull-Clark細分曲面既能實現(xiàn)形狀控制,又能插值法向量,本文在文獻[19]的基礎(chǔ)上提出一種基于頂點法向量約束的兩步Catmull-Clark細分插值算法,插值目標是給定一個閉合的初始四邊形網(wǎng)格其中為頂點集,為邊集,控制頂點相應(yīng)的法向量,生成的極限曲面插值初始網(wǎng)格中的頂點集和相應(yīng)的法向量.

1 頂點法向量插值條件

本文討論定義在閉合的四邊形網(wǎng)格上的Catmull-Clark細分,幾何規(guī)則是計算在細分過程中產(chǎn)生的新頂點(分別是新面點F點,新邊點E點,新頂點V點),每一次細分后生成的新頂點的拓撲連接規(guī)則都保持一致.為了分析一個頂點周圍的極限曲面,引入兩個矩陣來描述局部的細分過程,分別是頂點的1-領(lǐng)域頂點組成的列矩陣和相應(yīng)的細分矩陣.為網(wǎng)格中n個頂點中的一個對應(yīng)1-領(lǐng)域頂點組成的列矩陣在一次細分后生成的相應(yīng)列矩陣可以通過線性運算求得,方矩陣為Catmull-Clark細分矩陣由四邊形網(wǎng)格組成的閉合初始網(wǎng)格相應(yīng)的Catmull-Clark細分矩陣為:

整個細分過程可以表示為對初始控制頂點重復左乘細分矩陣,因此,存在一當i趨于無窮大時，為極限曲面.

Halstead通過對Doo-Sabin細分進行分析獲得細分矩陣與極限曲面的性質(zhì),可以推廣到Loop細分與Catmull-Clark細分,同時給出了的左特征向量與極限法向量的關(guān)系,從而推導出極限頂點法向量的計算方法.

引理1[10].初始控制網(wǎng)格上的任一頂點,該頂點1-領(lǐng)域頂點集為以及相應(yīng)的局部細分矩陣為,它會收斂到頂點上特征值為1的特

2 兩步Catmull-Clark細分插值方法

兩步Loop細分插值方法在文獻[19]中第一次被提出,本文提出的方法是給定一個初始控制網(wǎng)格,通過兩步Catmull-Clark細分插值方法使得生成的極限曲面S∞插值于初始控制頂點V={v1，v2，...，vm}和相應(yīng)的法向量N={N1，N2，...，Nm}.兩步Catmull-Clark細分方法中第一步是對初始控制網(wǎng)格M0進行一次改造型Catmull-Clark插值細分[14]得到新的控制網(wǎng)格,然后對新的控制網(wǎng)格生成極限曲面,調(diào)整新頂點位置,生成控制網(wǎng)格; 第二步是調(diào)整新邊點和新面點位置.經(jīng)過以上兩步Catmull-Clark細分可以生成,其中調(diào)整新頂點是為了實現(xiàn)插值初始控制頂點,調(diào)整新邊點和新面點是為了實現(xiàn)插值法向量.重復上述過程會得到一系列網(wǎng)格時,極限曲面插值初始網(wǎng)格上的控制頂點和法向量.兩步Catmull-Clark細分規(guī)則中的第一步分為兩個步驟,第一個步驟是對初始控制網(wǎng)格進行一次改造型Catmull-Clark插值細分得到新的控制網(wǎng)格.具體的第一個步驟:

1) 拓撲規(guī)則與傳統(tǒng)的Catmull-Clark細分方法保持不變;

2) 幾何規(guī)則中,新邊點和新面點與傳統(tǒng)的Catmull-Clark細分方法保持不變.新頂點的取法修改為:

3 插值法向量分析

要證明第2節(jié)給出的兩步Catmull-Clark細分的初始控制頂點法向量插值,就是要確定差向量,從而獲得相應(yīng)的法向量插值于給定的法向量.

這里采用拉格朗日乘子法求解上述問題,引入兩個拉格朗日乘子都為標量.相應(yīng)的目標函數(shù)為:

由于本文討論閉合的四邊形網(wǎng)格上的 Catmull-Clark 細分,則網(wǎng)格上每個頂點的度因此通過三角函數(shù)的運算得出推導出:

得到新邊點和新面點的差向量為:

4 實驗結(jié)果與分析

本文利用 Visual Studio 2012 和 CSGL 實現(xiàn)了基于頂點法向量約束的兩步Catmull-Clark細分插值方法.本文給出了4個四邊形網(wǎng)格模型的例子,各個頂點處形狀控制參數(shù)值都取其中標記紅色的頂點為初始網(wǎng)格對應(yīng)的頂點.例1為正方體網(wǎng)格,實驗結(jié)果見圖1,例2為圓環(huán)形網(wǎng)格,實驗結(jié)果見圖2,例3為圓錐形網(wǎng)格,實驗結(jié)果見圖3,例4為正方體與球形,實驗結(jié)果見圖4,圖中(a)表示初始控制網(wǎng)格,(b)表示Catmull-Clark細分2次,(c)表示改造型Catmull-Clark細分2次,(d)表示本文基于頂點法向量約束的兩步Catmull-Clark細分2次.從實驗結(jié)果看,本文給定的方法生成的曲面插值于初始控制網(wǎng)格和給定的法向量,方法簡單,曲面造型效果良好.

圖1 基于頂點法向量約束的兩步Catmull-Clark細分插值方法(正方體形)

圖2 基于頂點法向量約束的兩步Catmull-Clark細分插值方法(圓環(huán)形)

圖3 基于頂點法向量約束的兩步Catmull-Clark細分插值方法(圓錐形)

圖4 基于頂點法向量約束的兩步Catmull-Clark細分插值方法(正方體與球形)

5 結(jié)語

本文提出了一種基于頂點法向量約束的兩步Catmull-Clark細分插值方法,該方法在改造型 Catmull-Clark 細分規(guī)則基礎(chǔ)上結(jié)合初始控制頂點法向量的約束實現(xiàn)對 Catmull-Clark 細分生成曲面的插值,引入拉格朗日乘子法求出乘子,從而求出差向量實現(xiàn)插值法向量.該方法同時具有形狀調(diào)整和插值法向量兩個特性,豐富了細分曲面造型的形狀控制方法.本文方法只研究了實驗圖形的效果,還可以繼續(xù)研究細分的精度和效率.