基于Delaunay三角剖分和區(qū)域生長的散亂點(diǎn)云重構(gòu)

王先澤，李忠科，馬亞奇，張曉娟

(第二炮兵工程大學(xué) 401教研室，西安 710025)

近年來，對無規(guī)則點(diǎn)云表示的模型的曲面重構(gòu)已經(jīng)在逆向工程、計(jì)算機(jī)視覺、計(jì)算機(jī)圖形學(xué)和虛擬現(xiàn)實(shí)中得到了廣泛的應(yīng)用。目前解決重構(gòu)問題的方法可以劃分為3種:隱式曲面法、基于Delaunay三角剖分法和區(qū)域生長法。

隱式曲面法首先從點(diǎn)云數(shù)據(jù)中定義一個(gè)帶符號的距離函數(shù)，然后利用該函數(shù)的零值集來近似生成三角網(wǎng)格曲面。Hoppe等［1］提出的重構(gòu)方法就是基于隱式曲面法。但是該方法不能插值點(diǎn)云中的點(diǎn)，在CAD系統(tǒng)中的應(yīng)用受到了限制?；贒elaunay三角剖分法首先通過Delaunay三角剖分或是Voronoi圖從散亂點(diǎn)云數(shù)據(jù)中建立幾何鄰近結(jié)構(gòu)，然后從結(jié)構(gòu)中提取出一些面片來近似表示曲面。該方法很好地建立了散亂點(diǎn)云內(nèi)部的幾何信息，具有很強(qiáng)的魯棒性和系統(tǒng)性。但是由于使用了中間數(shù)據(jù)結(jié)構(gòu)，計(jì)算量大，時(shí)效性比較差。Edelsbrunner等［2］提出的著名的alpha shapes算法和Dey等［3］提出的co-cone算法都屬于基于Delaunay三角剖分的算法。區(qū)域生長算法先初始化一個(gè)三角形作為初始的區(qū)域，然后在區(qū)域的邊界迭代加入三角形生成曲面。比較有代表性的區(qū)域生長算法有 Bernardini等［4］提出的 ball-pivoting算法和最近 Cohen-Steiner［5］提出的基于 Delaunay的貪婪算法。區(qū)域生長算法的優(yōu)點(diǎn)是效率高，缺點(diǎn)是網(wǎng)格的構(gòu)建質(zhì)量過分依賴種子面片的選取以及自定義的參數(shù)，在采樣密度不均勻的情況下容易留下孔洞，需要后續(xù)的孔洞修補(bǔ)算法以構(gòu)建封閉的曲面。

本文提出了一種基于Delaunay三角剖分和區(qū)域生長相結(jié)合的散亂點(diǎn)云重構(gòu)方法，首先計(jì)算采樣點(diǎn)集的Delaunay三角剖分，得到點(diǎn)集的Delaunay剖分結(jié)果，然后用區(qū)域生長算法從中“生長”出三角網(wǎng)格曲面。生長的過程是先初始化一個(gè)三角形作為初始區(qū)域，然后僅在區(qū)域的邊界邊上迭代添加新的三角面片，這樣在迭代的過程中生成的區(qū)域會不斷擴(kuò)展。圖1為實(shí)驗(yàn)?zāi)Ｐ蚳orse的區(qū)域生長過程的展示。與傳統(tǒng)的區(qū)域增長算法相比，本文的算法在區(qū)域生長的過程中使用自定義的可接受度因子作為判斷添加新三角面片的標(biāo)準(zhǔn)，在一定程度上避免了狹長的三角形，提高了網(wǎng)格質(zhì)量。區(qū)域生長完成后，對其中的孔洞進(jìn)行后處理，可使生成的曲面更加完整。

圖1 重構(gòu)模型horse的區(qū)域生長過程

1 基本概念

首先，對本文所用到的一些主要符號作一下簡要說明:P表示所要重構(gòu)的散亂點(diǎn)云數(shù)據(jù)集;S表示重構(gòu)出的三角網(wǎng)格曲面;?S表示區(qū)域生長過程中邊界邊集;t表示三角形;v表示頂點(diǎn);e表示邊;tseed表示選取出的種子面片。

定義1:設(shè)三角形t的外接圓半徑為rt，他是指通過三角形頂點(diǎn)的不包含其他采樣點(diǎn)的最小圓的半徑。

在Voronoi圖中，每個(gè)Voronoi點(diǎn)恰好是三條Voronoi邊的交點(diǎn)［6］。也就是說，Voronoi點(diǎn)是由點(diǎn)集P中3點(diǎn)形成的三角形的外接圓的圓心，因此，三角形t的外接圓半徑rt也可以定義為t的任意一個(gè)頂點(diǎn)到其對偶Voronoi邊的距離。在本算法的計(jì)算過程中所用的就是這個(gè)定義。

在區(qū)域生長算法中，迭代添加三角面片時(shí)通常使用的原則是添加外接圓半徑rt最小的三角形［5］，這樣對于一些狹長但外界圓半徑小的三角形也被添加進(jìn)去，影響生成網(wǎng)格的質(zhì)量。在本算法中，提出了一種新的解決方案，自定義一個(gè)參數(shù)因子可接受度Acceptance(t)作為區(qū)域生長中迭代添加三角面片的標(biāo)準(zhǔn)。

定義2:在區(qū)域生長中，一個(gè)三角形t作為迭代添加的三角形的可接受度Acceptance(t)為

其中:remin表示所有與邊e相關(guān)的三角形的外接圓中的最小半徑;aud(t)是指三角形的最小內(nèi)角與π/3的比值。對散亂點(diǎn)云進(jìn)行三角剖分的時(shí)候，理想狀況就是三角網(wǎng)格的各個(gè)單元都是等邊三角形，但這一目標(biāo)通常難以實(shí)現(xiàn)，通常只能是三角形的最小內(nèi)角最大，這也是判斷網(wǎng)格質(zhì)量的一個(gè)重要標(biāo)準(zhǔn)。三角形t的最小內(nèi)角可以通過aud(t)反映出來。aud(t)越大表示三角形3條邊越均勻，則t的最小內(nèi)角越大，網(wǎng)格質(zhì)量也越好。當(dāng)aud(t)等于1時(shí)，表示三角形為等邊三角形。

權(quán)重α和β的值可以調(diào)整。α越大，表示候選三角形傾向于外接圓半徑最小的三角形;β大則表示對三角網(wǎng)格的質(zhì)量要求較高，但α和β的取值應(yīng)該滿足α+β=1。通過對α和β的取值，當(dāng)2個(gè)三角形的外接圓半徑相差不大時(shí)，可以選取到能使網(wǎng)格質(zhì)量更好的三角形。Acceptance(t)越大，表示該三角形下一次被添加的可能性越高。

2 基于Delaunay和區(qū)域生長的散亂點(diǎn)云重構(gòu)算法

2.1 Delaunay三角剖分

近年來，在曲面重建算法研究領(lǐng)域中，Delaunay三角剖分和Voronoi圖已經(jīng)得到了廣泛的應(yīng)用。一個(gè)三維的Delaunay三角剖分后的結(jié)果就是將采樣點(diǎn)形成一個(gè)四面體的凸包，每個(gè)四面體包含4個(gè)要素:頂點(diǎn)，邊，三角形和四面體。在所形成的四面體中，其外接球內(nèi)都不包含其他的采樣點(diǎn)，這也是使用Delaunay三角剖分對散亂點(diǎn)云進(jìn)行重構(gòu)的一個(gè)重要優(yōu)點(diǎn)［7］。

本文提出的算法是直接使用CGAL算法庫來計(jì)算點(diǎn)云的三維Delaunay三角剖分DT，數(shù)據(jù)結(jié)構(gòu)也是采用CGAL提供的Delaunay三角剖分的數(shù)據(jù)結(jié)構(gòu)。使用CGAL進(jìn)行Delaunay三角剖分采用了逐點(diǎn)插入的算法策略，包括點(diǎn)的定位和正確性檢查等過程。點(diǎn)的定位有2種方法:一種是通過查找與定位點(diǎn)最近的初始點(diǎn)，再由初始點(diǎn)沿一直線搜索定位;另一種是使用一種層次的數(shù)據(jù)結(jié)構(gòu)，隨機(jī)采樣，完成定位。正確性檢查首先檢查三角化數(shù)據(jù)結(jié)構(gòu)的一致性，每個(gè)面與其鄰面具有3個(gè)共點(diǎn)，并具有連續(xù)編號。總的點(diǎn)線面數(shù)量也要做檢查。進(jìn)而更改每一個(gè)體元的朝向，以及頂點(diǎn)凸集的正確性。三角剖分完成后，可以很容易地得到任意的邊或是頂點(diǎn)相鄰的四面體和三角形，這為獲得后面區(qū)域生長中所必需的幾何信息提供了捷徑。

2.2 區(qū)域生長算法

區(qū)域生長方法通常首先從點(diǎn)云數(shù)據(jù)中選定一個(gè)初始三角片，并作為網(wǎng)格曲面的種子面加入三角曲面集，3條邊分別加入邊界集。然后按照一定的規(guī)則從邊界處向三角曲面集中添加新的三角片元素，并實(shí)時(shí)刷新邊界集，通過曲面網(wǎng)格由局部到整體的動態(tài)增長最終生成一張完整的三角網(wǎng)格曲面。

2.2.1 種子面片的選取

區(qū)域生長的第1步就是選取種子三角面片tseed。首先就是從三角剖分后的點(diǎn)集中選出z坐標(biāo)值最大的點(diǎn)vi，然后計(jì)算所有與其相關(guān)的三角形的外接圓半徑rt和角均勻度aud(t)，得到三角形的可接受度Acceptance(t)，選取可接受度最大的三角形作為種子面片，加入到曲面S中。同時(shí)，也將該三角形的3條邊e加入到邊界邊集?S中，作為曲面的邊界邊。另外，種子三角面片tseed的法向量應(yīng)與z軸正方向一致，也就是說，tseed的法線方向與z軸正方向的夾角必須小于π/2。

2.2.2 有效三角形的幾何和拓?fù)浼s束

在本算法中，要求所構(gòu)建出的曲面S必須為封閉的或帶邊界的二維流型，這也是我們希望得到的好的構(gòu)建曲面。在這里，采用文獻(xiàn)［8］中對幾何一致性的證明，通過4種拓?fù)浣Y(jié)構(gòu)得到想要構(gòu)建的流型曲面。假設(shè)e為構(gòu)建曲面S邊界邊，t為e所在的三角形，v為t中與e所對的點(diǎn)，則這4種拓?fù)潢P(guān)系分別為面延伸(v?S)、填充洞(v∈?S，并且v在?S中的2個(gè)鄰點(diǎn)同時(shí)是e的2個(gè)端點(diǎn))、填充耳(v∈?S，并且v在?S中的1個(gè)鄰點(diǎn)是e的端點(diǎn))和粘貼面(v∈?S，但是v在?S中的2個(gè)鄰點(diǎn)都不是e的端點(diǎn))。4種拓?fù)浣Y(jié)構(gòu)如圖2所示，滿足這4種結(jié)構(gòu)之一的都認(rèn)為t是邊e的有效三角形，反之則是無效三角形。

在這4種拓?fù)浣Y(jié)構(gòu)中，面延伸、填充洞和填充耳都不會出現(xiàn)非流型的點(diǎn)或邊，但粘貼面操作后會出現(xiàn)網(wǎng)格僅通過1點(diǎn)相連的情況，在點(diǎn)云噪聲過大且密度較低的區(qū)域執(zhí)行此操作時(shí)可能造成平面不可定向并引起錯(cuò)誤，通常是通過增加附加三角形t'來避免這種情況。添加三角形時(shí)得滿足2個(gè)條件:一是t'中必須有1條邊的端點(diǎn)作為頂點(diǎn)，并且在?S中與v相關(guān)的邊作為對邊;二是加入t和t'后不能導(dǎo)致曲面不可定向。

2.2.3 候選三角形的選取

種子面片選擇好之后，下一步就是按照一定的標(biāo)準(zhǔn)選擇一個(gè)新的三角形加入到構(gòu)建曲面S中。這可以分為2步來完成:首先從?S中的每1條邊界邊e的所有有效三角形中選出候選三角形，然后從所有的候選三角形中選擇出要添加的三角形。

圖2 4種拓?fù)浣Y(jié)構(gòu)

在從邊界邊的有效三角形中選擇候選三角形時(shí)，選取的是可接受度最大的三角形，但是由于有片狀四面體的存在，有可能出現(xiàn)生長方向往回長的情況，從而引起錯(cuò)誤。解決這一問題的方法是對三角形與構(gòu)建曲面間的二面角加以限制。假設(shè)與邊界邊e∈?S相關(guān)的三角形為t，包含在曲面S中的與e相關(guān)的三角形為tb，θt表示t與tb之間法線的夾角的絕對值，αsliver是一個(gè)常數(shù)，則邊界邊e的候選三角形ce可以表示為

式中:t是邊e的有效三角形，并且qt＜asliver。如果邊界邊e的有效三角形中沒有滿足上面條件的，則ce為空。αsliver的取值并不是嚴(yán)格規(guī)定的，在本算法中將其設(shè)置為5π/6。在計(jì)算可接受度Acceptance(t)時(shí)，根據(jù)先驗(yàn)知識，取α=0.8，β=0.2。

2.2.4 三角面片的迭代添加

區(qū)域生長中每次迭代只能將一個(gè)候選三角形添加進(jìn)構(gòu)建曲面S中，文獻(xiàn)［5］中采用貪婪算法，每次都選擇最有可能的候選三角形加入，可以避免前面提出的啟發(fā)式搜索策略在采樣點(diǎn)稀疏時(shí)可能失效的缺陷。本算法在選取要添加的三角形時(shí)，主要是以三角形與曲面S之間的二面角為標(biāo)準(zhǔn)，在采樣密度大的時(shí)候，考慮到曲率問題，二面角越小則曲面質(zhì)量越好。但是，當(dāng)2個(gè)候選三角形與曲面S的二面角都很小或者是有噪聲的時(shí)候，這個(gè)選擇標(biāo)準(zhǔn)就不適用。在這里同樣需要引入可接受度Acceptance(t)，對于那些二面角θt小于1個(gè)常數(shù)θ的三角形t來說，就需要通過他們的可接受度來排列其優(yōu)先級。因此，可以對候選三角形t的優(yōu)先級P(t)作如下定義

當(dāng)t為空集時(shí)，優(yōu)先級P(t)為－∞。根據(jù)實(shí)驗(yàn)，設(shè)置θ=π/6。

3 后處理

在實(shí)際的操作過程中，由于噪聲等因素的干擾，構(gòu)建出來的曲面S通常會含有一些小的孔洞。本文參照文獻(xiàn)［9］中提出的三角網(wǎng)格模型的補(bǔ)洞算法，首先根據(jù)網(wǎng)格中的點(diǎn)、邊和三角形之間的關(guān)系提取孔洞邊界，然后采用最小角度法在孔洞中依次填補(bǔ)三角形，接著對一些新增加的高度彎曲的三角形進(jìn)行細(xì)分操作，最后對修補(bǔ)后的孔洞網(wǎng)格進(jìn)行幾何形態(tài)調(diào)整和曲面光順化。

4 實(shí)驗(yàn)結(jié)果

本算法已經(jīng)用VC++2008在2.8GHz Intel CPU，2G內(nèi)存的計(jì)算機(jī)上編譯實(shí)現(xiàn)。表1為部分模型的實(shí)驗(yàn)數(shù)據(jù)，按類別分為了封閉模型和帶邊界的模型。對于帶邊界的模型，采用啟發(fā)式搜索策略，計(jì)算所有三角面片外接圓半徑的平均值radius_aver，設(shè)置閥值γ，將那些外接圓半徑大于γ倍radius_aver的三角面片刪除。根據(jù)實(shí)驗(yàn)分析，γ取值通常在5～100。圖3為一些重構(gòu)出的實(shí)驗(yàn)?zāi)Ｐ托Ч?/p>

表1 幾個(gè)實(shí)驗(yàn)?zāi)Ｐ偷膶?shí)驗(yàn)數(shù)據(jù)

圖3 一些實(shí)驗(yàn)?zāi)Ｐ托Ч?/p>

5 結(jié)束語

本文提出的基于Delaunay三角剖分和區(qū)域生長相結(jié)合的對散亂點(diǎn)云進(jìn)行三角網(wǎng)格重構(gòu)的方法，是在對散亂點(diǎn)云進(jìn)行三角剖分的基礎(chǔ)上采用區(qū)域生長算法“生長”出三角網(wǎng)格曲面。與其他的區(qū)域生長算法相比，本算法根據(jù)自定義的可接受度因子作為區(qū)域生長過程中迭代添加三角形的判斷標(biāo)準(zhǔn)，可以在一定程度上避免狹長的三角形，提高網(wǎng)格質(zhì)量。通過對一些散亂點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果表明，該算法是快速、穩(wěn)定、有效的。但是，該方法還存在一些缺陷，需要自定義的參數(shù)很多，沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)，特別是在對Acceptance(t)中α和β的取值上，如果β取值過大，則區(qū)域生長的過程中有可能出現(xiàn)添加一些外界圓半徑很大的三角形，使區(qū)域生長不能完成。

［1］ Hoppe H，Derose T，Duchamp T，et al.Surface reconstruction from unorganized points［C］//SIGGRAPH，［S.l.］:［s.n.］，1992:71 －8.

［2］ Amenta N，Bern M，Kamvysselis M.A new Voronoi-based surface reconstruction algorithm［C］//SIGGRAPH，［S.l.］:［s.n.］，1998:415 －21.

［3］ Dey TK，Giesen J，Leekha N，et ct.Detecting boundaries for surface reconstruction using co-cones［C］//Int J Comput Graph CAD/CAM，［S.l.］:［s.n.］，2001(16):141 －59.

［4］ Bernardini F，Mittleman J，Rushmeier H，et al.The ball-pivoting algorithm for surface reconstruction［J］.IEEE Trans Vis Comput Graph，1999，5(4):349 －59.

［5］ David C S.A greedy Delaunay based surface reconstruction algorithm［R］.Research Report，INRIA，2002.

［6］ 周培德.計(jì)算幾何－算法與設(shè)計(jì)與分析［M］.3版.北京:清華大學(xué)出版社，2008:127－128.

［7］ Chuan-Chu Kuo，Hong-Tzong Yau.A Delaunay-based region-growing approach to surface reconstruction from unorganized points［C］//Computer-Aided Design，［S.l.］:［s.n.］，2005(37):825 －835.

［8］ Huang J，Menq C H.Combinatorial manifold mesh reconstruction and optimization from unorganized points with arbittary topology［J］.Computer-Aided Design，2002，34(2):149－165.

［9］ 田建磊，劉旭敏，關(guān)永.三角網(wǎng)格模型的補(bǔ)洞算法研究［J］.計(jì)算機(jī)應(yīng)用，2009，29(8):2035 －2037.

(責(zé)任編輯魯 進(jìn))