基于快速Delaunay三角化的散亂點(diǎn)曲面重建算法*

楊軍，林巖龍，李龍杰，王小鵬

(蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

摘要：針對現(xiàn)有三維重建算法速度較慢的問題，提出了一種基于快速Delaunay三角化的散亂數(shù)據(jù)點(diǎn)的三維重建算法。首先，提出一種新的平面Delaunay三角化插入點(diǎn)目標(biāo)三角形定位算法，利用插入點(diǎn)的方向搜索線與三角形是否相交以及交點(diǎn)個(gè)數(shù)加速目標(biāo)三角形定位，不用額外判斷點(diǎn)是否在三角形內(nèi)；其次，自動檢測曲面漏洞，利用凸殼的邊界拼接方法進(jìn)行漏洞彌補(bǔ)。實(shí)驗(yàn)結(jié)果表明，本算法不僅能較好地重建出三維模型，而且有較高的效率。

關(guān)鍵詞：曲面重建；散亂數(shù)據(jù)點(diǎn)；Delaunay三角剖分；漏洞填充

中圖分類號：TP391.4 文獻(xiàn)標(biāo)志碼：A

doi:10.3969/j.issn.1007-130X.2015.06.023

收稿日期：*2014-03-25;修回日期：2014-06-30

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61462059)；中國博士后科學(xué)基金面上項(xiàng)目(2013M542396)；人社部留學(xué)人員科技活動項(xiàng)目擇優(yōu)資助(2013277)；甘肅省自然科學(xué)基金資助項(xiàng)目(1208RJZA243)；隴原青年創(chuàng)新人才扶持計(jì)劃資助項(xiàng)目(201182)

作者簡介:

通信地址：730070 甘肅省蘭州市蘭州交通大學(xué)研究生院

Address:Graduate School,Lanzhou Jiaotong University,Lanzhou 730070,Gansu,P.R.China

AsurfacereconstructionalgorithmforunorganizedpointsbasedonfastDelaunaytriangulation

YANGJun，LINYan-long，LILong-jie，WANGXiao-peng

(SchoolofElectronic&InformationEngineering,LanzhouJiaotongUniversity,Lanzhou730070,China)

Abstract:To solve the problem of low efficiency in three-dimensional reconstruction, we propose a surface reconstruction algorithm for unorganized points based on fast Delaunay triangulation.First,a new algorithm is designed for searching the target triangle of an inserted point in the plane Delaunay triangulation.The number of intersection points of the direction searching line of the inserted points and the triangles is used to speed up locating the target triangle.No extra work is required to determine whether the point is inside the triangle.Second,the holes on the mesh are detected automatically and they are made up by the boundary combination method of convex hull.Experimental results demonstrate the high quality and the efficient performance of the proposed algorithm in processing 3D reconstruction for unorganized points.

Keywords:surfacereconstruction;unorganizedpoints;Delaunaytriangulation;holesfilling

1引言

隨著激光掃描設(shè)備的發(fā)展，三維表面采樣數(shù)據(jù)的獲取有多種途徑，主要有醫(yī)學(xué)圖像、三維數(shù)字掃描儀、雷達(dá)和超聲波定位儀以及數(shù)字曲面模擬等等。根據(jù)所獲得數(shù)據(jù)點(diǎn)集的組織形式的不同，可以將點(diǎn)集大致分成三類，即點(diǎn)與點(diǎn)之間毫無內(nèi)在聯(lián)系的散亂點(diǎn)數(shù)據(jù)(ScattedData)、來自于醫(yī)學(xué)圖像的體數(shù)據(jù)(VolumetricData)和由三維激光掃描測距技術(shù)獲得的深度數(shù)據(jù)(RangData)，這三種數(shù)據(jù)類型可以相互轉(zhuǎn)化，比如體數(shù)據(jù)和深度數(shù)據(jù)都可以轉(zhuǎn)換為散亂點(diǎn)數(shù)據(jù)。散亂點(diǎn)數(shù)據(jù)的三維重建算法研究可以提高曲面重建算法的適應(yīng)性，在許多領(lǐng)域具有重要意義。例如，在逆向工程領(lǐng)域中建立產(chǎn)品的數(shù)字化模型；在醫(yī)學(xué)領(lǐng)域中根據(jù)測量的數(shù)據(jù)建立人體以及骨骼和器官的計(jì)算機(jī)模型等。

目前，關(guān)于散亂點(diǎn)的三維重建主要有四類方法。第一類方法是構(gòu)建點(diǎn)到物體表面的有向距離場，該距離場的零等值面即為重建曲面[1,2]，但是這種方法涉及等值面的抽取，重建比較耗時(shí)，且對邊界或尖銳部分的重建結(jié)果不夠理想。第二類方法是采用隱函數(shù)法進(jìn)行散亂點(diǎn)重建。FoleyTA[3]綜述了隱式曲面和參數(shù)曲面重建的有關(guān)算法;文獻(xiàn)[4,5]通過Wendland緊致支集徑向基函數(shù)方法從大量散亂點(diǎn)中重建了隱式曲面，該算法被KojekineN等人[6]做了進(jìn)一步改進(jìn)，但是支集的半徑必須為全局的，對高度非一致的散亂點(diǎn)集算法不具有良好魯棒性；CarrJC等人[7]利用快速多級RBF計(jì)算技術(shù)提高重建效率，但是算法步驟比較復(fù)雜；文獻(xiàn)[8]提出一種基于徑向Hermite基函數(shù)隱式擬合點(diǎn)云數(shù)據(jù)的方法，但基函數(shù)構(gòu)造比較復(fù)雜；杜新偉等人[9]通過劃分將點(diǎn)集分為一個(gè)由粗糙到精細(xì)的分層結(jié)構(gòu)，針對給定的誤差限對每個(gè)分層的數(shù)據(jù)進(jìn)行插值，并將其插值結(jié)果作為前一層插值的彌補(bǔ)，這種方法可以在較少采樣點(diǎn)的情況下達(dá)到較好的重建結(jié)果;其后，該算法又被進(jìn)一步改進(jìn)，在以前工作的基礎(chǔ)上通過增加少量離面點(diǎn)，并利用曲面導(dǎo)數(shù)等信息，降低求解方程組階數(shù)，進(jìn)一步提高重建速度[10]；文獻(xiàn)[11]針對傳統(tǒng)徑向基函數(shù)在重建復(fù)雜曲面時(shí)效率低下的問題，引入分塊思想，針對每個(gè)子塊使用不同的隱函數(shù)進(jìn)行插值，并在邊界處利用窗口函數(shù)進(jìn)行權(quán)值約束求和得到全局插值函數(shù)，最終利用MC方法輸出三角網(wǎng)格曲面，這樣不僅降低了每個(gè)包圍盒內(nèi)隱函數(shù)的求解復(fù)雜度，而且此方法也適用于并行計(jì)算，對規(guī)模較大的模型有較好的重建效率。第三類方法是應(yīng)用Vorionoi圖對散亂點(diǎn)進(jìn)行三角化。LawsonCL[12]提出了三角化的最大角最小化原則;SibonR[13]證明了Delaunay三角化是符合這一原則的唯一形式;GreenPJ和SibonR[14]實(shí)現(xiàn)了二維空間的Voronoi圖的計(jì)算以及Delaunay三角化;BowyerA[15]和WatsonDF[16]將結(jié)論推廣到任意維，但這種方法包含過多冗余的三角形或四面體。第四類方法是映射法，即將散亂點(diǎn)投影到二維空間，將二維的三角化結(jié)果反投影到三維空間來實(shí)現(xiàn)三維散亂點(diǎn)的曲面重建。田軍委等人[17]在理論上證明了這種方法的正確性；文獻(xiàn)[18]利用鄰近點(diǎn)集反映出的局部幾何信息，在切平面完成投影并進(jìn)行Delaunay三角化，最終通過自動矯正局部數(shù)據(jù)點(diǎn)的非法連接關(guān)系，以增量擴(kuò)張的方式實(shí)現(xiàn)局部三角網(wǎng)格的拼接，完成整個(gè)曲面的重建。但是，這種方法在平面Delaunay三角化時(shí)速率比較慢，而且容易產(chǎn)生偽漏洞(真實(shí)模型不存在的漏洞)。

本文在局部網(wǎng)格拼接技術(shù)的基礎(chǔ)上，提出了一種新的三維曲面快速重建算法。在完成k鄰域搜索的前提下，利用局部的鄰域信息估算某點(diǎn)的近似法向量，并完成局部的切平面投影。提出一種新的目標(biāo)三角形的快速定位算法，利用搜索方向線和三角形的交點(diǎn)個(gè)數(shù)完成三角形的快速定位。在平面三角化過程中加入對特殊情況的處理，使細(xì)節(jié)特征更加明顯。自動檢測曲面漏洞，利用凸殼邊界拼接技術(shù)完成漏洞彌補(bǔ)。

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

2.1相關(guān)概念

給定未知曲面F的散亂點(diǎn)數(shù)據(jù)集S={pi|i=1,…,n}，其中pi的三維坐標(biāo)值為(xi,yi,zi)，n為點(diǎn)集內(nèi)點(diǎn)的數(shù)量。以下介紹重建過程中的幾個(gè)基本概念。

2.1.1點(diǎn)的概念

在三角形T中，若某一采樣點(diǎn)p為T的一個(gè)頂點(diǎn)，則三角形T稱為p的鄰接三角形。若三角形T中存在以p0、p為頂點(diǎn)的邊，則頂點(diǎn)p0稱為p的鄰接點(diǎn)。頂點(diǎn)p0對于p的鄰接度是指在三角形網(wǎng)絡(luò)中含有以p0、p為端點(diǎn)的邊的三角形個(gè)數(shù)。

根據(jù)上述鄰接點(diǎn)和鄰接度的定義，本文將點(diǎn)分為三類：一類是孤點(diǎn)，它沒有鄰接點(diǎn)；另一類是邊界點(diǎn)，它的鄰接點(diǎn)的鄰接度為2或1；第三類是內(nèi)點(diǎn)，它的所有鄰接點(diǎn)相對它的鄰接度都為2。在一個(gè)封閉的流形曲面三角網(wǎng)格中，所有頂點(diǎn)的鄰接點(diǎn)的鄰接度都為2，即所有點(diǎn)都是內(nèi)點(diǎn)。

在平面Delaunay三角化過程中，對任一插入點(diǎn)p，以p為中心，以邊長l形成一個(gè)四邊形，此四邊形稱為p的自身小四邊形，自身小四邊形主要用在平面三角化過程中定位目標(biāo)三角形的預(yù)篩選上。p和首三角形重心的連線稱為p的搜索方向線。

2.1.2空間三角形的重疊

在本文中, 兩個(gè)空間三角形T1、T2相互重疊是相對于某一頂點(diǎn)而言的。設(shè)p∈S 是曲面網(wǎng)格上的一個(gè)頂點(diǎn)，曲面在p點(diǎn)處的切平面為Fp，如果T1、T2在Fp上的投影相互重疊(除共享點(diǎn)及共享邊外)，稱T1、T2關(guān)于p 相互重疊。

2.2近似法矢量計(jì)算

在點(diǎn)集k鄰域搜索完成的前提下，通過每個(gè)點(diǎn)p的k個(gè)最鄰近點(diǎn)來估算p點(diǎn)處的近似法向量。已知p的k鄰域Nbhd(p)={qi|i=1,…,k}, qi∈S，求p的近似法向量N，也就是使式(1)最小：

(1)

使用最小二乘法可得3×3階矩陣C，即:

(2)

容易證明將C的最小特征值對應(yīng)的特征向量單位化即可作為p的單位法向量的近似值。

2.3平面Delaunay三角化

逐點(diǎn)插入法由于其思想簡單、占用內(nèi)存少等優(yōu)點(diǎn)而被廣泛應(yīng)用，但其本身也具有時(shí)間效率差等不足。通過對插入點(diǎn)算法的分析可知，算法的時(shí)間消耗主要集中在插入點(diǎn)對目標(biāo)三角形的定位上。為此，本文提出一種新的目標(biāo)三角形定位算法以加快Delaunay三角化。

2.3.1目標(biāo)三角形的快速定位算法

目前，絕大多數(shù)學(xué)者對逐點(diǎn)插入算法的改進(jìn)都集中在插入點(diǎn)對目標(biāo)三角形的定位上，已有文獻(xiàn)都利用點(diǎn)和線的相對關(guān)系在搜索方向線上進(jìn)行最短路徑搜索。但是，這種方法存在一些缺陷，比如插入點(diǎn)的搜素方向線和三角形某條邊重合，或和三角形某個(gè)頂點(diǎn)相交等，這些情況下算法的最短搜索路徑不唯一，甚至還可能出現(xiàn)死循環(huán)等情況。許多學(xué)者為了解決這一問題對算法進(jìn)行了諸多改進(jìn)，如劉少華等人[19]在相交的頂點(diǎn)p處按逆時(shí)針?biāo)阉鞔隧旤c(diǎn)的鄰接三角形，然后判斷點(diǎn)是否在三角形內(nèi)，若在內(nèi)則結(jié)束算法，若不在，則判斷p的對邊和搜索方向線是否相交，若不相交，則對下一個(gè)三角形進(jìn)行判斷，若相交，則把此三角形作為當(dāng)前判斷的三角形，糾正搜索方向線，重新按上述方法進(jìn)行目標(biāo)三角形定位。通過這種方法可以有效地解決搜索方向線和頂點(diǎn)相交時(shí)搜索路徑不唯一的情況，但是如果方向線和三角形頂點(diǎn)頻繁相交，則判斷過程比較耗時(shí)，而且在每次定位過程中需要額外判斷點(diǎn)和三角形的關(guān)系，造成了一定的時(shí)間浪費(fèi)。本文首先利用插入點(diǎn)的小四邊形和三角形重心的位置關(guān)系完成三角形的預(yù)篩選；其次，根據(jù)重心和插入點(diǎn)的最小距離確定搜索判斷的首三角形；最后，利用搜索方向線和三角形三邊是否相交以及相交點(diǎn)個(gè)數(shù)來判斷點(diǎn)是否位于三角形內(nèi)，并進(jìn)行快速定位，不需要額外判斷點(diǎn)和三角形的包含關(guān)系。算法的實(shí)現(xiàn)過程如下：

(1)利用插入點(diǎn)p的小四邊形限定首三角形的搜索范圍，選取其重心離p距離最近的三角形T作為搜索判斷的首三角形。

(2)T的重心和p連接生成搜索方向線，若方向線和首三角形不相交，則p位于T中，算法結(jié)束。若和T中某條邊e相交，則計(jì)算搜索方向線和邊e鄰接三角形T0的交點(diǎn)個(gè)數(shù)，若個(gè)數(shù)為1，則p 在T0中；若交點(diǎn)個(gè)數(shù)為2(相交邊分別為e、e1)，則繼續(xù)判斷和邊e1的鄰接三角形的交點(diǎn)個(gè)數(shù)，直至算法結(jié)束。若搜索方向線和首三角形相交但交點(diǎn)為三角形的頂點(diǎn)p0，則按逆時(shí)針方向搜索p0的對邊e，判斷e和搜索方向線是否相交；若e和搜索方向線不相交，則對p0的下一個(gè)對邊判斷，若相交且交點(diǎn)不是頂點(diǎn)，則直接對該邊的鄰接三角形進(jìn)行判斷，若相交但交點(diǎn)仍是頂點(diǎn)，則按上述方法繼續(xù)判斷。

(3)完成插入點(diǎn)目標(biāo)三角形定位。以圖1為例對本文算法的定位過程進(jìn)行描述。

Figure 1　Best location path of the target triangle 圖1　目標(biāo)三角形的最佳定位路徑

如圖1所示，插入點(diǎn)為p，首三角形T1的重心為G，搜索方向線為pG，與三角形T1判斷，pG和T1相交且交點(diǎn)為頂點(diǎn)c，則逆時(shí)針?biāo)阉鱟的對邊，分別為〈b，d〉、〈d，e〉、〈e，a〉，判斷pG和這些邊是否相交，圖中和〈d，e〉相交，交點(diǎn)仍為交點(diǎn)e，逆時(shí)針?biāo)阉鱡的對邊〈d，g〉、〈g，f〉、〈f，a〉、〈a，e 〉，其中邊〈g，f〉和方向線相交且交點(diǎn)不是頂點(diǎn)，且pG和邊〈g，f〉的鄰接三角形T8的交點(diǎn)個(gè)數(shù)為2，則搜索相交邊〈f，h〉的鄰接三角形T10，交點(diǎn)個(gè)數(shù)仍為2，則搜索T11，方向線pG和T11交點(diǎn)個(gè)數(shù)為1，則認(rèn)為p處于T11中，目標(biāo)三角形定位完成。上例中本文算法只進(jìn)行了12次和三角形邊的相交判斷即完成了目標(biāo)三角形定位，且搜索過程中基本按最短路徑進(jìn)行搜索，在速率上得到了較大提高。文中〈p，p0〉表示以p、p0為端點(diǎn)的邊。

2.3.2Delaunay三角化

根據(jù)2.3.1節(jié)介紹的快速定位算法，實(shí)現(xiàn)平面的三角化。具體步驟如下：

步驟1增加三個(gè)附加點(diǎn)構(gòu)造超級三角形作為初始三角形。

步驟2從平面點(diǎn)集中選擇未處理的點(diǎn)p，利用上述的快速定位技術(shù)從三角形鏈表中選擇包含p的目標(biāo)三角形，連接p和三角形的三個(gè)頂點(diǎn)，刪除原三角形，并根據(jù)Delaunay優(yōu)化準(zhǔn)則進(jìn)行局部優(yōu)化。

步驟3刪除附加點(diǎn)的所有鄰接三角形，生成二維Delaunay三角網(wǎng)格。

由于采樣的隨機(jī)性和采樣精度等原因，可能會出現(xiàn)某點(diǎn)在三角形邊上或者在局部優(yōu)化過程中四點(diǎn)共圓，此時(shí)進(jìn)行如下處理：

(1)若點(diǎn)在三角形的邊e上，則和e的對點(diǎn)連接，與三角形的其它邊形成三角形。

(2)若四點(diǎn)共圓，則不做處理，即不交換三角形對角線。

2.4網(wǎng)格拼接

將二維三角化結(jié)果反投影至三維空間并進(jìn)行拼接，完成網(wǎng)格融合。

假設(shè)p1、p2∈S, 它們的最近點(diǎn)集分別為Nbhd(p1)和Nbhd(p2)，由它們生成的兩張局部三角網(wǎng)為M1和M2。下面的任務(wù)是將它們整合成一張三角形網(wǎng), 使得整個(gè)曲面在重建過程能以局部擴(kuò)張的方式進(jìn)行。

本方法先將M2中的所有三角形無條件地加入到M1中去, 然后判別并刪除非法三角形。設(shè)pa為Nbhd(p2) 中的一點(diǎn)，記合并后pa的鄰接三角形集為DT(pa) , 現(xiàn)在希望找出并刪除DT(pa)中的非法三角形, 使得M1在pa處仍符合二維流形的定義。具體方法如下:

(1)如果pa的某一個(gè)鄰接點(diǎn)pb關(guān)于pa的重?cái)?shù)為3 或4, 則刪去一個(gè)或兩個(gè)擁有邊〈pa，pb〉的三角形, 使得pb關(guān)于pa的重?cái)?shù)為2, 且剩下的兩個(gè)三角形不與DT(pa) 中的其它三角形關(guān)于pa重疊。

(2)當(dāng)不存在重?cái)?shù)為3 或4 的鄰接點(diǎn)后, 如果DT(pa)中還有兩個(gè)三角形關(guān)于pa重疊, 則刪除其中一個(gè)三角形, 且使另一個(gè)三角形不再與DT(pa) 中的其它三角形關(guān)于pa重疊。

按上述過程對Nbhd(p2)中所有點(diǎn)進(jìn)行操作，并更新點(diǎn)的鄰接度，直至所有點(diǎn)都符合要求。

2.5漏洞檢測

由于實(shí)際得到的點(diǎn)云數(shù)據(jù)總是存在噪聲或采樣不均勻等情況，導(dǎo)致重建后的曲面可能存在一些漏洞(這種情況很少)，需要對這些漏洞進(jìn)行自動檢測并處理。

根據(jù)重建后三角網(wǎng)格中的邊信息，判斷網(wǎng)絡(luò)中是否存在邊界邊。若存在，則將邊界邊保存。在邊界邊中任取一邊e，從邊界邊數(shù)組中搜索與e相連的邊，直至這些邊界邊形成一個(gè)閉合回路，則停止搜索，進(jìn)行下一個(gè)漏洞的檢測。如圖2所示中邊界邊有〈p1，p2〉、〈p2，p3〉、〈p3，p4〉、〈p4，p5〉、〈p5、p6〉、〈p6，p7〉、〈p7，p8〉、〈p8，p6〉，任選擇一邊〈p1，p2〉進(jìn)行搜索，當(dāng)搜索到〈p5，p6〉時(shí)，同時(shí)有兩條邊界邊〈p6，p7〉、〈p6，p1〉與其相連，若選擇〈p6，p7〉，則形成一個(gè)閉合回路{p1p2p3p4p5p6p7p8p6p1}；若選擇〈p6，p1〉，則形成兩個(gè)閉合回路{p1p2p3p4p5p6p1}和{p6p7p8p6}，這兩者用下述方法進(jìn)行漏洞彌補(bǔ)時(shí)效果是一樣的，不用進(jìn)行額外的判斷。

在完成漏洞邊界提取后，進(jìn)行以下操作：如果漏洞的頂點(diǎn)個(gè)數(shù)為3，則直接將三點(diǎn)形成一個(gè)三角形加入三角網(wǎng)格；若頂點(diǎn)個(gè)數(shù)大于3，則任取回路上的一條邊作為初始邊，搜索與此邊相連的兩條邊，分別計(jì)算這兩邊和初始邊圍成的夾角，取夾角最大的邊和初始邊形成三角形，并將新生成的邊作為新的初始邊重復(fù)上述過程。以圖2為例，選取〈p1，p2〉作為初始邊，并與其相連的兩條邊〈p2，p3〉、〈p1，p6〉分別計(jì)算∠p1p3p2和∠p2p6p1的大小，若∠p2p6p1大，則連接p2p6，使p1p2p6形成三角形加入網(wǎng)格，同時(shí)，p2p6代替p1p2形成新的邊界邊，持續(xù)上述過程，直至邊界邊數(shù)組為空。

Figure 2　Holes testing 圖2　漏洞檢測

2.6算法整體框架

輸入散亂數(shù)據(jù)點(diǎn)集合S={pi}，輸出模型的三角網(wǎng)格M。算法整體實(shí)現(xiàn)框架如下：

步驟1置每個(gè)點(diǎn)為孤立點(diǎn)，根據(jù)每個(gè)點(diǎn)pi的k最近鄰域Nbhd(pi)計(jì)算各個(gè)點(diǎn)的近似法矢量。

步驟2遍歷集合S中的每個(gè)點(diǎn)，對邊界點(diǎn)或者孤立點(diǎn)pi，刪除Nbhd(pi)中的內(nèi)點(diǎn)得到投影點(diǎn)的集合P，將P中點(diǎn)投影到pi所在的切平面上，且以pi的近似法向量為平面法向量。計(jì)算集合P時(shí)，可以設(shè)置閾值d，Nbhd(pi)中和pi歐氏距離小于d的點(diǎn)才能作為投影點(diǎn)，這可以在一定程度上降低噪聲點(diǎn)對建模結(jié)果的影響。一般情況下，d=r*min(|pi,Nbhd(pi)|)，r為常數(shù)。

步驟3在切平面上利用2.3.2節(jié)介紹的Delaunay三角化方法進(jìn)行快速三角化，并將結(jié)果投影至三維空間并得到局部三角網(wǎng)格Mi。

步驟4利用2.4節(jié)中介紹的網(wǎng)格拼接方法將Mi加入到M中，并用Delaunay優(yōu)化準(zhǔn)則進(jìn)行局部優(yōu)化。

步驟5集合S中的點(diǎn)遍歷完成，得到一個(gè)比較完整的三維網(wǎng)格。

步驟6根據(jù)邊信息檢測是否存在漏洞，若有則進(jìn)行漏洞彌補(bǔ)。

3實(shí)驗(yàn)結(jié)果與分析

本文算法已用C++在個(gè)人計(jì)算機(jī)上實(shí)現(xiàn)，并用人體膝關(guān)節(jié)等模型進(jìn)行了測試(如圖3～圖5所示)。在實(shí)驗(yàn)中，k取10，運(yùn)行時(shí)間測試結(jié)果見表1，時(shí)間單位為s。

Figure 3　Triangulation net generation of ACL of the knee using our algorithm 圖3　本文算法生成的膝關(guān)節(jié)ACL三角網(wǎng)格

Figure 4　Comparison of reconstruction results of ACL and PATELLA 圖4　膝關(guān)節(jié)ACL和PATELLA重建結(jié)果對比

Figure 5　Reconstruction results of other models 圖5　其它模型重建的結(jié)果

由表1中實(shí)驗(yàn)結(jié)果可以看出，隨著散亂數(shù)據(jù)點(diǎn)數(shù)量的增加，重建總耗時(shí)以趨于斜率為0.6的直線緩慢增加，避免了重建較大模型時(shí)時(shí)間消耗的幾何倍數(shù)增加。在網(wǎng)格重建部分，本文算法明顯快于文獻(xiàn)[18]算法，而且隨著模型規(guī)模的變大，本文算法在重建效率上的優(yōu)勢相對更加明顯。這是因?yàn)槲墨I(xiàn)[18]算法在切平面內(nèi)進(jìn)行Delaunay三角剖分時(shí)，首先將點(diǎn)進(jìn)行預(yù)分類并在每個(gè)子類中進(jìn)行排序，然后以最近生成的新三角形為首三角形，利用點(diǎn)和三角形三邊關(guān)系進(jìn)行三角形定位。通過分析可知，該算法不僅在分類、排序時(shí)浪費(fèi)了一定的時(shí)間，而且選擇的首三角形不一定是最適合的，并且利用點(diǎn)和三角形三邊關(guān)系定位目標(biāo)三角形時(shí)會出現(xiàn)搜索路徑不唯一的情況，這進(jìn)一步造成了時(shí)間的消耗。本文算法利用小四邊形對首三角形搜索范圍的限定和最小歐氏距離對首三角形的有效選擇，使插入點(diǎn)在一般情況下至多判斷兩次便能確定目標(biāo)三角形，而且利用插入點(diǎn)搜索方向線和三角形是否相交以及交點(diǎn)個(gè)數(shù)判斷點(diǎn)和三角形的關(guān)系，在較大程度上提高了目標(biāo)三角形的定位速度；而且本文算法能有效解決搜索路徑不唯一情況，使定位路徑最短或接近最短，這進(jìn)一步提高了切平面內(nèi)Delaunay三角剖分的速度。但是，切平面內(nèi)進(jìn)行三角化的采樣點(diǎn)數(shù)量比較少，使本文的快速平面Delaunay三角化算法的優(yōu)勢得不到更加完美的展現(xiàn)。在漏洞檢測及彌補(bǔ)階段，避免文獻(xiàn)[20]算法在提取漏洞邊界時(shí)對邊界環(huán)特殊情況的多余判斷，而且利用凸殼邊界的拼接技術(shù)直接對漏洞進(jìn)行彌補(bǔ)，避免了在漏洞填充時(shí)文獻(xiàn)[18]算法對新三角形的重疊判斷和文獻(xiàn)[20]算法對邊界點(diǎn)的投影操作，在一定程度上提高了彌補(bǔ)速度。算法中漏洞邊界的提取是漏洞處理階段的主要耗時(shí)部分；另外，漏洞處理耗時(shí)和模型的大小無關(guān)，而和漏洞的多少、大小緊密相關(guān)；同時(shí)，邊界邊的存儲順序和存儲方式在一定程度上影響漏洞邊界的提取速度。

Table 1　 Comparison of running

4結(jié)束語

本文提出了一種新的平面Delaunay三角網(wǎng)中插入點(diǎn)目標(biāo)三角形的快速定位算法，提高了切平面上的三角化速度；此外，本文還提出了一種新的漏洞彌補(bǔ)方法，借鑒多個(gè)凸殼邊界的拼接思想完成漏洞彌補(bǔ)。實(shí)驗(yàn)表明了本算法的高效性和正確性。然而，由于采樣的不均勻性以及模型的復(fù)雜性，算法還存在一些不足，例如本文算法中拓?fù)溧徑狱c(diǎn)的確定是以假定幾何鄰接點(diǎn)就是拓?fù)溧徑狱c(diǎn)為前提的，如何根據(jù)點(diǎn)之間的幾何信息得到比較正確的拓?fù)湫畔⑹且粋€(gè)難點(diǎn)。真?zhèn)温┒吹蔫b別也需要進(jìn)一步研究，這將是未來要進(jìn)一步解決的主要問題。

參考文獻(xiàn):

[1]HoppeH,DeRoseT,DuchampT,etal.Surfacereconstructionfromunorganizedpoints[J].CompterGraphics, 1992, 26(2):71-78.

[2]ZhouRu-rong,ZhangLi-yan,SuXu,etal.Algorithmicresearchonsurfacereconstructionfromdensescatteredpoints[J].JournalofSoftware, 2000, 12(2):249-255.(inChinese)

[3]FoleyTA.Visualizingandmodelingunstructureddata[J].TheVisualComputerInternationalJournalofComputerGraphics, 1993, 9(8):439-449.

[4]WendlandH.Piecewisepolynomial,positivedefiniteandcompactlysupportedradialfunctionsofminialdegree[J].AdvancesinComputationalMathematics, 1995, 14(4):389-396.

[5]MorseBS,YooTS,RheingansP,etal.Interpolationgimplicitsurfacefromscatteredsurfacedatausingcompactlysupportedraialbasisfunctions[C]//ProcofInternationalConferenceonShapeModeling, 2001:89-98.

[6]KojekineN,HagiwaraI,SavchenkoV.SoftwaretoolsusingCBRBFsforprocessingscattereddata[J].Computers&Graphics, 2003, 27(2):311-319.

[7]CarrJC,BeatsonRK,CherriJB,etal.Reconstructionandrepresentationof3Dobjectswithradialbasisfunctions[C]//ProcofSIGGR-APH’01, 2001:67-76.

[8]NielsonGM,HagenH,LeeK,etal.ImplicitfittingofpointclouddatausingradialHermitebasisfunctions[J].Computing, 2007, 79(2/3/4):301-307.

[9]DuXin-wei,YangXiao-ying,LiangXue-zhang.Amulti-scaleapproachto3Dscattereddatainterpolationbasedonradialbasisfunction[J].JournalofJilinUniversity(ScienceEdition), 2009, 47(5):1039-1041.(inChinese)

[10]DuXin-wei,YangXiao-ying,LiangXue-zhang.Implicitfittingofpointclouddataviaradialbasisfunctions[J].JournalofJilinUniversity(ScienceEdition), 2010, 48(2):157-162.(inChinese)

[11]FangLin-cong,WangGuo-zhao.Analgorithmofsurfacereconstructionbasedonradialbasisfunctions[J].JournalofZhejiangUniversity(EngineeringScience), 2010, 44(4):728-731.(inChinese)

[12]LawsonCL.Generationofatriangulargridwithapplicationtocontourplotting[M].California:JetPropulsionLaboratory,Pasadena, 1972.

[13]SibsonR.Locallyequiangulartriangulations[J].TheComputerJournal, 1978, 21(3):243-245.

[14]GreenPJ,SibsonR.Computingdirichlettessellationsinthelane[J].TheComputerJournal,1978,21(2):168-173.

[15]BowyerA.Computingdirichlettessellations[J].TheComputerJournal, 1981, 24(2):162-166.

[16]WatsonDF.Computingthen-dimensionalDelaunaytessellationwithapplicationtoVoronoipolytopes[J].TheComputerJournal, 1981, 24(2):167-172.

[17]TianJun-wei,ChenGang.AnimprovedDelaunaytriangulationalgorithm[J].JournalofXi’anTechnologicalUniversity, 2011, 31(4):334-338.(inChinese)

[18]WangQing,WangRong-qing,BaoHu-jun,etal.Afastprogressivealgorithmforunorganizedpoints[J].JournalofSoftware, 2000, 11(9):1221-1227.(inChinese)

[19]LiuShao-hua,WuDong-sheng,LuoXiao-long,etal.ResearchonalgorithmsofpointfastpositioninDelaunaytriangularnet[J].ScienceofSurveyingandMapping, 2007, 32(2):69-70.(inChinese)

[20]ZhangJian-qing,LiCai-lin,GuoBao-yun.Afastsurfacereconstructionalgorithmforunorganizedpointsontangentplaneprojection[J].GeomaticsandInformationScienceofWuhanUniversity, 2011, 36(7):757-762.(inChinese)

[21]WangShu-zhong,ZhangYou-sheng.Surfacereconstructionbasedonscatteredpointsets[J].ComputerScience, 2009, 36(5):269-272.(inChinese)

參考文獻(xiàn)：附中文

[2]周儒榮, 張麗艷, 蘇旭, 等. 海量散亂點(diǎn)的曲面重建算法研究[J]. 軟件學(xué)報(bào), 2000, 12(2):249-255.

[9]杜新偉, 楊孝英, 梁學(xué)章. 基于徑向基函數(shù)的3D散亂點(diǎn)數(shù)據(jù)插值多尺度方法[J]. 吉林大學(xué)學(xué)報(bào)(理學(xué)版), 2009, 47(5):1039-1041.

[10]杜新偉, 楊孝英, 梁學(xué)章. 用徑向基函數(shù)隱式擬合點(diǎn)云數(shù)據(jù)[J]. 吉林大學(xué)學(xué)報(bào)(理學(xué)版), 2010, 48(2):157-162.

[11]方林聰, 汪國昭. 基于徑向基函數(shù)的曲面重建算法[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版), 2010, 44(4):728-731.

[17]田軍委，程鋼. 改進(jìn)Delaunay三角剖分算法[J]. 西安工業(yè)大學(xué)學(xué)報(bào), 2011, 31(4):334-338.

[18]王青, 王融清, 鮑虎軍, 等. 散亂數(shù)據(jù)點(diǎn)的增量快速曲面重建算法[J]. 軟件學(xué)報(bào), 2000, 11(9):1221-1227.

[19]劉少華, 吳東勝, 羅小龍, 等.Delaunay三角網(wǎng)中點(diǎn)目標(biāo)快速定位算法研究[J]. 測繪科學(xué), 2007, 32(2):69-70.

[20]張劍清, 李彩林, 郭寶云. 基于切平面投影的散亂數(shù)據(jù)點(diǎn)快速全面重建算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2011, 36(7):757-762.

[21]王樹忠, 張佑生. 基于散亂點(diǎn)集的曲面重建[J]. 計(jì)算機(jī)科學(xué), 2009, 36(5):269-272.

楊軍(1973-),男,寧夏吳忠人，博士后，教授，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail:yangj@mail.lzjtu.cn

YANGJun,bornin1973,postdoctor,professor,hisresearchinterestincludescomputergraphics.

林巖龍(1985-),男,河南許昌人，碩士生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail:715099393@qq.com

LINYan-long,bornin1985,MScandidate,hisresearchinterestincludescomputergraphics.

李龍杰(1989-),男,山西太原人，碩士生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail:503241156@qq.com

LILong-jie,bornin1989,MScandidate,hisresearchinterestincludescomputergraphics.

王小鵬(1969-),男,甘肅慶陽人，博士，教授，研究方向?yàn)閿?shù)字信號處理和計(jì)算機(jī)視覺。E-mail:wangxp1969@sina.com

WANGXiao-peng,bornin1969,PhD,professor,hisresearchinterestsincludedigitalsignalprocessing,andcomputervision.