袁天然　程筱勝　孫全平

1.淮陰工學(xué)院江蘇省先進(jìn)制造技術(shù)重點(diǎn)實(shí)驗室,淮安,2230032.南京航空航天大學(xué),南京,210016

復(fù)雜形態(tài)孔洞的網(wǎng)格模型修復(fù)

袁天然1程筱勝2孫全平1

1.淮陰工學(xué)院江蘇省先進(jìn)制造技術(shù)重點(diǎn)實(shí)驗室,淮安,2230032.南京航空航天大學(xué),南京,210016

為了滿足實(shí)際工程應(yīng)用對復(fù)雜形態(tài)孔洞修復(fù)的需要,模擬拉鏈閉合原理,并基于局部最優(yōu)化的權(quán)值規(guī)則和曲面最小能量值特性的k階離散歐拉-拉格朗日方程,提出了一種具有C0～C2連續(xù)的網(wǎng)格模型修復(fù)架構(gòu)。實(shí)驗結(jié)果表明,該孔洞修復(fù)架構(gòu)能有效地對復(fù)雜孔洞邊界進(jìn)行C0～C2連續(xù)修復(fù)。

三角網(wǎng)格;孔洞修復(fù);復(fù)雜孔洞剖分;孔洞修補(bǔ)

0　引言

隨著三維測量技術(shù)的發(fā)展,三角網(wǎng)格模型逐漸成為最常用的幾何模型表示形式,廣泛應(yīng)用于計算機(jī)圖形學(xué)、幾何建模等領(lǐng)域。由于被測實(shí)體表面復(fù)雜、局部形態(tài)缺失、測量設(shè)備受限制等原因，有時無法直接測量獲取模型表面的全部三維數(shù)據(jù)，從而導(dǎo)致生成的網(wǎng)格模型出現(xiàn)孔洞。帶有孔洞的網(wǎng)格模型在很多應(yīng)用領(lǐng)域會導(dǎo)致不良后果,需要對模型孔洞按滿足原始模型自然連續(xù)屬性的方法進(jìn)行修復(fù)[1]。很多學(xué)者針對三角網(wǎng)格模型的孔洞修復(fù)進(jìn)行了研究,主要分為非幾何方法[2-5]和幾何方法[6-11]:①非幾何方法主要根據(jù)模型孔洞邊界頂點(diǎn)及N環(huán)鄰域頂點(diǎn)的幾何屬性,構(gòu)造描述孔洞對應(yīng)缺失區(qū)域的場函數(shù)[2]或隱式曲面[3],并采用等值面抽取的方法進(jìn)行網(wǎng)格化[4],生成對應(yīng)的修復(fù)曲面片。非幾何方法生成的修復(fù)曲面片具有唯一性,不能根據(jù)實(shí)際需要實(shí)現(xiàn)給定連續(xù)性的模型修復(fù),且算法的總體效率較低。②幾何方法中比較具有代表性的是采用基于映射平面[9]或者空間的網(wǎng)格化方法[7]對孔洞邊界進(jìn)行三角化剖分,然后對三角化剖分網(wǎng)格進(jìn)行細(xì)分、優(yōu)化[10]及Reshape調(diào)整得到均勻連續(xù)的修復(fù)曲面片[8,12]。該類算法的關(guān)鍵是對孔洞邊界的三角化剖分和后續(xù)的Reshape處理?；谟成淦矫娴钠史址椒ㄔ谔幚硇螤詈唵蔚目锥催吔鐣r，具有較好的效果，但在處理曲率變化劇烈、形態(tài)復(fù)雜的孔洞時，投影后產(chǎn)生的自相交使剖分結(jié)果出現(xiàn)劇烈“凹陷”。常用的空間三角化剖分方法[7]為NP complete問題,具有O(N3)的復(fù)雜度,不適合處理頂點(diǎn)較多的模型邊界。同時,現(xiàn)有的對修復(fù)曲面片Reshape調(diào)整的方法通?；趶较蚧瘮?shù)[6]、最小化能量函數(shù)[13]和光順?biāo)惴╗8,11]等,難以取得指定連續(xù)性的修復(fù)結(jié)果,對復(fù)雜形態(tài)孔洞修復(fù)的效果較差。

針對現(xiàn)有孔洞修復(fù)方法效率低、修復(fù)結(jié)果單一、不能有效處理復(fù)雜形態(tài)孔洞的問題,本文深入研究分析了在對孔洞邊界進(jìn)行空間三角化剖分時的各種影響因素后，基于局部最優(yōu)化的權(quán)值規(guī)則和曲面最小能量值特性的k階離散歐拉-拉格朗日方程，提出了一種能有效地對復(fù)雜孔洞邊界進(jìn)行Ck-1(k=1，2，3)連續(xù)的三角網(wǎng)格模型修復(fù)算法。本文所提出的修復(fù)算法主要由封閉孔洞邊界的三角化剖分、剖分網(wǎng)格的細(xì)分優(yōu)化以及后續(xù)的Ck-1連續(xù)變形調(diào)整三個步驟組成。

1　孔洞修復(fù)算法及其實(shí)現(xiàn)

1.1符號定義

對網(wǎng)格模型中的任意頂點(diǎn)vi，用NV，1(i)表示頂點(diǎn)vi的一環(huán)鄰域頂點(diǎn)集合，NT,1(i)表示頂點(diǎn)vi的一環(huán)鄰域三角形集合。|NV，1(i)|表示集合中頂點(diǎn)的個數(shù)，|NT，1(i)|表示集合中三角形的個數(shù)。NT,1(i)中的三角形在頂點(diǎn)vi處對應(yīng)的內(nèi)角稱為vi的鄰接內(nèi)角(圖1中的Aj、Ak)，定義A(vi)為NT,1(i)在vi處的鄰接內(nèi)角之和：

(1)

圖1　尖銳棱角對應(yīng)的初始邊界

對網(wǎng)格模型進(jìn)行孔洞修復(fù)時,相應(yīng)符號定義如下:孔洞邊界三角化剖分生成的網(wǎng)格用MC表示；MC細(xì)分、優(yōu)化后生成的網(wǎng)格用MRO表示;MRO進(jìn)行Reshape調(diào)整后生成的最終修復(fù)網(wǎng)格用MF表示。

1.2孔洞邊界的三角化剖分

(1)新增三角形后，待刪除頂點(diǎn)及其一環(huán)鄰域頂點(diǎn)組成的多面體，應(yīng)與周邊網(wǎng)格近似連續(xù)過渡，避免形成尖銳的棱角，使新增的網(wǎng)格表面出現(xiàn)凸凹不平和褶皺。

(2)剖分過程中,應(yīng)避免同一邊界頂點(diǎn)包含過多的鄰接三角形,使剖分結(jié)果產(chǎn)生扭曲。

(3)生成的剖分網(wǎng)格中的邊,應(yīng)均勻地分布在孔洞邊界上。

1.2.1頂點(diǎn)一環(huán)鄰域內(nèi)角因素

當(dāng)頂點(diǎn)vi為網(wǎng)格模型內(nèi)部任意頂點(diǎn)時，A(vi)的大小表示網(wǎng)格模型在該點(diǎn)處的“平坦”度,A(vi)越大，當(dāng)前頂點(diǎn)與其一環(huán)鄰域頂點(diǎn)共面度越大，網(wǎng)格模型內(nèi)部的連續(xù)性越好;A(vi)較小的頂點(diǎn),在模型表面會形成粗糙的特征,不僅影響后續(xù)的模型處理，而且對視覺效果有著不良影響。A(vi)≈2π時，頂點(diǎn)vi的鄰接內(nèi)角?j∈NT,1(i);Aj≈π時,曲面的連續(xù)性發(fā)生劇烈變化。因此應(yīng)避免生成A(vi)較小及存在鄰接內(nèi)角接近于π的新增三角形。

(a)生成尖銳棱角(b)生成內(nèi)角近于π的三角形圖2　新增三角形后生成的非“平坦”情況

1.2.2頂點(diǎn)一環(huán)鄰域三角形因素

1.2.3三角形邊長因素

1.2.4權(quán)值及三角化剖分算法

經(jīng)對孔洞邊界三角化剖分時可能產(chǎn)生影響的因素進(jìn)行綜合分析以及實(shí)際的編程驗證后,權(quán)值Ω及l(fā)less、lbigger相應(yīng)的計算公式如下：

(2)

式中,RC為模型的包圍球半徑。

三角化剖分算法描述如下：

1.3三角化剖分網(wǎng)格的細(xì)分及優(yōu)化

由于三角化剖分網(wǎng)格MC中的邊由BH中的頂點(diǎn)直接連接而成，故需對MC進(jìn)行細(xì)分、優(yōu)化，得到與原始網(wǎng)格模型網(wǎng)格密度相近的曲面片。網(wǎng)格模型的密度通常是由三角形的平均邊長度量的，因此本文采用1-3“面分裂”方法，將邊長較大的三角形△vivjvk按圖3a所示的方式進(jìn)行分裂,新增頂點(diǎn)為三角形的質(zhì)心坐標(biāo)vc,并采用邊交換的方法進(jìn)行優(yōu)化調(diào)整,得到邊長均勻且近似符合Delaunay劃分準(zhǔn)則的曲面片MRO[10](見圖3b、圖3c)。

(a)三角形的細(xì)分、優(yōu)化機(jī)制

(b)三角化剖分網(wǎng)格(c)細(xì)分、優(yōu)化實(shí)例圖3　三角化剖分網(wǎng)格的細(xì)分、優(yōu)化

1.4Ck-1連續(xù)的形狀恢復(fù)

MC經(jīng)過細(xì)分、優(yōu)化后得到的網(wǎng)格MRO仍為邊界和內(nèi)部均為C0連續(xù)的曲面片。為得到在邊界和內(nèi)部符合Ck-1連續(xù)性約束的曲面片,圖形學(xué)領(lǐng)域中,在給定邊界信息和邊界約束條件的情況下，通常采用最小能量定律來實(shí)現(xiàn)曲面片的Ck-1連續(xù)Reshape調(diào)整[12-13]。因用二次函數(shù)表示的能量函數(shù)在求解時有著較高的效率和較好的穩(wěn)定性，故本文基于二次能量函數(shù)的通用表示方式,設(shè)計了一種能實(shí)現(xiàn)Ck-1連續(xù)的Reshape調(diào)整框架，框架的設(shè)計過程如下：

設(shè)S:Ψ→R3為三角網(wǎng)格模型M對應(yīng)的連續(xù)曲面，S*…*表示曲面的k階偏導(dǎo)數(shù),δΨ為曲面的邊界。其對應(yīng)的二次能量函數(shù)為

Ek(S)=∫SFk(Su…u,Su…uv,…,Sv…v)

(3)

通常應(yīng)用變分的方法對等式(3)進(jìn)行求解,以得出對應(yīng)最小能量值特性的歐拉-拉格朗日方程：

(4)

其中,Δ為拉普拉斯算子;bj為具有j(j

當(dāng)用三角網(wǎng)格曲面取代連續(xù)曲面時,式(4)中的拉普拉斯算子對應(yīng)離散為

(5)

其中,S(vi)為頂點(diǎn)一環(huán)鄰域三角形的面積之和；αi j、βi j為邊ei j的對角。k階的拉普拉斯算子通過迭代定義求出：

(6)

對拉普拉斯算子進(jìn)行離散后,式(4)轉(zhuǎn)化為帶有稀疏矩陣的線性方程：

(7)

其中,P=[vp,1vp,2…vp,n]T表示網(wǎng)格模型M的內(nèi)部的自由頂點(diǎn);B=[vb,1vb,2…vb,m]T表示具有Ck-1邊界連續(xù)的約束頂點(diǎn),對應(yīng)為邊界頂點(diǎn)的k-1環(huán)鄰域頂點(diǎn)集合(包含邊界頂點(diǎn))；n、m為對應(yīng)頂點(diǎn)個數(shù)。根據(jù)設(shè)計的變形框架,對優(yōu)化細(xì)分網(wǎng)格MRO中的頂點(diǎn),按照給定的邊界連續(xù)性約束進(jìn)行調(diào)整后得到MF。

2　實(shí)驗分析

2.1剖分算法工作機(jī)理分析

圖4e所示為不考慮鄰接內(nèi)角約束時，對圖4a中孔洞剖分的結(jié)果，圖4f所示為不考慮鄰接三角形個數(shù)約束時，對圖4a中孔洞剖分的結(jié)果。由剖分結(jié)果可知，鄰接內(nèi)角約束主要影響剖分生成的三角片大小，鄰接三角形個數(shù)約束主要影響剖分結(jié)果在孔洞邊界上的均布性。

(a)初始孔洞(b)消除“鋸齒”生成拉合起點(diǎn)

(c)由權(quán)值規(guī)則驅(qū)動閉合孔洞(d)最終剖分結(jié)果

(e)無鄰接內(nèi)角約束剖分結(jié)果(f)無鄰接三角形個數(shù)約束剖分結(jié)果圖4　孔洞剖分機(jī)理分析

孔洞剖分過程中，剖分算法會在多個分支的“交匯處”生成較大的三角形，對多個分支進(jìn)行閉合。

本文所提的權(quán)值規(guī)則使剖分過程近似分為邊界平滑和邊界“拉合”的過程，使得剖分結(jié)果能張緊在孔洞邊界，得到均勻、自然和無扭曲的剖分。

2.2算法效率分析

由于對孔洞邊界采用局部最優(yōu)化的權(quán)值規(guī)則，基于迭代刪除頂點(diǎn)的方法進(jìn)行三角化剖分，三角化剖分階段對應(yīng)的時間復(fù)雜度為線性O(shè)(N)(N為邊界頂點(diǎn)個數(shù))。對三角化剖分網(wǎng)格MC的細(xì)分、優(yōu)化，以得到與原始網(wǎng)格模型密度相近的網(wǎng)格MRO，其對應(yīng)的時間復(fù)雜度為線性O(shè)(M)(M為優(yōu)化細(xì)分后得到的三角形的個數(shù))。在對矩陣的求解階段， 本文采用增量最小二乘求解矩陣的方

法，基于CPU(P4 2.4 GHz)的速率可達(dá)每秒5萬個頂點(diǎn)。因此，本文所提的模型修復(fù)算法，具有較高的效率，且算法的魯棒性較好。

表1顯示了本文算法在對網(wǎng)格模型修復(fù)過程中，生成MC、MRO和MF各步驟所用時間,并與文獻(xiàn)[7-8]的剖分算法進(jìn)行了對比。表1數(shù)據(jù)表明,利用本文的剖分算法對模型進(jìn)行修復(fù)時，剖分效率為每毫秒200～300個頂點(diǎn)，修復(fù)效率為每秒3000～5000個頂點(diǎn)， 適合應(yīng)用于修復(fù)地形、 文物

表1　對模型修復(fù)過程中各步驟所需時間，新生成的頂點(diǎn)(V)/三角形(T)的個數(shù)

等包含海量級數(shù)據(jù)的大尺寸三維模型。

2.3應(yīng)用舉例

本節(jié)對帶有大面積缺失的球模型(圖5a)、牙頜模型(圖5b、圖5c)、 兔子模型(圖5d、圖5e)、

(a)球孔洞模型　(b)牙頜孔洞模型1(c)牙頜孔洞模型2

(d)兔子單個復(fù)雜孔洞模型1(e)兔子單個復(fù)雜孔洞模型2

(f)Pulley單個復(fù)雜孔洞模型1(g)Pulley單個復(fù)雜孔洞模型2圖5　孔洞模型

Pulley上的孔洞(圖5f、圖5g)，進(jìn)行了實(shí)驗分析。

圖6a顯示,采用映射平面剖分時，由于孔洞邊界曲率變化劇烈，模型缺失面積較大，投影后的邊界會產(chǎn)生自交。圖6b為基于映射平面法所生成的修復(fù)結(jié)果，其并不能滿足實(shí)際需要。

(a)邊界在其最小二乘平面上的投影

(b)基于映射平面法的修復(fù)結(jié)果圖6　平面映射平面部分的結(jié)果

(a)齒間孔洞

(b)底部孔洞

(c)兔子孔洞 圖7　本文算法所得剖分結(jié)果

圖7a、圖7b、圖7c顯示,在利用本文算法對孔洞邊界進(jìn)行三角化剖分時，能得到均布在孔洞

邊界上的剖分結(jié)果。

圖8a、圖8b、圖8c為采用文獻(xiàn)[7-8]面積最小化的剖分結(jié)果，剖分過程中沒有對頂點(diǎn)的鄰接三角形個數(shù)和鄰接內(nèi)角進(jìn)行限制，這使得剖分結(jié)果會產(chǎn)生扭曲和生成內(nèi)角接近于π的三角形。

由于對相同的孔洞邊界無論采用何種剖分方法，總會得到具有相同三角形個數(shù)的剖分結(jié)果,因此,對空間孔洞邊界的剖分好壞的判斷標(biāo)準(zhǔn)，即為剖分后生成的邊在孔洞邊界上的均布性。由圖7a、圖7b、圖7c可知，本文算法剖分得出的三角形更為均勻合理。

圖9顯示了利用本文算法，對模型進(jìn)行具有不同邊界連續(xù)性和內(nèi)部連續(xù)性的修復(fù)結(jié)果。圖10、圖11顯示，本文算法可以處理帶有大面積缺失的復(fù)雜孔洞模型，對孔洞的修復(fù)結(jié)果均勻自然。由實(shí)例分析可知，本文算法能實(shí)現(xiàn)對模型不同連續(xù)性的修復(fù)，修復(fù)后的網(wǎng)格密度與原始網(wǎng)格密度相近，能滿足實(shí)際工程的需要。

(a)齒間孔洞

(b)底部孔洞

(c)兔子孔洞圖8　文獻(xiàn)[7-8]算法所得剖分結(jié)果

(c)邊界C1連續(xù)(d)邊界C2連續(xù)圖9　球模型的孔洞修復(fù)

圖11　復(fù)雜Pulley孔洞模型邊界C1連續(xù)修復(fù)結(jié)果

3　結(jié)語

本文深入分析了對三角網(wǎng)格模型孔洞邊界進(jìn)行剖分時的各種影響因素，根據(jù)二維流形網(wǎng)格模型的特性，對剖分過程中由邊界頂點(diǎn)組成的候選三角形進(jìn)行加權(quán)，使得對空間孔洞邊界的剖分轉(zhuǎn)化為邊界平滑和邊界“拉合”的過程，得到成“簾幕”狀均布在孔洞邊界上的三角化剖分網(wǎng)格。對三角化剖分網(wǎng)格進(jìn)行細(xì)分、優(yōu)化后操作后，采用基于能量最小化定律的方法進(jìn)行Reshape調(diào)整，從而實(shí)現(xiàn)具有Ck-1連續(xù)的模型修復(fù)。由最終的修復(fù)模型可知,本文算法能根據(jù)模型的部分信息來恢復(fù)網(wǎng)格模型，可用于網(wǎng)格模型的壓縮。本文算法簡單、易于理解，能處理形狀復(fù)雜、大面積缺失的網(wǎng)格模型孔洞，具有較好的工程應(yīng)用價值。

[1]Attene M,Campen M，Kobbelt L. Polygon Mesh Repairing：an Application Perspective[J].ACM Computing Surveys，2013，45(2)：1-37.

[2]Davis J，Marschner S R，Garr M，et al. Filling Holes in Complex Surfaces Using Volumetric Diffusion[C]//First International Symposium on 3D Data Processing Visualization and Transmission.Padua，Italy，2002：428-441.

[3]Wu X J，Wang M Y，Han B. An Automatic Hole-filling Algorithm for Polygon Meshes[J]. Computer-aided Design and Applications，2008，5(6):889-899.

[4]Zhou K，Gong M，Huang X，et al. Data-parallel Octrees for Surface Reconstruction[J]. IEEE Transactions on Visualization and Computer Graphics,2011,17(5):669-681.

[5]Marchandise E，Piret C,Remacle J F.CAD and

Mesh Repair with Radial Basis Functions[J].Journal of Computational Physics,2012，231(5)：2376-2387.

[6]杜佶，張麗艷，王宏濤，等. 基于徑向基函數(shù)的三角網(wǎng)格曲面孔洞修補(bǔ)算法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2005，17(9)：1976-1982.

Du Ji，Zhang Liyan，Wang Hongtao，et al. Hole Repairing in Triangular Meshes Based on Radial Basis Function[J]. Journal of Computer-Aided Design & Computer Graphics，2005，17 (9)：1976-1982.

[7]Barequet G,Sharir M.Filling Gaps in the Boundary of a Polyhedron [J]. Computer Aided Geometric Design,1995,12(2):207-229.

[8]Liepa P. FillingHoles in Meshes[C]//Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing.Aire-la-Ville,Switzerland，2003：200-205.

[9]Li G，Ye X Z，Zhang S Y. An Algorithm for Filling Complex Holes in Reverse Engineering[J]. Engineering with Computers，2008，24(2)：119-125.

[10]Pfeifle R,Seidel H P.Triangular B-splines for Blending and Filling of Polygonal Holes[C]//Proceedings of the Conference on Graphics Interface. Ontario，Canada,1996:186-193.

[11]韋爭亮,鐘約先,袁朝龍，等. 三角網(wǎng)格大面積孔洞光順修補(bǔ)算法的研究[J]. 中國機(jī)械工程，2008，19(8)：949-954.

Wei Zhengliang，Zhong Yuexian，Yuan Chaolong. Research on Smooth Filling Algorithm of Large Holes in Triangular Mesh Model[J]. China Mechanical Engineering，2008，19(8)：949-954.

[12]Botsch M，Kobbelt L. An Intuitive Framework for Real-time Freeform Modeling[J]. ACM Transactions on Graphics (TOG)，2004，23(3)：630-634.

[13]Bobenko A I，Schr?der P. Discrete Willmore Flow[C]// Eurographics Symposium on Geometry Processing.Aire-la-Ville,Switzerland,2005：101-110.

(編輯張洋)

Mesh Model Restoration for Complex Holes

Yuan Tianran1Cheng Xiaosheng2Sun Quanping1

1.Key Lab of Advanced Manufacturing Technology of Jiangsu Province,Huaiyin Institute of Technology,Huaian,Jiangsu,223003 2.Nanjing University of Aeronautics and Astronautics,Nanjing,210016

In order to meet the practical engineering application needs of complex hole restoration,this paper proposed a robust mesh model restoration architecture with C0～C2continuity based on zipper closure principle and thekorder discrete Euler-Lagrange equation derived from minimizer of the surface energy functional.The final experimental results show that the proposed hole restoration method can deal with complex holes efficiently and correctly.

triangular mesh;hole restoration;complex hole boundary triangulation; hole repairing

2014-05-15

國家自然科學(xué)基金資助項目(51075173)；江蘇省自然科學(xué)基金資助項目(BK2010288)

TP391.72;R783.4DOI：10.3969/j.issn.1004-132X.2015.12.019

袁天然，男，1982年生?；搓幑W(xué)院機(jī)械工程學(xué)院講師、博士。主要研究方向為逆向工程、數(shù)字口腔醫(yī)療裝備。發(fā)表論文10余篇。程筱勝，男，1964年生。南京航空航天大學(xué)機(jī)電學(xué)院教授、博士研究生導(dǎo)師。孫全平，男，1969年生?；搓幑W(xué)院機(jī)械工程學(xué)院教授。