基于快速Delaunay三角化的散亂點曲面重建算法*

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

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

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

關鍵詞：曲面重建；散亂數據點；Delaunay三角剖分；漏洞填充

中圖分類號：TP391.4 文獻標志碼：A

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

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

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

作者簡介:

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

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引言

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

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

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

2算法實現

2.1相關概念

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

2.1.1點的概念

在三角形T中，若某一采樣點p為T的一個頂點，則三角形T稱為p的鄰接三角形。若三角形T中存在以p0、p為頂點的邊，則頂點p0稱為p的鄰接點。頂點p0對于p的鄰接度是指在三角形網絡中含有以p0、p為端點的邊的三角形個數。

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

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

2.1.2空間三角形的重疊

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

2.2近似法矢量計算

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

(1)

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

(2)

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

2.3平面Delaunay三角化

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

2.3.1目標三角形的快速定位算法

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

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

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

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

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

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

2.3.2Delaunay三角化

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

步驟1增加三個附加點構造超級三角形作為初始三角形。

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

步驟3刪除附加點的所有鄰接三角形，生成二維Delaunay三角網格。

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

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

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

2.4網格拼接

將二維三角化結果反投影至三維空間并進行拼接，完成網格融合。

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

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

(1)如果pa的某一個鄰接點pb關于pa的重數為3 或4, 則刪去一個或兩個擁有邊〈pa，pb〉的三角形, 使得pb關于pa的重數為2, 且剩下的兩個三角形不與DT(pa) 中的其它三角形關于pa重疊。

(2)當不存在重數為3 或4 的鄰接點后, 如果DT(pa)中還有兩個三角形關于pa重疊, 則刪除其中一個三角形, 且使另一個三角形不再與DT(pa) 中的其它三角形關于pa重疊。

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

2.5漏洞檢測

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

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

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

Figure 2　Holes testing 圖2　漏洞檢測

2.6算法整體框架

輸入散亂數據點集合S={pi}，輸出模型的三角網格M。算法整體實現框架如下：

步驟1置每個點為孤立點，根據每個點pi的k最近鄰域Nbhd(pi)計算各個點的近似法矢量。

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

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

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

步驟5集合S中的點遍歷完成，得到一個比較完整的三維網格。

步驟6根據邊信息檢測是否存在漏洞，若有則進行漏洞彌補。

3實驗結果與分析

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

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

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

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

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

Table 1　 Comparison of running

4結束語

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

參考文獻:

[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)

參考文獻：附中文

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

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

[10]杜新偉, 楊孝英, 梁學章. 用徑向基函數隱式擬合點云數據[J]. 吉林大學學報(理學版), 2010, 48(2):157-162.

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

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

[18]王青, 王融清, 鮑虎軍, 等. 散亂數據點的增量快速曲面重建算法[J]. 軟件學報, 2000, 11(9):1221-1227.

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

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

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

楊軍(1973-),男,寧夏吳忠人，博士后，教授，研究方向為計算機圖形學。E-mail:yangj@mail.lzjtu.cn

YANGJun,bornin1973,postdoctor,professor,hisresearchinterestincludescomputergraphics.

林巖龍(1985-),男,河南許昌人，碩士生，研究方向為計算機圖形學。E-mail:715099393@qq.com

LINYan-long,bornin1985,MScandidate,hisresearchinterestincludescomputergraphics.

李龍杰(1989-),男,山西太原人，碩士生，研究方向為計算機圖形學。E-mail:503241156@qq.com

LILong-jie,bornin1989,MScandidate,hisresearchinterestincludescomputergraphics.

王小鵬(1969-),男,甘肅慶陽人，博士，教授，研究方向為數字信號處理和計算機視覺。E-mail:wangxp1969@sina.com

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