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

劉　震，白麗麗，繆永偉

(1．浙江工業(yè)大學(xué) 理學(xué)院，浙江 杭州 310023；2．浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

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

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

(1．浙江工業(yè)大學(xué) 理學(xué)院，浙江 杭州 310023；2．浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

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

關(guān)鍵詞：孔洞修復(fù)；基曲面；特征線；優(yōu)先三角形；擬合二次曲面

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

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

1基于特征線的修復(fù)方法

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

1.1基于切割耳的基曲面構(gòu)建方法

該小節(jié)推廣二維耳切三角化算法[17]，給出一種三維孔洞的剖分方法.利用這種方法得到的基曲面為孔洞區(qū)域提供了網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，這種網(wǎng)格數(shù)據(jù)結(jié)構(gòu)為孔洞區(qū)域進(jìn)一步添加細(xì)節(jié)信息提供了方便.

對于三維模型上的某個(gè)多邊形孔洞P=[p0,p1,…,pn-1]，如果三個(gè)連續(xù)的頂點(diǎn)pi-1,pi,pi+1構(gòu)成的內(nèi)角小于π，那么pi-1,pi,pi+1構(gòu)成P的一個(gè)耳.切割耳就是把Δpi-1pipi+1從多邊形P中移除，移除后的多邊形變?yōu)閇p0,p1,…,pi-1,pi+1,…,pn-1].利用切割耳的方法對孔洞進(jìn)行剖分，首先按逆時(shí)針方向收集模型上某個(gè)孔洞的邊界頂點(diǎn)p0,p1,…,pn-1，得到孔洞P=[p0,p1,…,pn-1].然后利用切割耳對P進(jìn)行剖分，再給出對帶有孔洞的兔子模型的剖分結(jié)果.

1.2基于特征線的細(xì)節(jié)修復(fù)

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

1.2.1特征線的探測與匹配

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

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

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

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

1.2.2孔洞區(qū)域三角形細(xì)分順序的確定

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

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

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

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

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

1.2.3三角形的細(xì)分方法

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

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

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

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

在細(xì)分過程中，如果三角形Δpipjps的平均邊長大于孔洞的邊界邊的平均邊長，就對Δpipjps進(jìn)行細(xì)分.如果細(xì)分之后的三角形為狹長三角形，就把它的邊進(jìn)行翻轉(zhuǎn)以保證得到正規(guī)的網(wǎng)格.為了能夠使孔洞區(qū)域的頂點(diǎn)密度與孔洞周圍的頂點(diǎn)密度一樣，從孔洞邊界開始重復(fù)這一細(xì)分過程直到內(nèi)部三角形的平均邊長低于孔洞邊界的平均邊長.修復(fù)結(jié)果如圖3～5所示.

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

圖4　駱駝的修復(fù)Fig.4　The results of completion of camel

圖5　對零件模型的修復(fù)結(jié)果Fig.5　The results of completion of the machine part

2實(shí)驗(yàn)結(jié)果與討論

提出的基于特征線的修復(fù)算法已經(jīng)在2.3GHz，4GB內(nèi)存i3處理器上利用VisualC++得到了實(shí)現(xiàn),圖3～5給出了幾個(gè)模型的修復(fù)結(jié)果并與Davis[9]和Ju[11]的方法進(jìn)行了比較.

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

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

3結(jié)論

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

參考文獻(xiàn)：

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

[2]呂慧強(qiáng)，李益明，孔繁勝.基于互聯(lián)網(wǎng)的3D復(fù)雜場景渲染算法研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2003,31(1)：36-41.

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

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

[5]徐彩虹，劉志，潘翔，等.一種基于實(shí)例學(xué)習(xí)的三維模型檢索匹配方法[J].浙江工業(yè)大學(xué)學(xué)報(bào)，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]周培德.計(jì)算幾何——算法設(shè)計(jì)與分析[M].3版.北京：清華大學(xué)出版社,2008.

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

(責(zé)任編輯：陳石平)

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A

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

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

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61272309)

收稿日期：2014-12-03