賈軍輝，黃 明,3，劉祥磊

1. 北京建筑大學(xué)測(cè)繪與城市空間信息學(xué)院,北京 100044； 2. 北京市建筑遺產(chǎn)精細(xì)重構(gòu)與健康監(jiān)測(cè)重點(diǎn)實(shí)驗(yàn)室,北京 100044； 3. 代表性建筑與古建筑數(shù)據(jù)庫(kù)教育部工程中心,北京 100044

三維激光掃描技術(shù)作為一種精確高效的測(cè)量手段，其應(yīng)用領(lǐng)域不斷拓展，對(duì)三維激光掃描的點(diǎn)云數(shù)據(jù)進(jìn)行三維建模的需求逐漸增大。曲面重建技術(shù)作為三維建模的核心技術(shù)之一，在逆向工程、計(jì)算機(jī)視覺(jué)、計(jì)算機(jī)制圖以及虛擬現(xiàn)實(shí)技術(shù)領(lǐng)域都有非常廣泛的應(yīng)用前景。

三維點(diǎn)云的曲面重建是基于點(diǎn)云完成對(duì)曲面的一種近似操作，文獻(xiàn)[1]利用幾何結(jié)構(gòu)來(lái)表達(dá)三維圖形，并由此引出曲面重建的方法。近年來(lái)，曲面重建越來(lái)越受到關(guān)注，并有很多理論和技術(shù)應(yīng)用其中，比較經(jīng)典的有變分法[2-3]、Level Set方法[4]、Alpha Shapes算法[5]、隱式曲面[6-7]、尺度空間模型[8]以及狄洛尼三角網(wǎng)[9]。目前應(yīng)用最為廣泛的是隱式曲面重建算法，如移動(dòng)最小二乘算法[10]、Poisson曲面重建算法[11-13]、HRBF曲面重建算法[14]以及RIMLS法[15]。隱式曲面重建算法主要是通過(guò)局部、全局或者分段平整度指示函數(shù)來(lái)構(gòu)建隱式曲面，然后利用Matching Cubes算法[16]或者Dual Contouring算法[17]提取等值面完成曲面重建。此外，文獻(xiàn)[18]提出的Wrapping算法也類(lèi)似于上述隱式曲面算法，但是它沒(méi)有提取等值面，而是基于Morse理論對(duì)狄洛尼三角形復(fù)雜度的定義，對(duì)單形聚類(lèi)進(jìn)行潰減操作?；诔叨瓤臻g和多尺度分析的算法[19-20]重建效果較好，但是應(yīng)用于大型曲面模型時(shí)重建效率較低，而且無(wú)法保證重建曲面正確的拓?fù)浣Y(jié)構(gòu)。文獻(xiàn)[21—22]提出的Ball-Pivoting算法和Natural Neighbor Interpolation算法都屬于曲面生長(zhǎng)算法的范疇，重建曲面的速度較快，但是同樣無(wú)法保證曲面的拓?fù)湔_性，并且需要準(zhǔn)確的參數(shù)設(shè)置才能重建出理想的效果。文獻(xiàn)[23—24]提出的曲面重建算法采用了曲面生長(zhǎng)的思想，在此基礎(chǔ)上引入狄洛尼三角形的概念，以此克服傳統(tǒng)曲面生長(zhǎng)算法的缺點(diǎn)。但是這兩種算法的程序本身計(jì)算三維狄洛尼三角網(wǎng)的效率較低，并且約束條件存在不足，從而嚴(yán)重制約了算法的廣泛應(yīng)用。

本文提出一種基于三維狄洛尼三角網(wǎng)的曲面重建算法。算法的思路是：在一定的約束條件下，按最優(yōu)三角形選擇標(biāo)準(zhǔn)，從預(yù)先構(gòu)建好的三維狄洛尼三角網(wǎng)中逐個(gè)篩選出最優(yōu)三角形添加到生長(zhǎng)曲面上，最終輸出的曲面是由一系列顯式三角形組成的流形曲面。

1 算法原理

1.1 數(shù)據(jù)結(jié)構(gòu)

曲面重建是一個(gè)不斷選擇符合約束條件的三角形，然后添加到重建曲面S上的過(guò)程。在曲面重建過(guò)程中，存在3種數(shù)據(jù)形式：采樣點(diǎn)集P、重建曲面S以及曲面邊界?S，如圖1所示。采樣點(diǎn)(point)、邊(edge)結(jié)構(gòu)和三角形(triangle)結(jié)構(gòu)是組成上述3種數(shù)據(jù)形式的基本數(shù)據(jù)單元。圖2是算法所使用的三角形(triangle)結(jié)構(gòu)。

圖1 算法數(shù)據(jù)形式Fig.1 Algorithm data form

圖2 三角形(Triangle)結(jié)構(gòu)示意圖Fig.2 Schematic diagram of triangle structure

結(jié)合圖1、圖2，T是在邊界?S上選出的最優(yōu)三角形，與?S存在一條公共邊CE。CE的起點(diǎn)為P1，終點(diǎn)為P2，所對(duì)三角形頂點(diǎn)為Pn，Pn既可以是曲面S外的一點(diǎn)，也可以是邊界?S上的一點(diǎn)，但絕不可能是曲面S內(nèi)的點(diǎn)。P1、P2在邊界?S上，P1所對(duì)三角形的邊為E1，P2所對(duì)三角形的邊為E2。這種數(shù)據(jù)結(jié)構(gòu)便于構(gòu)建曲面正確的拓?fù)潢P(guān)系，同時(shí)構(gòu)建了不同拓?fù)湓氐乃饕Y(jié)構(gòu)，在對(duì)三角形進(jìn)行計(jì)算、添加、移除等操作時(shí)，必須按照這個(gè)結(jié)構(gòu)進(jìn)行，否則將無(wú)法保證重建曲面的正確性。

1.2 算法流程

本算法需要一個(gè)種子三角形作為起始條件，然后根據(jù)算法的約束條件來(lái)拓展曲面。算法首先利用點(diǎn)云數(shù)據(jù)構(gòu)建三維狄洛尼三角網(wǎng)，它包含了曲面重建所需的所有三角面片，然后按照約束條件從三維狄洛尼三角網(wǎng)中提取正確的三角面片。此外，在重建點(diǎn)云數(shù)量在百萬(wàn)級(jí)以上的點(diǎn)云數(shù)據(jù)時(shí)，為防止程序占用內(nèi)存過(guò)大，算法會(huì)先對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行分塊，然后依次對(duì)各個(gè)分塊點(diǎn)云進(jìn)行重建，算法整體流程如圖3所示。

圖3 算法整體流程圖Fig.3 The overall flow chart of the algorithm

1.2.1 三維狄洛尼三角剖分

對(duì)采樣點(diǎn)進(jìn)行三維狄洛尼三角剖分主要是為曲面提取階段提供拓?fù)浣Y(jié)構(gòu)優(yōu)良、網(wǎng)格質(zhì)量較好的三維狄洛尼三角網(wǎng)。三維狄洛尼三角剖分也叫四面體剖分，因?yàn)閽呙璁a(chǎn)生的采樣點(diǎn)集是三維空間實(shí)體的某種映射，而空間實(shí)體的基本單形是四面體，即任何體都可以由多個(gè)四面體組成，所以采樣點(diǎn)集的三維狄洛尼三角剖分的結(jié)果其實(shí)是四面體的集合。三維狄洛尼三角剖分在三維建模中具有重要的作用，但這是一件非常繁重并且耗時(shí)的任務(wù)，不過(guò)相關(guān)算法已經(jīng)相當(dāng)成熟，例如CGAL的3D Triangulation Data Structure模塊[25]和TetGen三角剖分器[26]?？紤]到程序本身的效率、模型的可操作性和數(shù)據(jù)使用的便利性，本文采用TetGen生成初始的三維狄洛尼三角網(wǎng)。

TetGen是一款優(yōu)良的三維狄洛尼三角剖分器，它可以作為一個(gè)獨(dú)立的程序使用。利用輸入的三維點(diǎn)集，TetGen可以生成三維狄洛尼三角網(wǎng)(圖4)，如果采樣點(diǎn)集是經(jīng)過(guò)加權(quán)的，即每個(gè)點(diǎn)都分配了一個(gè)實(shí)數(shù)作為它的權(quán)重，那么TetGen也可以生成采樣點(diǎn)和三角網(wǎng)對(duì)應(yīng)的權(quán)重圖。本文只利用它生成三維狄洛尼三角網(wǎng)。

1.2.2 曲面提取

本算法本質(zhì)上是一個(gè)貪心算法，即新的三角面片都需要在已構(gòu)建曲面的基礎(chǔ)上進(jìn)行選擇，那么這就需要一個(gè)起始條件來(lái)啟動(dòng)算法，然后按照特定的約束條件，從三維狄洛尼三角網(wǎng)(記為DT)中選擇合適的三角面片進(jìn)行添加，提取正確的曲面。

圖4 TetGen 3D Delaunay三角剖分示意圖Fig.4 Schematic diagram of TetGen 3D Delaunay triangulation

1.2.3 算法初始化

將三角形的外接圓半徑記為半徑參數(shù)rt，DT中rt最小的三角形設(shè)為種子三角形，作為算法的起始條件。將種子三角形加入曲面S中，這里曲面S即是存儲(chǔ)合適的三角形的容器，而種子三角形的三條邊就成為曲面S的初始邊界?S。于是，基于種子三角形及其邊界，開(kāi)始搜索合適的三角形添加到曲面S上。

1.2.4 約束條件

(1) 拓?fù)湎拗茥l件：為保證曲面S的可定向性，防止產(chǎn)生類(lèi)似Mobius環(huán)的曲面，需要附加拓?fù)湎拗茥l件來(lái)篩選出相對(duì)正確的三角形。如圖5所示，虛線表示待選三角形，記為T(mén)。e是T的三角形結(jié)構(gòu)中的CE∈?S，b是邊e所對(duì)三角形頂點(diǎn)Pn，拓?fù)湎拗茥l件包含4種情況：①拓展，T的頂點(diǎn)b在曲面S外；②粘合，T的頂點(diǎn)b在邊界?S上，但b的兩個(gè)鄰邊不在?S上；③邊界填充，T的頂點(diǎn)b在邊界?S上，但b只有一條鄰邊在邊界?S上；④孔洞填充，T的3條邊都在邊界?S上。

圖5 拓?fù)湎拗茥l件(A=拓展；B=粘合；C=邊界填充；D=孔洞填充)Fig.5 Topological constraints(A=extension；B=gluing；C=ear filling；D=hole filling)

滿(mǎn)足上述4種情況的三角形能夠保證曲面的可定向性。需要特殊說(shuō)明的是“粘合”這種情況，僅僅添加三角形T是不能保證可定向性的，因?yàn)轫旤c(diǎn)b作為一個(gè)邊界點(diǎn)，在邊界上與它相連的邊的個(gè)數(shù)不止兩個(gè)時(shí)，此點(diǎn)在邊界上的導(dǎo)向就會(huì)出現(xiàn)錯(cuò)亂。為避免出現(xiàn)這種情況，添加三角形T的同時(shí)還需要添加一個(gè)特定的三角形T′(如圖5中待選三角形B相鄰的虛線部分)，T′與T是鄰接關(guān)系。

(2) 半徑限制條件：?S是由邊緣三角形的外側(cè)邊E構(gòu)成的，每條E在DT中連接有多個(gè)三角形(圖6)，要從中選擇一個(gè)最合適的三角形作為候選三角形Tc。

圖6 根據(jù)T∈S選擇候選三角形TcFig.6 Select candidate triangle Tc according to T∈S

關(guān)于如何選擇候選三角形Tc，這里需要引入一個(gè)結(jié)論：根據(jù)上文對(duì)半徑參數(shù)rt的定義，可知rt是三角形中任意頂點(diǎn)到其對(duì)偶Voronoi圖邊界的距離，因?yàn)閂oronoi圖是基于狄洛尼三角形的各邊中垂線構(gòu)成的。從比較簡(jiǎn)單的二維光滑曲線重建來(lái)分析rt的意義，在采樣點(diǎn)足夠密集的時(shí)候，點(diǎn)集的Voronoi邊界會(huì)收斂于曲線圖形的骨架線(圖7)。以圖7中點(diǎn)P為例，與P相連的圖形邊界線中，正確的邊界線往往是P連接相鄰采樣點(diǎn)的線段，長(zhǎng)度也近似于點(diǎn)P到骨架線的垂直距離，而錯(cuò)誤的邊界線長(zhǎng)度往往要大于這個(gè)數(shù)值。根據(jù)這一結(jié)論，在三維空間中半徑越小的三角形越有可能構(gòu)建正確的曲面。所以，每條E都選擇半徑最小的三角形作為這條邊的候選三角形。邊界?S上的每條E都對(duì)應(yīng)一個(gè)Tc，當(dāng)然也有可能出現(xiàn)某條E不存在滿(mǎn)足條件的候選三角形的情況，但那種情況較少，最終多個(gè)候選三角形組成一個(gè)集合，記為T(mén)U。

圖7 狄洛尼三角剖分(a)及其對(duì)偶Voronoi圖(b)，(c)為光滑曲線重建演示圖，粗實(shí)線為其中軸線Fig.7 Delaunay triangulation (a) and its dual Voronoi diagram (b)，(c) for smooth curve reconstruction demo map，the heavy line for its skeleton line

1.2.5 三角形優(yōu)劣等級(jí)

為從TU中選出最合適的三角形，需要賦予每個(gè)候選三角形一個(gè)評(píng)估參數(shù)，記為優(yōu)劣等級(jí)L。此外，候選三角形是通過(guò)對(duì)比rt篩選得出，而rt是基于二維平面元素得到的，并未拓展到三維空間。為保證重建曲面的質(zhì)量，還需要引入一個(gè)參數(shù)，即鄰接三角形之間的二面角參數(shù)β。

如圖8所示，T是曲面S邊緣處的三角形，它所在平面的法向量記為N1，而與之相鄰接的候選三角形Tc的法向量記為N2，N1、N2的夾角即是Tc的二面角參數(shù)β。β的大小直接影響到曲面局部的起伏，需要設(shè)定一個(gè)閾值α來(lái)篩選出β盡量合理的候選三角形。α的數(shù)值并不客觀，初步設(shè)定為π/6。當(dāng)β<α?xí)r，兩三角面片之間的二面角被認(rèn)為是在合理范圍內(nèi)，此時(shí)優(yōu)劣等級(jí)L=1/rt；α<β<π-α?xí)r，L=-β；β>π-α?xí)r，此時(shí)二面角不在合理范圍內(nèi)，將β設(shè)定成一個(gè)足夠小的值。所有候選三角形按照優(yōu)劣等級(jí)降序排列，構(gòu)成候選三角形序列Q，排位越靠前的三角形越先被添加。定性來(lái)講，當(dāng)Q中存在β小于α的三角形時(shí)，優(yōu)先選擇rt較小的三角形，不存在β小于α的三角形時(shí)，選擇β較小的三角形。

圖8 二面角示意圖Fig.8 Schematic diagram of the dihedral angle

如圖9所示，Tc1的二面角不在合理范圍內(nèi)，所以將其排除，Tc2、Tc3的二面角都在最合理的范圍內(nèi)，但是Tc3的半徑最小，所以最合適的三角形是Tc3。Tc4只有在Tc2、Tc3這類(lèi)三角形不存在的情況下才有可能被選，且優(yōu)先選擇二面角較小的三角形。

圖9 最終三角形的選擇Fig.9 Selection of the final triangle

2 算法實(shí)現(xiàn)

算法在重建曲面過(guò)程中，曲面邊界?S、候選三角形序列Q都隨著曲面S的拓展而不斷變化，添加新的三角形到曲面S上時(shí)，不同的拓?fù)淝闆r需要不同的操作。對(duì)于“拓展”“邊界填充”“孔洞填充”這3種情況，都會(huì)在曲面S上添加新的三角形，但是對(duì)于“粘合”這種情況卻不一定。算法添加三角形的同時(shí)必須根據(jù)三角形符合的拓?fù)湎拗茥l件來(lái)更新Q。特別的是，對(duì)于“粘合”這種情況，只有存在鄰接三角形對(duì)T′∪T且T′的優(yōu)劣等級(jí)L大于T時(shí)才會(huì)執(zhí)行添加操作。

算法的終止條件有兩種：如果重建的曲面是閉合的，那么邊界?S中邊的個(gè)數(shù)最終會(huì)為0，此時(shí)算法會(huì)終止循環(huán)輸出曲面S；如果重建的曲面是不閉合的，那么添加邊界三角形時(shí)會(huì)遇到“粘合”這種情況，如果“粘合”的三角形不符合三角形選擇標(biāo)準(zhǔn)，那么算法會(huì)檢驗(yàn)Q中的下一個(gè)三角形。如果邊界內(nèi)的平面已經(jīng)充分重建，那么Q中的三角形全部不符合標(biāo)準(zhǔn)，當(dāng)Q中最后一個(gè)三角形已被檢驗(yàn)不符合后，算法就會(huì)跳出循環(huán)，輸出曲面S，算法的具體實(shí)現(xiàn)如下偽代碼所示。

surface reconstruction algorithm function

compute the 3D Delaunay triangulation DT of sample points;

{Initialization: compute the radius(rt) of triangles，initialize the seed triangletsand ?S}

for all triangles of DT do compute thertof triangle

ts←t;

end if

end for

inserttsintoS;

insert 3 edges into ?S，initialize theSand ?S；

insert all the candidate triangles of edges of ?SintoQ;

{surface extraction: add(T) means insertTintoSand return whether it is inserted successfully；c(E) means the candidate triangle of edgeE}

T← the first element ofQ;

do case = add(T);

if case = true，then

T← the first element ofQ;

end if

if case = false，then

removeTfromQ;

insert c(E) (exceptT) inQ;

T← the first element ofQ;

end if

if case = later，then

ifTis the last element ofQ，then

returnS;

end if

else

T← the first element ofQ;

end if

end while until the size of ?Sis zero

returnS

算法中存在這樣的一類(lèi)三角形，即它的優(yōu)劣等級(jí)L會(huì)被設(shè)置為一個(gè)足夠小的數(shù)從而避免選擇它，但是隨著曲面形態(tài)的變化，這些三角形可能又會(huì)符合曲面整體的情況。對(duì)此，算法會(huì)重新計(jì)算它的優(yōu)劣等級(jí)，更新候選三角形序列，從而添加最合適的三角形。此外，由于某些曲面信息過(guò)去復(fù)雜，依據(jù)標(biāo)準(zhǔn)不足以完全避免錯(cuò)誤的三角形，但是這些三角形rt數(shù)值比較大，所以可以在三維狄洛尼三角剖分階段通過(guò)設(shè)置一個(gè)閾值來(lái)去除過(guò)大的三角形。

3 數(shù)據(jù)處理結(jié)果與分析

目前，大部分曲面重建算法的重建效果都比較依賴(lài)于點(diǎn)云數(shù)據(jù)的質(zhì)量，不同的算法可能適合不同的掃描狀況，如Poisson曲面重建算法，除了點(diǎn)云的坐標(biāo)信息外，還需要點(diǎn)云的法向信息，但是對(duì)于大部分采樣點(diǎn)稀疏或者不均勻的點(diǎn)云數(shù)據(jù)來(lái)講，法向信息是難以計(jì)算準(zhǔn)確的。圖10(a)是對(duì)模型充分掃描所得的點(diǎn)云，點(diǎn)云比較密集并且能夠一定程度上反映模型的外形特征。但很多時(shí)候由于儀器設(shè)備、技術(shù)支持、掃描成本的制約，在實(shí)際生產(chǎn)過(guò)程中，可能無(wú)法獲得掃描質(zhì)量足夠好的點(diǎn)云。例如，圖10(b)點(diǎn)云相對(duì)于圖10(a)就比較稀疏，并且圈選處的點(diǎn)云相對(duì)其他部位更為稀疏，整體點(diǎn)云的分布很不均勻。對(duì)于圖10(b)這種質(zhì)量較差的點(diǎn)云數(shù)據(jù)，利用Poisson算法重建出理想的模型還是相當(dāng)困難的。即使是著名的Wrapping算法，重建此類(lèi)模型也有不同程度的缺陷，如圖10(c)。但是本文算法能夠適應(yīng)這種點(diǎn)云數(shù)據(jù)，并且重建出較好的模型質(zhì)量，如圖10(d)。

點(diǎn)云數(shù)據(jù)的稀疏和密集是相對(duì)于掃描模型本身而言，并沒(méi)有明確的界定，但是質(zhì)量較差的點(diǎn)云數(shù)據(jù)一般較為稀疏并且點(diǎn)云分布不均勻，有些可能還會(huì)出現(xiàn)數(shù)據(jù)缺失的現(xiàn)象。除此之外，大部分點(diǎn)云還會(huì)存在噪聲數(shù)據(jù)，對(duì)于噪聲點(diǎn)云的曲面重建，還需要利用專(zhuān)門(mén)的點(diǎn)云去噪算法[27]對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行預(yù)處理。所以，構(gòu)造出適應(yīng)性更強(qiáng)的算法也是曲面重建算法研究的重點(diǎn)。

圖10 人體模型點(diǎn)云數(shù)據(jù)及其重建效果圖Fig.10 The point cloud data and the reconstruction results of man model

3.1 曲面重建結(jié)果

本文在Intel? CoreTMi7-4790 CPU @ 3.60 GHz，RAM(16.0 GB),Windows 8.1 64位操作系統(tǒng)配置環(huán)境下，對(duì)曲面重建質(zhì)量和效率進(jìn)行測(cè)試。

3.1.1 地形掃描點(diǎn)云模型

掃描地形表面獲取的三維點(diǎn)云數(shù)據(jù)可以用于生成DEM，而生成DEM的算法一般是將點(diǎn)云投影到二維平面上構(gòu)建二維狄洛尼三角網(wǎng)，并在此基礎(chǔ)上添加高程(圖11(b))，與三維曲面重建算法是有本質(zhì)區(qū)別的，由于投影的多值性(投影點(diǎn)對(duì)應(yīng)多個(gè)Z值)，在表示陡峭的地形時(shí)，容易產(chǎn)生畸變。而本文算法按照約束條件構(gòu)建最優(yōu)曲面，較傳統(tǒng)的DEM具有明顯優(yōu)勢(shì)，如圖11所示。

圖11 某工程用地的三維點(diǎn)云數(shù)據(jù)及其表面模型Fig.11 The 3D point cloud data and its surface model for an construction site

3.1.2 建筑物掃描點(diǎn)云模型

建筑物掃描點(diǎn)云的數(shù)據(jù)量大，質(zhì)量較差，無(wú)法構(gòu)建精細(xì)的曲面模型。針對(duì)大數(shù)據(jù)量的點(diǎn)云，本文算法首先利用所有點(diǎn)云生成自適應(yīng)八叉樹(shù)，再基于八叉樹(shù)對(duì)點(diǎn)云進(jìn)行空間分割，然后依次在各個(gè)分塊點(diǎn)云中啟動(dòng)算法。相鄰的分塊點(diǎn)云完成曲面重建時(shí)，由于相鄰曲面滿(mǎn)足“粘合”拓?fù)湎拗茥l件，所以再次重啟算法以完成曲面的拼接，最終獲得整體重建的曲面，如圖12所示。

3.1.3 精細(xì)化掃描點(diǎn)云模型

精細(xì)化掃描主要應(yīng)用于文物保護(hù)，這類(lèi)點(diǎn)云模型采樣點(diǎn)的密度和數(shù)量較大，細(xì)節(jié)較多，形態(tài)構(gòu)造較為復(fù)雜。圖13為3個(gè)精細(xì)化掃描點(diǎn)云模型的曲面重建結(jié)果。

圖12 建筑物掃描點(diǎn)云重建表面模型Fig.12 Reconstruction surface model of building scanning point cloud

圖13 精細(xì)化掃描點(diǎn)云重建表面模型Fig.13 Fine scanning point cloud reconstruction surface model

3.2 時(shí)間統(tǒng)計(jì)與結(jié)果分析

如表1所示，本算法的重建效率對(duì)比DBRG算法有一定的優(yōu)勢(shì)，但遜于Poisson曲面重建算法，而Poisson曲面重建算法無(wú)法正確重建人體和太和殿點(diǎn)云模型。

表1點(diǎn)云模型點(diǎn)數(shù)、對(duì)應(yīng)三維狄洛尼三角形數(shù)及重建時(shí)間

Tab.1Thenumberofpointsofpointcloudmodels，thenumberoftrianglesintheir3DDelaunaytriangulationandrunningtimes

modelpointsDelaunaytriangulationt1t2tDBRG:tPoisson:t人體 174951374330.091.221.311.35×建筑工地2490573214571.1722.6323.8024.134.87龍形神獸43765462914003.8845.7149.5953.1726.72佛像54365277420914.7669.7374.4980.4327.12柱狀文物12374536764956721.72293.07314.79332.6673.24太和殿55772531229753841.75998.361040.111462.63×佛塔56339251087363637.12974.241011.361543.72372.21

注：t1=construction of 3D Delaunay triangulation

t2=main function of surface reconstruction

t=total running time

DBRG:t=the total running time of DBTG algorithm[24]

Poisson:t=the total running time of Poisson algorithm[11]×=failed reconstruction

算法重建效率方面，Poisson曲面重建算法依賴(lài)于法線的計(jì)算，而計(jì)算點(diǎn)云法線以及法線一致性[28]也具有一定的時(shí)間復(fù)雜度，有時(shí)法線計(jì)算的時(shí)間可能會(huì)遠(yuǎn)遠(yuǎn)大于曲面重建的時(shí)間，而且存在某些模型的法線無(wú)法定向。此外，Poisson曲面重建算法是通過(guò)曲面擬合實(shí)現(xiàn)重建，生成的曲面與原始點(diǎn)云存在偏離現(xiàn)象，需要調(diào)整相關(guān)參數(shù)來(lái)提高重建精度，而本算法生成的曲面三角網(wǎng)本身就是由原始點(diǎn)云構(gòu)造的三角形組成的，每個(gè)原始點(diǎn)均在曲面上，故不存在點(diǎn)位精度問(wèn)題。在算法適應(yīng)性方面，本算法能夠適應(yīng)除植被掃描點(diǎn)云模型外的多種點(diǎn)云模型，而Poisson曲面重建算法對(duì)于人體模型、太和殿這種無(wú)法定向法線的點(diǎn)云模型則無(wú)法完成重建，并且重建帶有邊界的點(diǎn)云模型還需要經(jīng)過(guò)裁剪才能達(dá)到最終效果，重建過(guò)程較為復(fù)雜。

4 結(jié) 論

本文算法通過(guò)構(gòu)建三維狄洛尼三角網(wǎng)，按照拓?fù)洹霃郊s束條件從中選取候選三角形，再根據(jù)半徑參數(shù)和二面角參數(shù)計(jì)算優(yōu)劣等級(jí)，從而不斷選出最優(yōu)三角形添加到生長(zhǎng)曲面上。經(jīng)過(guò)試驗(yàn)測(cè)試，結(jié)論如下：

(1) 本算法能夠適應(yīng)包括地形掃描、建筑物掃描和精細(xì)化掃描在內(nèi)的多種點(diǎn)云模型，算法適應(yīng)性強(qiáng)；

(2) 重建曲面的細(xì)節(jié)紋理還原度較高，曲面質(zhì)量好；

(3) 對(duì)比常用的顯式和隱式曲面重建算法都具有一定優(yōu)勢(shì)，實(shí)用性較強(qiáng)。

但本算法也存在不足，如無(wú)法應(yīng)對(duì)噪聲數(shù)據(jù)，建模前需做濾波處理；針對(duì)大規(guī)模點(diǎn)云數(shù)據(jù)三維重建的時(shí)間復(fù)雜度需進(jìn)一步優(yōu)化，研究結(jié)合并行計(jì)算的數(shù)據(jù)分塊算法以提高算法的整體效率。

[1] BOISSONNAT J D. Geometric Structures for Three-dimensional Shape Representation[J]. ACM Transactions on Graphics (TOG), 1984, 3(4): 266-286.

[2] TURK G, O’BRIEN J F. Shape Transformation Using Variational Implicit Functions[C]∥Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1999: 335-342.

[3] TURK G, O’BRIEN J F. Modelling with Implicit Surfaces that Interpolate[J]. ACM Transactions on Graphics (TOG), 2002, 21(4): 855-873.

[4] ZHAO Hongkai, OSHER S, MERRIMAN B, et al. Implicit and Nonparametric Shape Reconstruction from Unorganized Data Using a Variational Level Set Method[J]. Computer Vision and Image Understanding, 2000, 80(3): 295-314.

[5] PARK S H, LEE S S, KIM J H. A Surface Reconstruction Algorithm Using Weighted Alpha Shapes[M]∥WANG Lipo, JIN Yaochu. Fuzzy Systems and Knowledge Discovery. Berlin: Springer, 2005: 1141-1150.

[6] BOISSONNAT J D, CAZALS F. Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions[J]. Computational Geometry, 2002, 22(1-3): 185-203.

[7] MEDIONI G, LEE M S, TANG C K. A Computational Framework for Segmentation and Grouping[M]. New York, NY, USA: Elsevier, 2000: 243-253.

[8] DIGNE J. An Implementation and Parallelization of the Scale Space Meshing Algorithm[J]. Image Processing On Line, 2015, 5: 282-295.

[9] LHUILLIER M. Overview of Shelling for 2-manifold Surface Reconstruction Based on 3D Delaunay Triangulation[J]. Journal of Mathematical Imaging and Vision, 2017, 59(2): 318-340.

[10] MERRY B, GAIN J, MARAIS P. Moving Least-squares Reconstruction of Large Models with GPUs[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(2): 249-261.

[11] KAZHDAN M, BOLITHO M, HOPPE H. Poisson Surface Reconstruction[C]∥Proceedings of the 4th Eurographics Symposium on Geometry Processing. Cagliari, Sardinia, Italy: Eurographics Association, 2006: 61-70.

[12] KAZHDAN M, HOPPE H. Screened Poisson Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2013, 32(3): 29.

[13] BOLITHO M, KAZHDAN M, BURNS R, et al. Multilevel Streaming for Out-of-core Surface Reconstruction[C]∥Proceedings of the 5th Eurographics Symposium on Geometry Processing. Barcelona, Spain: Eurographics Association, 2007: 69-78.

[14] LIU Shengjun, WANG C C L, BRUNNETT G, et al. A Closed-form Formulation of HRBF-based Surface Reconstruction by Approximate Solution[J]. Computer-aided Design, 2016, 78: 147-157.

[15] YANG Long, YAN Qing’an, XIAO Chunxia. Shape-Controllable Geometry Completion for Point Cloud Models[J]. The Visual Computer: International Journal of Computer Graphics, 2017, 33(3): 385-398.

[16] LORENSEN W E, CLINE H E. Marching Cubes: A High Resolution 3D Surface Construction Algorithm[J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4): 163-169.

[17] SCHAEFER S, JU Tao, WARREN J. Manifold Dual Contouring[J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(3): 610-619.

[18] EDELSBRUNNER H. Surface Reconstruction by Wrapping Finite Sets in Space[M]∥ARONOV B, BASU S, PACH J, et al. Discrete and Computational Geometry. Berlin: Springer, 2003: 379-404.

[19] DIGNE J, MOREL J M, SOUZANI C M, et al. Scale Space Meshing of Raw Data Point Sets[J]. Computer Graphics Forum, 2011, 30(6): 1630-1642.

[20] FUHRMANN S, GOESELE M. Floating Scale Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2014, 33(4): 46.

[21] AN Yi, ZHAO Peng, LI Zhuohan, et al. Self-adaptive Polygon Mesh Reconstruction Based on Ball-pivoting Algorithm[J]. International Journal of Computer Applications in Technology, 2016, 54(1): 51-60.

[22] BOISSONNAT J D, CAZALS F. Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions[C]∥Proceedings of the 16th Annual Symposium on Computational Geometry. Hong Kong, China: ACM, 2000: 223-232.

[23] COHEN-STEINER D, DA F. A Greedy Delaunay-based Surface Reconstruction Algorithm[J]. The Visual Computer: International Journal of Computer Graphics, 2004, 20(1): 4-16.

[24] KUO Chuanchu, YAU H T. A Delaunay-based Region-growing Approach to Surface Reconstruction from Unorganized Points[J]. Computer-Aided Design, 2005, 37(8): 825-835.

[25] TEILLAUD M. Three Dimensional Triangulations in CGAL[C]∥Abstracts 15th European Workshop Computational Geometry. [S.l.]: INRIA Sophia-Antipolis, 1999: 175-158.

[26] SI Hang. Three Dimensional Boundary Conforming Delaunay Mesh Generation[D]. Berlin: Technische Universit?t Berlin, 2008.

[27] PARK M K, LEE S J, JANG I Y, et al. Feature-aware Filtering for Point-set Surface Denoising[J]. Computers & Graphics, 2013, 37(6): 589-595.

[28] BOULCH A, MARLET R. Fast and Robust Normal Estimation for Point Clouds with Sharp Features[J]. Computer Graphics Forum, 2012, 31(5): 1765-1774.