基于二面角逆插值Loop細分的漸進傳輸方法

史 卓，孔 謙，玉 珂，藍如師，羅笑南

?

基于二面角逆插值Loop細分的漸進傳輸方法

史 卓，孔 謙，玉 珂，藍如師，羅笑南

(桂林電子科技大學藝術與設計學院，廣西 桂林 541004)

隨著虛擬現(xiàn)實、增強現(xiàn)實等領域快速發(fā)展，漸進傳輸獲得了良好的用戶體驗。為了三角網(wǎng)格在移動終端的快速傳輸和顯示，提出了一種基于二面角逆插值Loop細分(DRILS)的漸進傳輸算法。主要通過對原始三角網(wǎng)格進行基于二面角插值Loop細分(DILS)和插值Loop細分(ILS)進行預處理，在局部特征精確保持的同時獲得具備細分連通性的精網(wǎng)格。在漸進傳輸?shù)倪^程中通過對該精網(wǎng)格迭代操作3個步驟，即奇偶頂點劃分、預測偏移量、更新三角網(wǎng)格。由于采用DILS與ILS結合獲取精網(wǎng)格，在漸進傳輸?shù)倪^程中保持了精確的局部特征，同時也加快了漸進傳輸?shù)乃俣?。實驗對比表明，該算法精確、高效，適應于移動終端設備的顯示傳輸及存儲。

漸進傳輸；逆細分；插值Loop細分；二面角

漸進傳輸在視頻動畫、游戲、三維建模等領域具有廣泛地應用價值。漸進網(wǎng)格在漸進傳輸中是具體內(nèi)容表現(xiàn)形式，HOPPE[1]首次提出的采用基于頂點分裂生成漸進網(wǎng)格，為三維網(wǎng)格在多分辨率漸進傳輸過程中受限于存儲空間及傳輸帶寬的影響提供了解決方案。通常情況下，科研人員采用基于QEM (quadric error metrics)[2]算法在邊折疊、點分裂等改進方法進行三角網(wǎng)格簡化和生成多層次的三角網(wǎng)格模型。隨著三角網(wǎng)格細分方法的深入研究，逆細分[3]的提出使得細分在漸進網(wǎng)格生成得到了發(fā)展。文獻[4]提出了基于逆蝶形細分算法對三角網(wǎng)格進行漸進傳輸；文獻[5]在此基礎上提出修改細分模板為Loop細分[6]，同時不再對上一層網(wǎng)格留下來的頂點進行補償計算的逆Loop細分算法，雖然逆Loop細分算法相對于逆蝶形細分算法計算量小，但由于Loop細分是逼近型細分，無法完成保持局部網(wǎng)格特征，網(wǎng)格將會產(chǎn)生凹陷收縮等問題。文獻[7]根據(jù)插值Loop細分算法[8]并采用其算法對該類問題進行了解決，使得漸進傳輸過程中生成的漸進網(wǎng)格能夠更好地重建。但在獲取精網(wǎng)格的過程中，此類方法由于采用相應的細分算法對其進行細分連通性處理，在數(shù)次細分之后，三角網(wǎng)格細分消耗代價將呈指數(shù)級上升，無法完成局部特征要求十分精細的網(wǎng)格處理。文獻[9]提出的一種基于DM (delaunay mesh)的簡化算法，該算法雖然簡化速度很快，但無法完成漸進傳輸功能。

本文在獲取漸進傳輸精網(wǎng)格的過程中，提出基于二面角逆插值Loop細分算法。其與插值Loop細分算法結合可對初始網(wǎng)格進行處理，該類算法采取二面角插值Loop細分算法通過對三角面片兩兩之間夾角閾值做判斷，并按照一定的細分規(guī)則進行局部細分。由此可以使局部特征明顯的部分更加精細，而平滑部分則不再進行過多的增加頂點和邊的信息，再通過插值Loop細分算法對其做細分連通性補償，此方法更加高效、精確。在獲取漸進傳輸精網(wǎng)格之后，采用奇偶頂點劃分、預測偏移量、更新三角網(wǎng)格循環(huán)操作，直到三角網(wǎng)格無法再分裂為止。最終生成一個粗網(wǎng)格和一系列偏移量組成的漸進網(wǎng)格。本文算法在奇偶頂點劃分過程中將原有插值Loop細分算法過程中分層生成邊點作為冗余信息進行刪除，通過更多的控制頂點，實現(xiàn)邊緣的插值點對中心頂點的補償。此算法在保持網(wǎng)格模型整體特性的同時，增強局部特征信息，由于比傳統(tǒng)逆細分算法計算網(wǎng)格頂點數(shù)少，在計算量上也有大幅的降低，在實際應用過程中更加有效。

1 漸進網(wǎng)格編碼規(guī)則

1.1 插值Loop細分和逆細分

曲面細分主要分為逼近型細分和插值型細分。在處理三角網(wǎng)格細分算法上，逼近型細分典型模式為Loop細分，插值型細分典型模式為Butterfly細分。該類細分算法均為漸進生成三角網(wǎng)格。如Loop細分規(guī)則，在每條邊上加一個新的頂點作為邊點，原來的頂點根據(jù)該邊點權重重新調(diào)整頂點位置。由于傳統(tǒng)Loop細分是逼近型細分，在奇異點處會產(chǎn)生收縮問題。為解決該類問題，結合插值型細分Butterfly模板對奇異點處理方法，首先通過擴大Loop細分的模板(圖1)，實現(xiàn)邊緣插值點對中心點的補償。

圖1 插值Loop細分模板

再根據(jù)改進的Butterfly細分對奇異點處理方法，修改傳統(tǒng)Loop細分處理奇異點規(guī)則，解決收縮凹陷問題。

將新生成的邊點定義為奇點Odd，原始頂點重新調(diào)整后可定義為偶點Even。其中由于奇異點是特征保持頂點，也定義為偶點。

當偶點Even為正則頂點時(度為6的頂點)，插值Loop細分的奇點Odd的計算模板為

當偶點Even為奇異點時，非邊界頂點的模板為

其中，為頂點的度，與改進的蝶形細分的奇異點處理方法類似。

通過仔細分析插值Loop細分頂點生成規(guī)則發(fā)現(xiàn)偶點。偶點集中的頂點均為控制頂點，其在插值Loop細分的過程中保持不變，此特征可在逆細分過程中作為特征頂點保存下來。而奇點是細分過程中生成的頂點，根據(jù)奇點生成計算公式可看出并未對偶點位置產(chǎn)生影響，可以作為冗余頂點在逆插值Loop細分過程中刪除。

1.2 二面角細分規(guī)則

傳統(tǒng)的Loop細分算法是對三角網(wǎng)格進行1-4分裂，該算法將導致三角面片及頂點個數(shù)呈幾何式增長，經(jīng)過幾次細分后再對三角網(wǎng)格進行細分平滑處理將會產(chǎn)生時間和內(nèi)存方面更高的代價，不利于多分辨率漸進網(wǎng)格移動傳輸。自適應細分有很多方法，如基于GPU的特征自適應細分算法[10-11]，其在GPU上運行，運行環(huán)境受限；基于頂點曲率特征[12]算法，其實現(xiàn)比較復雜；判定面片向量夾角[13]提出類似算法，但其僅針對于傳統(tǒng)的Loop細分，對插值Loop細分并未進行改進，依然存在收縮問題。為解決該類問題，本文提出基于二面角細分規(guī)則，可高效獲得在保持局部特征的同時又具有平滑處理效果的三角網(wǎng)格。

通常一個三維模型具有明顯局部特征，即曲率較高的頂點，在漸進傳輸?shù)倪^程中，該類特征是需要保留的。而平滑部分則在初始網(wǎng)格或者細分數(shù)次后達到區(qū)域平滑后三角片面無需再次進行1-4分裂，減少計算量及運算時間。本文提出的基于二面角夾角判斷準則來劃分細分規(guī)則算法步驟如下：

步驟1.創(chuàng)建2個空集Fsmooth和Fsteep，其中集合Fsmooth存儲三角網(wǎng)格中的平滑面，集合Fsteep存儲陡峭面。

步驟2.計算所有三角面片的法向量(= 1,···,為三角網(wǎng)格中面片個數(shù))。

步驟3.計算所有相鄰兩面的向量夾角，其中每個面片均有3個共邊面片?？蓸擞浧鋬蓛煞ㄏ蛄繆A角分別為，，，同時設定一個夾角閾值為。

步驟4.分別判斷一個三角面片相關的3個向量夾角，，與閾值的大小關系，如果小于該閾值，則將相應面片存入集合Fsmooth中，否則存入集合Fsteep。面片的細分規(guī)則根據(jù)閾值的大小來確定。

步驟5.迭代操作步驟4，直到所有的三角面片均判斷結束。

步驟6.對集合Fsmooth集中的面片不進行細分處理，對集合Fsteep集進行細分處理。

1.3 漸進網(wǎng)格生成原理

在三角網(wǎng)格中，一個頂點的度表示為與該頂點相連接邊的個數(shù)。正則點表示度為6的頂點，非正則點或奇異點表示度不為6的頂點。正則網(wǎng)格定義為所有的頂點都為正則點，該類三角網(wǎng)格很少有現(xiàn)成的；大部分頂點為正則點，存在少數(shù)非正則點的三角網(wǎng)格定義為半正則網(wǎng)格。而對于非正則點過多造成無法實現(xiàn)逆插值Loop細分的模型，其不具備細分連通性，可通過重新三角化或再次細分使其達到符合要求的網(wǎng)格。

根據(jù)逆細分規(guī)則，要求生成的三角網(wǎng)格為正則網(wǎng)格或半正則網(wǎng)格，即具備細分連通性，且必須滿足

傳統(tǒng)的細分準則生成的頂點大部分為正則點，而根據(jù)二面角Loop細分頂點生成準則，可知在下一層頂點生成的過程中可能會產(chǎn)生一定量的非正則點，如圖2所示。

圖2 二面角規(guī)則產(chǎn)生非正則點

在解決上述問題時，考慮到二面角規(guī)則細分在保持局部特征的同時快速完成細分，在漸進網(wǎng)格傳輸過程中具有一定的價值。因此二面角規(guī)則結合插值Loop細分獲取精網(wǎng)格具有一定的必要性。

將一個粗網(wǎng)格通過二面角規(guī)則細分若干次之后，再進行插值Loop細分，獲得的精網(wǎng)格既保持了局部特征的尖銳性，同時在效率方面得到提升，也滿足了其精網(wǎng)格通過逆細分算法漸進傳輸。

2 漸進網(wǎng)格傳輸算法

根據(jù)漸進網(wǎng)格生成原理，生成的精網(wǎng)格可對其進行漸進傳輸。其漸進傳輸算法步驟如下：

步驟1. 奇偶集頂點迭代分裂。

圖3 奇偶頂點分布情況

初始化偶點集E和奇點集O(0≤≤)。其中偶點集E是正則點或奇異點，假設將頂點劃分至偶點集E；由于奇點集O是新生成的頂點，且是冗余頂點。根據(jù)細分準則，偶點對應的奇點為其鄰接的所有頂點，其劃分在奇點集中，任取一點為，設點關于點對稱的頂點，頂點劃分至偶點集E，依次迭代劃分，直到所有的頂點全部劃分到奇點集O或偶點集E中。

具體劃分算法如下：

Bool setEven (){

將歸并到偶點集E中；

遍歷所有與相鄰的頂點{

返回false；

否則將并入奇點集O；

找出與關于對稱的頂點；

調(diào)用setEven ()；

}

返回true；

}

步驟2. 頂點預測，計算頂點偏移量。

步驟3. 更新三角網(wǎng)格。

3 實驗結果與分析

本算法用C++實現(xiàn)，采用的環(huán)境包括：CPU：E5 3.5 GHz；內(nèi)存：16 G。其中獲取二面角Loop細分模型是通用雙系統(tǒng)Linux環(huán)境下編程完成，漸進傳輸三角網(wǎng)格生成程序在Windows下利用開發(fā)工具Visual Studio 2013及CGAL庫完成。

首先通過二面角插值Loop細分算法獲取初步精網(wǎng)格模型，如圖4所示，設二面角夾角閾值為20°，局部特征通過細分更加明顯，而基本平滑部分則不再增加額外的頂點及邊的信息。其算法比插值Loop細分算法在時間上有明顯優(yōu)勢，同時也為生成精細漸進網(wǎng)格做好了前期處理，減小了巨大的運算開銷。

圖4的前兩行為Dragon的三角網(wǎng)格細分處理示意圖。圖4(a)為對初始圖進行5次插值Loop細分層次圖，(b)為對初始圖進行5次二面角插值Loop細分層次圖；圖4(c)和(d)分別對應圖4(a)和(b)的模型渲染圖。由渲染圖可以看出，在第5層之后，兩者的渲染結果基本上相同。

圖4 Dragon(1 000面片)三角網(wǎng)格及渲染分層圖

由表1可知，插值Loop細分算法新增加的網(wǎng)格數(shù)呈指數(shù)式增長，在精細網(wǎng)格的獲取中代價巨大。而隨著網(wǎng)格數(shù)的增多，二面角插值Loop細分算法獲得網(wǎng)格的速度更快。由此可以采用二面角插值Loop細分算法獲得的網(wǎng)格為漸進傳輸精細網(wǎng)格做預處理。

表1 Dragon不同細分算法運行時間對比

在獲取漸進傳輸最精細網(wǎng)格的過程中，采用二面角插值Loop細分規(guī)則后再進行插值Loop細分獲取的網(wǎng)格與僅采用插值Loop細分規(guī)則獲取的網(wǎng)格，通過使用網(wǎng)格誤差評估軟件Metro (v4.07)對誤差進行測量并對運行時間進行對比，如圖5所示。

圖5 獲取漸進傳輸精密網(wǎng)格

表2中，E0為Ellipsoid初始網(wǎng)格，E1為圖5 (b)生成的精密網(wǎng)格，E2為圖5(c)生成的精密網(wǎng)格。具體時間與距離誤差分析見表2。

表2 Ellipsoid網(wǎng)格誤差分析及時間對比

在Hausdorff距離誤差極小的情況下，表2采用二面角插值Loop細分再進行插值Loop細分，大幅度提高了計算速度，同時消耗較短時間生成模型，有助于后續(xù)漸進傳輸。而僅采用插值Loop細分算法不僅消耗大量時間，在細分后期也將會帶來巨大的運算開銷，無法完成快速漸進傳輸功能。

在漸進傳輸?shù)倪^程中，通過將DM、逆蝶形細分(reverse butterfly subdivision，RBS)與二面角逆插值Loop細分(dihedral reverse interpolation Loop subdivision，DRILS)算法在運行時間及漸進傳輸可行性上進行對比，如圖6所示，DM算法在經(jīng)過數(shù)次傳輸之后，三角網(wǎng)格僅保存局部網(wǎng)格形式，且無法表達原有模型形狀，并未實現(xiàn)漸進網(wǎng)格的重建工作，也無法完成漸進傳輸及顯示。

圖6 多分辨率漸進網(wǎng)格生成顯示

根據(jù)圖6多分辨率漸進網(wǎng)格生成顯示和表3的Hausdorff誤差分析，逆蝶形細分算法與二面角逆插值Loop細分均達到了漸進傳輸功能。

表3 Bear多分辨率漸進傳輸時間對比及誤差分析

從表3的傳輸時間上看，RBS算法在漸進傳輸?shù)倪^程中耗時長，用戶體驗較差。而DM算法雖然在傳輸時間上有一定優(yōu)勢，但根據(jù)圖6 (g)運行2次后獲取的三角網(wǎng)格已經(jīng)無法準確地顯示原有網(wǎng)格所具備的拓撲結構，無法給用戶帶來多分辨率體驗。

4 結束語

本文提出一種采用二面角插值Loop細分規(guī)則與逆細分算法結合的漸進網(wǎng)格傳輸算法。描述了逆細分準則以及通過頂點分裂、預測偏移量和更新網(wǎng)格3個步驟獲取漸進傳輸網(wǎng)格，在漸進傳輸過程中具有保持局部特征及高效傳輸?shù)忍攸c。通過實驗對比，采用二面角插值Loop細分規(guī)則與插值Loop細分混合算法，使網(wǎng)格達到具有細分連通性，滿足逆細分準則。該網(wǎng)格在多分辨率漸進傳輸過程中具有高效、局部特征明顯的特點，符合算法設計初衷。該算法的主要特點如下：

(1) 在獲取精網(wǎng)格過程中采用二面角插值Loop快速、精確的特點，混合插值Loop細分算法達到漸進傳輸網(wǎng)格要求。避免了傳統(tǒng)的細分算法在獲取精密網(wǎng)格的巨大計算量。

(2) 提出頂點分裂、根據(jù)細分模板預測偏移量、更新網(wǎng)格3步驟對符合漸進傳輸?shù)木芫W(wǎng)格進行漸進傳輸，避免了像逆蝶形細分算法使用頂點仿射組合對偶點補償?shù)挠嬎悖涌炝藵u進傳輸?shù)男省?/p>

(3) 采用以插值Loop細分算法為模板，較傳統(tǒng)的逼近型Loop細分算法可避免模型凹陷缺點，保持了模型的局部特征。

通過大量的實驗結果表明，采用基于二面角逆插值Loop細分漸進傳輸算法效率高、局部特征明顯，給用戶在終端產(chǎn)品上快速渲染及視覺顯示帶來更多真實感，比以往算法更加高效、精確，具有一定的應用價值。

[1] HOPPE H. Progressive meshes [C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1996: 99-108.

[2] GARLAND M, HECKBERT P S. Surface simplification using quadric error metrics [C]//Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1997: 209-216.

[3] HASSAN M F, DODGSON N A. Reversesubdivision [M]//Advances in Multiresolution for Geometric Modelling. Berlin: Springer-Verlag, 2005: 271-283.

[4] LUO X N, ZHENG G F. Progressive meshes transmission over a wired-to-wireless network [J]. Wireless Networks, 2008, 14(1): 47-53.

[5] MA J P, LUO X N, CHEN B, et al. Triangle mesh compression based on reverse subdivision for mobile terminals [J]. Journal of Software, 2009, 20(9): 2607-2615.

[6] LOOP C. Smooth subdivision surfaces based on triangles [D]. Salt Lake City: University of Utah, 1987.

[7] SHI Z, AN Y, XU S, et al. Mesh simplification method based on reverse interpolation Loop subdivision [C]//Proceedings of the 8th International Conference on Computer Modeling and Simulation. New York: ACM Press, 2017: 141-145.

[8] SHI Z, LIN S J, LUO X N, et al. Interpolatory and mixed Loop schemes [J].Computer Graphics Forum, 2008, 27(7): 1829-1835.

[9] LIU Y J, XU C X, FAN D, et al. Efficient construction and simplification of Delaunay meshes [J]. ACM Transactions on Graphics (TOG), 2015, 34(6): 174.

[10] NIE?NER M, LOOP C, MEYER M, et al. Feature-adaptive GPU rendering of Catmull-Clark subdivision surfaces [J]. ACM Transactions on Graphics (TOG), 2012, 31(1): 6.

[11] HUANG Y C, FENG J Q, NIE?NER M, et al. Feature-adaptive rendering of Loop subdivision surfaces on modern GPUs [J]. Journal of Computer Science and Technology, 2014, 29(6): 1014-1025.

[12] 吳劍煌, 劉偉軍, 王天然. 面向三角網(wǎng)格的自適應細分[J]. 計算機工程, 2006, 32(12): 14-16.

[13] AMRESH A, FARIN G, RAZDAN A. Adaptive subdivision schemes for triangular meshes [C]//Hierarchical and Geometrical Methods in Scientific Visualization. Berlin: Springer-Verlag, 2003: 319-327.

[14] PASCUCCI V, BAJAJ C L, ZHUANG G. Single resolution compression of arbitrary triangular meshes with properties [C]//Proceeding of the Conference on Data Compression. Washington, DC: IEEE Computer Society Press, 1999:247.

[15] MONGKOLNAM P, RAZDAN A, FARIN G. Lossy 3D mesh compression using Loop scheme [C]//Proceedings of the 6th IASTED International Conference on Computer Graphics and Imaging. Anaheim: ACTA Press, 2003: 64.

[16] LEE A W F, SWELDENS W, SCHR?DER P, et al. MAPS: Multiresolution adaptive parameterization of surfaces [C]//Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1998: 95-104.

Progressive Transmission Method Based on Dihedral Reverse Interpolation Loop Subdivision

SHI Zhuo, KONG Qian, YU Ke, LAN Ru-shi, LUO Xiao-nan

(School of Art and Design, Guilin University of Electronic Technology, Guilin Guangxi 541004, China)

With the rapid development of virtual reality, augmented reality, etc., Multi-resolution progressive transmission can provide a good user experience. In order to implement the fast transmission and display of triangular mesh in the mobile terminal, this paper presents a progressive transmission algorithm based on dihedral reverse interpolation Loop subdivision (DRILS). The algorithm mainly uses dihedral interpolation Loop subdivision (DILS) and interpolation Loop subdivision (ILS) algorithm processing. A fine mesh with subdivision connectivity is obtained at the same time as the local feature is accurate. In the process of progressive transmission, three steps are taken for the iterative operation of the accurate triangular mesh: odd and even vertex partition, offset prediction, and triangular mesh prediction. Due to the combination of the DILS and ILS which is used to obtain accurate mesh, the local characteristics of the progressive transmission are accurate, and the speed of progressive transmission is also accelerated. The experimental comparison shows that the algorithm is accurate and efficient, and is suitable for display, transmission and storage of mobile terminal devices.

progressive transmission; reverse subdivision; interpolation Loop subdivision; dihedral

TP 391

10.11996/JG.j.2095-302X.2019010092

A

2095-302X(2019)01-0092-07

2018-07-27；

2018-09-18

廣西信息科學實驗中心開放基金項目(YB1506)；國家自然科學基金項目(61862018)；廣西自然科學基金項目(2018GXNSFAA138084)；廣西高校圖形圖像重點實驗室開放課題(GIIP201404)

史 卓(1978-)，男，江蘇常州人，副教授，博士，碩士生導師。主要研究方向為圖形圖像處理、數(shù)字媒體。E-mail：shzh@guet.edu.cn

玉 珂(1979-)，女，廣西柳州人，研究實習員，本科。主要研究方向為圖形學、虛擬現(xiàn)實。E-mail：xiaoxiao-yk@163.com