一種基于邊指針?biāo)阉骷皡^(qū)域劃分的三角剖分算法

張俊 田慧敏

三維重建技術(shù)是根據(jù)物體的二維圖像信息恢復(fù)其三維模型,多年來一直是計算機(jī)圖形學(xué)領(lǐng)域的研究熱點(diǎn)[1?2].三角剖分是三維重建過程中最重要的基礎(chǔ)之一,通過將散點(diǎn)連接形成許多互不相交的三角形或四面體,從而使模型面化或者體化[3].經(jīng)過多年探索,研究者們對于二維三角剖分的研究已經(jīng)取得了很多成果,提出了多種三角網(wǎng)格的優(yōu)化準(zhǔn)則和構(gòu)造方法.其中,Delaunay 三角剖分由于具有良好的幾何特性-可以最大化最小角[4],即能使得到的三角網(wǎng)格最平均,使用最廣泛[5].然而,隨著計算機(jī)圖形學(xué)技術(shù)的發(fā)展,掃描設(shè)備的精度越來越高,用于三維重建的點(diǎn)集對象的規(guī)模也越來越大.因此,在保證三角網(wǎng)格的整體質(zhì)量的提前下,有必要尋找一種更高效的Delaunay 三角剖分,從而滿足三維重建的實(shí)時性.

Delaunay 三角剖分算法有很多種類,主要分為三大類:逐點(diǎn)插入算法[6]、分治算法[7]、三角網(wǎng)生長算法.其中,逐點(diǎn)插入法由于實(shí)現(xiàn)相對簡單且占用空間相對較小[8],被大量研究者所采用;分治算法在執(zhí)行時間方面可以達(dá)到最優(yōu),但占用內(nèi)存較大,不適用于一般的計算機(jī)平臺;三角網(wǎng)生長算法相對于前兩種算法效率較低,不適用于大規(guī)模點(diǎn)集,在實(shí)際應(yīng)用中很少被采用.逐點(diǎn)插入法的主要流程如下:1) 構(gòu)造一個包含所有插入點(diǎn)的超級三角形;2) 將存儲在鏈表中的點(diǎn)按序插入,遍歷三角形鏈表找出包含插入點(diǎn)的三角形(即目標(biāo)三角形),利用插入點(diǎn)將目標(biāo)三角形拆分生成新的三角形,在三角形鏈表中刪除目標(biāo)三角形,完成一個點(diǎn)的插入;3) 利用空圓特性對新生成的三角形進(jìn)行Delaunay 規(guī)則判斷;4) 循環(huán)執(zhí)行2) 和3),直至完成對所有插入點(diǎn)的處理.經(jīng)典的逐點(diǎn)插入法有Bowyer 算法[9]、Watson 算法[10]以及Lawson 算法[11]等.

雖然逐點(diǎn)插入法易于實(shí)現(xiàn),但在處理大規(guī)模的散點(diǎn)集數(shù)據(jù)時,實(shí)時性不是很好,為了提高逐點(diǎn)插入法的效率,研究者們進(jìn)行了大量的研究.一部分研究者認(rèn)為可以對插入點(diǎn)進(jìn)行預(yù)處理,通過改進(jìn)插入點(diǎn)的序列來提高三角剖分的效率.Liu 等[12]提出了一種基于廣度優(yōu)先搜索的確定性插入序列,使用k-d樹來構(gòu)造Delaunay 三角關(guān)系,但是構(gòu)造k-d 較為復(fù)雜,需耗費(fèi)大量時間.在多重網(wǎng)格插入法[13]的基礎(chǔ)上,Su 等[14]提出了使用Hilbert 曲線遍歷插入點(diǎn),減少了三角剖分過程中狹長三角形出現(xiàn)的數(shù)量,從而降低局部優(yōu)化時間.Zalik 等[15]提出一種兩級均勻細(xì)分加速技術(shù),將目標(biāo)三角形問題轉(zhuǎn)化為最近點(diǎn)問題,在他們的方案中,從最近的Delaunay 點(diǎn)開始,然后從第二個最近的Delaunay 點(diǎn)開始,以這種遞歸的方式直到找到目標(biāo)三角形.在此基礎(chǔ)上,Zadravec等[16]提出結(jié)合哈希表與跳躍表來尋找插入點(diǎn)的最近點(diǎn),從而快速定位目標(biāo)三角形.一些研究人員提出基于重心方向來定位目標(biāo)三角形,但是,當(dāng)出現(xiàn)分界點(diǎn)時,這種方法的搜索路徑可能不唯一.針對此問題,Xi 等[17]提出可以通過移動重心來避免截點(diǎn),從而使目標(biāo)三角形可以連續(xù)搜索.隨著計算機(jī)技術(shù)的快速發(fā)展,許多研究者們提出了并行Delaunay 三角剖分,將點(diǎn)集劃分成許多獨(dú)立的分區(qū),這些分區(qū)可以同時進(jìn)行Delaunay 三角剖分,Kohout 等[18]、Rong等[19]、Cuong 等[20]、Lo[21]均對此進(jìn)行了研究及改進(jìn).此外,楊昊禹等[22]提出了并行動態(tài)Delaunay三角剖分算法,可以解決新增點(diǎn)位于原來三角網(wǎng)之外的情況.另外李國慶等[23]提出了基于凸多邊形的Delaunay 三角剖分算法,使用生成的凸多邊形代替?zhèn)鹘y(tǒng)算法中的超級三角形.常見的生成凸包算法有Graham 掃描法[24]、分區(qū)算法[25]等.劉斌等[26]提出將主成分分析法(PCA) 與二分法結(jié)合,通過快速確定凸包邊緣點(diǎn)來計算平面點(diǎn)集的凸包.

通過對Delaunay 三角剖分逐點(diǎn)插入法的研究,可知在構(gòu)建三角網(wǎng)過程中最耗時的部分為尋找插入點(diǎn)的目標(biāo)三角形.本文在傳統(tǒng)算法的基礎(chǔ)上,將邊指針與區(qū)域劃分相結(jié)合,很大程度上提高了構(gòu)建Delaunay 三角網(wǎng)的效率.

1 基于邊指針的搜索

在傳統(tǒng)的逐點(diǎn)插入法中,對每個插入點(diǎn)的目標(biāo)三角形的搜索總是從三角形鏈表的表頭開始.這意味著,目標(biāo)三角形若位于鏈表的表頭,則可以很快被找到;若位于鏈表的尾部,則需要遍歷整個鏈表才能被找到.隨著點(diǎn)的數(shù)量大幅度增加,三角形鏈表的長度也必然會大幅度增加,從而導(dǎo)致尋找目標(biāo)三角形會越來越耗時,降低三角剖分的效率.針對此問題,本文對三角形的數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化,提出了基于邊指針的數(shù)據(jù)結(jié)構(gòu).如圖1 所示,在△ABC中,A為起始頂點(diǎn)且A、B、C逆時針分布,AC為邊1,AB為邊2,BC為邊3.在三條邊上分別存在邊指針P1、P2、P3,分別指向邊指針?biāo)诘墓策叺南噜徣切?如P1 指向與邊AC相鄰的三角形,對于P2、P3 情況類似.

圖1 三角形數(shù)據(jù)結(jié)構(gòu)Fig.1 Data structure of triangle

1.1 點(diǎn)與三角形的位置判斷

點(diǎn)與三角形之間的位置關(guān)系可以根據(jù)其坐標(biāo)的相對關(guān)系來判斷.對于任意三個點(diǎn)A(xA,yA),B(xB,yB),C(xC,yC),其中

若Flag(A,B,C)>0,則A、B、C按逆時針方向分布;若Flag(A,B,C)<0,則A、B、C按順時針方向分布;若Flag(A,B,C)=0,則A、B、C三點(diǎn)共線.如圖2(a) 所示,若Flag(C,A,M)、Flag(A,B,M)、Flag(B,C,M)三者的值都大于零,則點(diǎn)M位于△ABC的內(nèi)部.若三者中一個值為零且其余二者皆為正值,則位于某條邊上,如圖2(b) 中Flag(A,B,M) 為零,Flag(C,A,M)、Flag(B,C,M)為正值,故點(diǎn)M位于邊AB上.若三者中至少有一個為負(fù)值,則點(diǎn)位于三角形的外部.如圖2(c) 所示,Flag(A,B,M)為負(fù)值,故點(diǎn)M位于邊AC的外側(cè).當(dāng)然,點(diǎn)位于三角形外側(cè)還會出現(xiàn)圖2(d) 與圖2(e) 的情況.在圖2(d) 中,Flag(A,B,M)、Flag(B,C,M) 皆為負(fù)值,在此情況下,由于AB為邊2,而BC為邊3,本文中優(yōu)先取編號在前的邊,故認(rèn)為M位于邊AB的外側(cè).在圖2(e) 中,點(diǎn)M雖位于三角形外部且與邊AC共線,但是Flag(B,C,M) 為負(fù)值,故本文認(rèn)為點(diǎn)M位于邊BC的外側(cè).

1.2 基于邊指針?biāo)阉鞯穆窂酱_定

圖2 點(diǎn)與三角形位置關(guān)系判斷Fig.2 Judgment of positional relationship between point and triangle

在搜索目標(biāo)三角形的過程中,搜索路徑通過判斷插入點(diǎn)與當(dāng)前被搜索三角形的位置關(guān)系來確定的.如圖3 所示,點(diǎn)V為插入點(diǎn),假設(shè)△AIJ存儲在三角形鏈表的表頭,搜索過程如下所述.1) 檢測點(diǎn)V與△AIJ的位置關(guān)系,首先確定了點(diǎn)V位于△AIJ的外部,然后確定點(diǎn)V位于△AIJ的哪條邊的外側(cè),根據(jù)式(1) 可知點(diǎn)V位于邊IJ外側(cè),故下一個被搜索的三角形為△AIJ的邊IJ上的邊指針p1所指的△IEJ.2) 用同樣的方法確定接下來的被搜索三角形分別是△EFJ、△EHF,然后根據(jù)式(1)可知點(diǎn)V位于△EHF的內(nèi)部,故△EHF為點(diǎn)V的目標(biāo)三角形.在整個搜索過程中,共經(jīng)過4 次搜索找到點(diǎn)V的目標(biāo)三角形,搜索路徑為:△AIJ(p1)→△IEJ(p2) →△EFJ(p3) →△EHF.邊指針?biāo)阉鞯姆绞?由于在搜索目標(biāo)三角形的過程中通過邊指針的方向性可以快速地定位目標(biāo)三角形,使搜索路徑大大縮短,從而大大降低了三角剖分的耗時.

圖3 點(diǎn)V 的目標(biāo)三角形的搜索路徑Fig.3 Search path for target triangle of point V

2 基于邊指針?biāo)阉骷皡^(qū)域劃分的三角剖分

2.1 區(qū)域分塊

基于邊指針?biāo)阉髂繕?biāo)三角形的方法,雖然可以利用插入點(diǎn)與三角形的位置關(guān)系來快速定位目標(biāo)三角形,但是在點(diǎn)數(shù)量很大的情況下,目標(biāo)三角形的搜索路徑可能仍然會比較長,此時依舊較為耗時.因此,在邊指針?biāo)阉鞯幕A(chǔ)上,提出了區(qū)域劃分的方案,以縮小目標(biāo)三角形的搜索范圍.

設(shè)區(qū)域分塊為N × N,構(gòu)造超級三角形的時候,首先遍歷所有散點(diǎn)找到最大的縱橫坐標(biāo)值Xmax、Ymax,取兩者中較大者得到max,然后根據(jù)max構(gòu)造超級三角形,其各點(diǎn)坐標(biāo)為:

區(qū)域劃分是指將包含超級三角形的正方形劃分成N ×N個大小相同的區(qū)域,并將這些區(qū)域存儲在二維數(shù)組中.每個區(qū)域的位置坐標(biāo)值X和Y對應(yīng)于其在二維數(shù)組中的存儲位置,如位置坐標(biāo)(1,2) 的區(qū)域塊存儲在數(shù)組area[1][2]中.對于插入點(diǎn)P(x,y),它的區(qū)域坐標(biāo)由其本身的橫縱坐標(biāo)值確定:

在式(3) 中,L指包含超級三角形的正方形的邊長.

區(qū)域可以劃分成不同的大小,對應(yīng)的區(qū)域數(shù)量也會不同.對于某個確定的點(diǎn)集,如果區(qū)域太大,搜索范圍會變大.但是,如果區(qū)域太小,則過多的區(qū)域很難被分配到入口三角形,從而導(dǎo)致入口三角形的使用率下降,進(jìn)一步導(dǎo)致搜索目標(biāo)三角形的時間增加.所以對于處理不同規(guī)模的點(diǎn)集,最優(yōu)的分塊也會不同.

對于點(diǎn)集V={V1,V2,···,Vn},兩個點(diǎn)組成一條邊,三條邊組成一個三角形,三角形通過公共邊上的邊指針相互連接組成三角形網(wǎng)格.基于邊指針?biāo)阉骷皡^(qū)域劃分的Delaunay 三角剖分的數(shù)據(jù)結(jié)構(gòu)如表1 所示.

表1 基于邊指針及區(qū)域劃分的算法數(shù)據(jù)結(jié)構(gòu)Table 1 Data structure of algorithm based on edge-pointer and region-division

數(shù)據(jù)結(jié)構(gòu)包括4 部分:點(diǎn)、邊、三角形和區(qū)域.每個頂點(diǎn)包含x和y坐標(biāo)以及區(qū)域入口標(biāo)志entryflag;連接頂點(diǎn)的邊包含頂點(diǎn)Vi和Vj的編號;三角形采用空間網(wǎng)狀結(jié)構(gòu),包含頂點(diǎn)Vi、Vj、Vk的編號,三角形的區(qū)域入口標(biāo)志entry以及該區(qū)域的坐標(biāo)X、Y,將位置相鄰的三角形連接起來的邊指針p1、p2、p3,區(qū)域坐標(biāo)只有在entry=1 時才意義,如果entry=1,意味著三角形是該區(qū)域的入口三角形;區(qū)域塊包含區(qū)域是否分配入口三角形的標(biāo)志valid,以及區(qū)域的入口三角形指針對于一個入口三角形,在其三個頂點(diǎn)中存在一個入口頂點(diǎn),其值被置為1,并且入口頂點(diǎn)位于于該三角形所記錄的區(qū)域中.邊指針?biāo)阉骷皡^(qū)域劃分?jǐn)?shù)據(jù)結(jié)構(gòu)中不同區(qū)域之間的關(guān)系如圖4 所示,不同局域會分配一個入口三角形作為該區(qū)域的搜索入口,該入口三角形再通過邊指針指向存在該區(qū)域內(nèi)或其它區(qū)域內(nèi)的相鄰三角形.

圖4 結(jié)構(gòu)體關(guān)系圖Fig.4 Structure diagram

2.2 搜索目標(biāo)三角形

實(shí)現(xiàn)Delaunay 三角剖分最重要也最耗時的部分就是搜索目標(biāo)三角形,本文對目標(biāo)三角形的搜索過程如算法1 所示.在基于邊指針?biāo)阉鞯幕A(chǔ)上,區(qū)域劃分的搜索方式為每個區(qū)域分配了入口三角形.這使得對散點(diǎn)的目標(biāo)三角形的搜索不是從三角形鏈表的表頭開始,而是從入口三角形開始,故搜索的起始三角形更接近目標(biāo)三角形,目標(biāo)三角形的搜索路徑進(jìn)一步被簡化.

圖5 展示了基于邊指針?biāo)阉骷皡^(qū)域劃分算法中搜索目標(biāo)三角形的過程.如圖5(a) 所示,包含超級三角形的正方形被劃分成2×2 個區(qū)域.插入點(diǎn)V時,首先根據(jù)點(diǎn)V的坐標(biāo)確定其所在區(qū)域?yàn)閍rea[1][0].由于在點(diǎn)V之前,點(diǎn)H與點(diǎn)K已經(jīng)被插入該區(qū)域,故該區(qū)域一定存在入口三角形,假設(shè)△GCH為入口三角形,對點(diǎn)V的目標(biāo)三角形的搜索從△GCH開始.接下來,按照第1.2 節(jié)中所述邊指針?biāo)阉鞯姆绞?確定目標(biāo)三角形的搜索路徑為:△GCH(p1) →△DGH(p2) →△EDH(p3) →△EHF,目標(biāo)三角形為△EHF.

如果檢測到點(diǎn)V位于三角形的某條邊上,則需要根據(jù)邊指針?biāo)阉髁硪粋€包含該點(diǎn)的一個三角形.如圖5(b) 所示,點(diǎn)V位于邊HF上,當(dāng)找到△EHF之后,根據(jù)邊HF上的邊指針p4找到共邊三角形△FHK.故△EHF與△FHK為點(diǎn)V的目標(biāo)三角形,并且點(diǎn)V 將會被插入這兩個三角形所構(gòu)成的四邊形內(nèi).

如果在點(diǎn)V所在區(qū)域中沒有入口三角形,則從最新插入的點(diǎn)生成的三角形開始搜索目標(biāo)三角形,搜索路徑由邊指針確定.由于該算法主要用于三維重建,而三維重建中掃描得到的連續(xù)點(diǎn)在位置上可能是相鄰的,因此,由最新插入點(diǎn)生成的三角形可能更接近當(dāng)前插入點(diǎn)的目標(biāo)三角形.

在傳統(tǒng)算法中,假設(shè)當(dāng)前所有三角形按一下順序存儲在三角形鏈表中:△AIJ、△AJF、△IEJ、△EFJ、△IBL、△ILD、△IDE、△EDH、△EHF、△FHK、△CFK、△BGL、△DLG、△DGH、△GCH.插入散點(diǎn)V時,則需要依次判斷鏈表中在△EHF之前的三角形是否包含點(diǎn)V,可以發(fā)現(xiàn)一共需要經(jīng)過9 次搜索才能找到目標(biāo)三角形,而本文的算法只需要經(jīng)過4 次搜索就能找到目標(biāo)三角形,搜索深度為傳統(tǒng)算法的44.4%.隨著點(diǎn)集的規(guī)模不斷變大,傳統(tǒng)算法的執(zhí)行時間將會呈指數(shù)增長,本文算法的優(yōu)越性會越來越明顯.

圖5 搜索點(diǎn)V 的目標(biāo)三角形Fig.5 Searching for target triangle of point V

目標(biāo)三角形的定位是根據(jù)插入點(diǎn)與當(dāng)前搜索三角形的位置關(guān)系來確定的,通過判斷插入點(diǎn)位于三角形的哪條邊的外側(cè)來確定下一個被搜索的三角形.每一次被搜索的三角形都比上一次的三角形更接近插入點(diǎn),因此通過這種方式一定能找到目標(biāo)三角形,故該算法是收斂的.

2.3 區(qū)域入口三角形及邊指針的更新

隨著點(diǎn)地不斷插入,區(qū)域的入口三角形也需要不斷更新以確保其不會隨著某些三角形的拆分而消失.同時,與新三角形有關(guān)的邊指針也需要被更新以確保三角形之間能夠互相找到相鄰的三角形.找到目標(biāo)三角形之后,需要將點(diǎn)插入到目標(biāo)三角形中,并使用空圓特性對新生成的三角形進(jìn)行Delaunay 規(guī)則判斷及調(diào)整違背規(guī)則的三角形.在此過程中,需要更新入口三角形及邊指針,入口三角形的更新分為本區(qū)域的更新以及他區(qū)域的更新.

如圖6 所示,找到目標(biāo)三角形△EHF之后,插入點(diǎn)V,生成了三個新的三角形(△EHV,△HFV與△FEV),并將原目標(biāo)三角形△EHF從三角形鏈表中刪掉.首先,對本區(qū)域的入口三角形進(jìn)行更新.如果在此之前,區(qū)域area[1][0]沒有分配到入口三角形,則選擇△EHV為該區(qū)域的入口;如果area[1][0]之前已經(jīng)分配了入口三角形如第2.2 節(jié)中所提到的△GCH,則△EHV代替△GCH作為該區(qū)域的新入口,并將點(diǎn)V指定為入口頂點(diǎn).然后,根據(jù)被刪除三角形的標(biāo)志位及區(qū)域坐標(biāo)信息檢測其是否為其他區(qū)域的入口,若是,則需要指定一個新的三角形來更新此區(qū)域的入口.例如,如果三角形△EHF是區(qū)域area[1][1]的入口,判斷△EHF的哪個頂點(diǎn)是入口頂點(diǎn),根據(jù)點(diǎn)的入口標(biāo)志位得出點(diǎn)F是入口頂點(diǎn),因此,包含點(diǎn)F的△FEV成為了area[1][1]的新入口.

圖6 入口三角形及邊指針的更新Fig.6 Update of entry triangle and edge-pointer

此外,還需要更新和原三角形△EHF有關(guān)的邊指針.在圖6 中,隨著△EHF的刪除,原本指向該三角形的邊指針應(yīng)該指向新的三角形,△EDH的邊EH上的邊指針p3現(xiàn)在應(yīng)該指向△EHV,同理,△EFJ的邊EF上的邊指針p5、△FHK的邊FH上的邊指針p6現(xiàn)在分別指向其相鄰三角形△FEV、△HFV.

在進(jìn)行Delaunay 規(guī)則判斷的過程中,區(qū)域入口及邊指針會以同樣的方式更新,此處不再贅述.

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

為了驗(yàn)證基于邊指針?biāo)阉骷皡^(qū)域劃分的三角剖分算法的效率,本文對隨機(jī)生成的不同規(guī)模大小的點(diǎn)集進(jìn)行三角剖分,并比較了傳統(tǒng)的Delaunay 三角剖分(TD)、使用CGAL 庫的三角剖分、基于邊指針?biāo)阉鞯娜瞧史?EPD)、基于邊指針?biāo)阉骱蛥^(qū)域劃分相結(jié)合的三角剖分(EPRDD) 幾種算法之間的執(zhí)行時間,此處的執(zhí)行時間不包括讀取插入點(diǎn)數(shù)據(jù)的時間.

在進(jìn)行區(qū)域劃分的時候,包含超級三角形的正方形被劃分成了15×15 個區(qū)域.本實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM) CPU i5-8500 @ 3.00 GHz,16 GB 內(nèi)存,Windows 10,VS2013,64 位操作系統(tǒng),得到的結(jié)果如表2 所示:

表2 算法的執(zhí)行時間(s)Table 2 Running time of algorithms (s)

從表2 可以看出,當(dāng)插入點(diǎn)的數(shù)量為2 萬時,基于邊指針?biāo)阉鞯娜瞧史趾臅r為傳統(tǒng)算法的1/201,加入?yún)^(qū)域劃分之后,算法的執(zhí)行時間為傳統(tǒng)算法1/970.當(dāng)插入點(diǎn)的數(shù)量為10 萬時,基于邊指針的搜索算法執(zhí)行時間分別為傳統(tǒng)算法的1/643,而基于邊指針及區(qū)域劃分算法的執(zhí)行時間為傳統(tǒng)算法的1/4 886.此外,與CGAL 算法相比,只使用邊指針的算法優(yōu)勢并不是很明顯;但是,邊指針與區(qū)域劃分相結(jié)合之后,算法的耗時明顯低于CGAL 算法.當(dāng)對10 萬個點(diǎn)進(jìn)行三角剖分的時候,CGAL 算法需要8.594 s,而基于邊指針及區(qū)域劃分的算法僅僅需要0.813 s 就能完成.

為了比較幾種算法的執(zhí)行時間與散點(diǎn)數(shù)量的關(guān)系,繪制了圖7 所示折線圖.由于傳統(tǒng)算法的執(zhí)行時間遠(yuǎn)遠(yuǎn)高于其余幾種算法,故不與其他算法作比較.從圖7 可以看出,隨著散點(diǎn)數(shù)量的增多,CGAL算法,基于邊指針?biāo)阉鞯乃惴ㄅc基于邊指針?biāo)阉骷皡^(qū)域劃分算法的執(zhí)行時間基本上都是呈線性增長的,CGAL 算法與基于邊指針?biāo)阉鞯乃惴ǖ膱?zhí)行時間隨散點(diǎn)數(shù)量變化的增長速度還是較快,但是基于邊指針及區(qū)域劃分算法的執(zhí)行時間的增長速度較為緩慢,斜率遠(yuǎn)遠(yuǎn)小于前兩種算法.可以得知,隨著插入點(diǎn)數(shù)量的增長,邊指針?biāo)阉髋c區(qū)域劃分結(jié)合的方法在時間上的優(yōu)勢將會越來越大.

圖7 執(zhí)行時間比較Fig.7 Comparison of run time

進(jìn)一步對幾種算法的平均搜索深度進(jìn)行比較,結(jié)果如表3 所示.搜索深度是指在將散點(diǎn)插入到Delaunay 網(wǎng)格中的過程中搜索三角形的次數(shù),搜索深度越小,三角剖分的實(shí)時性越好.由于CGAL 的源代碼沒有找到,在此處未對CGAL 的搜索深度進(jìn)行比較.從表中可以看出,在傳統(tǒng)算法中平均搜索深度與散點(diǎn)數(shù)目也是線性增長的,而基于邊指針?biāo)阉骷皡^(qū)域劃分的算法的平均搜索深度很小.即使散點(diǎn)數(shù)量成倍增加,平均搜索深度也只是稍微增加,證明邊指針與區(qū)域劃分結(jié)合的算法實(shí)時性要高于傳統(tǒng)Delaunay 三角剖分算法.其原因在于,區(qū)域劃分縮小了目標(biāo)三角形的搜索范圍,邊指針優(yōu)化了搜索方向,最終使得搜索深度大大減小,執(zhí)行時間得到降低.

表3 算法的平均搜索深度Table 3 Average search depth of algorithms

4 結(jié)論

為了滿足三維重建的實(shí)時性,針對其基礎(chǔ)部分三角剖分處理時間過長的問題,本文提出了一種基于邊指針?biāo)阉骷皡^(qū)域劃分的Delaunay 三角剖分算法.在對傳統(tǒng)Delaunay 三角剖分算法進(jìn)行研究及實(shí)現(xiàn)的基礎(chǔ)上,進(jìn)一步優(yōu)化了三角形存儲的數(shù)據(jù)結(jié)構(gòu)及搜索過程,設(shè)計了一種通過邊指針反映三角形空間相鄰關(guān)系的三角形數(shù)據(jù)結(jié)構(gòu)來取代傳統(tǒng)算法中的一維三角形鏈表.由于邊指針具有方向性,可以用于確定距離插入點(diǎn)最近的相鄰三角形,從而快速確定目標(biāo)三角形的搜索方向.在此基礎(chǔ)上將整個超級三角形進(jìn)行區(qū)域劃分,且隨著散點(diǎn)的插入,每個區(qū)域?qū)峙湟粋€區(qū)域入口三角形,作為搜索目標(biāo)三角形的起始三角形,且入口三角形在構(gòu)建Delaunay 三角網(wǎng)的過程中會不斷更新.這使得目標(biāo)三角形的搜索范圍由以前的整個三角形鏈表縮小到插入點(diǎn)所在區(qū)域,從而進(jìn)一步縮短搜索的起始三角形與目標(biāo)三角形之間的距離,大大縮小了搜索范圍,降低了搜索目標(biāo)三角形的耗時,以滿足三維重建的實(shí)時性需求.實(shí)驗(yàn)結(jié)果表明,該算法的執(zhí)行時間隨散點(diǎn)數(shù)量的增長較為緩慢,且散點(diǎn)數(shù)量為10 萬時,所耗費(fèi)的執(zhí)行時間僅為0.813 s.

本文中的區(qū)域劃分為固定劃分,當(dāng)散點(diǎn)分布密度變化大時,對于密度大的區(qū)域搜索深度可能會相應(yīng)增加.為了進(jìn)一步擴(kuò)大算法的適用范圍,后續(xù)研究中將引入自適應(yīng)算法,尋求一種能夠根據(jù)散點(diǎn)分布密度或者搜索深度的變化對區(qū)域劃分方式進(jìn)行調(diào)整的優(yōu)化算法.