基于特征線的三維模型孔洞修復方法

劉　震，白麗麗，繆永偉

(1．浙江工業大學 理學院，浙江 杭州 310023；2．浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

基于特征線的三維模型孔洞修復方法

劉震1，白麗麗1，繆永偉2

(1．浙江工業大學 理學院，浙江 杭州 310023；2．浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

摘要：三維模型的孔洞修復是數字幾何處理中的一個重要問題.首先利用耳切三角化技術，提出了針對三維模型孔洞的一種基曲面構建方法.然后利用孔洞周圍探測得到的特征線的信息來恢復孔洞區域的細節.對于孔洞區域的三角形，根據特征線確定的細分順序進行細分.細分方法是利用三角形的鄰域點的信息和特征線的信息擬合二次曲面，再將三角形的重心投影到擬合的二次曲面上.實驗表明：基于特征線的修復方法能夠較好地捕獲模型的全局特征，并能夠有效恢復孔洞區域的顯著幾何特征，從而獲得較自然的修復效果.

關鍵詞：孔洞修復；基曲面；特征線；優先三角形；擬合二次曲面

The repair methods for hole of three-dimensional model based on feature lines

LIU Zhen1, BAI Lili1, MIAO Yongwei2

(1.College of Science, Zhejiang University of Technology, Hangzhou 310023, China；

2.College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:The repair method for hole of three-dimensional model is an important quesiton in the area of 3D digital geometry processing. A surface-based construction method for 3D model is presented in this paper based on the technique of ear clipping triangulation. The characterisitic lines detected from the region around the hole are used to recover the details of the hole area. According to the order of the feature line, the triangular region of the hole will be subdivided. The subdivided method takes advantage of the information of adjacent points in the triangle region and the information of feature lines to fit conicoid. Then the center of gravity of the triangle is projected onto the fitted conicoid. The experiment results shows that this method based on feature lines can capture the global structure of the model and recover the salient geometric features in the hole patch in a natural way.

Keywords:model repair; base surface; feature lines; prior triangle; quadric surface fitting

隨著三維掃描技術和建模技術的發展，三維數字化模型的應用變得越來越廣泛.但由于掃描技術的限制和模型實體本身的缺陷，獲取的大量的3D模型通常情況下都有孔洞存在.為了方便地對模型進一步進行各類幾何處理操作[1]，如三維渲染[2]，重建[3]，檢索[4-5]等，都需要對模型的孔洞進行修復.現有的修復方法主要分為兩類，即基于體的算法和曲面定向算法[6-8].基于體的算法主要思想是將輸入的待修補模型轉換成體素，然后利用等值面的提取最終實現修復[9-12].這類方法以較低的時間復雜度自動完成修復工作，但是由于網格和體素之間的轉換，會丟失一些原始模型上本有的細節特征.曲面定向的算法一般是直接探測孔洞并對孔洞區域進行修復[13-16].這些算法可以分為兩種.一種是利用平滑的曲面片直接對孔洞區域進行修復.這些方法能快速有效的實現模型修復，但是并不能恢復孔洞的細節特征.另一類是通過尋找與孔洞相似的區域進行修復.對于那些有相似區域的模型，利用這類算法能夠得到一個非常好的修補結果，但是搜索相似區域的過程往往都比較耗時.筆者提出了一種基于特征線的三維孔洞修復方法.該方法的優勢是效率較高，而且能夠恢復孔洞區域的顯著幾何特征.

1基于特征線的修復方法

首先給出三維的耳切三角化的方法構建基曲面.然后，為了盡可能的利用孔洞周圍的特征信息并沿著特征線恢復孔洞區域的細節特征，給出孔洞區域三角形的細分順序和細分方法.

1.1基于切割耳的基曲面構建方法

該小節推廣二維耳切三角化算法[17]，給出一種三維孔洞的剖分方法.利用這種方法得到的基曲面為孔洞區域提供了網格數據結構，這種網格數據結構為孔洞區域進一步添加細節信息提供了方便.

對于三維模型上的某個多邊形孔洞P=[p0,p1,…,pn-1]，如果三個連續的頂點pi-1,pi,pi+1構成的內角小于π，那么pi-1,pi,pi+1構成P的一個耳.切割耳就是把Δpi-1pipi+1從多邊形P中移除，移除后的多邊形變為[p0,p1,…,pi-1,pi+1,…,pn-1].利用切割耳的方法對孔洞進行剖分，首先按逆時針方向收集模型上某個孔洞的邊界頂點p0,p1,…,pn-1，得到孔洞P=[p0,p1,…,pn-1].然后利用切割耳對P進行剖分，再給出對帶有孔洞的兔子模型的剖分結果.

1.2基于特征線的細節修復

為了利用孔洞周圍的幾何特征恢復孔洞區域的特征信息，首先探測和匹配孔洞周圍的特征線.再根據探測到的特征線的信息給出孔洞區域三角形的細分順序.有了這種細分順序，可以沿著特征線為基曲面添加細節特征.對于孔洞區域要細分的三角形，通過把它的重心投影到擬合的二次曲面上對其進行細分.基于特征線的細節恢復過程具體如下.

1.2.1特征線的探測與匹配

首先利用[18]的方法探測孔洞周圍的特征線，然后為探測得到的每一條特征線尋找其最優匹配對.下面給出選擇一條特征線的最優匹配對的衡量標準MP，即

式中：S={si}為孔洞周圍的特征線集合；si為以邊界頂點vi,0為起點有m個采樣點vi,0,…,vi,m的邊界周圍的特征線；aj,t為sj的第t個采樣點vj,t在由si延伸的曲線上的投影，如圖1所示.對于特征線si，能夠使MP(si,sj)最大的sj為它的最優匹配.如果sj的最優匹配對也是si，那么我們稱(si,sj)是一個匹配對.對于特征線匹配對(si,sj)我們用球線性插值u(t)將他們連接起來，即

式中:u0=(vi,0-o)，u1=(vj,0-o)(o是三個點vi,0,vj,0,vi,1所確定圓的中心)；φ為向量u0和u1之間的夾角.

圖1　特征線的匹配Fig.1　Matching of the feature lines

1.2.2孔洞區域三角形細分順序的確定

首先將孔洞區域從邊界到孔洞中心進行分層.以P=[p0,p1,…,pn-1]，為邊界的孔洞區域的第k層的三角形集合Δk為

Δk={Δpipjps|Δpipjps∈Nk(pm)且Δpipjps?

Δk-1,m=0,1,…,n-1}

式中：Δ0=?；Nk(pm)為點pm的k鄰域三角形.

然后在孔洞區域的每一層，根據特征線判斷要先細分的三角形，即優先三角形，就是那些與特征線的起點相連或與匹配對(si,sj)上的點vi,0,vj,0,vi,1,vj,1所擬合的特征平面相交的三角形.這樣確定的孔洞區域三角形的細分順序是從孔洞的第一層到其最后一層，在每一層首先細分優先三角形.

1.2.3三角形的細分方法

一個三角形通過把它的重心向擬合的二次曲面上投影的方法細分為三個三角形.對于某個層的三角形Δpipjps，下面是具體的細分過程.

1) 擬合二次曲面.對于Δpipjpk，用來擬合它的二次曲面的點的選擇方式:① 如果三角形Δpipjps是一個非優先三角形，從三個頂點pi,pj,pk中選擇到其重心G距離較近的兩個點的鄰域頂點來擬合這個三角形相應的二次曲面.② 如果三角形Δpipjpk有一個頂點在特征線上，那么選擇在特征線上的頂點和另外一個到其重心較近的頂點的鄰域頂點擬合二次曲面.③ 如果三角形Δpipjpk是一個與特征平面相交的優先三角形，那么首先選擇在特征平面同側的三角形的兩個頂點，再選擇一個位于球線性插值曲線上到兩個同側頂點的中點的距離最近的點.然后利用兩個同側頂點的鄰域頂點和位于球線性插值曲線上的那個點擬合二次曲面.

2) 重心投影細分三角形Δpipjpk.首先將三角形Δpipjpk的重心G沿著三角形的法線方向n投影到擬合的二次曲面G′上，然后把Δpipjpk細分成為三個三角形ΔpipjG′,ΔpjpkG′和ΔpkpiG′，如圖2所示.

圖2　重心投影細分三角形Fig.2　Refinement of a triangle by projection of centroid

在細分過程中，如果三角形Δpipjps的平均邊長大于孔洞的邊界邊的平均邊長，就對Δpipjps進行細分.如果細分之后的三角形為狹長三角形，就把它的邊進行翻轉以保證得到正規的網格.為了能夠使孔洞區域的頂點密度與孔洞周圍的頂點密度一樣，從孔洞邊界開始重復這一細分過程直到內部三角形的平均邊長低于孔洞邊界的平均邊長.修復結果如圖3～5所示.

圖3　兔子模型的孔洞的修復Fig.3　The results of completion of the rabbit model

圖4　駱駝的修復Fig.4　The results of completion of camel

圖5　對零件模型的修復結果Fig.5　The results of completion of the machine part

2實驗結果與討論

提出的基于特征線的修復算法已經在2.3GHz，4GB內存i3處理器上利用VisualC++得到了實現,圖3～5給出了幾個模型的修復結果并與Davis[9]和Ju[11]的方法進行了比較.

圖3給出了具有33 600個頂點的模型兔子的修復結果.圖3(b)為利用Ju[11]的方法得到的修復結果，運行時間為4s.圖3(c)為利用Davis[9]等的方法修復的結果，運行時間為27s.筆者的方法因為恢復模型的細節特征，所用的時間比Davis[9]和Ju[11]的方法稍微長一些，運行時間為39s.在筆者的修復結果中，兔子的背部和腿部的特征得到了很好的保持，頸部的谷線也得到了很好地恢復.

圖4給出了駱駝模型的修復結果.對于駝峰的修復，筆者的修復結果明顯好于Ju[11]和Liepa[13]的修復結果.圖5給出了零件的修復結果.對于該模型中不同尺度的孔洞，利用筆者的方法使得特征得到了很好地保持，獲得了令人滿意的修復結果.因為圖5中模型的孔洞較大，Davis[9]和Ju[11]這兩種方法都沒有實現對孔洞的修復.

3結論

首先提出了一種構建基曲面的方法.這種方法的時間復雜度是線性的.在構建的基曲面的基礎上，利用孔洞周圍探測得到特征線的信息，給出孔洞區域三角形的細分順序.這種細分順序可以盡可能的利用孔洞周圍的幾何信息，沿著特征線修復孔洞區域的細節.基于特征線的修復方法不會破壞原始網格的數據結構，而且能夠有效的恢復孔洞區域的幾何特征，最終得到令人較滿意的修復結果.

參考文獻：

[1]BOTSCHM,PAULYM,KOBBELTL,etal.Geometricmodelingbasedonpolygonalmeshes[M].NewYork:ACMPress,2007.

[2]呂慧強，李益明，孔繁勝.基于互聯網的3D復雜場景渲染算法研究[J].浙江工業大學學報，2003,31(1)：36-41.

[3]劉培君,陸國棟.基于面識別的三維重建[J].浙江工業大學學報，2000,28(7)：57-63.

[4]馮毅攀，劉志，潘翔，等.一種基于單一視圖的三維模型檢索方法[J].浙江工業大學學報，2012,40(4)：431-436.

[5]徐彩虹，劉志，潘翔，等.一種基于實例學習的三維模型檢索匹配方法[J].浙江工業大學學報，2012,40(3)：326-330.

[6]JUT.Fixinggeometricerrorsonpolygonalmodels:asurvey[J].JournalofComputerScienceandTechnology,2009,24(1):19-29.

[7]ATTENEM,CAMPENM,KOBBELTL.Polygonmeshrepairing:anapplicationperspective[J].ACMComputingSurveys,2013,45(2):33-70.

[8]BOTSCHM,KOBBELTL,PAULYM,etal.Polygonmeshprocessing[M].Bombay:PetersAK,2010.

[9]DAVISJ,MARSCHNERSR,GARRM,etal.Fillingholesincomplexsurfacesusingvolumetricdiffusion[C]//ProceedingsofSymposiumon3DDataProcessingVisualizationandTransmission.Washington:IEEEComputerSociety,2002,428-438.

[10]NOORUDDINF.S,TURKG.Simplificationandrepairofpolygonalmodelsusingvolumetrictechniques[J].IEEETransactionsonVisualizationandComputerGraphics,2003,9(2):191-205.

[11]JUT.Robustrepairofpolygonalmodels[J].ACMTransactionsonGraphics,2004,23(3):888-895.

[12]BISCHOS,KOBBELTL.StructurepreservingCADmodelrepair[J].ComputerGraphForum,2005,24(3):527-536.

[13]LIEPAP.Fillingholesinmeshes[C]//ProceedingsoftheEurographicsSymposiumonGeometryProcessing．Aachen:EurographicsAssociation,2003:200-205.

[14]HARARYG,TALA,GRINSPUNE.Context-basedcoherentsurfacecompletion[J].ACMTransactionsonGraphics,2014,33(1):701-712.

[15]ZHAOW,GAOS,LIH.Arobusthole-fillingalgorithmfortriangularmesh[J].TheVisualComputer,2007,23(12):987-997.

[16]BRECKONTP,FISHERRB.Ahierarchicalextensionto3Dnon-parametricsurfacereliefcompletion[J].PatternRecognition,2012,45(1):172-185.

[17]周培德.計算幾何——算法設計與分析[M].3版.北京：清華大學出版社,2008.

[18]HILDEBRANDTK,POLTHIERK,WARDETZKYM.Smoothfeaturelinesonsurfacemeshes[C]//ProceedingsoftheEurographicsSymposiumonGeometryProcessing．Vienna:EurographicsAssociation,2005:85-90.

(責任編輯：陳石平)

中圖分類號：TP391

文獻標志碼：A

文章編號：1006-4303(2015)03-0346-04

作者簡介：劉震(1976—)，男，河南商丘人，副教授，研究方向為數字幾何處理，E-mail:zhenliu@zjut.edu.cn.

基金項目：國家自然科學基金資助項目(61272309)

收稿日期：2014-12-03