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

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

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

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

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

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

1 基本概念

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

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

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

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

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

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

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

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

2.1 Delaunay三角剖分

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

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

2.2 區(qū)域生長算法

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

2.2.1 種子面片的選取

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

2.2.2 有效三角形的幾何和拓撲約束

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

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

2.2.3 候選三角形的選取

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

圖2 4種拓撲結(jié)構(gòu)

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

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

2.2.4 三角面片的迭代添加

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

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

3 后處理

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

4 實驗結(jié)果

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

表1 幾個實驗模型的實驗數(shù)據(jù)

圖3 一些實驗模型效果

5 結(jié)束語

本文提出的基于Delaunay三角剖分和區(qū)域生長相結(jié)合的對散亂點云進行三角網(wǎng)格重構(gòu)的方法，是在對散亂點云進行三角剖分的基礎上采用區(qū)域生長算法“生長”出三角網(wǎng)格曲面。與其他的區(qū)域生長算法相比，本算法根據(jù)自定義的可接受度因子作為區(qū)域生長過程中迭代添加三角形的判斷標準，可以在一定程度上避免狹長的三角形，提高網(wǎng)格質(zhì)量。通過對一些散亂點云數(shù)據(jù)進行實驗，結(jié)果表明，該算法是快速、穩(wěn)定、有效的。但是，該方法還存在一些缺陷，需要自定義的參數(shù)很多，沒有一個統(tǒng)一的標準，特別是在對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］ 周培德.計算幾何－算法與設計與分析［M］.3版.北京:清華大學出版社，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)格模型的補洞算法研究［J］.計算機應用，2009，29(8):2035 －2037.

(責任編輯魯 進)