楊振發(fā)，萬(wàn) 剛，李 鋒，李 濱

（1.信息工程大學(xué)，河南 鄭州 450000；2. 75711部隊(duì)，廣東 廣州 510000）

多分辨率LOD的海量點(diǎn)云顯示技術(shù)研究

楊振發(fā)1，萬(wàn) 剛1，李 鋒1，李 濱2

（1.信息工程大學(xué)，河南 鄭州 450000；2. 75711部隊(duì)，廣東 廣州 510000）

利用八叉樹(shù)數(shù)據(jù)結(jié)構(gòu)對(duì)海量點(diǎn)云進(jìn)行分塊處理，將八叉樹(shù)葉結(jié)點(diǎn)的點(diǎn)云逐層隨機(jī)采樣后保存在外存中構(gòu)建多分辨率LOD數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)了一種基于視點(diǎn)的多分辨率點(diǎn)云內(nèi)外存調(diào)度策略，實(shí)現(xiàn)了海量點(diǎn)云的流暢顯示。通過(guò)對(duì)一組海量點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，分析了不同八叉樹(shù)劃分深度對(duì)八叉樹(shù)劃分、多分辨率數(shù)據(jù)構(gòu)建以及顯示的影響。

八叉樹(shù)；多分辨率LOD；海量點(diǎn)云；內(nèi)外存調(diào)度；點(diǎn)云繪制

隨著三維激光掃描技術(shù)和多角度攝影測(cè)量稠密匹配技術(shù)的發(fā)展，海量點(diǎn)云數(shù)據(jù)的處理和實(shí)時(shí)繪制為城市高效建模提出一種新的解決方案。傳統(tǒng)的基于三角面的模型繪制需要額外存儲(chǔ)點(diǎn)之間的拓?fù)潢P(guān)系，而基于點(diǎn)的表達(dá)是最自然、直接的方式，在大場(chǎng)景中瀏覽足夠密集的點(diǎn)模型時(shí)，采樣點(diǎn)在屏幕上的投影小于單位像素，可直接用于大區(qū)域場(chǎng)景的可視化表達(dá)。因此，海量點(diǎn)云數(shù)據(jù)的實(shí)時(shí)繪制作為點(diǎn)云數(shù)據(jù)處理和分析的基礎(chǔ)，成為了計(jì)算機(jī)視覺(jué)領(lǐng)域的研究熱點(diǎn)。

國(guó)內(nèi)外學(xué)者對(duì)海量點(diǎn)云的快速顯示進(jìn)行了研究，主要關(guān)注點(diǎn)在優(yōu)化點(diǎn)云數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)調(diào)度方式。Surfels[1]和Qsplat[2,3]都通過(guò)樹(shù)狀結(jié)構(gòu)進(jìn)行數(shù)據(jù)的存儲(chǔ)，并通過(guò)多細(xì)節(jié)層次減少內(nèi)存消耗，但二者預(yù)處理過(guò)程比較費(fèi)時(shí)，不平衡的樹(shù)狀結(jié)構(gòu)易導(dǎo)致樹(shù)深過(guò)大進(jìn)而降低查詢(xún)效率。文獻(xiàn)[4]采用改進(jìn)四叉樹(shù)的數(shù)據(jù)組織方法管理機(jī)載激光點(diǎn)云，并采用分段文件映射隨機(jī)抽取不同細(xì)節(jié)的點(diǎn)云來(lái)實(shí)現(xiàn)海量點(diǎn)云的管理和顯示，這種二維的數(shù)據(jù)管理方法難以穩(wěn)定支持視錐體裁剪的可視化算法。文獻(xiàn)[5]采用計(jì)算機(jī)集群的并行訪問(wèn)技術(shù)，將海量點(diǎn)云分配到多個(gè)服務(wù)器，以提高數(shù)據(jù)的管理效率。文獻(xiàn)[6,7]通過(guò)數(shù)據(jù)分塊降低海量數(shù)據(jù)的復(fù)雜性，并建立數(shù)據(jù)塊的多分辨率結(jié)構(gòu)，實(shí)現(xiàn)了海量點(diǎn)云在一般配置機(jī)器上的輕松瀏覽，但這種算法僅適用于均勻分布的稠密點(diǎn)云模型。

針對(duì)以上問(wèn)題，本文采用易于實(shí)現(xiàn)的八叉樹(shù)數(shù)據(jù)結(jié)構(gòu)對(duì)海量點(diǎn)云進(jìn)行分塊處理，將八叉樹(shù)葉結(jié)點(diǎn)上的點(diǎn)云進(jìn)行隨機(jī)采樣建立點(diǎn)云八叉樹(shù)的多分辨率數(shù)據(jù)結(jié)構(gòu)，并逐層保存在外存設(shè)備中，最后設(shè)計(jì)了一種基于視點(diǎn)的內(nèi)外存調(diào)度策略實(shí)現(xiàn)了海量點(diǎn)云的流暢顯示，為海量點(diǎn)云的數(shù)據(jù)處理和分析奠定基礎(chǔ)。本文的算法流程如圖1所示。

圖1 海量點(diǎn)云實(shí)時(shí)顯示流程圖

1 點(diǎn)云的八叉樹(shù)劃分與多分辨率外存組織

八叉樹(shù)是四叉樹(shù)在三維空間上的延伸[8]，由于其采用規(guī)則的格網(wǎng)剖分，具有較好的可操作性，能滿足三維視錐體裁剪算法，因此，本文采用八叉樹(shù)的數(shù)據(jù)索引結(jié)構(gòu)，在對(duì)海量點(diǎn)云進(jìn)行數(shù)據(jù)組織的基礎(chǔ)上，以一定的采樣率建立各層級(jí)的多分辨率點(diǎn)云數(shù)據(jù)，并以文件映射的方式將海量點(diǎn)云進(jìn)行外存。

1.1 海量點(diǎn)云的八叉樹(shù)劃分與文件組織

規(guī)則的空間八叉樹(shù)將點(diǎn)云數(shù)據(jù)所處的正方體包圍盒進(jìn)行規(guī)則的八等分，結(jié)點(diǎn)的收斂條件一般為點(diǎn)云的數(shù)量閾值或者最高深度閾值。經(jīng)遞歸劃分之后，中間結(jié)點(diǎn)僅作為過(guò)渡，沒(méi)有存儲(chǔ)點(diǎn)云數(shù)據(jù)，點(diǎn)云數(shù)據(jù)實(shí)際上保存在葉結(jié)點(diǎn)中。

結(jié)合數(shù)據(jù)的外存分塊映射組織，本文提出的點(diǎn)云八叉樹(shù)劃分算法步驟如下：

算法描述：點(diǎn)云的八叉樹(shù)劃分及外存文件組織。算法輸入：點(diǎn)云集合、八叉樹(shù)的最大深度DepthMax、外存點(diǎn)云的根目錄。

算法輸出：基于八叉樹(shù)的點(diǎn)云外存組織結(jié)構(gòu)。

步驟1：計(jì)算點(diǎn)云集合的最小外包圍盒大小，以包圍盒最大邊長(zhǎng)為八叉樹(shù)邊長(zhǎng)，以包圍盒中心為八叉樹(shù)中心，建立點(diǎn)云八叉樹(shù)的最小正方體外包圍盒，并在外存的根目錄下保存外包圍盒結(jié)構(gòu)信息。

步驟2：如果八叉樹(shù)深度小于DepthMax，將空間等分為8個(gè)子結(jié)點(diǎn)childi（i=0～7），并將該結(jié)點(diǎn)的點(diǎn)云分配到子結(jié)點(diǎn)中，進(jìn)入步驟3；如果八叉樹(shù)深度等于DepthMax，則停止劃分，進(jìn)入步驟4。

步驟3：遍歷8個(gè)子結(jié)點(diǎn)，如果結(jié)點(diǎn)為空，則繼續(xù)下一個(gè)子結(jié)點(diǎn)；如果不為空，創(chuàng)建新的文件夾，并命名為子結(jié)點(diǎn)編號(hào)i，保存結(jié)點(diǎn)的外包圍盒信息，回到步驟2。

步驟4：將葉結(jié)點(diǎn)的點(diǎn)云數(shù)據(jù)以二進(jìn)制格式保存。

步驟5：退出算法。

算法的流程如圖2所示。

圖2 點(diǎn)云的八叉樹(shù)劃分與外存組織

1.2 點(diǎn)云的多分辨率LOD建立

細(xì)節(jié)分層技術(shù)[9]（levels of details，簡(jiǎn)稱(chēng)LOD）為解決仿真效果與仿真實(shí)時(shí)性之間的矛盾提供了一種有效的解決方案，已在基于三維網(wǎng)格的實(shí)時(shí)繪制中得到廣泛應(yīng)用[10]。為解決海量點(diǎn)云數(shù)據(jù)實(shí)時(shí)顯示的調(diào)度問(wèn)題，在構(gòu)建八叉樹(shù)索引的基礎(chǔ)上，本文利用隨機(jī)采樣的方法，以葉結(jié)點(diǎn)的點(diǎn)云為起點(diǎn)，采用深度遍歷的順序向上逐層采樣，得到點(diǎn)云的八叉樹(shù)多分辨率LOD數(shù)據(jù)，并保存在上一節(jié)所述的文件組織結(jié)構(gòu)下，如圖3所示。算法描述如下：

算法描述：點(diǎn)云的八叉樹(shù)多分辨率LOD生成。

算法輸入：點(diǎn)云隨機(jī)采樣率sample。

算法輸出：各層次的多分辨率點(diǎn)云數(shù)據(jù)。

步驟1：將點(diǎn)云的根結(jié)點(diǎn)加入八叉樹(shù)結(jié)點(diǎn)鏈表Vector中，如果鏈表末結(jié)點(diǎn)為空，則退出算法；否則進(jìn)入步驟2。

步驟2：如果鏈表的末結(jié)點(diǎn)是八叉樹(shù)結(jié)構(gòu)的非葉子結(jié)點(diǎn)，進(jìn)入步驟3；如果鏈表的最后結(jié)點(diǎn)是八叉樹(shù)結(jié)構(gòu)的葉子結(jié)點(diǎn)，進(jìn)入步驟4。

步驟3：遍歷本結(jié)點(diǎn)的8個(gè)子結(jié)點(diǎn)，將子結(jié)點(diǎn)加入鏈表結(jié)構(gòu)，如果鏈表末結(jié)點(diǎn)不為空，回到步驟2；如果為空結(jié)點(diǎn)，將鏈表末結(jié)點(diǎn)刪除。

圖3 點(diǎn)云的多分辨率LOD建立與外存映射

步驟4：遍歷鏈表中的所有非葉子結(jié)點(diǎn)，各層級(jí)采樣率計(jì)算公式為SamoleRatio=samplesize(Vector)-Depthcurrent-1，其中size（Vector）表示鏈表中結(jié)點(diǎn)總數(shù)，DepthMax表示該層級(jí)的深度值。對(duì)葉結(jié)點(diǎn)按采樣率進(jìn)行隨機(jī)采樣，得到該層級(jí)非葉結(jié)點(diǎn)的點(diǎn)云，并將點(diǎn)云保存在該層級(jí)八叉樹(shù)目錄下，如果文件已經(jīng)存在，則對(duì)點(diǎn)云進(jìn)行合并操作。

2 基于視點(diǎn)的點(diǎn)云內(nèi)外存調(diào)度繪制技術(shù)

內(nèi)外存調(diào)度技術(shù)是指計(jì)算機(jī)需要處理的數(shù)據(jù)一部分放在內(nèi)存中[11]，另一部分放在外部存儲(chǔ)設(shè)備中，并通過(guò)I/O進(jìn)行調(diào)度的技術(shù)。該技術(shù)是處理數(shù)據(jù)容量大于計(jì)算機(jī)內(nèi)存時(shí)的常用技術(shù)。在建立八叉樹(shù)索引結(jié)構(gòu)下的多分辨率LOD點(diǎn)云數(shù)據(jù)的基礎(chǔ)上，本文設(shè)計(jì)了一種基于視點(diǎn)的多分辨率點(diǎn)云內(nèi)外存調(diào)度策略：將點(diǎn)云的八叉樹(shù)結(jié)構(gòu)保存在內(nèi)存中，點(diǎn)云的多分辨率數(shù)據(jù)存儲(chǔ)在外部存儲(chǔ)設(shè)備中。當(dāng)觀察視點(diǎn)位于某一八叉樹(shù)父結(jié)點(diǎn)外，八叉樹(shù)外包圍盒中心點(diǎn)到視點(diǎn)的距離小于閾值R1時(shí)，便從外存中加載該結(jié)點(diǎn)對(duì)應(yīng)的多分辨率點(diǎn)云數(shù)據(jù)；當(dāng)距離進(jìn)一步減少且小于閾值R2時(shí)，遍歷父結(jié)點(diǎn)下的子結(jié)點(diǎn)，當(dāng)子結(jié)點(diǎn)的包圍盒中心到視點(diǎn)的距離小于閾值r時(shí)，從外存中加載該子結(jié)點(diǎn)，反之則從內(nèi)存中卸載該結(jié)點(diǎn)的點(diǎn)云數(shù)據(jù)。如圖4所示，R表示某一八叉樹(shù)結(jié)點(diǎn)半徑大小。將點(diǎn)云根結(jié)點(diǎn)的LOD半徑閾值設(shè)為無(wú)窮大，此時(shí)，一進(jìn)入場(chǎng)景便可以觀察到三維場(chǎng)景的整體情況。另外在使用OpenGL圖形渲染語(yǔ)言繪制點(diǎn)云數(shù)據(jù)時(shí)，通過(guò)開(kāi)辟另一線程來(lái)預(yù)先判斷哪些多分辨率數(shù)據(jù)需要從外存中加載或者從內(nèi)存中卸載，便可以在不影響繪制線程的前提下，提高內(nèi)外存調(diào)度的效率，實(shí)現(xiàn)海量點(diǎn)云的流暢顯示與調(diào)度。

圖4 基于視點(diǎn)的多分辨率點(diǎn)云調(diào)度策略

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

本文的點(diǎn)云數(shù)據(jù)來(lái)源于無(wú)人機(jī)航拍的影像經(jīng)過(guò)三維重建得到的稠密點(diǎn)云數(shù)據(jù)，點(diǎn)的數(shù)據(jù)組成包括三維坐標(biāo)信息（經(jīng)度、緯度和高程值）和顏色信息（RGB顏色值）。實(shí)驗(yàn)區(qū)域?yàn)槌菂^(qū)中的校園，占地面積為1.25 km2；點(diǎn)的數(shù)量為219 367 498，文件大小為3.26 GB。計(jì)算機(jī)為普通PC，配置為Core i5 2.4 GHz、4 GB內(nèi)存、750 GB硬盤(pán)，軟件方面為Windows7 64位操作系統(tǒng)，VS2010 編譯環(huán)境，OpenGL三維渲染語(yǔ)言。為了比較不同的八叉樹(shù)深度值對(duì)八叉樹(shù)構(gòu)建、多分辨率LOD生成以及點(diǎn)云顯示效果的影響，設(shè)計(jì)了兩組實(shí)驗(yàn)進(jìn)行比較分析。

實(shí)驗(yàn)一：海量點(diǎn)云的八叉樹(shù)構(gòu)建和多分辨率外存組織。八叉樹(shù)深度值分別取3～8，多分辨率點(diǎn)云生成時(shí)隨機(jī)采樣率sample設(shè)為0.25，數(shù)據(jù)處理時(shí)各主要步驟耗時(shí)如表1所示。

表1 不同深度值下點(diǎn)云的八叉樹(shù)劃分與多分辨率點(diǎn)云生成的時(shí)間比較/s

可以看出，隨著八叉樹(shù)劃分深度的增加，構(gòu)建八叉樹(shù)和生成點(diǎn)云的多分辨率數(shù)據(jù)結(jié)構(gòu)的時(shí)間消耗近似呈現(xiàn)指數(shù)增長(zhǎng)的趨勢(shì)。

實(shí)驗(yàn)二： 基于視點(diǎn)的點(diǎn)云多分辨率內(nèi)外存調(diào)度繪制。以實(shí)驗(yàn)一得到的不同八叉樹(shù)深度值（選取深度值為3～6）的多分辨點(diǎn)云數(shù)據(jù)為顯示實(shí)驗(yàn)的數(shù)據(jù)，視點(diǎn)調(diào)度的閾值R1設(shè)為4R，R2設(shè)為2R，r設(shè)為R（其中R為某一父結(jié)點(diǎn)的外包圍盒半徑值）。使用OpenGL三維渲染引擎的點(diǎn)圖元為繪制單元，分別賦予其點(diǎn)的坐標(biāo)信息和顏色信息。圖5為4種不同數(shù)據(jù)在點(diǎn)云加載和視點(diǎn)漫游階段，內(nèi)存和硬盤(pán)讀寫(xiě)隨時(shí)間變化的情況，從左到右分別為八叉樹(shù)深度值3到6的4種點(diǎn)云數(shù)據(jù)。

從4個(gè)圖可以看出，點(diǎn)云在顯示時(shí)，首先從硬盤(pán)上讀取根結(jié)點(diǎn)層級(jí)上的多分辨率點(diǎn)云數(shù)據(jù)，當(dāng)視點(diǎn)逐漸拉近時(shí)，從硬盤(pán)上加載或者卸載相應(yīng)的多分辨率點(diǎn)云數(shù)據(jù)，導(dǎo)致內(nèi)存使用產(chǎn)生波動(dòng)；當(dāng)八叉樹(shù)最大深度較小時(shí)，各深度上的多分辨率點(diǎn)云數(shù)據(jù)相對(duì)較大，因此在內(nèi)外存調(diào)度時(shí)內(nèi)存波動(dòng)幅度較大；反之，則內(nèi)外存調(diào)度的波動(dòng)幅度較??；另外，由于點(diǎn)云在顯示時(shí)，需從外存的八叉樹(shù)結(jié)構(gòu)的文件中讀取各層級(jí)的多分辨率數(shù)據(jù)結(jié)構(gòu)，因此隨著深度的增加，顯示用時(shí)明顯增加。圖6為4種不同八叉樹(shù)最大深度數(shù)據(jù)的顯示效果圖。當(dāng)最大深度值小時(shí)，被加載的子結(jié)點(diǎn)點(diǎn)云較大，內(nèi)存消耗相應(yīng)增加；深度大時(shí)，需要加載的多分辨率結(jié)點(diǎn)較多，增加了CPU的調(diào)度負(fù)擔(dān)。在三維點(diǎn)云中漫游時(shí)，4種測(cè)試數(shù)據(jù)均可以保證幀率在20～40之間，符合流暢顯示的要求。

圖5 不同深度值多分辨率點(diǎn)云顯示的內(nèi)存使用和內(nèi)外存調(diào)度情況

圖6 不同八叉樹(shù)最大深度值下的海量點(diǎn)云顯示效果

4 結(jié) 語(yǔ)

在普通計(jì)算機(jī)上，海量點(diǎn)云數(shù)據(jù)的流暢顯示受到硬件設(shè)備的制約。本文將點(diǎn)云數(shù)據(jù)按照深度值進(jìn)行八叉樹(shù)劃分，并將得到的數(shù)據(jù)結(jié)構(gòu)組織在外存中，然后通過(guò)隨機(jī)采樣的方法由子結(jié)點(diǎn)向根結(jié)點(diǎn)構(gòu)建多分辨率的點(diǎn)云數(shù)據(jù)，保存在相應(yīng)的外存文件中，最后設(shè)計(jì)了一種基于視點(diǎn)的點(diǎn)云多分辨率調(diào)度策略，實(shí)現(xiàn)了海量點(diǎn)云的流暢顯示。通過(guò)實(shí)驗(yàn)驗(yàn)證了不同的八叉樹(shù)深度值對(duì)點(diǎn)云多分辨率結(jié)構(gòu)生成的效率、內(nèi)存調(diào)度和顯示的影響，并在普通計(jì)算機(jī)上實(shí)現(xiàn)了數(shù)億點(diǎn)云的流暢顯示。

[1] PFISTER H, ZWICKER M, VAN BAAR J, et al. Surfels: Surface Elements as Rendering Primitives [C] //Proceedings of ACM SIGGRAPH 2000. New York: ACM Press, 2000

[2] RUSINKIEWICZ S, LEVOY M. QSplat: A Multiresolution Point Rending System for Large Meshes [C] //Proceeding of ACM SIGGRAPH 2000. New York: ACM Press,2000

[3] BOTSCH M, HORNUN A,ZWICKER M, et al. High-quality Surface Splatting on Today's Gpus [C] //Proceedings of the 2nd Eurographics / IEEE VGTC Symp. Point-Based Graphics, 2005

[4] 支曉棟, 林宗堅(jiān), 蘇國(guó)中, 等. 基于改進(jìn)四叉樹(shù)的LiDAR點(diǎn)云數(shù)據(jù)組織研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2010, 46(9): 71-74

[5] MA H, WANG Z. Distributed Data Organization and Parallel Data Retrieval Methods for Huge Scanner Point Clouds [J]. Computer&Geoscience, 2011, 37(1): 193-201

[6] 孟放, 査紅彬. 基于LOD控制與內(nèi)外存調(diào)度的大型三維點(diǎn)云數(shù)據(jù)繪制[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 18(1): 1-7

[7] 張毅, 呂秀琴. 大規(guī)模點(diǎn)云內(nèi)外存調(diào)度繪制技術(shù)[J].計(jì)算機(jī)工程, 2014, 40(1): 49-54

[8] 邵正偉, 席平. 基于八叉樹(shù)編碼的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法[J].工程圖學(xué)學(xué)報(bào), 2010(4): 73-76

[9] HOPPE H. Smooth View-dependent Level-of-detail Control and Its Application to Terrain Rendering [C] // Proceedings of IEEE Visualization, Research Triangle Park, North Carolina, 1998

[10] 吳小東, 許捍衛(wèi). 基于OSGEarth的城市三維場(chǎng)景構(gòu)建[J].地理空間信息, 2013, 11(2): 107-110

[11] CHIANG Y, El-SANA J, LINDSTROM P, et al. Out-of-core Algorithms for Scientific Visualization and Computer Graphic [C] //Proceedings of IEEE Visualization, Boston, 2002

P208

B

1672-4623（2016）10-0022-04

10.3969/j.issn.1672-4623.2016.10.006

楊振發(fā)，碩士研究生，主要研究方向?yàn)閼?zhàn)場(chǎng)環(huán)境仿真。

2015-09-30。

項(xiàng)目來(lái)源：國(guó)家自然科學(xué)基金資助項(xiàng)目（41371384、41401465）；地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目（SKLGIE2014-2-4-1）。