結(jié)合Delaunay三角面分離法與搜索球策略的三維曲面重建算法

袁清洌，吳學(xué)群

?

結(jié)合Delaunay三角面分離法與搜索球策略的三維曲面重建算法

袁清洌1，吳學(xué)群2

(1. 攀枝花學(xué)院土木與建筑工程學(xué)院，四川 攀枝花 617000；2. 昆明理工大學(xué)國(guó)土資源工程學(xué)院，云南 昆明 650093)

基于曲面重建在計(jì)算機(jī)圖形學(xué)、三維GIS、逆向工程等領(lǐng)域有重要應(yīng)用，結(jié)合區(qū)域生長(zhǎng)法與Delaunay三角剖分的優(yōu)勢(shì)，提出了一種新的散亂點(diǎn)云曲面重建算法。首先根據(jù)曲面中軸性質(zhì)提出了分離角定義并推導(dǎo)了相關(guān)結(jié)論，利用局部Delaunay三角形分離角性質(zhì)抽取大量位于模型表面三角形，從而構(gòu)建種子三角網(wǎng)增加初始區(qū)域的生長(zhǎng)面積其次運(yùn)用自適應(yīng)搜索球法加快鄰域三角形搜索并識(shí)別曲面邊界。對(duì)比傳統(tǒng)的基于Delaunay法和傳統(tǒng)區(qū)域生長(zhǎng)法，該方法只需要一次三角剖分，無需極點(diǎn)與法向量計(jì)算，重建速度快，具有Delaunay三角網(wǎng)格的優(yōu)良結(jié)構(gòu)特性，孔洞數(shù)量少，重建出的三維模型幾何信息與拓?fù)潢P(guān)系準(zhǔn)確。實(shí)驗(yàn)表明，結(jié)合Delaunay三角剖分與區(qū)域生長(zhǎng)法重構(gòu)有向的流形三角網(wǎng)格模型，能夠提高三維模型的重建效果與速度，有效地自動(dòng)識(shí)別曲面邊界。

表面重建；點(diǎn)云；Delaunay；分離角；區(qū)域生長(zhǎng)

近幾十年來，隨著三維激光掃描系統(tǒng)的不斷完善，基于三維點(diǎn)云數(shù)據(jù)的曲面重建在計(jì)算機(jī)圖形學(xué)領(lǐng)域受到了廣泛關(guān)注和大量的研究，同時(shí)三維模型也在逆向工程、地理信息領(lǐng)域、數(shù)字礦山和醫(yī)療等領(lǐng)域有許多應(yīng)用[1-5]。

曲面重建已經(jīng)有很多算法，主要分為隱式法和顯式法。隱式法主要有基于徑向基函數(shù)(radial basis function，RBF)法、移動(dòng)最小二乘法(moving least squares，MLS)、B樣條曲面(non-uniform rational b-splines，NURBS)，泊松曲面法(Poisson)等[6-9]。此類算法需要正確的估算每個(gè)點(diǎn)的法向量，計(jì)算量較大。顯式法主要是網(wǎng)格生長(zhǎng)法和基于Voronoi圖和Delaunay三角剖分的方法。前者比較典型的算法是BERNARDINI等[10]提出的球轉(zhuǎn)法，類似的方法還有王楠[11]提出的球擴(kuò)張法。網(wǎng)格生長(zhǎng)過程中，HUANG和MENQ等[12]從擴(kuò)展邊端點(diǎn)的K鄰域內(nèi)選擇最佳候選點(diǎn)；陳金瑞[13]構(gòu)建評(píng)價(jià)函數(shù)來選取候選點(diǎn)?？傮w來說運(yùn)用網(wǎng)格生長(zhǎng)法能夠較快的生長(zhǎng)出曲面，但是重建結(jié)果過度依賴于種子三角形的選取。后者算法中有EDELSBRUNNER等[14]提出-shape算法；AMENTA等[15]提出的Crust、Powercrust、Cocone算法[16]以及改進(jìn)算法；DEY和GOSWAMI[17]提出的處理有噪聲點(diǎn)數(shù)據(jù)的Tightcocone算法。此類算法在一些尖銳特征和邊界區(qū)域重建效果不好，而且會(huì)涉及到兩次三角剖分，導(dǎo)致算法復(fù)雜度較高，重建的表面是非流形的需要后續(xù)的流形提取。近幾年一些學(xué)者用貪婪投影算法構(gòu)建三角網(wǎng)，將三維點(diǎn)云投影到二維平面內(nèi)進(jìn)行Delaunay三角化，重建速度快但是構(gòu)建的網(wǎng)格會(huì)出現(xiàn)拓?fù)浣Y(jié)構(gòu)錯(cuò)誤和狹長(zhǎng)三角面[18]。對(duì)比顯式法曲面重建，基于隱式曲面重建法需要對(duì)采樣點(diǎn)進(jìn)行擬合估計(jì)，重建的曲面不一定會(huì)經(jīng)過采樣點(diǎn)，導(dǎo)致重建結(jié)果不夠精確。

本文提出一種基于Delaunay三角剖分和區(qū)域生長(zhǎng)法首先對(duì)采樣點(diǎn)進(jìn)行Delaunay四面體化，然后計(jì)算Delaunay三角面的分離值，抽取位于實(shí)體表面三角形構(gòu)建種子三角網(wǎng)。根據(jù)區(qū)域生長(zhǎng)法的生長(zhǎng)規(guī)則，從Delaunay四面體中抽取剩余的三角形從而生長(zhǎng)出完整的三維曲面模型。生長(zhǎng)過程中從種子三角網(wǎng)開始，通過構(gòu)建搜索范圍球過濾掉不符合的三角面并根據(jù)分離值選取最優(yōu)三角面，不斷地添加新的三角形到生長(zhǎng)區(qū)域完成生長(zhǎng)過程。該算法既結(jié)合了Delaunay三角網(wǎng)優(yōu)良特性，又有區(qū)域生長(zhǎng)法的優(yōu)勢(shì)。

1 Delaunay三角面的分離條件

1.1 點(diǎn)云數(shù)據(jù)的采樣密度與中軸性質(zhì)

本文是基于散亂點(diǎn)云進(jìn)行三維重建的，而用散亂點(diǎn)集來表示一個(gè)曲面必須具有一定的密度才能表達(dá)曲面上的幾何特征信息。AMENTA等[15]提出的密度樣本稱為-sample采樣，由此進(jìn)一步提出了一個(gè)重要概念：中軸(medial-axis)。在維空間R中存在一個(gè)曲面對(duì)應(yīng)的中軸面，定義中任意一點(diǎn)到曲面歐氏距離最短的點(diǎn)有兩個(gè)或兩個(gè)以上。如圖1所示，曲線與曲面中軸的例子。在曲面上任意點(diǎn)與其最近鄰域點(diǎn)的歐氏距離為，點(diǎn)到中軸最短的歐氏距離為()，將()稱為點(diǎn)的局部特征尺度，當(dāng)0<<1時(shí)，≤·()。

圖1 曲線與曲面中軸

1.2 Delaunay圓/球的分離角

圖2(a)表示某曲線的局部區(qū)域內(nèi)：點(diǎn)為一采樣點(diǎn)集={P|=1,2,3,···,}，點(diǎn)P所在的Delaunay三角區(qū)域中，假設(shè)P2和P+5為點(diǎn)P的最鄰近點(diǎn)，而P1，P3，P4為相對(duì)曲線的非鄰近采樣點(diǎn)并將其作為參考點(diǎn)，對(duì)采樣點(diǎn)Delaunay三角剖分后的三角形為圖2(b)所示。V~V4為Voronoi點(diǎn)也是對(duì)應(yīng)Delaunay圓的圓心。每一條Delaunay邊有且僅有兩個(gè)Delaunay圓，如P，P1對(duì)應(yīng)圓V和V1。三維空間中每個(gè)Delaunay三角面有且僅有兩個(gè)Delaunay球?qū)?yīng)。定義Delaunay圓分離角如下：

定義1. 在二維平面內(nèi)，對(duì)采樣點(diǎn)集進(jìn)行Delaunay三角剖分；若P與P構(gòu)成一條Delaunay邊，則通過邊PP所在的Delaunay圓中，若V與V為兩圓的圓心，將角∠VPV稱為一組Delaunay圓的分離角，用角表示，?(0,p)。如圖2(a)中的Delaunay圓V與V1的分離角∠VPV1。

在三維空間中的Delaunay四面體的分離角也有類似的定義如下：

1.3 分離角的閾值與分離條件

在二維平面內(nèi)若采樣點(diǎn)滿足-sample采樣條件分離角出現(xiàn)如下情況：

結(jié)論1. 當(dāng)0<<1時(shí)任意一點(diǎn)P與最鄰近點(diǎn)構(gòu)成Delaunay圓的分離角大于120°小于180°。

證明. 如圖2(a)中邊PP2的分離角∠V1PV3設(shè)為，連接點(diǎn)V1V3，根據(jù)圓相交弦的性質(zhì)構(gòu)成的Voronoi邊垂直平分邊PP+2。則設(shè)角∠V1PP21，∠V3PP2=2，則=1+2。因?yàn)閏os(1)=(PP+2)/2PV+1，根據(jù)-sample采樣條件與中軸性質(zhì)，即當(dāng)0<1時(shí)，PP2=dp，PV1=(f1)，且dp≤·LFS(f1)，所以60°<1<90°。

同理可證60°<2<90°，所以120°<<180°。

結(jié)論2.在二維平面中當(dāng)0<0.765時(shí)點(diǎn)云分布密集，非最鄰近點(diǎn)的分離角0<≤90°；當(dāng)0.765≤<1時(shí)，點(diǎn)云分布較稀疏，大部分非鄰近點(diǎn)的分離角0<≤90°；少量的分離角為90°<≤120°。

證明. 任意一點(diǎn)P與非最鄰近點(diǎn)構(gòu)成Delaunay邊的分離角會(huì)出現(xiàn)兩種情況；第一種是如圖2(a)中的分離角，此時(shí)所有非最鄰近點(diǎn)的一組Delaunay圓心落在兩圓之間的相交區(qū)域，點(diǎn)V與V1距離d1小于圓半徑VP和V1P，所以根據(jù)余弦定理可判斷0<<60°；若只有一個(gè)圓心落在兩圓相交區(qū)域內(nèi)時(shí)，0<<90°。第二種情況是圓心都落在相交區(qū)域外部，分離角數(shù)為3，若3個(gè)最鄰近點(diǎn)123構(gòu)成Delaunay三角形，由結(jié)論1中同樣的方法可推斷0°<≤120°。若3個(gè)最鄰近點(diǎn)沒有構(gòu)成Delaunay三角形又會(huì)出現(xiàn)圖2(a)的情況，此時(shí)點(diǎn)P的鄰域內(nèi)分離角的個(gè)數(shù)將大于3，顯然在點(diǎn)P的所有分離角和為360°，而兩個(gè)最鄰近點(diǎn)構(gòu)成的分離角大于120°，所以非最鄰近點(diǎn)的分離角至多有一個(gè)大于90°。

綜上所述，可用分離角來衡量Delaunay球(圓)之間的相交程度。當(dāng)點(diǎn)云密集時(shí)位于曲面上的Delaunay三角形和非曲面上三角形的分離角大小有顯著的差異，位于曲面上的三角面的分離角較大，曲面內(nèi)分離角較小，顯然三角面的分離值越小越有可能位于曲面上。如圖2(b)中點(diǎn)1、2和3分別為邊PP、PP和PP的中點(diǎn)，為了能快速求解分離值，本文根據(jù)克萊姆法則解算線性方程。根據(jù)Delaunay剖分與Voronoi圖的性質(zhì)，點(diǎn)v和v為Delaunay四面體外接球球心；由點(diǎn)P、P、P和P的坐標(biāo)可得點(diǎn)1、2和3的坐標(biāo)為

根據(jù)空間幾何性質(zhì)可得方程

根據(jù)克萊姆法則得到v點(diǎn)坐標(biāo)

同理可得到v點(diǎn)坐標(biāo)，則根據(jù)余弦定理可得分離值

由上述分離角特點(diǎn)可以得到Delaunay圓的分離條件，一組Delaunay圓的分離角的余弦值cos()作為分離值，cos(0)作為分離閾值。每一個(gè)三角形都對(duì)應(yīng)一個(gè)分離值，因此設(shè)定閾值0將Delaunay圓相交程度小的Delaunay三角形分離出來作為種子三角形，若點(diǎn)云稀疏可以降低0。位于凸殼上的三角形沒有分離角，則分離值設(shè)為-1。

由二維推廣到三維空間的情況基本相同，不同之處在于剖分后有一些較扁平的四面體在曲面附近，此時(shí)Voronoi點(diǎn)將遠(yuǎn)離中軸靠近曲面附近，此時(shí)曲面上鄰近點(diǎn)的分離角可能出現(xiàn)銳角[15]，無法將三角面完全分離出來，因此本文通過網(wǎng)格生長(zhǎng)法進(jìn)一步完善后續(xù)的抽取。

2 算法描述

步驟1.計(jì)算散亂點(diǎn)云的Delaunay四面體剖分，構(gòu)建數(shù)據(jù)結(jié)構(gòu)。

步驟2. 構(gòu)建種子三角網(wǎng)，初始化GT()與Efront()。

步驟2.1.計(jì)算三角形的分離值，從DT()中篩選出分離值小于cos(0)的Delaunay三角形作為種子三角網(wǎng)seed，將seed中的邊界邊加入到Efront()中，將標(biāo)記為GT()。

步驟2.2.選取Efront()中任意一條邊，并確定所在的三角形集合Tinc()。

步驟3. 構(gòu)建搜索球篩選候選三角形。

步驟3.1. 對(duì)于邊構(gòu)建一個(gè)搜索球SearchBall()，遍歷Tinc()的所有候選點(diǎn)，將不在搜索球范圍的候選點(diǎn)所在的Delaunay三角形在Tinc()中標(biāo)記為無效，將Tinc()中有效的作為最優(yōu)候選三角形集合Canp()。

步驟4.進(jìn)行區(qū)域生長(zhǎng)過程。

步驟4.2.依次遍歷pct的3條邊，檢核pct與其鄰接三角形之間的拓?fù)潢P(guān)系，如果滿足條件則進(jìn)行。

步驟4.3.否則返回步驟3.1，并且在Efront()中將邊標(biāo)記為無效。

步驟4.4.將pct標(biāo)記為GT()，并更新Efront()與?，否則返回到步驟4.1。

步驟5.重復(fù)步驟2.2~4.3，直到Efront()有效為空。輸出標(biāo)記為GT()三角網(wǎng)格。

2.1 網(wǎng)格區(qū)域生長(zhǎng)的初始化

2.1.1 種子三角網(wǎng)的構(gòu)建

根據(jù)步驟1中對(duì)散亂點(diǎn)的Delaunay四面體剖分結(jié)果，依次遍歷所有三角形，計(jì)算每個(gè)三角形的分離值cos()；根據(jù)1.3節(jié)推導(dǎo)的結(jié)論將-1)≤cos(0)的三角形選出。本文取0=5π/6，得到seed三角網(wǎng)。大量位于曲面上的三角形seed被篩選出來，相比其他傳統(tǒng)生長(zhǎng)法能增加初始區(qū)域生長(zhǎng)面積和生長(zhǎng)邊長(zhǎng)度，加快曲面的生長(zhǎng)速度。將所有seed中只有一個(gè)seed的邊標(biāo)記為Efront()，作為區(qū)域生長(zhǎng)邊集合。

2.1.2 自適應(yīng)搜索球

運(yùn)用這種搜索法的原因在于：

(1) 由于散亂點(diǎn)云數(shù)據(jù)三角剖分后，每條邊的三角面可能有多個(gè)，需要確定一個(gè)范圍從中尋找滿足幾何與拓?fù)湫畔⒆顑?yōu)的一個(gè)三角面。

(2) 點(diǎn)云數(shù)據(jù)密度不一定均勻，特別是散亂點(diǎn)集，如果沒有合理的網(wǎng)格生長(zhǎng)條件容易導(dǎo)致在生長(zhǎng)過程中出現(xiàn)孔洞。

(3) 對(duì)于非封閉型曲面以及形狀結(jié)構(gòu)復(fù)雜的和一些單側(cè)曲面的邊界需要識(shí)別。

因此，本文構(gòu)建了基于生長(zhǎng)邊的自適應(yīng)搜索球SearchBall()來優(yōu)化最優(yōu)的候選三角形pct的搜索范圍。每次搜索過程中根據(jù)局部區(qū)域點(diǎn)云密度動(dòng)態(tài)的改變搜索半徑大小快速篩選候選三角形。如圖3所示，以一條生長(zhǎng)邊所在的種子三角形seed()為基準(zhǔn)，以生長(zhǎng)邊為搜索球的一條固定弦；半徑為()，搜索中心點(diǎn)()與三角形seed()在同一個(gè)平面上。三角形seed()的邊的兩個(gè)端點(diǎn)為7，8，第3個(gè)頂點(diǎn)為2。

;

圖3 搜索球范圍與搜索方向

2.1.3 候選三角形

對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行三維Delaunay剖分后，在Efront()中的每一條邊界邊都有若干個(gè)相連三角形。本文用Tinc()代表邊的鄰接三角形集合，其中Tinc()一個(gè)三角形為tinc()，Canp()為候選三角形集合，用Canp()表示Canp()中候選點(diǎn)。令seed()表示邊所在的種子三角形(seed()?seed，()?Tinc())，其中的兩個(gè)端點(diǎn)為1和2；令(tinc()，())為tinc與()之間的二面角，且tinc()1()。某些情況下，三維的Delaunay四面體剖分會(huì)出現(xiàn)扁平四面體，導(dǎo)致(tinc()，())值非常小。在許多曲面重建的算法中用類似flat的參數(shù)來處理扁平四面體[11-12]，在本文中flat的值設(shè)為π/6。將一組候選三角形Canp()可以通過邊界邊Efront()獲取，候選三角形和候選點(diǎn)可定義為：Canp()={?Tinc()，1()|()≤()且(tinc()，())>flat}；Canp()={?v，11，2|v為Canp()中的頂點(diǎn)}。

根據(jù)2節(jié)提出的結(jié)論，分離角度越大的越有可能為曲面上的三角面。因此，Canp()中的三角形按照分離角由大到小進(jìn)行排序，得到一個(gè)優(yōu)先隊(duì)列，然后每次選取分離角度最大的三角形作為pct進(jìn)行拓?fù)錂z核。若滿足條件則pct放入到GT()中，如果不滿足則從隊(duì)列中選擇下一個(gè)pct，并在Canp()中將上一個(gè)pct標(biāo)記為無效。

2.2 區(qū)域生長(zhǎng)與拓?fù)錂z查

在2.1節(jié)中介紹的方法可以通過自適應(yīng)搜索球策略完成最優(yōu)候選三角形pct的選取。但是在pct標(biāo)記為GT()之前，為了確保網(wǎng)格曲面是一個(gè)有向的流形網(wǎng)格得到一個(gè)最優(yōu)化的曲面模型，需要持續(xù)地對(duì)pct進(jìn)行局部的拓?fù)錂z查。如圖4所示，首先候選點(diǎn)Canp()的屬性狀態(tài)會(huì)出現(xiàn)4種情況：①Canp()?Efront()，此時(shí)候選點(diǎn)可能位于?上，也能為位于GT()內(nèi)；②Canp()?Efront()，同時(shí)在Efront()中點(diǎn)的最近的兩個(gè)鄰域點(diǎn)均為的一個(gè)端點(diǎn)，此時(shí)局部生長(zhǎng)區(qū)域呈現(xiàn)出一個(gè)三角形小孔洞；③Canp()?Efront()，同時(shí)點(diǎn)的最近的兩個(gè)鄰域點(diǎn)中只有一個(gè)點(diǎn)為的端點(diǎn)；④Canp()?Efront()，點(diǎn)沒有最近的鄰域點(diǎn)為的端點(diǎn)。

根據(jù)以上Canp()的屬性狀態(tài)對(duì)三角網(wǎng)格進(jìn)行拓?fù)錂z查。首先判斷Canp()的屬性，如果Canp()?Efront()，對(duì)pct的邊進(jìn)行判斷，若pct其他兩條非生長(zhǎng)邊通過搜索球進(jìn)行判斷，若兩邊都沒有候選三角形，則此三角形為一個(gè)孤立三角形不能標(biāo)記為GT()。若Canp()?Efront()，對(duì)于pct的拓?fù)錂z核主要體現(xiàn)在：①形插入的pct能確保GT()是流形三角網(wǎng)；②重建的曲面要確保在其法線方向是有向的，否則模型在光照渲染后會(huì)出現(xiàn)模型顏色明暗變化不統(tǒng)一。因此當(dāng)pct的邊放入到Efront()時(shí)，需要對(duì)邊的方向進(jìn)行檢核，確保兩個(gè)三角形是相容的。

每一條邊關(guān)聯(lián)的三角面確保是流形的，即不能被3個(gè)或3個(gè)以上的三角形共用，如圖4(e)所示。本文創(chuàng)建數(shù)據(jù)結(jié)構(gòu)edt((i, j))進(jìn)行判斷。初始化edt((i, j))=0，若edt(e)=0，表明此邊是新邊放入Efront()中，否則表明此邊已有，則令edt(e)=1；若判斷edt(e)>0且edt(e)>0，表明此邊不可被加入其他。對(duì)于三角網(wǎng)的候選點(diǎn)也要持續(xù)進(jìn)行檢查。如圖4(e)所示，pct的一個(gè)頂點(diǎn)連接到了相對(duì)曲面內(nèi)部的一點(diǎn)，導(dǎo)致自相交三面的出現(xiàn)。如果pct存在拓?fù)潢P(guān)系錯(cuò)誤則pct被排除不能標(biāo)記為GT()。

3 實(shí)驗(yàn)分析

本文提出的算法用C語言和Matlab-2011a混合編程完成，其他經(jīng)典算法用Meshlab軟件實(shí)現(xiàn)，貪婪投影三角化算法(GPT)用PCL點(diǎn)云算法庫(kù)完成[18]，程序運(yùn)行環(huán)境為L(zhǎng)enovo Windows 7筆記本，處理器為Intel(R) Core(TM) i5-2410M CPU, 2.3 GHz，安裝內(nèi)存(RAM) 4 GB，64位操作系統(tǒng)。

實(shí)驗(yàn)中的點(diǎn)云模型數(shù)據(jù)介紹，Goaf為一采空區(qū)點(diǎn)云模型，由Riegl-VZ-4000三維激光掃描儀完成。平均長(zhǎng)為417.05 m；寬58.961 5 m；高為579.845 m；點(diǎn)集數(shù)為1 284 636。Angel等其他的點(diǎn)云模型來自于斯坦福大學(xué)點(diǎn)云數(shù)據(jù)庫(kù)、Aimatshape圖形庫(kù)和3Dlodbook點(diǎn)云數(shù)據(jù)庫(kù)，這些數(shù)據(jù)均是去噪后的光滑點(diǎn)云模型。

曲面網(wǎng)格重建的效果根據(jù)三角化速率和生成的網(wǎng)格質(zhì)量進(jìn)行評(píng)估，二者受到三角網(wǎng)格的正則度、網(wǎng)格拓?fù)浣Y(jié)構(gòu)、孔洞數(shù)量等方面的影響。本文生成的網(wǎng)格的正則度用BèCLET等[19]提出的()質(zhì)量因子進(jìn)行評(píng)估，即

其中，d是一個(gè)三角面的第條邊長(zhǎng)。()為所有三角面∑(t)的平均值，其值域?yàn)閇0,1]，(t)值從0到1，表示三角面從空面到接近一個(gè)等邊三角形邊長(zhǎng)比例的變化程度。()值越接近1表明三角網(wǎng)格接近正三角網(wǎng)的程度越高，曲面的重建結(jié)果越好；()值越小表明三角網(wǎng)有較多的狹長(zhǎng)三角面，網(wǎng)格的質(zhì)量較差，曲面的幾何特征信息不夠豐富。對(duì)于拓?fù)浣Y(jié)構(gòu)的檢核有以下3種指標(biāo)：

(1) 非流形頂點(diǎn)n：由一個(gè)三角面的頂點(diǎn)構(gòu)成的傘形區(qū)域多余一個(gè)；

(2) 非流行邊n：構(gòu)成一條邊的三角面多于兩個(gè)；

(3) 孔洞個(gè)數(shù)n：沒有構(gòu)建網(wǎng)格的區(qū)域，本文將非邊界的孔洞為作為沒有構(gòu)建三角網(wǎng)格的區(qū)域。

表1中的數(shù)據(jù)為算法各部分的運(yùn)行時(shí)間，本文算法三角化的平均速度為16 196.0 t/s；Cocone平均速度為11 965.2 t/s；BPA算法平均速度為21 600.6 t/s；Poisson平均速度為10 645.7 t/s；GPT算法的平均速度為18 425.4 t/s，由此可以看出本文算法在速度上優(yōu)于Cocone和Poisson算法，但是沒有BPA算法與GPT算法重建快。表2、3數(shù)據(jù)可以看出本文算法的網(wǎng)格是流形的，且孔洞數(shù)量很少，而BPA與GPT算法卻出現(xiàn)了較多的孔洞。對(duì)于點(diǎn)云分布不規(guī)則的數(shù)據(jù)，Cocone、BPA和GPT算法出現(xiàn)了拓?fù)浣Y(jié)構(gòu)錯(cuò)誤部分網(wǎng)格是非流形的，且孔洞數(shù)量較多。在網(wǎng)格正則度方面本文算法()值高于其他算法，Cocone和本文算法都是建立在Delaunay四面體構(gòu)建的()值比較接近，但是BPA算法重建的網(wǎng)格()值相對(duì)較低，而且對(duì)于分布不均，密度較低的點(diǎn)云數(shù)據(jù)重建的曲面效果不好，甚至無法重建完整的三維模型，如Block、Goaf和Mannequin。Poisson算法在非閉合型曲面會(huì)重建出閉合面，且重建的幾何細(xì)節(jié)特征與本文方法相比不夠鮮明(圖5)。

表1 算法運(yùn)行速率

表2 網(wǎng)格質(zhì)量檢測(cè)對(duì)比

表3 網(wǎng)格質(zhì)量檢測(cè)對(duì)比

圖5 Goaf點(diǎn)云曲面三角網(wǎng)

圖6顯示了閉合型曲面模型和非閉合的兩類復(fù)雜三維曲面模型在不同時(shí)刻中重建結(jié)果。重建過程中，初始化階段構(gòu)建的種子三角網(wǎng)大約占40%~70%，其余部分是通過網(wǎng)格生長(zhǎng)法提取的，由此可見通過分離值的篩選可以分離出大部分的表面三角形，為后續(xù)抽取節(jié)省了時(shí)間。圖5在Matlab三維圖形窗口中展示了在光照渲染后點(diǎn)云曲面模型和重建出的三維曲面在不同方法中的重建結(jié)果，從圖5可看出，由于局部點(diǎn)云數(shù)據(jù)采樣不充分，導(dǎo)致在地表起伏較大的褶皺地帶在BPA、Cocone和GPT算法中出現(xiàn)孔洞較多，如圖中橢圓標(biāo)記的區(qū)域，Cocone算法在一些點(diǎn)云密度較低區(qū)域無法重建出完整的曲面，且拓?fù)浣Y(jié)構(gòu)出現(xiàn)錯(cuò)誤；Possion方法雖然能生成無孔洞的曲面，但是在曲率變化較大的地表中平滑程度較高，而且重構(gòu)的三角面出現(xiàn)了狹長(zhǎng)三角面，導(dǎo)致對(duì)非光滑的三維實(shí)體曲面的細(xì)節(jié)表現(xiàn)不夠充分。其他點(diǎn)云曲面重建模型如圖7所示。

圖6 Goaf點(diǎn)云與Angel點(diǎn)云模型曲面生長(zhǎng)

圖7 其他點(diǎn)云曲面重建模型

4 總 結(jié)

對(duì)比傳統(tǒng)的基于Delaunay三角剖分算法，本文利用Delaunay三角形分離特性，抽取大量的表面三角形，增加種子三角網(wǎng)面積，通過自適應(yīng)搜索球加快了生長(zhǎng)速度，并且能夠自動(dòng)識(shí)別模型邊界，完成封閉與非封閉點(diǎn)云模型的三維曲面構(gòu)建。通過簡(jiǎn)單的計(jì)算合理控制三角形抽取確保整個(gè)過程更高效。對(duì)比傳統(tǒng)的區(qū)域生長(zhǎng)法，本文算法重構(gòu)的三角網(wǎng)繼承了Delaunay三角網(wǎng)結(jié)構(gòu)的優(yōu)良特性；能夠較好地完善散亂點(diǎn)集的幾何信息缺失，確保重建的三維曲面更真實(shí)合理。此外，對(duì)比顯式的表面重建方法，能夠保證細(xì)節(jié)特征的正確與真實(shí)性。

[1] 唐琦, 達(dá)飛鵬. 平面散亂點(diǎn)集的Delaunay三角剖分算法[J]. 東南大學(xué)學(xué)報(bào), 2006, 36(1): 35-38.

[2] 錢歸平. 散亂點(diǎn)云網(wǎng)格重建及修補(bǔ)研究[D]. 杭州: 浙江大學(xué), 2008.

[3] 徐靜芳. 基于三維散亂數(shù)據(jù)點(diǎn)的曲面重建及變形技術(shù)研究[D]. 南京: 南京航空航天大學(xué), 2007.

[4] 周瑾, 潘建江, 童晶, 等. 使用Kinect快速重建三維人體[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2013, 25(6): 873-879.

[5] 姜翰青, 趙長(zhǎng)飛, 章國(guó)鋒, 等. 基于多視圖深度采樣的自然場(chǎng)景三維重建[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2015, 27(10): 1805-1815.

[6] CARR J, BEATSON R, CHERRIE H, et al. Reconstruction and representation of 3D objects with radial basis functions [C]//USA: SIGGRAPH. New York: ACM Press, 2001: 67-76.

[7] GRIMM C, HUGHES J. Modeling surfaces of arbitrary topology using manifolds [C]//Proceedings of SIG-GRAPH.95. New York: ACM Press, 1995: 359-368.

[8] DEY T K, SUN J. An adaptive MLS surface for reconstruction with guarantees [C]//Proceedings of the Third Eurographics Symposium on Geometry Processing. New York: ACM Press, 2005: 43.

[9] KAZHDAN M, BOLITHO M, HOPPE H. Poisson surface reconstruction [C]//Proceedings of the Third Eurographics Symposium on Geometry Processing. New York: ACM Press, 2006: 61-70.

[10] BERNARDINI F, MITTLEMAN J, RUSHMEIER H, et al. The ball-pivoting algorithm for surface reconstruction [C]// IEEE Transactions on Visualization and Computer Graphics. New York: IEEE Press, 1999: 349-359.

[11] 王楠. 基于三維散亂點(diǎn)云的網(wǎng)格重構(gòu)技術(shù)研究[D]. 大連: 大連大學(xué), 2011.

[12] HUANG J, MENQ C H. Combinatorial manifold mesh reconstruction and optimization from unorganized points with arbitrarytopology [J]. Computer-Aided Design, 2002, 34(2): 149-165.

[13] 陳金瑞. 點(diǎn)云數(shù)據(jù)三維重建研究[D]. 武漢: 武漢理工大學(xué), 2011.

[14] EDELSBRUNNER H, KIRKPATIRCK D G, SEIDEL R. On the shape of a set of points in the plane [J]. New York: IEEE Press, 1983, 29(4): 551-559.

[15] AMENTA N, BERN M, KAMVYSSELIS M. A new Voronoi-based surface reconstruction algorithm [C]//The Proceeding of Computer Graphics. USA: SIGGRAPH. New York: ACM Press, 1998: 415-422.

[16] AMENTA N, CHOI S, DEY T K, et al. A simple algorithm for homeomorphic surfacereconstruction [J]. International Journal of Computational Geometry & Applications, 2002, 12(1-2): 125-141.

[17] DEY T K, GOSWAMI S. Tight cocone: a watertight surface reconstructor [J]. Journal of Computing and Information Science in Engineering, 2003, 3(4): 302-307.

[18] 朱德海. 點(diǎn)云庫(kù)PCL學(xué)習(xí)教程[M].北京: 北京航空航天大學(xué), 2012: 32-40.

[19] BèCLET E, CUILLIERE J C, TROCHU F. Generation of a finite element MESH from stereolithography (STL) files [J]. Computer-Aided Design, 2002, 34: 1-17.

3D Surfaces Reconstruction Algorithm Via Detaching Delaunay Triangular Mesh and Search-Ball Approach

YUAN Qinglie1, WU Xuequn2

(1. School of Civil and Architectural Engineering, Panzhihua University, Panzhihua Sichuan 617000, China; 2. School of Land and Resources Engineering, Kunming University of Science and Technology, Kunming Yunnan 650093, China)

3D surface reconstruction are becoming increasing important in geometric modeling and related applications such as in computer graphics, 3D GIS, reverse engineering. This paper presents an algorithm that holds the advantages of both region- growth approaches and Delaunay based on unorganized point cloud. Separation angle is defined and deduced the related conclusion according to the nature of the surface axis, which is applied to extract triangles from the surface of model and increase the initial growth area of the region. An approach of adaptive search-ball method is presented to speed up searching the neighbourhood-triangles and identify the surface boundary. Compared with the traditional Delaunay-based approach, this algorithm requires only one-pass Delaunay computation and reconstruct surfacesrapidly without calculation of pole and the vector. Compared with the traditional region growing method, this algorithm inherits the structural characteristics of the Delaunay triangulation with fewer holes and accurate the 3D geometry information and topology. Experimental results shows that it is highly efficient compared with other existing algorithms and capable of handling surfaces with complex topology, boundaries, which holds the advantages of both region- growth approaches and Delaunay.

surface-reconstruction; point-cloud; Delaunay; separation angle; reigon-growing

TP 242.2

10.11996/JG.j.2095-302X.2018020278

A

2095-302X(2018)02-0278-09

2017-01-15；

2017-05-16

國(guó)家自然科學(xué)基金項(xiàng)目(41161071)

袁清洌(1991–)，男，山東臨沂人，講師，碩士。主要研究方向?yàn)槿S激光點(diǎn)云建模、三維GIS。E-mail：yuanqinglie@163.com