基于逆Loop細分的半正則網格簡化算法

欒婉娜，劉成明

基于逆Loop細分的半正則網格簡化算法

欒婉娜，劉成明

(鄭州大學軟件學院，河南 鄭州 450002)

三維網格簡化是在保留目標物體幾何形狀信息的前提下盡量減小精細化三維模型中的點數和面數的一種操作，對提高三維網格數據的存取和網絡傳輸速度、編輯和渲染效率具有十分重要的作用。針對大多網格簡化算法在簡化過程中未考慮網格拓撲結構與視覺質量的問題，提出了一種基于逆Loop細分的半正則網格簡化算法。首先根據鄰域質心偏移量進行特征點檢測，隨后隨機選取種子三角形，以邊擴展方式獲取正則區域并執行逆Loop細分進行簡化。最后，以向內分割方式進行邊緣拼接，獲取最終的簡化模型。與經典算法在公開數據集上進行實驗對比，結果表明，該算法能夠在簡化的同時有效地保持網格特征，盡可能保留與原始網格一致的規則的拓撲結構，并且在視覺質量上優于邊折疊以及聚類簡化算法。

網格簡化；逆Loop細分；網格拼接；視覺度量；半正則化

在計算機圖形學和幾何造型中，物體通常是由多邊形網格描述，其中又以三角網格最為常見。隨著如Kinect、激光掃描儀等三維數據獲取設備的不斷完善，人們獲取的三維數據以及由此建立的網格模型往往是高度密集的，對傳統的計算機硬件以及網絡帶寬提出了極高的要求。但在動畫、游戲等具體應用場景中，人們往往并不總是需要高精度的模型。為滿足各種實際場景的需求，產生了諸如網格簡化、網格壓縮、動態細節層次(levels of detail)和漸進傳輸等一系列方法來平衡人們對于模型精度、硬件限制、網絡帶寬以及運算速度的需求。

網格簡化是圖形學中一項基本而又重要的問題，是指以幾何或視覺度量為評價標準，在最大程度保持模型特征的同時，通過剔除視覺冗余細節來降低模型的復雜度。目前，國內外學者提出的網格簡化算法大致可以分為如下幾類：

(1) 基于低級幾何特征的簡化算法。以幾何誤差為指導，通過對原始模型中的幾何元素進行動態削減或重新分布達到模型簡化的目的，如圖元聚類/區域合并、幾何元素刪除和采樣算法。圖元聚類算法[1-4]通過頂點聚類或者聚合近似平面實現了模型幾何元素的削減，具有易于實現、健壯性好、無拓撲限制、適于并行處理并且計算效率高等優點，但簡化精度受聚類數目和包圍盒大小的影響，無法保持一些精細特征。幾何元素刪除算法通過刪除頂點[5]、邊折疊[6]、三角形收縮[7]等方式將基本圖元進行刪除，執行效率高，但不能顯著簡化模型內部結構。采樣法[8-9]通過將頂點或者體素添加到模型的表面，然后根據幾何誤差指導規則進行重新分布調整，生成與原模型盡可能接近的簡化模型。

(2) 基于高級語義特征指導的簡化算法。除了幾何特征，諸如顯著度[10-12]等高級視覺特征也被引入網格簡化算法，使簡化模型可以更多得保留人眼視覺中更為顯著的部分。

(3) 結合各種實際應用場景的簡化算法。如結合實時簡化[13]、GPU并行計算[14]、紋理[15-16]、視點[17-18]、漸進傳輸[19-21]等因素的簡化算法。其在簡化模型的同時，能夠使得算法更符合某些特定的應用需求。

(4) 其他簡化算法。小波分解的方法[22]將原始模型分解成低分辨率和細節2個部分，該方法比較適合光滑的表面。一些研究也開始注重網格簡化后的形態優化問題[23-24]，以獲得在視覺感受上更為優質的模型。另外，最新一些研究將神經網絡與傳統簡化算法相結合[25-26]，使得網格簡化在動態參數的選擇以及運算速度上得到了提升。

盡管存在著各種各樣的簡化方式，但上述算法在網格簡化過程中均沒有兼顧網格的原始拓撲結構與視覺效果。正則網格以及半正則網格(如分片正則網格)作為一種特殊的網格結構，具有更規則的連接、更一致的拓撲、更良好的視覺效果，往往作為一種高質量的網格來保存三維模型。但上述方法在簡化過程中均會對這種規則拓撲造成破壞，由此生成的網格模型在面片形狀以及頂點度方面往往不易控制。此外，雖然一些算法得到的簡化模型與原始模型在形態和體積上都較為接近，但是人類的視覺感知卻取決于多種因素。針對上述問題，本文提出了基于逆細分的半正則網格簡化算法，可以更好地適應于正則以及半正則網格模型，并獲得在視覺感受上更為優質的簡化模型。

1 相關工作

1.1 半正則網格

三角網格可以表示為=(,)，其中={p=(x,y,z)|=1,2,···,}為網格頂點集合；為網格拓撲信息集合。若頂點p和六條邊相連接則稱p為正則點，否則為非正則點，也稱為奇異點。對于網格，若所有頂點都是正則點稱為正則網格，多數頂點是正則點則為半正則網格。

1.2 逆Loop細分

曲面細分是幾何造型中一種常見方法，常見基于三角網格的細分方法分為逼近型細分(如Loop細分)與插值型細分(如Butterfly細分)。不同的網格細分方法按照不同的規則對原始網格進行分裂操作，逐層加細。

圖1展示了Loop細分過程。Loop細分是一個逼近型的1-4分裂過程。在細分過程中，不僅計算新增頂點0(奇點)的位置，原始頂點(偶點，統一用v表示)也要根據原網格中此點和與之相鄰頂點v所占權值進行相應的位置調整，頂點計算式為

其中，；n為偶點的度數。

逆Loop細分是Loop細分的逆過程，在計算時，往往需要耗費大量資源計算逆細分前后頂點坐標的對應關系。但是，在密集的網格中，頂點局部位置的調整并不會過多影響網格的形態，因此，通過將逼近型細分當作插值型細分進行處理，可以有效地簡化計算過程并保持網格的基本形態。

2 算法描述

本文算法的完成步驟包括：特征點標記、選取種子三角形、正則區域擴展與邊緣奇點標記、逆細分簡化、邊緣拼接等。首先根據鄰域質心偏移量進行網格特征點檢測，以便在網格簡化過程中保留特征。然后隨機選取種子三角形，以邊擴展方式動態獲取正則區域。在擴展過程中，通過構建頂點擴展隊列，驗證當前擴展頂點是否為特征點并利用回退機制將網格模型特征點保留在擴展區域之外。隨后通過對正則區域執行逆Loop細分進行簡化，最后以向內分割方式進行網格邊緣拼接，從而獲得最終簡化模型。

2.1 標記特征點

首先進行模型特征點判斷，避免在網格簡化過程中損失過多原始特征。特征點一般位于網格表面發生明顯變化的地方，對應較大的局部曲率。本文根據質心偏移距離進行網格特征點檢測。質心偏移距離為

其中，p為當前頂點；qi為當前頂點的鄰接點；n為頂點的鄰域頂點個數，即頂點的度，norm為模長。由文獻[27]可知，從微分坐標角度，質心偏移的方向趨近于頂點局部法向量，其大小體現了頂點的局部平均曲率，因此，通過質心偏移距離，可以方便地快速檢測出模型表面變化明顯的特征點。圖2顯示了前10%最大質心偏移距離對應的特征點。在實際簡化過程中，可以通過設定特征點的數量，達到特征簡化的目的。

2.2 選取種子三角形

選取一個滿足條件(3個頂點的度均為6)的三角形作為種子三角形。理論上，所有滿足此要求的三角形都可以作為種子三角形，本文隨機選取一個初始的種子三角形。

2.3 正則區域擴展與邊緣奇點標記

在種子三角形的基礎上，將正則區域盡量擴展。

首先將種子三角形的3個頂點放入隊列當中，然后通過共享邊擴展種子三角形，擴展后的偶點將會再次放入隊列。隨后從隊列頭部取出一個頂點，若該頂點的度為6，則由該頂點定位一個與已擴展區域無鄰接邊但共享該頂點的三角形，作為新的奇點三角形，再次擴展逆Loop細分單元。如果擴展過程中遇到非正則點或者特征點，則回退，并跳過當前擴展點，從隊列中取出下一個點來繼續執行，直至隊列為空。

在擴展過程中，為了減少搜索范圍和避免擴展區域的交疊重合，每個擴展過后的三角形將會從原始模型的面片集合中去除。由于在逆細分簡化過程中，將會消除當前層的奇點，并將偶點連接成新的面片，所以，通過標記所有擴展邊緣的奇點，可以定位拼接過程中需要調整的頂點。擴展過程如圖3所示。

圖3 正則區域擴展

重復選取種子三角形和正則區域擴展與邊緣奇點標記，搜尋所有的可逆細分區域，并標記邊緣。

2.4 逆細分簡化

在擴展眾多正則區域后，所有的特征點以及奇異點均被保留下來，由此保留了原始網格的絕大部分特征。本文將Loop細分視作插值型細分，刪除每個正則區域內部的奇點，保留偶點，更新網格拓撲結構，實現區域內部的簡化。

2.5 邊緣拼接

在對區域內部進行簡化過后，不同的正則區域的邊緣形態是極其不規則的，對網格邊緣的直接拼接造成極大困難。因此，本文采取向內分割方式來拼接不同的擴展區域。在正則區域擴展過程中，經常出現圖4所示情況，對奇點所在可逆細分單元進行重新分割和邊緣拼接。從左到右分別為正則區域擴展，逆細分以及邊緣拼接結果。藍色部分代表正則區域，紅色頂點為邊緣奇點，綠色部分為待擴展區域，青色部分為重分割結果。

圖4 向內分割和邊緣拼接

至此完成一輪完整的逆細分簡化過程。重復本文算法步驟可反復進行網格簡化，直到模型滿足要求，或模型中不存在滿足條件的正則區域。通過這種拼接與簡化方式，避免了直接對復雜邊緣形態進行調整，將各種情況下的邊緣拼接簡化為2種分割方式，且特征點被保留在簡化區域外部，待簡化正則區域在簡化過后仍為正則區域。簡化完成后，特征點附近的網格由于重分割較為細密，非特征處網格較為稀疏，在保留一致拓撲的同時，實現了自適應簡化。

3 實驗結果分析

本文算法在Windows環境下采用MatLab實現，實驗環境配置為：i5-8250U，1.60 GHz，16 G內存。將本文算法(邊擴展)與基于頂點分裂[20]方式的逆細分算法以及邊折疊[6]和頂點聚類[28]算法的源碼實驗結果進行了對比。采用的數據模型為網格編輯中常用的幾何模型，如chain，cat head，knot，casting和rocker-arm等。

3.1 幾何誤差度量與評價

本文采用Hausdorff 距離作為簡化前后模型的幾何誤差度量評價。表1展示了本文算法與頂點分裂算法的對比結果，可以看出，兩者的Hausdorff 距離極為接近。但是，頂點分裂算法一般需要對網格模型進行預處理獲取基網格，并且非正則點數量達到一定程度，會終止頂點的遞歸分裂。表2展示了本文算法與邊折疊以及頂點聚類方法的對比結果。可以看出，在幾何誤差上，本文算法優于邊折疊算法，并在部分模型上優于頂點聚類方法。

表1 邊擴展與點分裂簡化誤差對比

表2 邊擴展與邊折疊，聚類簡化誤差對比

3.2 視覺質量度量與評價

圖5顯示了點分裂以及本文算法對正則網格模型的簡化結果。點分裂和本文算法的區別主要在于逆細分單元的獲取方式不同，但隨著非正則點的增多，點分裂方法將不再適用。

圖5 Chain (簡化38%，94%)

圖6~9顯示了本文算法與邊折疊以及頂點聚類方法在不同簡化率上的簡化結果。從主觀感受上可以看出，在圖6 casting模型中，聚類算法無法保持諸如孔洞等細微結構，邊折疊算法中，某些折疊過后的面片也對孔洞造成了覆蓋，且產生了大量的狹長三角形，而本文算法對模型邊緣、孔洞部分影響較小。在圖7 rocker-arm模型中，本文算法保留了更多細節。這是因為奇異點以及特征點在邊擴展過程中被保留下來，且網格拼接部分往往發生在平坦區域與特征區域的交界處，因此模型特征保存較為完好。此外，由于逆細分算法采用逐層簡化方式，簡化后的面片往往在視覺上較為均勻，狹長三角形較少，從而擁有比較好的視覺效果，且保留了大部分正則點，如圖8和圖9所示。

圖6 Casting (簡化78%)

圖7 Rocker_arm (簡化76%)

圖8 Ball (簡化98%)

圖9 Chair (簡化60%)

文獻[29-30]表明Hausdorff距離、均方根誤差法等幾何距離測量方法與人眼視覺系統的質量感知之間的相關性較差，文獻[24]使用了三角形狹長度來評價網格質量，定義三角形狹長度為

其中，l1，l2，l3分別為三角形的3條邊長；S為三角形的面積，0≤Q≤1，且Q的值越大，面片質量越好。當Q=1時，三角形為正三角形。

圖10~11顯示了在相同的簡化程度下，不同算法簡化模型的三角形Q分布。從中可以看出，本文算法產生的狹長三角形較少，而形態良好的三角形數量較多。且本文算法盡可能保留了原始網格中的正則點，因而產生更規則的拓撲結構。雖然聚類算法在Q較大時擁有最多的面片數量，但是其對網格精細結構破壞較大。本文算法在較好的保持原始特征的情況下擁有比較良好的網格形態。

圖10 Casting模型Qk分布

圖11 Rocker_arm模型Qk分布

4 結 論

本文提出了一種結合逆細分與拼接策略的網格模型簡化算法，在保持模型基本特征的同時，獲取了視覺上更加均勻的網格模型。該算法通過正則區域的選擇性遞歸擴展，保留了奇異點與特征點，并利用逆插值型Loop細分進行簡化。最后，以分割策略實現了區域間復雜邊緣的拼接，得到完整的簡化模型。實驗結果表明，該算法獲取到的簡化模型可以得到視覺上更為均勻的簡化結果，并能保留特征區域。

[1] 周昆, 潘志庚, 石教英. 一種新的基于頂點聚類的網格簡化算法[J]. 自動化學報, 1999(1): 4-11. ZHOU K, PAN Z G, SHI J Y. A new mesh simplification algorithm based on vertex clustering[J]. Acta Automatica Sinica, 1999(1): 4-11 (in Chinese).

[2] 王家騰, 殷宏, 解文彬, 等. 基于頂點重要度和層次聚類樹的地形網格簡化[J].計算機工程與設計, 2016, 37(6): 1543-1548. WANG J T, YIN H, XIE W B, et al. Terrain mesh simplification based on vertex importance and hierarchical clustering tree[J]. Computer Engineering and Design, 2016, 37(6): 1543-1548 (in Chinese).

[3] HINKER P, HANSEN C. Geometric optimization[C]// Proceedings Visualization'93. NewYork: IEEE Press, 1993: 189-195.

[4] ROSSIGNAC J, BORREL P. Multi-resolution 3D approximations for rendering complex scenes[M]// Modeling in Computer Graphics. Heidelberg: Springer, 1993: 455-465.

[5] SCHROEDER W J. Decimation of triangle meshes[J]. Computer Graphics, 1992, 26(2): 65-70.

[6] 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.

[7] GIENG T S, HAMANN B, Joy K I, et al. Constructing hierarchies for triangle meshes[J]. IEEE Transactions on Visualization and Computer Graphics, 1998, 4(2): 145-161.

[8] TURK G. Re-tiling polygonal surfaces[C]//Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques.New York: ACM Press, 1992: 55-64.

[9] HE T, HONG L, VARSHNEY A, et al. Controlled topology simplification[J]. IEEE Transactions on Visualization and Computer Graphics, 1996, 2(2): 171-184.

[10] LEE C, VARSHNEY A, JACOBS D. Mesh saliency[J]. ACM Transactions on Graphics, 2005, 24(3): 659-666.

[11] ZHAO Y T, LIU Y H, SONG R, et al. A saliency detection based method for 3D surface simplification[C]// IEEE International Conference on Acoustics, Speech and Signal Processing. New York: IEEE Press, 2012: 889-892.

[12] 魏寧, 徐婷婷, 高開源, 等. 基于Voronoi極點特征值顯著度加權的網格簡化算法[J].圖學學報, 2017, 38(3): 314-319. WEI N, XU T T, GAO K Y, et al. Mesh simplification weighted by voronoi poles feature computed saliency[J]. Journal of Graphics, 2017, 38(3): 314-319 (in Chinese).

[13] BAHIRAT K, RAGHURAMAN S, PRABHAKARAN B. Real-time, curvature-sensitive surface simplification using depth images[J]. IEEE Transactions on Multimedia, 2018, 20(6): 1489-1498.

[14] 范豪, 劉峻, 孫宇, 等. GPU并行加速的邊折疊簡化算法[J]. 計算機工程與設計, 2016, 37(11): 3051-3057. FAN H, LIU J, SUN Y, et al. Parallel processing for accelerated edge collapse simplification algorithm with GPU[J]. Computer Engineering and Design, 2016, 37(11): 3051-3057 (in Chinese).

[15] 李世俊, 姜曉彤, 唐慧. 保持細節特征的帶紋理模型的高質量簡化算法[J]. 計算機應用研究, 2020, 37(1): 300-303, 312. LI S J, JIANG X T, TANG H. High-quality simplified algorithm of texture model for detailed features preserving[J]. Application Research of Computers, 2020, 37(1): 300-303, 312 (in Chinese).

[16] 馮翔, 周明全. 帶紋理的三維模型簡化算法[J]. 計算機輔助設計與圖形學學報, 2009, 21(6): 842-846, 852. FENG X, ZHOU M Q. An algorithm for simplification of 3D models with texture[J]. Journal of Computer-Aided Design & Computer Graphics, 2009, 21(6): 842-846, 852 (in Chinese).

[17] 馬軍, 郁永珍, 鄭憲, 等. 基于視點的網格模型快速簡化算法[J]. 計算機工程, 2006(9): 211-213. MA J, YU Y Z, ZHENG X, et al. An algorithm of viewpoint-based mesh model simplification[J]. Computer Engineering, 2006(9): 211-213 (in Chinese).

[18] 馮潔, 查紅彬. 大型三維網格模型的簡化及基于視點的LOD控制[J]. 計算機輔助設計與圖形學學報, 2006(2): 186-193. FENG J, ZHA H B. Simplification and view-dependent LOD control for large 3D mesh models[J]. Journal of Computer-Aided Design & Computer Graphics, 2006(2): 186-193 (in Chinese).

[19] 馬建平, 羅笑南, 陳渤, 等. 面向移動終端的三角網格逆細分壓縮算法[J]. 軟件學報, 2009, 20(9): 2607-2615.MA J P, LUO X N, CHEN B, et al. Triangle mesh compression based on reverse subdivision for mobile terminals[J]. Journal of software engineering, 2009, 20(9): 2607-2615 (in Chinese).

[20] 史卓, 孔謙, 玉珂, 等. 基于二面角逆插值Loop細分的漸進傳輸方法[J]. 圖學學報, 2019, 40(1): 92-98. SHI Z, KONG Q, YU K, et al. Progressive transmission method based on dihedral reverse interpolation loop subdivision[J]. Journal of Graphics, 2019, 40(1): 92-98 (in Chinese).

[21] 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.

[22] LOUNSBERY M, DEROSE T D, WARREN J. Multiresolution analysis for surfaces of arbitrary topological type[J]. ACM Transactions on Graphics (TOG), 1997, 16(1): 34-73.

[23] YI R, LIU Y J, HE Y. Delaunay mesh simplification with differential evolution[J]. ACM Transactions on Graphics (TOG), 2018, 37(6): 1-12.

[24] 王武禮, 段黎明, 王浩宇, 等.基于動態誤差控制和PSO的三角網格模型簡化優化方法[J].計算機集成制造系統, 2018, 24(1): 63-71. WANG W L, DUAN L M, WANG H Y, et al. Simplification and optimization of Triangular mesh Model based on dynamic error control and PSO [J]. Computer Integrated Manufacturing Systems, 2016, 24(1): 63-71 (in Chinese).

[25] 褚蘇榮, 牛之賢, 宋春花, 等. 面向移動端的漸進網格簡化算法[J]. 計算機應用, 2020, 40(3): 806-811. CHU S R, NIU Z X, SONG C H, et al. Progressive mesh simplification algorithm for mobile devices[J]. Journal of Computer Applications, 2020, 40(3): 806-811 (in Chinese).

[26] 楊煜, 冼楚華, 李桂清. 結合局部區域特征的自適應簡化率網格簡化算法[J]. 計算機輔助設計與圖形學學報, 2020, 32(6): 857-864. YANG Y, XIAN C H, LI G Q. Mesh simplification with adaptive simplified ratio based on local region features[J]. Journal of Computer-Aided Design & Computer Graphics, 2020, 32(6): 857-864. (in Chinese).

[27] SORKINE O. Laplacian mesh processing[C]//26th Annual Conference of the European Association for Computer Graphics. Goslar: Eurographics Association, 2005: 53-70.

[28] LINDSTROM P. Out-of-core simplification of large polygonal models[C]//Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 2000: 259-262.

[29] CORSINI M, LARABI M C, LAVOUé G, et al. Perceptual metrics for static and dynamic triangle meshes[J]. Computer Graphics Forum, 2013, 32(1): 101-125.

[30] LAVOUé G, CORSINI M. A comparison of perceptually-based metrics for objective evaluation of geometry processing[J]. IEEE Transactions on Multimedia, 2010, 12(7): 636-649.

A semi-regular mesh simplification algorithm based on inverse Loop subdivision

LUAN Wan-na, LIU Cheng-ming

(School of Software, Zhengzhou University, Zhengzhou Henan 450002, China)

3D mesh simplification is an operation to minimize the number of vertices and faces in the refined 3D model while preserving the geometric information of the target object. It plays a significant role in improving the access and network transmission speed of the 3D mesh data, and the efficiency of editing and rendering. To address the problem of most mesh simplification algorithms neglecting the mesh topology and visual quality during simplification, a semi-regular mesh simplification algorithm was proposed based on the inverse Loop subdivision. The algorithm first detected the feature points according to the neighborhood centroid offset. Then a seed triangle was randomly selected to obtain the regular region by edge extension, and the inverse Loop subdivision was performed to simplify the mesh. Finally, the simplified model was gained by edge splicing in the way of inwards segmentation. Regarding the open testing data, comparisons were made between the algorithm and the classical ones. The experimental results show that the proposed algorithm can preserve the features effectively and keep the regular topology structure as much as possible during simplification, and that it is superior to the edge collapse and clustering algorithm in visual quality.

mesh simplification; inverse Loop subdivision; mesh splicing; visual metrics; semi-regular

TP 391

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

A

2095-302X(2020)06-0980-07

2020-05-05；

2020-07-06

5 May，2020；

6 July，2020

河南省科技攻關項目(192102210107)；鄭州市重大科技創新專項

Key Scientific and Technological Project of Henan Province (192102210107); Major Technological Innovation Project of Zhengzhou

欒婉娜(1996-)，女，河南鹿邑人，碩士研究生。主要研究方向為圖形圖像處理。E-mail：wnluan@qq.com

LUAN Wan-na (1996–), female, master student. Her main research interests cover graphics and image processing. E-mail：wnluan@qq.com

劉成明(1979-)，男，山東沂源人，副教授，博士，碩士生導師。主要研究方向為圖形圖像與視覺計算等。E-mail：cmliu@zzu.edu.cn

LIU Cheng-ming (1979–), male, associate professor, Ph.D. His main research interests cover graphics, image processing and visual computing. E-mail：cmliu@zzu.edu.cn