基于頂點(diǎn)法向量約束的Catmull-Clark細(xì)分插值方法①

林傳鑾

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

引言

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

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

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

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

1 頂點(diǎn)法向量插值條件

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

整個(gè)細(xì)分過程可以表示為對(duì)初始控制頂點(diǎn)重復(fù)左乘細(xì)分矩陣,因此,存在一當(dāng)i趨于無窮大時(shí)，為極限曲面.

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

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

2 兩步Catmull-Clark細(xì)分插值方法

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

1) 拓?fù)湟?guī)則與傳統(tǒng)的Catmull-Clark細(xì)分方法保持不變;

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

3 插值法向量分析

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

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

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

得到新邊點(diǎn)和新面點(diǎn)的差向量為:

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

5 結(jié)語

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