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

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

1 引言

由多邊形面片組建的幾何立體圖形雖然具有規(guī)則的網(wǎng)格結(jié)構(gòu)，可以用來表示復(fù)雜的三維實(shí)體，但所構(gòu)成的表面不夠光滑，不能滿足實(shí)際應(yīng)用的要求，所以需要對(duì)多邊形網(wǎng)格進(jìn)行光滑處理。網(wǎng)格光順可以有效解決三維幾何實(shí)體表面的光滑問題。當(dāng)前主要網(wǎng)格光順?biāo)惴ㄓ兴念?，分別是拉普拉斯平滑法、曲率均勻法、能量法、曲面細(xì)分技術(shù)［1］。其中，曲面細(xì)分技術(shù)是通過用低分辨率的控制網(wǎng)格和定義在控制網(wǎng)格上的細(xì)分規(guī)則來表示光滑曲面。細(xì)分曲面造型技術(shù)規(guī)則簡(jiǎn)單，拓?fù)溥m應(yīng)能力強(qiáng)，因而在曲面設(shè)計(jì)加工中得到了廣泛應(yīng)用。三角形網(wǎng)格細(xì)分曲面方法具有穩(wěn)定性好、不受網(wǎng)格拓?fù)湎拗频膬?yōu)點(diǎn)，可以對(duì)任意拓?fù)渚W(wǎng)格進(jìn)行曲面造型，其遞歸結(jié)構(gòu)與小波和多分辨率分析有著密切聯(lián)系［2］。正是由于三角形網(wǎng)格細(xì)分曲面的特點(diǎn)，用三角網(wǎng)格來表示模型各個(gè)曲面，不僅可以獲得較好的視覺效果，并能通過控制模型中三角面片的數(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平臺(tái)將其顯示。同時(shí)，實(shí)驗(yàn)通過選擇相同的三維網(wǎng)格模型來測(cè)試并對(duì)比這4種細(xì)分算法在處理網(wǎng)格模型時(shí)，細(xì)分曲面與原始網(wǎng)格曲面的逼近程度，細(xì)分曲面的質(zhì)量，細(xì)分算法運(yùn)行復(fù)雜度等性能指標(biāo)。從細(xì)分算法原理上比較并分析了這四種細(xì)分算法，最后總結(jié)出這四種細(xì)分算法的特點(diǎn)和適用范圍。

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ī)則簡(jiǎn)單，光滑性好特點(diǎn)，但是細(xì)分曲面會(huì)產(chǎn)生較大的收縮。Loop細(xì)分算法是一種實(shí)現(xiàn)簡(jiǎn)單的逼近細(xì)分算法，對(duì)原有特征尤其尖銳特征的保持能力較弱。Loop細(xì)分在正則點(diǎn)處可以達(dá)到C2連續(xù)，在奇異點(diǎn)處達(dá)到C1連續(xù)。Loop細(xì)分曲面方案采用三角形分裂模式產(chǎn)生新的網(wǎng)格拓?fù)浣Y(jié)構(gòu)。設(shè)給定一個(gè)初始網(wǎng)格，經(jīng)過i次Loop細(xì)分之后，其網(wǎng)格頂點(diǎn)記為vi的鄰域有n個(gè)共邊頂點(diǎn)=（j=1，2，…，n），第i+1次細(xì)分后，新網(wǎng)格頂點(diǎn)記為vi+1，它的鄰域有n個(gè)共邊頂點(diǎn)（j=1，2，…，n），具體幾何點(diǎn)的產(chǎn)生規(guī)則如下。

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

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

3）邊界奇點(diǎn)，如圖1（c）所示：

4）邊界偶點(diǎn)，如圖1（d）所示：

2.2 Butterfly細(xì)分算法

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

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

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

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

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

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

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

2.3 Sqrt3細(xì)分算法

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

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

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

圖3 Sqrt3細(xì)分過程

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

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

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

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

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

3.1 實(shí)驗(yàn)過程

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

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

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

3.2 實(shí)驗(yàn)分析及改進(jìn)方法

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

4 結(jié)語

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