基于頂點法向量約束的Catmull-Clark細分插值方法①

林傳鑾

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

引言

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

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

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

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

1 頂點法向量插值條件

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

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

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

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

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

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

1) 拓撲規則與傳統的Catmull-Clark細分方法保持不變;

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

3 插值法向量分析

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

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

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

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

4 實驗結果與分析

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

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

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

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

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

5 結語

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