幾何立體圖形光順算法的研究與比較?

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

（武漢紡織大學數學與計算機學院 武漢 430073）

1 引言

由多邊形面片組建的幾何立體圖形雖然具有規則的網格結構，可以用來表示復雜的三維實體，但所構成的表面不夠光滑，不能滿足實際應用的要求，所以需要對多邊形網格進行光滑處理。網格光順可以有效解決三維幾何實體表面的光滑問題。當前主要網格光順算法有四類，分別是拉普拉斯平滑法、曲率均勻法、能量法、曲面細分技術［1］。其中，曲面細分技術是通過用低分辨率的控制網格和定義在控制網格上的細分規則來表示光滑曲面。細分曲面造型技術規則簡單，拓撲適應能力強，因而在曲面設計加工中得到了廣泛應用。三角形網格細分曲面方法具有穩定性好、不受網格拓撲限制的優點，可以對任意拓撲網格進行曲面造型，其遞歸結構與小波和多分辨率分析有著密切聯系［2］。正是由于三角形網格細分曲面的特點，用三角網格來表示模型各個曲面，不僅可以獲得較好的視覺效果，并能通過控制模型中三角面片的數量來得到不同需求的三維網格模型［3］。

本文著重介紹了Loop細分法、Butterfly細分法、Sqrt3細分法、PN-triangle細分法4種曲面細分算法的原理，并用程序實現了這4種曲面細分算法。程序通過讀取三維網格數據，并借助openGL平臺將其顯示。同時，實驗通過選擇相同的三維網格模型來測試并對比這4種細分算法在處理網格模型時，細分曲面與原始網格曲面的逼近程度，細分曲面的質量，細分算法運行復雜度等性能指標。從細分算法原理上比較并分析了這四種細分算法，最后總結出這四種細分算法的特點和適用范圍。

2 典型三角網格細分算法

2.1 Loop細分算法

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

1）內部奇點產生規則，如圖1（a）所示，設有兩個三角形（V0，V1，V2）和（V0，V1，V3），共享邊為V0V1，則V0V1新頂點的位置為

2）內部偶點產生規則，如圖1（b）所示，設V的邊臨點 V0，V1，…，Vn-1，n=|VE|，相應頂點的位置為

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

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

2.2 Butterfly細分算法

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

圖1 Loop細分模式幾何規則

圖2 改進Butterfly細分模式幾何規則

規則1：當網格邊的兩個端點都是規則點，即階為6的端點時，細分面具如圖2（a）所示，各權值設置為

規則2：當網格的一個端點是階為6的規則點，而另一端點為非規則點（階n不為6），則細分面具如圖2（b）所示，細分規則由非規則頂點以及它的鄰接點決定，其中各鄰接點的權重系數如下：

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

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

2.3 Sqrt3細分算法

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

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

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

圖3 Sqrt3細分過程

2.4 PN-triangle細分算法

近年來，隨著GPU運算能力的不斷增強，人們在GPU上實現曲面細分技術方向上進行了大量的研究工作。Vlachos、Jorg Peters、Chas Boyd等提出的Curved Point Normal三角形（PN-tringle）細分算法［12～14］，根據頂點位置和法向信息對三角形面片內部進行獨立的雙三次Bezier曲面插值，在不考慮幾何拓撲關系情況下，對每個patch進行均勻細化，實現滿足視覺需求的幾何模型平滑繪制，它適合硬件加速處理，并在實時精細渲染中得到了廣泛應用。PN-triangle三角形細分算法能夠將原始粗糙三角形網格生成光滑連續表面，針對參數三角形區域，其Bezier細化方程定義為

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

圖4 PN-triangle細化過程

3 細分算法比較分析

3.1 實驗過程

實驗選取維納斯頭部三角網格模型來進行測試，初始維納斯三角網格模型具有498個頂點，992個三角形面。該實驗目的是用Loop細分法，改進Butterfly細分法，Sqrt3細分法及PN-triangle細分法分別對相同模型進行細分測試，比較不同細分算法細分曲面與原始網格的逼近程度，細分曲面質量以及細分算法復雜度等方面的性能指標。實驗通過OpenGL平臺顯示各細分算法的細分效果，如圖5所示，為初始網格模型經過細分算法處理得到第一次細分和第二次細分后的曲面細分效果圖。同時，實驗統計了四種不同細分算法完成每次細分所使消耗的時間，如表1所示。

圖5 維納斯模型曲面細分效果圖

表1 曲面細分算法運行效率分析表

3.2 實驗分析及改進方法

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

4 結語

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