基于逆Loop細(xì)分的半正則網(wǎng)格簡化算法

欒婉娜，劉成明

基于逆Loop細(xì)分的半正則網(wǎng)格簡化算法

欒婉娜，劉成明

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

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

網(wǎng)格簡化；逆Loop細(xì)分；網(wǎng)格拼接；視覺度量；半正則化

在計算機(jī)圖形學(xué)和幾何造型中，物體通常是由多邊形網(wǎng)格描述，其中又以三角網(wǎng)格最為常見。隨著如Kinect、激光掃描儀等三維數(shù)據(jù)獲取設(shè)備的不斷完善，人們獲取的三維數(shù)據(jù)以及由此建立的網(wǎng)格模型往往是高度密集的，對傳統(tǒng)的計算機(jī)硬件以及網(wǎng)絡(luò)帶寬提出了極高的要求。但在動畫、游戲等具體應(yīng)用場景中，人們往往并不總是需要高精度的模型。為滿足各種實際場景的需求，產(chǎn)生了諸如網(wǎng)格簡化、網(wǎng)格壓縮、動態(tài)細(xì)節(jié)層次(levels of detail)和漸進(jìn)傳輸?shù)纫幌盗蟹椒▉砥胶馊藗儗τ谀Ｐ途?、硬件限制、網(wǎng)絡(luò)帶寬以及運(yùn)算速度的需求。

網(wǎng)格簡化是圖形學(xué)中一項基本而又重要的問題，是指以幾何或視覺度量為評價標(biāo)準(zhǔn)，在最大程度保持模型特征的同時，通過剔除視覺冗余細(xì)節(jié)來降低模型的復(fù)雜度。目前，國內(nèi)外學(xué)者提出的網(wǎng)格簡化算法大致可以分為如下幾類：

(1) 基于低級幾何特征的簡化算法。以幾何誤差為指導(dǎo)，通過對原始模型中的幾何元素進(jìn)行動態(tài)削減或重新分布達(dá)到模型簡化的目的，如圖元聚類/區(qū)域合并、幾何元素刪除和采樣算法。圖元聚類算法[1-4]通過頂點聚類或者聚合近似平面實現(xiàn)了模型幾何元素的削減，具有易于實現(xiàn)、健壯性好、無拓?fù)湎拗啤⑦m于并行處理并且計算效率高等優(yōu)點，但簡化精度受聚類數(shù)目和包圍盒大小的影響，無法保持一些精細(xì)特征。幾何元素刪除算法通過刪除頂點[5]、邊折疊[6]、三角形收縮[7]等方式將基本圖元進(jìn)行刪除，執(zhí)行效率高，但不能顯著簡化模型內(nèi)部結(jié)構(gòu)。采樣法[8-9]通過將頂點或者體素添加到模型的表面，然后根據(jù)幾何誤差指導(dǎo)規(guī)則進(jìn)行重新分布調(diào)整，生成與原模型盡可能接近的簡化模型。

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

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

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

盡管存在著各種各樣的簡化方式，但上述算法在網(wǎng)格簡化過程中均沒有兼顧網(wǎng)格的原始拓?fù)浣Y(jié)構(gòu)與視覺效果。正則網(wǎng)格以及半正則網(wǎng)格(如分片正則網(wǎng)格)作為一種特殊的網(wǎng)格結(jié)構(gòu)，具有更規(guī)則的連接、更一致的拓?fù)?、更良好的視覺效果，往往作為一種高質(zhì)量的網(wǎng)格來保存三維模型。但上述方法在簡化過程中均會對這種規(guī)則拓?fù)湓斐善茐模纱松傻木W(wǎng)格模型在面片形狀以及頂點度方面往往不易控制。此外，雖然一些算法得到的簡化模型與原始模型在形態(tài)和體積上都較為接近，但是人類的視覺感知卻取決于多種因素。針對上述問題，本文提出了基于逆細(xì)分的半正則網(wǎng)格簡化算法，可以更好地適應(yīng)于正則以及半正則網(wǎng)格模型，并獲得在視覺感受上更為優(yōu)質(zhì)的簡化模型。

1 相關(guān)工作

1.1 半正則網(wǎng)格

三角網(wǎng)格可以表示為=(,)，其中={p=(x,y,z)|=1,2,···,}為網(wǎng)格頂點集合；為網(wǎng)格拓?fù)湫畔⒓稀Ｈ繇旤cp和六條邊相連接則稱p為正則點，否則為非正則點，也稱為奇異點。對于網(wǎng)格，若所有頂點都是正則點稱為正則網(wǎng)格，多數(shù)頂點是正則點則為半正則網(wǎng)格。

1.2 逆Loop細(xì)分

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

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

其中，；n為偶點的度數(shù)。

逆Loop細(xì)分是Loop細(xì)分的逆過程，在計算時，往往需要耗費大量資源計算逆細(xì)分前后頂點坐標(biāo)的對應(yīng)關(guān)系。但是，在密集的網(wǎng)格中，頂點局部位置的調(diào)整并不會過多影響網(wǎng)格的形態(tài)，因此，通過將逼近型細(xì)分當(dāng)作插值型細(xì)分進(jìn)行處理，可以有效地簡化計算過程并保持網(wǎng)格的基本形態(tài)。

2 算法描述

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

2.1 標(biāo)記特征點

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

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

2.2 選取種子三角形

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

2.3 正則區(qū)域擴(kuò)展與邊緣奇點標(biāo)記

在種子三角形的基礎(chǔ)上，將正則區(qū)域盡量擴(kuò)展。

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

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

圖3 正則區(qū)域擴(kuò)展

重復(fù)選取種子三角形和正則區(qū)域擴(kuò)展與邊緣奇點標(biāo)記，搜尋所有的可逆細(xì)分區(qū)域，并標(biāo)記邊緣。

2.4 逆細(xì)分簡化

在擴(kuò)展眾多正則區(qū)域后，所有的特征點以及奇異點均被保留下來，由此保留了原始網(wǎng)格的絕大部分特征。本文將Loop細(xì)分視作插值型細(xì)分，刪除每個正則區(qū)域內(nèi)部的奇點，保留偶點，更新網(wǎng)格拓?fù)浣Y(jié)構(gòu)，實現(xiàn)區(qū)域內(nèi)部的簡化。

2.5 邊緣拼接

在對區(qū)域內(nèi)部進(jìn)行簡化過后，不同的正則區(qū)域的邊緣形態(tài)是極其不規(guī)則的，對網(wǎng)格邊緣的直接拼接造成極大困難。因此，本文采取向內(nèi)分割方式來拼接不同的擴(kuò)展區(qū)域。在正則區(qū)域擴(kuò)展過程中，經(jīng)常出現(xiàn)圖4所示情況，對奇點所在可逆細(xì)分單元進(jìn)行重新分割和邊緣拼接。從左到右分別為正則區(qū)域擴(kuò)展，逆細(xì)分以及邊緣拼接結(jié)果。藍(lán)色部分代表正則區(qū)域，紅色頂點為邊緣奇點，綠色部分為待擴(kuò)展區(qū)域，青色部分為重分割結(jié)果。

圖4 向內(nèi)分割和邊緣拼接

至此完成一輪完整的逆細(xì)分簡化過程。重復(fù)本文算法步驟可反復(fù)進(jìn)行網(wǎng)格簡化，直到模型滿足要求，或模型中不存在滿足條件的正則區(qū)域。通過這種拼接與簡化方式，避免了直接對復(fù)雜邊緣形態(tài)進(jìn)行調(diào)整，將各種情況下的邊緣拼接簡化為2種分割方式，且特征點被保留在簡化區(qū)域外部，待簡化正則區(qū)域在簡化過后仍為正則區(qū)域。簡化完成后，特征點附近的網(wǎng)格由于重分割較為細(xì)密，非特征處網(wǎng)格較為稀疏，在保留一致拓?fù)涞耐瑫r，實現(xiàn)了自適應(yīng)簡化。

3 實驗結(jié)果分析

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

3.1 幾何誤差度量與評價

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

表1 邊擴(kuò)展與點分裂簡化誤差對比

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

3.2 視覺質(zhì)量度量與評價

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

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

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

圖6 Casting (簡化78%)

圖7 Rocker_arm (簡化76%)

圖8 Ball (簡化98%)

圖9 Chair (簡化60%)

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

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

圖10~11顯示了在相同的簡化程度下，不同算法簡化模型的三角形Q分布。從中可以看出，本文算法產(chǎn)生的狹長三角形較少，而形態(tài)良好的三角形數(shù)量較多。且本文算法盡可能保留了原始網(wǎng)格中的正則點，因而產(chǎn)生更規(guī)則的拓?fù)浣Y(jié)構(gòu)。雖然聚類算法在Q較大時擁有最多的面片數(shù)量，但是其對網(wǎng)格精細(xì)結(jié)構(gòu)破壞較大。本文算法在較好的保持原始特征的情況下?lián)碛斜容^良好的網(wǎng)格形態(tài)。

圖10 Casting模型Qk分布

圖11 Rocker_arm模型Qk分布

4 結(jié) 論

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

[1] 周昆, 潘志庚, 石教英. 一種新的基于頂點聚類的網(wǎng)格簡化算法[J]. 自動化學(xué)報, 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] 王家騰, 殷宏, 解文彬, 等. 基于頂點重要度和層次聚類樹的地形網(wǎng)格簡化[J].計算機(jī)工程與設(shè)計, 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極點特征值顯著度加權(quán)的網(wǎng)格簡化算法[J].圖學(xué)學(xué)報, 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]. 計算機(jī)工程與設(shè)計, 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] 李世俊, 姜曉彤, 唐慧. 保持細(xì)節(jié)特征的帶紋理模型的高質(zhì)量簡化算法[J]. 計算機(jī)應(yīng)用研究, 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]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 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] 馬軍, 郁永珍, 鄭憲, 等. 基于視點的網(wǎng)格模型快速簡化算法[J]. 計算機(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] 馮潔, 查紅彬. 大型三維網(wǎng)格模型的簡化及基于視點的LOD控制[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 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] 馬建平, 羅笑南, 陳渤, 等. 面向移動終端的三角網(wǎng)格逆細(xì)分壓縮算法[J]. 軟件學(xué)報, 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細(xì)分的漸進(jìn)傳輸方法[J]. 圖學(xué)學(xué)報, 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] 王武禮, 段黎明, 王浩宇, 等.基于動態(tài)誤差控制和PSO的三角網(wǎng)格模型簡化優(yōu)化方法[J].計算機(jī)集成制造系統(tǒng), 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ìn)網(wǎng)格簡化算法[J]. 計算機(jī)應(yīng)用, 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] 楊煜, 冼楚華, 李桂清. 結(jié)合局部區(qū)域特征的自適應(yīng)簡化率網(wǎng)格簡化算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 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

河南省科技攻關(guān)項目(192102210107)；鄭州市重大科技創(chuàng)新專項

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-)，男，山東沂源人，副教授，博士，碩士生導(dǎo)師。主要研究方向為圖形圖像與視覺計算等。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