大規(guī)模點(diǎn)云內(nèi)外存調(diào)度繪制技術(shù)

張 毅，呂秀琴

(武漢大學(xué) a.測繪學(xué)院；b.資源與環(huán)境科學(xué)學(xué)院，武漢 430079)

1 概述

利用三維激光掃描技術(shù)獲取的點(diǎn)云是一種可直觀表達(dá)目標(biāo)空間形態(tài)和分布的海量三維空間數(shù)據(jù)。空間數(shù)據(jù)一般會涉及 3類操作：存儲管理，處理計(jì)算和顯示繪制。對于顯示繪制技術(shù)，主要是旋轉(zhuǎn)、縮放和漫游等操作。在大數(shù)據(jù)量情況下，通常采取抽稀、細(xì)節(jié)層次模型(Level of Detail,LOD)[1-2]、建立數(shù)據(jù)金字塔結(jié)構(gòu)[3-4]等技術(shù)進(jìn)行實(shí)現(xiàn)。二維遙感影像和數(shù)字高程模型(Digital Element Model, DEM)具有規(guī)則的數(shù)據(jù)結(jié)構(gòu)，三維模型和矢量數(shù)據(jù)僅需要繪制較少頂點(diǎn)。相比較而言，點(diǎn)云的空間排列不規(guī)則，密度不均勻，數(shù)據(jù)量異常龐大，因此，海量點(diǎn)云的快速顯示繪制有著特殊的技術(shù)要求。

有許多學(xué)者對海量點(diǎn)云快速顯示進(jìn)行了研究。如采用磁盤映射方式讀取數(shù)據(jù)并引入分塊索引，實(shí)現(xiàn)1965449個點(diǎn)的顯示[5]。利用并行k最鄰近點(diǎn)(k-Nearest Neighbor, kNN)算法，實(shí)現(xiàn)數(shù)據(jù)總大小約為2.3 GB、共約9000萬點(diǎn)的顯示[6]。采用規(guī)則空間八叉樹與平衡二叉樹相結(jié)合的嵌套復(fù)合結(jié)構(gòu)進(jìn)行組織，實(shí)現(xiàn)178799個點(diǎn)的顯示[7]。利用基于視點(diǎn)的LOD及點(diǎn)云分塊技術(shù)實(shí)現(xiàn)最大1205000個點(diǎn)的繪制[8]。還有基于核外多分辨率海量點(diǎn)云數(shù)據(jù)的處理和交互編輯[9]、通過沿空間掃描和點(diǎn)排序的流技術(shù)點(diǎn)云處理方法[10]等。但就點(diǎn)云數(shù)據(jù)量而言，以上方法并沒有達(dá)到億級或更大規(guī)模的水平，在存儲結(jié)構(gòu)和調(diào)度繪制方面都有可進(jìn)一步挖掘的空間。一些商業(yè)軟件在海量點(diǎn)云的快速顯示繪制方面具有各自特點(diǎn)。Cyclone[11]、Realworks Survey、Polyworks[12]等采用的是動態(tài)抽稀技術(shù)，Rigel、XGRT[13]等采用的是八叉樹結(jié)構(gòu)技術(shù)。其中一些軟件聲稱可以處理TB甚至PB級的點(diǎn)云數(shù)據(jù)。

海量點(diǎn)云快速繪制問題的關(guān)鍵在于如何利用有限的內(nèi)存資源建立點(diǎn)云繪制的存儲結(jié)構(gòu)和調(diào)度機(jī)制，實(shí)現(xiàn)任意范圍內(nèi)點(diǎn)云數(shù)據(jù)的快速吞吐，并盡可能降低繪制流水線的CPU階段限制。點(diǎn)云只能首先存儲在外存中，如果完全依靠外存來建立內(nèi)存結(jié)構(gòu)和繪制，頻繁的I/O操作將嚴(yán)重降低效率，而又無法完全通過有限的內(nèi)存來實(shí)現(xiàn)。因此，問題的核心是以多大的內(nèi)存和時間代價(jià)來完成內(nèi)存結(jié)構(gòu)的建立和點(diǎn)云繪制。針對該問題，本文在研究建立點(diǎn)云數(shù)據(jù)的八叉樹存儲結(jié)構(gòu)和內(nèi)外存調(diào)度策略的基礎(chǔ)上，分析點(diǎn)云規(guī)模和節(jié)點(diǎn)規(guī)模對于內(nèi)存結(jié)構(gòu)建立和繪制的影響，通過從百萬級到億級點(diǎn)云的實(shí)驗(yàn)，實(shí)現(xiàn)大規(guī)模點(diǎn)云數(shù)據(jù)的有效調(diào)度和繪制。

2 點(diǎn)云存儲結(jié)構(gòu)及建立

點(diǎn)云數(shù)據(jù)無論是來自原始掃描文件，還是由處理軟件導(dǎo)出，都是以順序方式存儲。這種文件內(nèi)的順序并不一定對應(yīng)于空間關(guān)系上的順序。點(diǎn)云的空間關(guān)系對于點(diǎn)云繪制十分重要。在三維視圖中，利用點(diǎn)云空間關(guān)系可以提高點(diǎn)云調(diào)度的效率，方便可視判斷和LOD設(shè)計(jì)。點(diǎn)云的空間關(guān)系通過點(diǎn)云存儲結(jié)構(gòu)來表達(dá)，可以采用的存儲結(jié)構(gòu)有規(guī)則存儲、八叉樹存儲和K-D樹存儲等。規(guī)則存儲實(shí)現(xiàn)簡單，但空間冗余大。K-D樹存儲主要有利于鄰域查找，但在隨視點(diǎn)變化的三維繪制和LOD設(shè)計(jì)中存在一定問題。八叉樹結(jié)構(gòu)按照從整體到局部的形式逐層進(jìn)行點(diǎn)云存儲，空間關(guān)系通過父子節(jié)點(diǎn)進(jìn)行連接，無空間冗余，比較適合三維繪制。

點(diǎn)云的存儲結(jié)構(gòu)分為內(nèi)存結(jié)構(gòu)和外存結(jié)構(gòu)，如圖 1所示。內(nèi)存結(jié)構(gòu)是嚴(yán)格的八叉樹結(jié)構(gòu)，節(jié)點(diǎn)node包含了該節(jié)點(diǎn)的外包盒坐標(biāo)、點(diǎn)號集合 ptID、點(diǎn)號集合對應(yīng)的點(diǎn)記錄指針pt，以及8個子節(jié)點(diǎn)指針next[8]。其中，點(diǎn)號集合對應(yīng)的點(diǎn)記錄指針pt在建立八叉樹過程中不占用內(nèi)存空間，而是在從外存讀入數(shù)據(jù)后進(jìn)行繪制時占用內(nèi)存。因此，在八叉樹建立過程中真正占用內(nèi)存空間的主要是點(diǎn)號集合ptID。在32位操作系統(tǒng)中，一個long型點(diǎn)號僅占用4 Byte，而一個點(diǎn)坐標(biāo)需要3個float型，占用12 Byte，因而在八叉樹中存儲點(diǎn)號可以節(jié)約內(nèi)存空間。外存結(jié)構(gòu)是將內(nèi)存按節(jié)點(diǎn)逐一進(jìn)行存儲，通過文件指針偏移量offset來標(biāo)記當(dāng)前節(jié)點(diǎn)在整個文件中的位置，有利于快速查找。當(dāng)八叉樹內(nèi)存結(jié)構(gòu)建立完成后，采用廣度優(yōu)先遞歸方式遍歷整個樹結(jié)構(gòu)，逐節(jié)點(diǎn)寫到外存文件中。當(dāng)繪制點(diǎn)云時，根據(jù)需要可以將特定的節(jié)點(diǎn)及其點(diǎn)云讀入內(nèi)存節(jié)點(diǎn)中。

圖1 點(diǎn)云內(nèi)外存存儲結(jié)構(gòu)

根據(jù)設(shè)計(jì)好的存儲結(jié)構(gòu)，對點(diǎn)云分 2個步驟進(jìn)行八叉樹的建立，如圖2所示。

圖2 點(diǎn)云內(nèi)外存存儲結(jié)構(gòu)的建立

點(diǎn)云內(nèi)存結(jié)構(gòu)的建立過程如下：

(1)建立點(diǎn)云八叉樹結(jié)構(gòu)。即通過反復(fù)計(jì)算和剖分點(diǎn)云外包盒，在內(nèi)存中構(gòu)造出從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的完整樹結(jié)構(gòu)。根節(jié)點(diǎn)就是全部點(diǎn)云，而葉節(jié)點(diǎn)的形成需要指定一個結(jié)束條件，本文將節(jié)點(diǎn)內(nèi)的點(diǎn)數(shù)上限M作為判斷條件。節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)上限對于建樹過程和實(shí)時繪制都具有重要影響。

八叉樹結(jié)構(gòu)的建立步驟如下：

1)初始化八叉樹根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。

2)如果當(dāng)前節(jié)點(diǎn)為空，則返回。

3)如果當(dāng)前節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)小于設(shè)定值，執(zhí)行步驟7)。

4)計(jì)算當(dāng)前點(diǎn)所在子節(jié)點(diǎn)的索引號。

5)如果索引子節(jié)點(diǎn)為空，則創(chuàng)建一個節(jié)點(diǎn)內(nèi)存空間并進(jìn)行初始化為當(dāng)前節(jié)點(diǎn)。

6)如果當(dāng)前節(jié)點(diǎn)的所有點(diǎn)都分配到子節(jié)點(diǎn)中，則清空當(dāng)前節(jié)點(diǎn)中的點(diǎn)。

7)對步驟2)～步驟6)進(jìn)行遞歸操作。

點(diǎn)云八叉樹結(jié)構(gòu)建立的結(jié)果是從根節(jié)點(diǎn)開始逐層將點(diǎn)云的點(diǎn)號分配到葉節(jié)點(diǎn)，根節(jié)點(diǎn)和其他子節(jié)點(diǎn)都沒有存儲點(diǎn)號信息。這樣做的目的有2個：1)為了節(jié)約內(nèi)存使用，即在步驟 6)中清空當(dāng)前節(jié)點(diǎn)內(nèi)的點(diǎn)，使得整個建樹過程的內(nèi)存開銷僅用于八叉樹節(jié)點(diǎn)結(jié)構(gòu)體，而點(diǎn)號如同水流一般從根節(jié)點(diǎn)開始逐層擴(kuò)散流向其他節(jié)點(diǎn)。2)為了便于在步驟 2)中平衡節(jié)點(diǎn)內(nèi)的點(diǎn)數(shù)。

(2)向八叉樹填充點(diǎn)云。采取深度優(yōu)先遍歷，從葉節(jié)點(diǎn)開始，以一定的比例抽取當(dāng)前節(jié)點(diǎn)中的點(diǎn)，將其填充到上層父節(jié)點(diǎn)內(nèi)，同時刪除當(dāng)前節(jié)點(diǎn)中的已抽取點(diǎn)。抽取比例控制著點(diǎn)云在不同節(jié)點(diǎn)內(nèi)的分布，是進(jìn)行LOD設(shè)計(jì)的重要依據(jù)。顯然，抽取比例越大，點(diǎn)云越密集地分布到上層節(jié)點(diǎn)中；反之，點(diǎn)云越密集地分布到下層節(jié)點(diǎn)中。為了平衡整個八叉樹的點(diǎn)云分布，使視點(diǎn)在任意位置的動態(tài)繪制中都產(chǎn)生相對均衡的內(nèi)存和時間消耗，本文的抽取比例為0.5。

經(jīng)過以上 2個步驟后，點(diǎn)云的內(nèi)存結(jié)構(gòu)建立完畢。根據(jù)設(shè)計(jì)好的外存文件結(jié)構(gòu)，將點(diǎn)云按節(jié)點(diǎn)單元寫到外存文件中。

在建立樹結(jié)構(gòu)的過程中，雖然點(diǎn)記錄指針pt沒有賦值，但計(jì)算外包盒是需要點(diǎn)坐標(biāo)的。而在建立外存文件過程中，點(diǎn)坐標(biāo)是要全部寫出的。因此，整個過程都要求訪問原始點(diǎn)云數(shù)據(jù)。有以下3種方式：

(1)全內(nèi)存訪問。該方式需要充足的內(nèi)存資源，優(yōu)點(diǎn)是建樹速度快。但在面臨海量點(diǎn)云數(shù)據(jù)的情況下，目前的內(nèi)存資源都是無法勝任的。

(2)全外存訪問。該方式可以完成建樹過程，且不需要考慮內(nèi)存情況。但頻繁的I/O操作會大大降低建樹速度。

(3)部分內(nèi)存訪問。該方式根據(jù)當(dāng)前內(nèi)存的使用情況，通過調(diào)用一部分內(nèi)存空間來實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)訪問。每次訪問量可以是固定大小，也可以根據(jù)內(nèi)存情況設(shè)置一個變量來控制。本文中采取每次直接將外存中10000個點(diǎn)一次讀入內(nèi)存進(jìn)行訪問，訪問完畢后從內(nèi)存刪除。顯然，只有采取這種方式，才能真正實(shí)現(xiàn)海量點(diǎn)云數(shù)據(jù)由隨機(jī)順序的外存文件轉(zhuǎn)換為具有空間關(guān)系的內(nèi)存結(jié)構(gòu)和外存文件，在轉(zhuǎn)換效率上也得到提高。

3 點(diǎn)云內(nèi)外存調(diào)度繪制

繪制過程采取廣度優(yōu)先方式遞歸遍歷八叉樹。每一個節(jié)點(diǎn)的繪制包括3個主要環(huán)節(jié)：(1)對節(jié)點(diǎn)進(jìn)行判斷分析，考查該節(jié)點(diǎn)是否真正需要繪制，這樣有利于提高整個場景的繪制速度。(2)內(nèi)外存調(diào)度數(shù)據(jù)，即根據(jù)節(jié)點(diǎn)判斷分析結(jié)果，對節(jié)點(diǎn)可見范圍外的節(jié)點(diǎn)進(jìn)行刪除，在內(nèi)存中釋放節(jié)點(diǎn)數(shù)據(jù)；對節(jié)點(diǎn)可見范圍內(nèi)的空節(jié)點(diǎn)，從外存中讀取節(jié)點(diǎn)數(shù)據(jù)。這樣可以保證繪制過程的整體內(nèi)存消耗處于相對穩(wěn)定的水平。(3)繪制點(diǎn)云實(shí)體。對3個環(huán)節(jié)進(jìn)行合理連接，構(gòu)成了點(diǎn)云內(nèi)外存調(diào)度繪制的流程，如圖3所示。

圖3 點(diǎn)云內(nèi)外存調(diào)度繪制流程

節(jié)點(diǎn)是否在可見范圍內(nèi)的判斷是節(jié)點(diǎn)判斷的重要內(nèi)容。在有限的屏幕范圍內(nèi)，只有部分節(jié)點(diǎn)外包盒是可見的，對這部分節(jié)點(diǎn)內(nèi)的點(diǎn)云進(jìn)行繪制足夠表達(dá)場景內(nèi)容。在三維場景中，視點(diǎn)和節(jié)點(diǎn)的空間關(guān)系決定著可見性判斷。在OpenGL世界坐標(biāo)下，設(shè)視點(diǎn)坐標(biāo)的為(ex, ey, ez)，視線向量為(lx, ly, lz)，節(jié)點(diǎn)中心坐標(biāo)為(nx, ny, nz)，則可見性判斷的條件有2個：

(1)視點(diǎn)到節(jié)點(diǎn)中心的距離條件：(2)視點(diǎn)到節(jié)點(diǎn)中心向量與視線向量的夾角條件：

由于是以節(jié)點(diǎn)中心代替了節(jié)點(diǎn)內(nèi)的所有點(diǎn)云進(jìn)行可見性判斷，計(jì)算量大大減少，這在動態(tài)繪制過程中十分重要。但以偏概全的判斷存在點(diǎn)云漏繪制的問題。本文的解決方法是對每一個節(jié)點(diǎn)都設(shè)置一個可視半徑，為N(N>1)倍于節(jié)點(diǎn)的外包盒的最大邊長。八叉樹中不同節(jié)點(diǎn)的外包盒大小不同，因而節(jié)點(diǎn)可視半徑隨節(jié)點(diǎn)位置變化。以根節(jié)點(diǎn)為例：

(1)如果視點(diǎn)在整個根節(jié)點(diǎn)外包盒內(nèi)，此時滿足距離條件，無論是否滿足夾角條件，根節(jié)點(diǎn)中的點(diǎn)都應(yīng)該繪制。

(2)如果視點(diǎn)在整個根節(jié)點(diǎn)外包盒外，但仍滿足距離條件時，根節(jié)點(diǎn)中心是否可見等同于其中點(diǎn)云是否可見。若根節(jié)點(diǎn)中心在視線前方，即cosθ＞0，繪制根節(jié)點(diǎn)；若根節(jié)點(diǎn)中心在視線后方，即cosθ＜0，不繪制根節(jié)點(diǎn)。

(3)如果不滿足距離條件，即整個節(jié)點(diǎn)離視點(diǎn)太遠(yuǎn)，則不繪制根節(jié)點(diǎn)。

其他節(jié)點(diǎn)的判斷與根節(jié)點(diǎn)一致。之所以將可視半徑設(shè)置為N倍于節(jié)點(diǎn)的外包盒的最大邊長，是考慮到視點(diǎn)在整個節(jié)點(diǎn)外包盒之外時，在該可視半徑內(nèi)點(diǎn)云仍可以顯示，可以以一定距離來觀察整個節(jié)點(diǎn)內(nèi)的點(diǎn)云。本文中N=5。

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

實(shí)驗(yàn)分成2類進(jìn)行：(1)全內(nèi)存訪問的點(diǎn)云數(shù)據(jù)；(2)部分內(nèi)存訪問的點(diǎn)云數(shù)據(jù)。全內(nèi)存訪問的點(diǎn)云數(shù)據(jù)選自Leica HDS6000三維激光掃描儀獲取的某廣場點(diǎn)云，點(diǎn)個數(shù)為7655936。部分內(nèi)存訪問的點(diǎn)云數(shù)據(jù)由該廣場點(diǎn)云按照1×1、2×2、3×3、4×4的矩陣排列方式平移復(fù)制得到，點(diǎn)個數(shù)分別為7655936、30623744、68903424、122494976。實(shí)驗(yàn)的目的是分析在不同量級點(diǎn)云數(shù)據(jù)情況下，點(diǎn)云內(nèi)外存結(jié)構(gòu)的建立過程和繪制過程中的內(nèi)存和時間消耗。

實(shí)驗(yàn)是在Visual C++ 6.0編譯環(huán)境下結(jié)合OpenGL進(jìn)行編程實(shí)現(xiàn)。主要硬件配置為 Inter Core2 P96002.66 GHz CPU，4 GB內(nèi)存，300 GB機(jī)械硬盤，Nvidia Quadro NVS 160 MB顯卡。

對于全內(nèi)存訪問的點(diǎn)云數(shù)據(jù)實(shí)驗(yàn)，主要是研究節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)上限對于建立內(nèi)外存結(jié)構(gòu)和內(nèi)外存調(diào)度繪制的影響。本文通過統(tǒng)計(jì)分析節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)的變化，考查內(nèi)外存結(jié)構(gòu)的建立和調(diào)度繪制過程中內(nèi)存和時間消耗的情況。表 1是分別設(shè)置節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)為 100、1000、10000、100000、1000000的情況下，八叉樹節(jié)點(diǎn)總數(shù)、建立八叉樹結(jié)構(gòu)耗時、生成外存文件耗時、總耗時、外存文件大小等各項(xiàng)指標(biāo)的統(tǒng)計(jì)結(jié)果。隨著節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)的倍增，八叉樹節(jié)點(diǎn)總數(shù)呈幾何級數(shù)減少，從而顯著降低了建立八叉樹結(jié)構(gòu)的耗時。相比較而言，建樹過程內(nèi)存峰值和外存文件大小并沒有比較大的變化。圖4是節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)上限為10000和1000000情況下的點(diǎn)云繪制結(jié)果。節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)越多，點(diǎn)云繪制越密集。以上結(jié)果說明本文的建樹方法內(nèi)外存占用較小，而建樹效率取決于節(jié)點(diǎn)內(nèi)的點(diǎn)數(shù)上限。

表1 節(jié)點(diǎn)內(nèi)的點(diǎn)數(shù)對內(nèi)外存結(jié)構(gòu)建立各項(xiàng)指標(biāo)的影響

圖4 點(diǎn)云繪制結(jié)果(7655936點(diǎn))

建樹過程的結(jié)果只是一方面，還要考慮繪制過程的情況。相對應(yīng)的，在節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)上限為1000、10000、100000、1000000的情況下，分別統(tǒng)計(jì)了點(diǎn)云繪制中的內(nèi)存使用和幀率變化情況，如圖5和圖6所示。設(shè)計(jì)視點(diǎn)在場景中的勻速漫游和旋轉(zhuǎn)構(gòu)成視點(diǎn)路徑，視點(diǎn)起點(diǎn)為點(diǎn)云中心，沿點(diǎn)云 Z坐標(biāo)軸移動到根節(jié)點(diǎn)外包盒外，然后繞點(diǎn)云中將視點(diǎn)旋轉(zhuǎn)90°，再沿視線方向穿越整個點(diǎn)云場景。通過對比可以發(fā)現(xiàn)，在節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)為10000的情況下，內(nèi)存使用最小(最高不超過380 MB)，而繪制幀率最高(最高時接近70 fps)。這就意味著繪制過程中存在一個節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)上限的平衡點(diǎn)，使得整個內(nèi)外存調(diào)度繪制過程達(dá)到最優(yōu)。而在繪制最優(yōu)的意義上，內(nèi)外存結(jié)構(gòu)建立的效率并不是最優(yōu)。但綜合而言，以節(jié)點(diǎn)內(nèi)的點(diǎn)數(shù)上限作為判斷條件，以一定的建樹時間消耗作為代價(jià)，可以保證內(nèi)外存結(jié)構(gòu)建立的內(nèi)存平衡，可以使得內(nèi)外存調(diào)度繪制達(dá)到最佳。

將全內(nèi)存訪問實(shí)驗(yàn)的結(jié)果作為參考，進(jìn)行部分內(nèi)存訪問的大規(guī)模點(diǎn)云數(shù)據(jù)實(shí)驗(yàn)，將節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)上限設(shè)置為10000。實(shí)驗(yàn)結(jié)果證明了本文方法以較低內(nèi)存消耗建立從百萬級到億級等大規(guī)模點(diǎn)云數(shù)據(jù)的內(nèi)外存結(jié)構(gòu)。表 2列出了4種點(diǎn)云的各項(xiàng)統(tǒng)計(jì)指標(biāo)。從表2中可以看出，當(dāng)點(diǎn)云在較大數(shù)量級時，無論是內(nèi)存消耗，還是時間消耗，都呈倍數(shù)增長。以線性回歸粗略估計(jì)，在4 GB的物理內(nèi)存條件下，本文方法可以完成的內(nèi)外存調(diào)度繪制的點(diǎn)云最大規(guī)模為762115166。此外，值得注意的是，同為7655936個點(diǎn)的點(diǎn)云，在全內(nèi)存訪問中的建樹時間和內(nèi)存峰值分別為8.3s、155376 KB，而在部分內(nèi)存訪問中分別為107.8 s、58300 KB。造成時間消耗增大的原因是用于點(diǎn)查找的ptID在內(nèi)存中沒有全部記錄，只能通過移動外存文件指針進(jìn)行定位，增加了I/O操作，一定程度上降低了訪問效率。

圖5 點(diǎn)云繪制中的內(nèi)存使用情況

圖6 點(diǎn)云繪制中的幀率變化情況

表2 大數(shù)據(jù)量點(diǎn)云點(diǎn)數(shù)對內(nèi)外存結(jié)構(gòu)建立各項(xiàng)指標(biāo)的影響

圖7～圖9是點(diǎn)數(shù)為122494976個點(diǎn)的點(diǎn)云在不同視點(diǎn)時的顯示。點(diǎn)云在內(nèi)外存調(diào)度技術(shù)的支持下，從整體到局部都能流暢繪制。為了定量分析，采取和全內(nèi)存訪問實(shí)驗(yàn)相似的視點(diǎn)路徑，統(tǒng)計(jì)內(nèi)存使用和幀率變化，如圖 10和圖 11所示。內(nèi)存使用在 405 MB～430 MB之間，幀率在10 fps～75 fps之間。內(nèi)存消耗較大的繪制幀，其幀率都對應(yīng)降低，這是當(dāng)視點(diǎn)移動到場景細(xì)節(jié)中，較多節(jié)點(diǎn)都處于可見性的情況。而其他繪制幀的幀率都維持在較高水平，內(nèi)存占用都在可用范圍內(nèi)，內(nèi)外存結(jié)構(gòu)建立和動態(tài)繪制的整個過程都不會因內(nèi)存不足而導(dǎo)致程序崩潰。

圖7 大規(guī)模點(diǎn)云在視點(diǎn)1的顯示

圖8 大規(guī)模點(diǎn)云在視點(diǎn)2的顯示

圖9 大規(guī)模點(diǎn)云在視點(diǎn)3的顯示

圖10 大規(guī)模點(diǎn)云繪制中的內(nèi)存使用情況

圖11 大規(guī)模點(diǎn)云繪制中的幀率變化情況

5 結(jié)束語

本文提出一種部分內(nèi)存訪問方式下的平衡八叉數(shù)存儲結(jié)構(gòu)，設(shè)計(jì)點(diǎn)與節(jié)點(diǎn)距離和夾角約束可見性判決條件下的點(diǎn)云內(nèi)外存數(shù)據(jù)調(diào)度方案。根據(jù)對不同規(guī)模實(shí)測點(diǎn)云的實(shí)驗(yàn)，得出以下結(jié)論：

(1)本文提出的內(nèi)外存結(jié)構(gòu)設(shè)計(jì)和調(diào)度繪制技術(shù)可以在有限的內(nèi)存資源條件下，以較小的內(nèi)存消耗實(shí)現(xiàn)上億級規(guī)模點(diǎn)云從整體到局部的流暢繪制。部分內(nèi)存訪問策略是提高內(nèi)外存結(jié)構(gòu)建立的有效方式。

(2)節(jié)點(diǎn)內(nèi)點(diǎn)數(shù)上限作為葉節(jié)點(diǎn)的形成條件，可以很好地控制內(nèi)外存結(jié)構(gòu)建立和動態(tài)繪制過程中的內(nèi)存和時間消耗。內(nèi)外存調(diào)度繪制過程中內(nèi)存和幀率的平衡點(diǎn)是確定該上限值的依據(jù)。

(3)隨節(jié)點(diǎn)變化的可視半徑能將點(diǎn)云的可見行判斷轉(zhuǎn)換為節(jié)點(diǎn)的可見性判斷，從而大大提高繪制效率。

加速計(jì)算、繪制速度與減小內(nèi)存占用始終是一對矛盾，目前解決這一矛盾的手段是以犧牲一方面為代價(jià)來換取另一方面。本文以建樹時間為代價(jià)，換取了較小的內(nèi)存消耗和較高的繪制效率，實(shí)現(xiàn)了大規(guī)模點(diǎn)云的快速瀏覽。在全外存訪問方式下，建樹過程雖沒有內(nèi)存上限約束，但建樹效率極低。隨著固態(tài)硬盤及高速磁盤陣列的普及，基于全外存的海量點(diǎn)云數(shù)據(jù)管理、處理和繪制將成為提高效率的一種途徑。

[1]馬曉晨, 孔小利.基于深度八叉樹的三維數(shù)據(jù)場LOD可視化[J].計(jì)算機(jī)應(yīng)用, 2010, 30(1): 47-49.

[2]張兵強(qiáng), 張立民, 張建廷.面向GPU的批LOD地形實(shí)時繪制[J].中國圖象圖形學(xué)報(bào), 2012, 17(4): 582-588.

[3]馮 莎, 盧選民, 陶旺林, 等.基于高斯金字塔的海量超大圖像快速漫游算法[J].計(jì)算機(jī)應(yīng)用研究, 2012, 29(3): 1141-1142.

[4]李建勛, 沈 冰, 姜仁貴, 等.面向影像金字塔的四叉樹空間索引算法[J].計(jì)算機(jī)工程, 2011, 37(10): 11-13.

[5]李 捷, 鐘若飛, 趙文吉.車載激光點(diǎn)云海量數(shù)據(jù)的管理與快速顯示[J].系統(tǒng)仿真學(xué)報(bào), 2008, 20(S1): 33-35.

[6]王宗躍, 馬洪超, 徐宏根, 等.多核 CPU 的海量點(diǎn)云并行kNN算法[J].測繪科學(xué)技術(shù)學(xué)報(bào), 2010, 27(1): 46-49.

[7]路明月, 何永健.三維海量點(diǎn)云數(shù)據(jù)的組織與索引方法[J].地球信息科學(xué), 2008, 10(2): 190-193.

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

[9]Wand M, Berner A, Bokeloh M, et al.Processing and Interactive Editing of Huge Point Clouds from 3D Scanners[J].Computers & Graphics, 2008, 32(2): 204-220.

[10]Pajarola R.Stream-processing Points[C]//Proc.of Conference on Visualization.Minneapolis, USA: IEEE Computer Society,2005.

[11]Leica Geosystems HDS, LLC.HDS Training Manual[EB/OL].(2006-01-01).http://hds.leica-geosystems.com/en/Downloads-Support-Downloads_27049.htm.

[12]InnovMetric Software Inc..PolyWorks Reference Guide Version 10.0 for Windows[EB/OL].(2007-01-01).http://www.polyworks.com.cn/3D-scanners/home.aspx.

[13]Wand M, Berner A, Bokeloh M, et al.The XGRT System[EB/OL].(2007-01-01).http://www.gris.uni-tuebingen.de/xgrt.