復雜形態孔洞的網格模型修復

袁天然　程筱勝　孫全平

1.淮陰工學院江蘇省先進制造技術重點實驗室,淮安,2230032.南京航空航天大學,南京,210016

復雜形態孔洞的網格模型修復

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

1.淮陰工學院江蘇省先進制造技術重點實驗室,淮安,2230032.南京航空航天大學,南京,210016

為了滿足實際工程應用對復雜形態孔洞修復的需要,模擬拉鏈閉合原理,并基于局部最優化的權值規則和曲面最小能量值特性的k階離散歐拉-拉格朗日方程,提出了一種具有C0～C2連續的網格模型修復架構。實驗結果表明,該孔洞修復架構能有效地對復雜孔洞邊界進行C0～C2連續修復。

三角網格;孔洞修復;復雜孔洞剖分;孔洞修補

0　引言

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

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

1　孔洞修復算法及其實現

1.1符號定義

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

(1)

圖1　尖銳棱角對應的初始邊界

對網格模型進行孔洞修復時,相應符號定義如下:孔洞邊界三角化剖分生成的網格用MC表示；MC細分、優化后生成的網格用MRO表示;MRO進行Reshape調整后生成的最終修復網格用MF表示。

1.2孔洞邊界的三角化剖分

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

(2)剖分過程中,應避免同一邊界頂點包含過多的鄰接三角形,使剖分結果產生扭曲。

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

1.2.1頂點一環鄰域內角因素

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

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

1.2.2頂點一環鄰域三角形因素

1.2.3三角形邊長因素

1.2.4權值及三角化剖分算法

經對孔洞邊界三角化剖分時可能產生影響的因素進行綜合分析以及實際的編程驗證后,權值Ω及lless、lbigger相應的計算公式如下：

(2)

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

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

1.3三角化剖分網格的細分及優化

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

(a)三角形的細分、優化機制

(b)三角化剖分網格(c)細分、優化實例圖3　三角化剖分網格的細分、優化

1.4Ck-1連續的形狀恢復

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

設S:Ψ→R3為三角網格模型M對應的連續曲面，S*…*表示曲面的k階偏導數,δΨ為曲面的邊界。其對應的二次能量函數為

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

(3)

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

(4)

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

當用三角網格曲面取代連續曲面時,式(4)中的拉普拉斯算子對應離散為

(5)

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

(6)

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

(7)

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

2　實驗分析

2.1剖分算法工作機理分析

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

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

(c)由權值規則驅動閉合孔洞(d)最終剖分結果

(e)無鄰接內角約束剖分結果(f)無鄰接三角形個數約束剖分結果圖4　孔洞剖分機理分析

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

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

2.2算法效率分析

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

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

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

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

等包含海量級數據的大尺寸三維模型。

2.3應用舉例

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

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

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

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

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

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

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

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

(a)齒間孔洞

(b)底部孔洞

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

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

邊界上的剖分結果。

圖8a、圖8b、圖8c為采用文獻[7-8]面積最小化的剖分結果，剖分過程中沒有對頂點的鄰接三角形個數和鄰接內角進行限制，這使得剖分結果會產生扭曲和生成內角接近于π的三角形。

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

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

(a)齒間孔洞

(b)底部孔洞

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

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

圖11　復雜Pulley孔洞模型邊界C1連續修復結果

3　結語

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

[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]杜佶，張麗艷，王宏濤，等. 基于徑向基函數的三角網格曲面孔洞修補算法[J]. 計算機輔助設計與圖形學學報，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]韋爭亮,鐘約先,袁朝龍，等. 三角網格大面積孔洞光順修補算法的研究[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

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

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

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