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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟5：退出算法。

算法的流程如圖2所示。

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

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

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

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

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

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

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

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

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

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

內(nèi)外存調(diào)度技術(shù)是指計算機(jī)需要處理的數(shù)據(jù)一部分放在內(nèi)存中[11]，另一部分放在外部存儲設(shè)備中，并通過I/O進(jìn)行調(diào)度的技術(shù)。該技術(shù)是處理數(shù)據(jù)容量大于計算機(jī)內(nèi)存時的常用技術(shù)。在建立八叉樹索引結(jié)構(gòu)下的多分辨率LOD點(diǎn)云數(shù)據(jù)的基礎(chǔ)上，本文設(shè)計了一種基于視點(diǎn)的多分辨率點(diǎn)云內(nèi)外存調(diào)度策略：將點(diǎn)云的八叉樹結(jié)構(gòu)保存在內(nèi)存中，點(diǎn)云的多分辨率數(shù)據(jù)存儲在外部存儲設(shè)備中。當(dāng)觀察視點(diǎn)位于某一八叉樹父結(jié)點(diǎn)外，八叉樹外包圍盒中心點(diǎn)到視點(diǎn)的距離小于閾值R1時，便從外存中加載該結(jié)點(diǎn)對應(yīng)的多分辨率點(diǎn)云數(shù)據(jù)；當(dāng)距離進(jìn)一步減少且小于閾值R2時，遍歷父結(jié)點(diǎn)下的子結(jié)點(diǎn)，當(dāng)子結(jié)點(diǎn)的包圍盒中心到視點(diǎn)的距離小于閾值r時，從外存中加載該子結(jié)點(diǎn)，反之則從內(nèi)存中卸載該結(jié)點(diǎn)的點(diǎn)云數(shù)據(jù)。如圖4所示，R表示某一八叉樹結(jié)點(diǎn)半徑大小。將點(diǎn)云根結(jié)點(diǎn)的LOD半徑閾值設(shè)為無窮大，此時，一進(jìn)入場景便可以觀察到三維場景的整體情況。另外在使用OpenGL圖形渲染語言繪制點(diǎn)云數(shù)據(jù)時，通過開辟另一線程來預(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ù)來源于無人機(jī)航拍的影像經(jīng)過三維重建得到的稠密點(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ī)為普通PC，配置為Core i5 2.4 GHz、4 GB內(nèi)存、750 GB硬盤，軟件方面為Windows7 64位操作系統(tǒng)，VS2010 編譯環(huán)境，OpenGL三維渲染語言。為了比較不同的八叉樹深度值對八叉樹構(gòu)建、多分辨率LOD生成以及點(diǎn)云顯示效果的影響，設(shè)計了兩組實(shí)驗(yàn)進(jìn)行比較分析。

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

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

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

實(shí)驗(yàn)二： 基于視點(diǎn)的點(diǎn)云多分辨率內(nèi)外存調(diào)度繪制。以實(shí)驗(yàn)一得到的不同八叉樹深度值（選取深度值為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)存和硬盤讀寫隨時間變化的情況，從左到右分別為八叉樹深度值3到6的4種點(diǎn)云數(shù)據(jù)。

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

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

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

4 結(jié) 語

在普通計算機(jī)上，海量點(diǎn)云數(shù)據(jù)的流暢顯示受到硬件設(shè)備的制約。本文將點(diǎn)云數(shù)據(jù)按照深度值進(jìn)行八叉樹劃分，并將得到的數(shù)據(jù)結(jié)構(gòu)組織在外存中，然后通過隨機(jī)采樣的方法由子結(jié)點(diǎn)向根結(jié)點(diǎn)構(gòu)建多分辨率的點(diǎn)云數(shù)據(jù)，保存在相應(yīng)的外存文件中，最后設(shè)計了一種基于視點(diǎn)的點(diǎn)云多分辨率調(diào)度策略，實(shí)現(xiàn)了海量點(diǎn)云的流暢顯示。通過實(shí)驗(yàn)驗(yàn)證了不同的八叉樹深度值對點(diǎn)云多分辨率結(jié)構(gòu)生成的效率、內(nèi)存調(diào)度和顯示的影響，并在普通計算機(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] 支曉棟, 林宗堅, 蘇國中, 等. 基于改進(jìn)四叉樹的LiDAR點(diǎn)云數(shù)據(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ī)輔助設(shè)計與圖形學(xué)學(xué)報, 2006, 18(1): 1-7

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

[8] 邵正偉, 席平. 基于八叉樹編碼的點(diǎn)云數(shù)據(jù)精簡方法[J].工程圖學(xué)學(xué)報, 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的城市三維場景構(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)場環(huán)境仿真。

2015-09-30。

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