蘇 剛 胡新榮 李佳黎 尹 汪 趙紅杏

（武漢紡織大學(xué)數(shù)學(xué)與計算機(jī)學(xué)院 武漢 430073）

1 引言

由多邊形面片組建的幾何立體圖形雖然具有規(guī)則的網(wǎng)格結(jié)構(gòu)，可以用來表示復(fù)雜的三維實體，但所構(gòu)成的表面不夠光滑，不能滿足實際應(yīng)用的要求，所以需要對多邊形網(wǎng)格進(jìn)行光滑處理。網(wǎng)格光順可以有效解決三維幾何實體表面的光滑問題。當(dāng)前主要網(wǎng)格光順?biāo)惴ㄓ兴念?，分別是拉普拉斯平滑法、曲率均勻法、能量法、曲面細(xì)分技術(shù)［1］。其中，曲面細(xì)分技術(shù)是通過用低分辨率的控制網(wǎng)格和定義在控制網(wǎng)格上的細(xì)分規(guī)則來表示光滑曲面。細(xì)分曲面造型技術(shù)規(guī)則簡單，拓?fù)溥m應(yīng)能力強(qiáng)，因而在曲面設(shè)計加工中得到了廣泛應(yīng)用。三角形網(wǎng)格細(xì)分曲面方法具有穩(wěn)定性好、不受網(wǎng)格拓?fù)湎拗频膬?yōu)點，可以對任意拓?fù)渚W(wǎng)格進(jìn)行曲面造型，其遞歸結(jié)構(gòu)與小波和多分辨率分析有著密切聯(lián)系［2］。正是由于三角形網(wǎng)格細(xì)分曲面的特點，用三角網(wǎng)格來表示模型各個曲面，不僅可以獲得較好的視覺效果，并能通過控制模型中三角面片的數(shù)量來得到不同需求的三維網(wǎng)格模型［3］。

本文著重介紹了Loop細(xì)分法、Butterfly細(xì)分法、Sqrt3細(xì)分法、PN-triangle細(xì)分法4種曲面細(xì)分算法的原理，并用程序?qū)崿F(xiàn)了這4種曲面細(xì)分算法。程序通過讀取三維網(wǎng)格數(shù)據(jù)，并借助openGL平臺將其顯示。同時，實驗通過選擇相同的三維網(wǎng)格模型來測試并對比這4種細(xì)分算法在處理網(wǎng)格模型時，細(xì)分曲面與原始網(wǎng)格曲面的逼近程度，細(xì)分曲面的質(zhì)量，細(xì)分算法運行復(fù)雜度等性能指標(biāo)。從細(xì)分算法原理上比較并分析了這四種細(xì)分算法，最后總結(jié)出這四種細(xì)分算法的特點和適用范圍。

2 典型三角網(wǎng)格細(xì)分算法

2.1 Loop細(xì)分算法

Loop細(xì)分曲面方案是Utah大學(xué)的Loop在1987年的碩士論文種提出的一種基于三角形控制網(wǎng)格的細(xì)分曲面算法，是目前應(yīng)用最為廣泛的算法之一［4-5］。Loop細(xì)分具有細(xì)分規(guī)則簡單，光滑性好特點，但是細(xì)分曲面會產(chǎn)生較大的收縮。Loop細(xì)分算法是一種實現(xiàn)簡單的逼近細(xì)分算法，對原有特征尤其尖銳特征的保持能力較弱。Loop細(xì)分在正則點處可以達(dá)到C2連續(xù)，在奇異點處達(dá)到C1連續(xù)。Loop細(xì)分曲面方案采用三角形分裂模式產(chǎn)生新的網(wǎng)格拓?fù)浣Y(jié)構(gòu)。設(shè)給定一個初始網(wǎng)格，經(jīng)過i次Loop細(xì)分之后，其網(wǎng)格頂點記為vi的鄰域有n個共邊頂點=（j=1，2，…，n），第i+1次細(xì)分后，新網(wǎng)格頂點記為vi+1，它的鄰域有n個共邊頂點（j=1，2，…，n），具體幾何點的產(chǎn)生規(guī)則如下。

1）內(nèi)部奇點產(chǎn)生規(guī)則，如圖1（a）所示，設(shè)有兩個三角形（V0，V1，V2）和（V0，V1，V3），共享邊為V0V1，則V0V1新頂點的位置為

2）內(nèi)部偶點產(chǎn)生規(guī)則，如圖1（b）所示，設(shè)V的邊臨點 V0，V1，…，Vn-1，n=|VE|，相應(yīng)頂點的位置為

3）邊界奇點，如圖1（c）所示：

4）邊界偶點，如圖1（d）所示：

2.2 Butterfly細(xì)分算法

Butterfly細(xì)分曲面方案是由Dyn，Gregory和Levin于1990年提出的。Butterfly細(xì)分法是一種定義在三角網(wǎng)格上的細(xì)分曲面方案［6～7］，屬于插值的面分裂方法，其細(xì)分極限曲面在正則點處達(dá)到C1連續(xù)，在奇異點處只能達(dá)到C0連續(xù)。后來Zorin對Butterfly細(xì)分曲面方案進(jìn)行了研究［8～9］，并對其算法進(jìn)行了改進(jìn)，使得可以在任意三角網(wǎng)格上生成C1連續(xù)的曲面。改進(jìn)Butterfly細(xì)分模式幾何規(guī)則如圖2所示，圖a是具有規(guī)則鄰接點的內(nèi)部奇點，圖b是具有非規(guī)則鄰接點的奇點，圖c為邊界奇點。由于該算法屬于插值類型，上一細(xì)分級別的所有控制點都位于曲面上，因此偶點不需要重新計算，只要計算奇點即可。

圖1 Loop細(xì)分模式幾何規(guī)則

圖2 改進(jìn)Butterfly細(xì)分模式幾何規(guī)則

規(guī)則1：當(dāng)網(wǎng)格邊的兩個端點都是規(guī)則點，即階為6的端點時，細(xì)分面具如圖2（a）所示，各權(quán)值設(shè)置為

規(guī)則2：當(dāng)網(wǎng)格的一個端點是階為6的規(guī)則點，而另一端點為非規(guī)則點（階n不為6），則細(xì)分面具如圖2（b）所示，細(xì)分規(guī)則由非規(guī)則頂點以及它的鄰接點決定，其中各鄰接點的權(quán)重系數(shù)如下：

規(guī)則3：細(xì)分邊2個端點都為奇異點時，則先對每一個奇異點利用規(guī)則2得到2個新頂點，然后取平均值作為當(dāng)前細(xì)分邊生成的頂點。

規(guī)則4：細(xì)分邊為邊界邊時，如圖2（c）所示，則插入點的計算公式為

2.3 Sqrt3細(xì)分算法

Sqrt3細(xì)分方案是由Kobbelt在2000年提出的一種逼近型、面分裂的三角網(wǎng)格細(xì)分方案［10～11］，該細(xì)分曲面方案能有效緩解面片增長速度。Sqrt3采用一種全新的頂點插入和分裂方式，每次細(xì)分時，在每個三角形面插入一個新頂點，新頂點與原三角形的三個頂點相連，然后去掉原三角形的內(nèi)部邊，這樣使得三角形面的個數(shù)增加3倍，細(xì)分過程如圖3所示。Sqrt3細(xì)分法使得三角形增加緩慢，不會出現(xiàn)尖銳三角形，并且連續(xù)性自動保留，適用于局部性適應(yīng)性細(xì)分。

設(shè)新頂點（V-vertex）：頂點v相鄰頂點為v0，v1，v2，…，vn-1，則（V-vertex）頂點Vv由下面的公式計算：

新面點（F-vertex）：設(shè)三角形的三個頂點為v0，v1，v2，新插入的（F-vertex）VF由下面的公式計算：

圖3 Sqrt3細(xì)分過程

2.4 PN-triangle細(xì)分算法

近年來，隨著GPU運算能力的不斷增強(qiáng)，人們在GPU上實現(xiàn)曲面細(xì)分技術(shù)方向上進(jìn)行了大量的研究工作。Vlachos、Jorg Peters、Chas Boyd等提出的Curved Point Normal三角形（PN-tringle）細(xì)分算法［12～14］，根據(jù)頂點位置和法向信息對三角形面片內(nèi)部進(jìn)行獨立的雙三次Bezier曲面插值，在不考慮幾何拓?fù)潢P(guān)系情況下，對每個patch進(jìn)行均勻細(xì)化，實現(xiàn)滿足視覺需求的幾何模型平滑繪制，它適合硬件加速處理，并在實時精細(xì)渲染中得到了廣泛應(yīng)用。PN-triangle三角形細(xì)分算法能夠?qū)⒃即植谌切尉W(wǎng)格生成光滑連續(xù)表面，針對參數(shù)三角形區(qū)域，其Bezier細(xì)化方程定義為

其中（u，v，w）是在該三角形中定點的重心坐標(biāo)形式，且u+v+w=1。如圖4所示，輸入單一基三角形，獲取法線控制點nijk和頂點控制點bijk，根據(jù)內(nèi)部和邊界細(xì)化因子執(zhí)行細(xì)化過程，得到插值后的光滑網(wǎng)格頂點布局。PN三角形的生成只依賴于基三角形的頂點位置和法向量，適合應(yīng)用在基于GPU的三角形細(xì)化渲染管線中。

圖4 PN-triangle細(xì)化過程

3 細(xì)分算法比較分析

3.1 實驗過程

實驗選取維納斯頭部三角網(wǎng)格模型來進(jìn)行測試，初始維納斯三角網(wǎng)格模型具有498個頂點，992個三角形面。該實驗?zāi)康氖怯肔oop細(xì)分法，改進(jìn)Butterfly細(xì)分法，Sqrt3細(xì)分法及PN-triangle細(xì)分法分別對相同模型進(jìn)行細(xì)分測試，比較不同細(xì)分算法細(xì)分曲面與原始網(wǎng)格的逼近程度，細(xì)分曲面質(zhì)量以及細(xì)分算法復(fù)雜度等方面的性能指標(biāo)。實驗通過OpenGL平臺顯示各細(xì)分算法的細(xì)分效果，如圖5所示，為初始網(wǎng)格模型經(jīng)過細(xì)分算法處理得到第一次細(xì)分和第二次細(xì)分后的曲面細(xì)分效果圖。同時，實驗統(tǒng)計了四種不同細(xì)分算法完成每次細(xì)分所使消耗的時間，如表1所示。

圖5 維納斯模型曲面細(xì)分效果圖

表1 曲面細(xì)分算法運行效率分析表

3.2 實驗分析及改進(jìn)方法

通過以上實驗，經(jīng)過對比可以分析出，各細(xì)分算法在曲面細(xì)分方面各有所長。第一，在細(xì)分曲面和控制網(wǎng)格的逼近程度方面，改進(jìn)Butterfly算法和PN-triangle算法具有突出表現(xiàn)，而改進(jìn)Butterfly算法作為一種插值型細(xì)分算法，由此可以說明插值型細(xì)分算法比逼近型細(xì)分算法生成的曲面更加接近控制網(wǎng)格，并且連續(xù)性越低，曲面越靠近控制網(wǎng)格，這符合插值型細(xì)分算法的特點。第二，在細(xì)分曲面質(zhì)量方面，Loop細(xì)分曲面方案生成曲面質(zhì)量較高，但細(xì)分曲面會產(chǎn)生較大的收縮性，產(chǎn)生的曲面會出現(xiàn)不對稱現(xiàn)象。第三，在算法實現(xiàn)復(fù)雜度方面，通過表2可以得出，經(jīng)過第一次細(xì)分及第二次細(xì)分時，各曲面細(xì)分算法運行效率相當(dāng)，在第三次細(xì)分時，Sqrt3細(xì)分算法運行效率較高，其中Loop細(xì)分和改進(jìn)Butterfly細(xì)分每次細(xì)分三角形個數(shù)將增加4倍，由此說明Sqrt3細(xì)分算法使三角形面片增長速度僅為每次3倍，不僅大幅度減少了新生三角形的數(shù)量，同時提高了運行效率和分辨率。其中PN-triangle是基于GPU管線和圖形庫（DirectX 11）技術(shù)前提下實現(xiàn)的［15］，細(xì)分產(chǎn)生的三角形由GPU進(jìn)行運算，其細(xì)分的結(jié)果在渲染管道內(nèi)傳輸，幾乎不需要額外顯存空間，由此，本實驗忽略計算PN-triangle細(xì)分算法的運算時間?？紤]到GPU運算的高并行和快速性，PN-triangle曲面細(xì)分相對其它傳統(tǒng)細(xì)分算法更有空間和時間上的優(yōu)勢。PN-triangle不僅對現(xiàn)有的模型沒有更多的要求，而且效率很高，可以應(yīng)用于實時性要求較高的程序中。

4 結(jié)語

本文著重介紹了4種典型三角網(wǎng)格細(xì)分算法，并通過程序?qū)崿F(xiàn)了這四種算法，最后通過實驗結(jié)果對比各曲面細(xì)分算法在細(xì)分方面的不同優(yōu)勢。除本文著重闡述的4種三角網(wǎng)格細(xì)分算法外，還有其它三角網(wǎng)格細(xì)分算法也具有重要的研究意義，如三重細(xì)分、混合細(xì)分、4-8細(xì)分等曲面細(xì)分算法，在此不一一詳述。曲面細(xì)分在涉及理論和實際的應(yīng)用領(lǐng)域有著廣泛的應(yīng)用。隨著計算機(jī)圖形學(xué)及相關(guān)領(lǐng)域?qū)W者和研究人員對曲面細(xì)分技術(shù)研究的不斷深入，細(xì)分曲面理論和技術(shù)將不斷得到完善。同時，細(xì)分曲面融入各種曲面造型系統(tǒng)與其它類型的曲面相融合是當(dāng)前曲面造型的發(fā)展趨勢。目前，雖然可以實現(xiàn)創(chuàng)建曲率連續(xù)的曲面，但創(chuàng)建更高階連續(xù)曲面的算法還待進(jìn)一步研究。除此之外，對細(xì)分曲面控制，編輯還比較困難，如何處理網(wǎng)格細(xì)分速度和曲面質(zhì)量的關(guān)系還有待深入研究［16～18］。隨著GPU計算能力的不斷增強(qiáng)以及GPU并行計算技術(shù)的日益成熟，如何利用現(xiàn)代GPU有效的生成和處理細(xì)分曲面成為近年來非常熱門的研究方向之一。