大規(guī)模點(diǎn)云數(shù)據(jù)的二維與三維混合索引方法

王晏民，郭 明，2

1.北京建筑工程學(xué)院現(xiàn)代城市測(cè)繪國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，北京100044；2.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北武漢430079

大規(guī)模點(diǎn)云數(shù)據(jù)的二維與三維混合索引方法

王晏民1，郭 明1，2

1.北京建筑工程學(xué)院現(xiàn)代城市測(cè)繪國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，北京100044；2.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北武漢430079

為提高點(diǎn)云查詢效率和按需提取數(shù)據(jù)，提出一種二維與三維混合索引的大規(guī)模點(diǎn)云數(shù)據(jù)管理方法。采用二維四叉樹(shù)和三維最小外包盒結(jié)構(gòu)管理原始點(diǎn)云，以3D－R樹(shù)管理多站點(diǎn)云，利用對(duì)象關(guān)系數(shù)據(jù)庫(kù)管理全部點(diǎn)云模型和相關(guān)屬性數(shù)據(jù)。利用古建筑大規(guī)模點(diǎn)云數(shù)據(jù)在微機(jī)上實(shí)現(xiàn)了點(diǎn)云模型的數(shù)據(jù)存儲(chǔ)與可視化。結(jié)果表明本方法能夠管理超過(guò)10 GB級(jí)的點(diǎn)云模型數(shù)據(jù)和十億級(jí)有效點(diǎn)，數(shù)據(jù)可視化效率較高。

地面激光雷達(dá)；大規(guī)模點(diǎn)云數(shù)據(jù)；空間索引；細(xì)節(jié)層次

1 引 言

近年來(lái)，基于矢量圖形信息的三維可視化和基于實(shí)景影像信息的三維可視化技術(shù)應(yīng)用越來(lái)越廣泛，以LiDAR技術(shù)為代表的空間數(shù)據(jù)獲取手段正支撐其快速發(fā)展［1］。地面激光雷達(dá)已經(jīng)成為在近地空間獲取精細(xì)三維圖形信息的主要手段之一。地面激光雷達(dá)獲取的數(shù)據(jù)是按陣列方式存放的、帶反射強(qiáng)度的三維點(diǎn)坐標(biāo)。在此定義按陣列存放的三維點(diǎn)坐標(biāo)序列為點(diǎn)圖像。經(jīng)過(guò)配準(zhǔn)的多視（站）點(diǎn)圖像稱(chēng)為點(diǎn)圖像模型。點(diǎn)圖像模型具有數(shù)據(jù)量大（海量性）、按掃描線排列（柵格性）、數(shù)據(jù)未經(jīng)任何處理（原始性）等特點(diǎn)。有學(xué)者利用這些特性進(jìn)行了很有意義的工作，采用球面有向搜索和球面LOP局部?jī)?yōu)化算法對(duì)單站點(diǎn)圖像進(jìn)行不規(guī)則三角網(wǎng)模型的構(gòu)建，提高了構(gòu)網(wǎng)時(shí)間效率，避免了由于數(shù)據(jù)噪聲引起的構(gòu)網(wǎng)錯(cuò)誤和空洞現(xiàn)象［2］；采用一種基于距離依賴的球面重采樣方法進(jìn)行點(diǎn)云數(shù)據(jù)的精簡(jiǎn)工作，有效地降低了配準(zhǔn)操作的時(shí)間成本［3］。點(diǎn)圖像模型能夠從整體上表達(dá)地物的真實(shí)形態(tài)，是必須永久保存的原始數(shù)據(jù)。但其數(shù)據(jù)量很大，且分布不規(guī)則，單站數(shù)據(jù)就有幾百萬(wàn)至幾千萬(wàn)個(gè)三維點(diǎn)。一般的面激光雷達(dá)站數(shù)較多，如故宮太和殿上下里外掃描達(dá)上百站。如何對(duì)這種海量數(shù)據(jù)進(jìn)行管理是當(dāng)前面臨的最大問(wèn)題?，F(xiàn)有的激光雷達(dá)數(shù)據(jù)處理軟件一般將其轉(zhuǎn)換為非結(jié)構(gòu)化隨機(jī)分布的散亂點(diǎn)云，對(duì)海量點(diǎn)云數(shù)據(jù)進(jìn)行分塊處理，只選取有用的數(shù)據(jù)，丟棄其他數(shù)據(jù)，失去了數(shù)據(jù)的原始性和柵格性。特別是對(duì)于故宮建筑物這樣的古建筑，其具有對(duì)象部件多樣化、數(shù)據(jù)查詢操作要求效率高等特點(diǎn)，空間數(shù)據(jù)的組織、存儲(chǔ)與管理具有較大難度。

利用數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)海量空間和屬性數(shù)據(jù)是未來(lái)發(fā)展的方向，空間數(shù)據(jù)和屬性數(shù)據(jù)可采用對(duì)象關(guān)系數(shù)據(jù)庫(kù)技術(shù)來(lái)存儲(chǔ)［4－5］；同時(shí)，有針對(duì)性地設(shè)計(jì)簡(jiǎn)單高效的空間索引也是關(guān)鍵問(wèn)題之一。純粹二維索引效率很低，因?yàn)槿S空間分布的點(diǎn)云在不同平面單元里差異很大，傳統(tǒng)三維索引一般又沒(méi)有顧及不同的對(duì)象。目前適合點(diǎn)云的三維空間索引方法主要有格網(wǎng)、四叉樹(shù)、八叉樹(shù)、k－d樹(shù)［5－7］、R樹(shù)及其變種［8－10］和一些很具代表性的混合索引［11－12］等。這些索引中很多是由點(diǎn)對(duì)象和空間實(shí)體的最小外包矩形建立的，但其索引粒度基本上都索引到了單個(gè)點(diǎn)對(duì)象，不適用于數(shù)據(jù)量特別大的點(diǎn)云三維空間索引?，F(xiàn)有的空間索引往往支持內(nèi)存或外存的細(xì)節(jié)層次技術(shù)，在生成空間索引和細(xì)節(jié)層次數(shù)據(jù)時(shí)通常是復(fù)制點(diǎn)云數(shù)據(jù)備份，采用“以空間換時(shí)間”的方法來(lái)選取所需層次的數(shù)據(jù)進(jìn)行處理與可視化。目前還沒(méi)有一種空間索引方法明顯優(yōu)于其他方法［5，7］，往往需要根據(jù)具體的應(yīng)用來(lái)設(shè)計(jì)合適的空間索引。

為了便于整體點(diǎn)云模型的場(chǎng)景表達(dá)，提高海量點(diǎn)云數(shù)據(jù)處理和可視化的效率，保證原始數(shù)據(jù)信息不被破壞或丟失，在充分利用點(diǎn)圖像模型高信息量的基礎(chǔ)上，針對(duì)上述問(wèn)題提供一套新的海量點(diǎn)圖像數(shù)據(jù)庫(kù)管理算法，為點(diǎn)云數(shù)據(jù)的后處理工作奠定基礎(chǔ)。對(duì)于單站點(diǎn)圖像模型提出一種二維與三維集成的空間索引進(jìn)行數(shù)據(jù)組織，對(duì)于多站點(diǎn)圖像數(shù)據(jù)采用該集成空間索引與三維R樹(shù)空間索引的混合索引來(lái)組織。將空間索引與點(diǎn)云數(shù)據(jù)分別組織，只生成一份點(diǎn)云數(shù)據(jù)，直接利用空間索引樹(shù)結(jié)構(gòu)生成細(xì)節(jié)層次模型，通過(guò)建立一種可視化調(diào)度策略針對(duì)不同視距采用不同的細(xì)節(jié)層次可視化。

2 海量點(diǎn)圖像數(shù)據(jù)管理算法原理

針對(duì)地面激光雷達(dá)掃描獲取的單站和多站點(diǎn)圖像數(shù)據(jù)，本文采用的算法主要包含以下幾個(gè)方面的內(nèi)容：二維與三維集成空間索引的設(shè)計(jì)、混合空間索引的構(gòu)建與數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)細(xì)節(jié)層次調(diào)度，算法原理流程如圖1所示；利用點(diǎn)云數(shù)據(jù)的柵格性在單站數(shù)據(jù)讀取的同時(shí)采用自上而下再自下而上的方式建立二維四叉樹(shù)和三維最小外包盒樹(shù)空間索引結(jié)構(gòu)（quad－MBB，QMBB樹(shù)），針對(duì)多站點(diǎn)圖像數(shù)據(jù)則采用3D－R樹(shù)空間索引管理各單站數(shù)據(jù)的根節(jié)點(diǎn)MBB，將海量原始數(shù)據(jù)分別組織成序列化空間索引數(shù)據(jù)和經(jīng)壓縮后的點(diǎn)云數(shù)據(jù)，并將組織好的兩類(lèi)數(shù)據(jù)和其他屬性數(shù)據(jù)存儲(chǔ)到大型商用數(shù)據(jù)庫(kù)中；基于自適應(yīng)細(xì)節(jié)層次技術(shù)和數(shù)據(jù)調(diào)度策略實(shí)現(xiàn)單站或多站點(diǎn)圖像數(shù)據(jù)的數(shù)據(jù)庫(kù)調(diào)度與可視化。

圖1 算法原理總流程圖Fig.1 The total flow of the algorithm principle

2.1 QMBB樹(shù)空間索引

利用原始掃描點(diǎn)云的柵格性，按點(diǎn)云的行數(shù)和列數(shù)先以自上而下的方式構(gòu)建基于二維四叉樹(shù)空間索引，每次按照實(shí)際掃描的橫向步進(jìn)角度和縱向步進(jìn)角度分別進(jìn)行二分，對(duì)點(diǎn)圖像數(shù)據(jù)進(jìn)行二維分割，每個(gè)分割都形成一個(gè)二維最小外包矩形（minimal bounding rectangle，MBR），如圖2左列所示，表示基于激光雷達(dá)二維深度圖的四叉樹(shù)分割示意圖。根據(jù)每個(gè)MBR對(duì)應(yīng)的點(diǎn)云在三維空間中計(jì)算每個(gè)MBR對(duì)應(yīng)的最小外包盒（minimal bounding box，MBB），以二維四叉樹(shù)的形式構(gòu)建3D－MBB樹(shù)，如圖2右列所示。將二維四叉樹(shù)與3D－MBB樹(shù)集成起來(lái)構(gòu)成2D－3D空間索引QMBB樹(shù)，它兼具二維和三維特征，是一種集成空間索引。

圖2 QMBB樹(shù)空間索引的數(shù)據(jù)分割Fig.2 Data segmentation using QMBB－tree spatial index

QMBB樹(shù)空間索引的索引粒度為一個(gè)2DMBR和對(duì)應(yīng)的3D－MBB，實(shí)際是索引一個(gè)點(diǎn)集。普通四叉樹(shù)節(jié)點(diǎn)只含二維信息，而QMBB樹(shù)則同時(shí)具備二維屬性和三維屬性，可進(jìn)行二維和三維空間查詢，分割后的點(diǎn)圖像數(shù)據(jù)塊沒(méi)有重疊點(diǎn)，而且QMBB樹(shù)非葉子節(jié)點(diǎn)內(nèi)的采樣點(diǎn)均來(lái)自原始數(shù)據(jù)，沒(méi)有經(jīng)過(guò)插值運(yùn)算。QMBB樹(shù)三維空間索引的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如圖3所示。它由指向子節(jié)點(diǎn)的標(biāo)識(shí)children和指向父節(jié)點(diǎn)的標(biāo)識(shí)pParent、三維坐標(biāo)偏移CoordOffset和三維點(diǎn)的ID標(biāo)識(shí)偏移IDOffset、三維點(diǎn)數(shù)據(jù)ID標(biāo)識(shí)IdList、節(jié)點(diǎn)的最小外包矩形體MBBox、節(jié)點(diǎn)的行列位置最小外包矩形MBR、節(jié)點(diǎn)的名稱(chēng)編碼strCode等組成。節(jié)點(diǎn)的名稱(chēng)編碼采用線性四叉樹(shù)編碼方法，每個(gè)節(jié)點(diǎn)名稱(chēng)編碼的字符串長(zhǎng)度代表它在QMBB空間索引樹(shù)中的深度。

圖3 QMBB樹(shù)空間索引節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)Fig.3 Node data structure of Q－MBB tree spatial index

QMBB樹(shù)空間索引的構(gòu)建流程為，在每個(gè)點(diǎn)坐標(biāo)讀取的過(guò)程中依次定義點(diǎn)的ID值并根據(jù)ID值將其插入QMBB樹(shù)索引的葉子節(jié)點(diǎn)中，如果某一個(gè)節(jié)點(diǎn)內(nèi)存儲(chǔ)的點(diǎn)數(shù)超過(guò)閾值就將該節(jié)點(diǎn)進(jìn)行分裂，直至所有的空間點(diǎn)均插入QMBB樹(shù)。QMBB樹(shù)構(gòu)建完畢后計(jì)算每個(gè)葉子節(jié)點(diǎn)的MBB，利用均勻采樣的方法以自下而上的方式填充空間索引樹(shù)的非葉子節(jié)點(diǎn)數(shù)據(jù)，直到根節(jié)點(diǎn)，該QMBB樹(shù)的非葉子節(jié)點(diǎn)也只存儲(chǔ)坐標(biāo)數(shù)據(jù)的索引ID。其構(gòu)建方法如圖4所示。首先獲取單視點(diǎn)圖像的行號(hào)列號(hào)，根據(jù)行列號(hào)530×789從上至下構(gòu)建QMBB樹(shù)，接下來(lái)將每個(gè)三維點(diǎn)數(shù)據(jù)按順序插入對(duì)應(yīng)葉子節(jié)點(diǎn)，如紅虛線的點(diǎn)插入“第三層次葉子節(jié)點(diǎn)1”，藍(lán)虛線的點(diǎn)插入“第三層次葉子節(jié)點(diǎn)2”，當(dāng)每個(gè)有效三維點(diǎn)均插入QMBB樹(shù)葉子節(jié)點(diǎn)后，再?gòu)娜~子節(jié)點(diǎn)自下而上依次重采樣填充各層次非葉子節(jié)點(diǎn)的點(diǎn)云數(shù)據(jù)，如圖綠實(shí)線箭頭所示。這樣QMBB樹(shù)在數(shù)據(jù)讀取的過(guò)程中一次性快速實(shí)時(shí)生成，點(diǎn)圖像在邏輯上被分割成多分辨率細(xì)節(jié)層次數(shù)據(jù)塊。

圖4 單站點(diǎn)圖像QMBB樹(shù)構(gòu)建及數(shù)據(jù)插入方法示意圖Fig.4 QMBB－tree index building of single－station grid point－cloud

2.2 多級(jí)混合空間索引的構(gòu)建與數(shù)據(jù)存儲(chǔ)

QMBB樹(shù)空間索引結(jié)構(gòu)建立后，多分辨率點(diǎn)云數(shù)據(jù)的層次通過(guò)QMBB樹(shù)的深度來(lái)表達(dá)，QMBB樹(shù)的每一層代表不同分辨率的點(diǎn)云數(shù)據(jù)，分辨率的大小取決于QMBB樹(shù)空間索引構(gòu)建時(shí)點(diǎn)云的均勻采樣率。QMBB樹(shù)空間索引結(jié)構(gòu)中只存儲(chǔ)三維點(diǎn)的ID號(hào)，作為真實(shí)點(diǎn)坐標(biāo)及灰度紋理信息的指針，而且點(diǎn)坐標(biāo)數(shù)據(jù)只存儲(chǔ)單個(gè)拷貝，檢索時(shí)通過(guò)ID號(hào)換算為偏移指針查詢數(shù)據(jù)，從而避免多層次數(shù)據(jù)的存儲(chǔ)冗余。利用3D－R樹(shù)空間索引管理每站點(diǎn)圖像數(shù)據(jù)，3D－R樹(shù)的每個(gè)葉子節(jié)點(diǎn)均存儲(chǔ)QMBB樹(shù)的根節(jié)點(diǎn)MBB，同時(shí)3D－R樹(shù)的每個(gè)節(jié)點(diǎn)也存儲(chǔ)各單站點(diǎn)圖像的均勻采樣數(shù)據(jù)，采用二級(jí)空間混合索引的方式來(lái)管理所有點(diǎn)圖像模型數(shù)據(jù)。以深度優(yōu)先遍歷的方式將空間索引序列化并入庫(kù)，將細(xì)節(jié)層次點(diǎn)云數(shù)據(jù)和一些必要的屬性數(shù)據(jù)，如掃描時(shí)間、掃描地點(diǎn)、掃描人員、掃描儀型號(hào)等分別存儲(chǔ)到已設(shè)計(jì)好的數(shù)據(jù)庫(kù)表中，按空間對(duì)象、點(diǎn)圖像數(shù)據(jù)對(duì)象和存儲(chǔ)的數(shù)據(jù)塊表3級(jí)模式來(lái)存儲(chǔ)海量點(diǎn)圖像數(shù)據(jù)，再次檢索序列化索引數(shù)據(jù)后可快速恢復(fù)該點(diǎn)云的空間索引結(jié)構(gòu)。受文獻(xiàn)［13］的雙字節(jié)存儲(chǔ)法啟發(fā)，對(duì)于三維浮點(diǎn)坐標(biāo)值采用空間位置量化的方法進(jìn)行壓縮，并將點(diǎn)的ID、灰度和紋理等屬性信息分別進(jìn)行壓縮，壓縮率可達(dá)37.5%，便于傳輸和現(xiàn)有微機(jī)顯存一次性繪制較大規(guī)模的數(shù)據(jù)。

3 點(diǎn)圖像數(shù)據(jù)可視化

近幾年國(guó)際國(guó)內(nèi)研究較多的是利用點(diǎn)模型［14－16］來(lái)進(jìn)行大規(guī)模點(diǎn)云的可視化工作。它能更好地表達(dá)形狀復(fù)雜且不規(guī)則的物體，能夠兼顧繪制速度與繪制質(zhì)量［17－19］，但其繪制的點(diǎn)數(shù)最多也只有千萬(wàn)級(jí)。而且在點(diǎn)模型的數(shù)據(jù)預(yù)處理階段往往需要很多的時(shí)間和很大的空間消耗來(lái)計(jì)算模型表面的幾何屬性，如求解主曲率、主方向，計(jì)算法矢和法錐面等，而原始的掃描數(shù)據(jù)往往是沒(méi)有這些幾何信息的，需要進(jìn)行求解與計(jì)算，且花費(fèi)時(shí)間大都比較長(zhǎng)，而且超過(guò)一定容量的數(shù)據(jù)不能被預(yù)處理。如QSplat軟件［14］的.qs格式轉(zhuǎn)換工具Laser Splat就對(duì)數(shù)據(jù)量大小有限制，又如XGRT軟件［20］在構(gòu)建基于外存的數(shù)據(jù)文件時(shí)生成的二進(jìn)制文件約為原始數(shù)據(jù)文件的3倍，這些都降低了海量點(diǎn)云后處理工作的效率。

針對(duì)可視化時(shí)海量點(diǎn)圖像數(shù)據(jù)的可視化問(wèn)題，本算法采用的方案是首先對(duì)單站或多站點(diǎn)云的MBB進(jìn)行視錐裁剪，然后采用基于視點(diǎn)遠(yuǎn)近的細(xì)節(jié)層次（LOD）技術(shù)來(lái)選擇需要顯示的指定級(jí)別數(shù)據(jù)，最后將選出的MBB進(jìn)行遮擋剔除，確定實(shí)際需要顯示到屏幕上的點(diǎn)云數(shù)據(jù)。在內(nèi)存內(nèi)設(shè)置檢索查找表，判斷哪些數(shù)據(jù)塊不用再到數(shù)據(jù)庫(kù)內(nèi)調(diào)度，只檢索不在內(nèi)存中的坐標(biāo)數(shù)據(jù)。通過(guò)選出的MBB獲取點(diǎn)ID，再根據(jù)ID值在數(shù)據(jù)庫(kù)中直接檢索對(duì)應(yīng)的真實(shí)點(diǎn)圖像模型數(shù)據(jù)參與可視化，提高了時(shí)間和空間利用率，可視化數(shù)據(jù)調(diào)度選擇流程如圖5所示。

圖5 柵格點(diǎn)云模型可視化Fig.5 Visualization of grid point－cloud model

利用3D－R樹(shù)和QMBB樹(shù)空間索引結(jié)構(gòu)中節(jié)點(diǎn)的MBB與三維場(chǎng)景視錐體進(jìn)行視域裁剪，判斷MBB與視錐體是否相交，排除不在視錐體內(nèi)的節(jié)點(diǎn)。進(jìn)行單站或多站之間的細(xì)節(jié)層次數(shù)據(jù)的選擇，在圖6所示的自適應(yīng)細(xì)節(jié)層次選取方案示意圖中，對(duì)于每個(gè)存在視錐體內(nèi)的MBB的8個(gè)頂點(diǎn)，逐個(gè)計(jì)算屏幕視點(diǎn)到各個(gè)頂點(diǎn)的距離，記錄距離的最大值MaxDist和最小值MinDist以及對(duì)應(yīng)的兩個(gè)頂點(diǎn)，將排除最大最小兩個(gè)頂點(diǎn)后的6個(gè)頂點(diǎn)分別投影到視錐體的近平面上，計(jì)算投影的六邊形（q1′q6′q3′q7′q4′q5′）在近平面上的投影面積Area，定義當(dāng)前每個(gè)點(diǎn)在屏幕上顯示的大小cursize，將Area的值乘以cursize和定權(quán)因子a即為實(shí)際投影面積ScreenArea。其中定權(quán)因子a的意義為點(diǎn)集中所有點(diǎn)的平均顯示大小的權(quán)值，由于點(diǎn)的固定大小在顯示的時(shí)候會(huì)有部分重疊或完全疊置的現(xiàn)象，用a來(lái)調(diào)節(jié)顯示的平均大小，提高LOD級(jí)別的判斷準(zhǔn)確性。最終采用ScreenArea與MinDist的比值定義比例因子RateofArea2Dist來(lái)保守估算細(xì)節(jié)層次級(jí)別數(shù)據(jù)。利用不同細(xì)節(jié)層次下RateofArea2Dist取值范圍的不同來(lái)自適應(yīng)確定需要顯示到計(jì)算機(jī)屏幕上的數(shù)據(jù)，比例因子越小，則對(duì)應(yīng)較為粗略的層次數(shù)據(jù)；比例因子越大，則對(duì)應(yīng)較為精細(xì)的層次數(shù)據(jù)。本文實(shí)現(xiàn)的細(xì)節(jié)層次模型的自適應(yīng)性不僅表現(xiàn)在依據(jù)視點(diǎn)遠(yuǎn)近關(guān)系判斷LOD層次上，而且表現(xiàn)在依據(jù)單個(gè)MBB的視距分別判斷其各自的LOD層次，對(duì)不同的MBB樹(shù)節(jié)點(diǎn)自動(dòng)地判定其在當(dāng)前三維場(chǎng)景中的LOD層次上，亦即不僅是判斷整個(gè)點(diǎn)圖像數(shù)據(jù)的LOD層次，而且是針對(duì)每個(gè)點(diǎn)圖像分割數(shù)據(jù)塊分別判定其LOD層次，不同的MBB樹(shù)節(jié)點(diǎn)內(nèi)的點(diǎn)圖像分塊數(shù)據(jù)具有不同的LOD層次。

圖6 單站時(shí)細(xì)節(jié)層次選取Fig.6 Single－station LOD selection

層次數(shù)據(jù)選定后，根據(jù)整個(gè)場(chǎng)景的視點(diǎn)和MBB間的分布情況判斷多站間哪些MBB內(nèi)的數(shù)據(jù)應(yīng)該保留下來(lái)參與繪制，統(tǒng)計(jì)需要繪制的點(diǎn)的總數(shù)，如果超過(guò)設(shè)定閾值，則將各個(gè)數(shù)據(jù)塊的LOD級(jí)別降為較粗略的一層數(shù)據(jù)顯示，直到點(diǎn)數(shù)滿足閾值要求為止，保證內(nèi)存中需要繪制點(diǎn)的數(shù)量和內(nèi)存消耗量在合理的水平，最終達(dá)到有較高的顯示幀率和較好的用戶體驗(yàn)。記錄保留下來(lái)參與繪制的MBB節(jié)點(diǎn)存儲(chǔ)的三維坐標(biāo)點(diǎn)的ID值，利用ID值從數(shù)據(jù)庫(kù)內(nèi)查詢點(diǎn)云數(shù)據(jù)，最后將一定個(gè)數(shù)的點(diǎn)數(shù)據(jù)置于GPU中進(jìn)行繪制。

本文采用配置為Intel（R）Core（TM）2 CPU6600 2.4GHz，3.00GB內(nèi)存、GeForce8500GT顯卡的微機(jī)，以O(shè)racle 11g作為數(shù)據(jù)庫(kù)管理平臺(tái)，利用數(shù)據(jù)庫(kù)系統(tǒng)設(shè)計(jì)工具PowerDesigner設(shè)計(jì)數(shù)據(jù)庫(kù)對(duì)象模型、數(shù)據(jù)庫(kù)表，使用PL／SQL語(yǔ)言進(jìn)行數(shù)據(jù)庫(kù)建庫(kù)和管理，利用Microsoft C＃／C＋＋.NET 2005實(shí)現(xiàn)了具有快速瀏覽和檢索查詢功能的交互式可視化管理原型系統(tǒng)。

4 試驗(yàn)與分析

圖7是點(diǎn)圖像（單視）的LOD顯示效果，掃描后得到的數(shù)據(jù)文件大小為18.52MB，含有彩色有效點(diǎn)個(gè)數(shù)為358 062，由于三維激光掃描儀的獲取深度圖像的特性，文件內(nèi)還含有以某種格式記錄的空間無(wú)效點(diǎn)，但其不參與可視化。每次屏幕內(nèi)顯示的點(diǎn)數(shù)約為150 000左右，在表2所示配置的計(jì)算機(jī)上采用OpenGL三維圖形庫(kù)實(shí)現(xiàn)了本文的算法，平均顯示幀率約為120。圖7中按箭頭所示方向點(diǎn)云的LOD級(jí)別逐漸減低，表示數(shù)據(jù)細(xì)節(jié)層次分割粒度的MBB線框隨之變大，但如圖所見(jiàn)每一幀上點(diǎn)云可視化效果并沒(méi)有減低。

圖7 單視點(diǎn)圖像LOD顯示效果Fig.7 LOD display of grid point－cloud

圖8是點(diǎn)圖像數(shù)模型的LOD顯示效果，數(shù)據(jù)文件大小為269.14M，含有12塊柵格數(shù)據(jù)，彩色有效點(diǎn)總數(shù)為5 347 765，每次屏幕內(nèi)顯示的點(diǎn)數(shù)約為300 000左右，在同樣配置的計(jì)算機(jī)上平均顯示幀率約為60左右。該圖則是展示點(diǎn)云的LOD級(jí)別逐漸增大的過(guò)程，灰色的線框表示內(nèi)部分塊節(jié)點(diǎn)數(shù)據(jù)的MBB，在不同的分辨率下查詢出的MBB的大小不同，分辨率越高，MBB線框越密集，LOD級(jí)別越高，數(shù)據(jù)顯示越精細(xì)。需要指出的是，本文采用的幀率計(jì)算方法為每次強(qiáng)制執(zhí)行顯卡緩沖區(qū)內(nèi)數(shù)據(jù)，而不用等到顯卡緩沖區(qū)滿再執(zhí)行指令，采用此方法計(jì)算的幀率不受計(jì)算機(jī)屏幕刷新率的限制，更能反映真實(shí)的顯示速度。

圖8 點(diǎn)圖像模型數(shù)據(jù)LOD顯示效果Fig.8 LOD display of grid point－cloud model

表1顯示利用本文算法調(diào)度和繪制海量點(diǎn)圖像模型的效率。根據(jù)LOD選擇后計(jì)算獲取的點(diǎn)集的數(shù)量的大小，不同總點(diǎn)數(shù)繪制的幀率也有所不同，在保證基本繪制質(zhì)量的前提下，經(jīng)多次試驗(yàn)統(tǒng)計(jì)，其中繪制速度達(dá)到或超過(guò)10 000 000點(diǎn)／s（實(shí)際繪制點(diǎn)數(shù)×實(shí)時(shí)幀率），比文獻(xiàn)［19］所用的方法快2倍以上，較文獻(xiàn)［17］報(bào)告的繪制速度快6倍以上。LOD數(shù)據(jù)檢索總時(shí)間包括多站視錐裁剪、LOD選擇等點(diǎn)的ID選定過(guò)程耗用時(shí)間之和。

本文方法能同時(shí)調(diào)度多站點(diǎn)圖像數(shù)據(jù)進(jìn)行繪制，如果某一層次的多站數(shù)據(jù)繪制時(shí)點(diǎn)的總數(shù)超過(guò)了某一閾值，則重新從3D－R樹(shù)和QMBB樹(shù)混合空間索引中檢索上一層次的數(shù)據(jù)顯示，確保每次屏幕顯示的點(diǎn)的總數(shù)不超過(guò)規(guī)定的閾值，基本不影響繪制質(zhì)量的前提下保持較高的幀率。如圖9所示，左圖為故宮太和門(mén)整體點(diǎn)圖像模型，交換格式文件總大小為1.54GB，它由241 596 602個(gè)有效點(diǎn)組成，實(shí)際繪制的點(diǎn)數(shù)為10 711 195個(gè)；右圖為中和殿整體點(diǎn)圖像模型，交換格式文件總大小為4.74GB，它由2 038 308 028個(gè)有效點(diǎn)組成，實(shí)際繪制的點(diǎn)數(shù)為3 940 690個(gè)，繪制幀率平均保持在4fps左右，能夠基本滿足流暢顯示的要求。

表1 部分點(diǎn)圖像數(shù)據(jù)采用本文算法的調(diào)度效率統(tǒng)計(jì)Tab.1 The scheduling efficiency statistic of part of grid point－cloud model using this algorithm

圖9 多站點(diǎn)圖像數(shù)據(jù)整體調(diào)度與可視化Fig.9 The whole visualization of multi－station grid point－cloud models

5 結(jié) 論

本文所提出的算法可以在海量點(diǎn)圖像數(shù)據(jù)讀取的同時(shí)快速建立QMBB樹(shù)集成空間索引，利用3D－R樹(shù)和QMBB樹(shù)多級(jí)混合索引方便地存取自組織的空間索引數(shù)據(jù)和點(diǎn)云數(shù)據(jù)，避免了外存的不必要LOD數(shù)據(jù)備份與采樣點(diǎn)冗余，節(jié)約外存和內(nèi)存的空間，數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單有效，可視化操作時(shí)查詢效率較高，同時(shí)利用大型商用數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)數(shù)據(jù)保證了數(shù)據(jù)的安全性與并發(fā)性，具有較高的實(shí)用價(jià)值。

下一步研究的主要方向有：構(gòu)建基于網(wǎng)絡(luò)的應(yīng)用平臺(tái)，實(shí)現(xiàn)實(shí)時(shí)遠(yuǎn)程數(shù)據(jù)處理應(yīng)用；在繪制質(zhì)量與繪制效率上考慮新型的GPU可編程繪制手段和自適應(yīng)點(diǎn)模型繪制模式，提高可視化質(zhì)量與效率；利用本文的空間數(shù)據(jù)模型和數(shù)據(jù)庫(kù)存儲(chǔ)的數(shù)據(jù)，開(kāi)發(fā)數(shù)據(jù)處理與可視化的算法與應(yīng)用系統(tǒng)，為大型LiDAR數(shù)據(jù)處理與管理平臺(tái)提供技術(shù)支撐。

［1］ LI Deren.3DVisualization of Geospatial Information：Graphics Based or Imagery Based［J］.Acta Geodaetica et Cartographica Sinic，2010，39（2）：111－114.（李德仁.論地球空間信息的三維可視化：基于圖形還是基于影像［J］.測(cè)繪學(xué)報(bào)，2010，39（2）：111－114.）

［2］ ZHANG Fan，HUANG Xianfeng，LI Deren.Spherical Projection Based Triangulation for One Station Terrestrial Laser Scanning Point Cloud［J］.Acta Geodaetica et Cartographica Sinica，2009，38（1）：48－54.（張帆，黃先鋒，李德仁.基于球面投影的單站地面激光掃描點(diǎn)云構(gòu)網(wǎng)方法［J］.測(cè)繪學(xué)報(bào)，2009，38（1）：48－54.）

［3］ MANDOW A，MARTíNEZ J L，REINA A，et al.Fast Range－independent Spherical Subsampling of 3DLaser Scanner Points and Data Reduction Performance Evaluation for Scene Registration［J］.Pattern Recognition Letters，2010，31（11）：1239－1250.

［4］ ZHU Qing.A Survey of Three Dimensional GIS Technologies［J］.Geomatics World，2004，2（3）：8－12.（朱慶.三維地理信息系統(tǒng)技術(shù)綜述［J］.地理信息世界，2004，2（3）：8－12.）

［5］ ZHENG Kun，ZHU Liangfeng，WU Xincai，et al.Study on Spatial Indexing Techniques for 3DGIS［J］.Geography and Geo－Information Science，2006，22（4）：35－39.（鄭坤，朱良峰，吳信才，等.三維GIS空間索引技術(shù)研究［J］.地理與地理信息科學(xué)，2006，22（4）：35－39.）

［6］ LI Qingquan，YANG Bisheng，SHI Wenzhong，et al.The Theory and Methods of Spatial Data Acquisition，Modeling，Visualization［M］.Wuhan：Wuhan University Press，2003.（李清泉，楊必勝，史文中，等.三維空間數(shù)據(jù)的實(shí)時(shí)獲取、建模與可視化［M］.武漢：武漢大學(xué)出版社，2003.）

［7］ SHI Wenzhong，WU Lixin，Li Qingquan，et al.Models and Algorithms for Three Dimensional Spatial Information System［M］.Beijing：Publishing House of Electronics Industry，2007.（史文中，吳立新，李清泉，等.三維空間信息系統(tǒng)模型與算法［M］.北京：電子工業(yè)出版社，2007.）

［8］ GUTTMAN A.R－trees：A Dynamic Index Structure for Spatial Searching［C］∥Proceedings of ACM International Conference on Management of Data.Boston：ACM Press，1984：47－57.

［9］ GONG Jun，ZHU Qing，ZHANG Yeting，et al.An Efficient 3DR－tree Extension Method Concerned with Levels of Detail［J］.Acta Geodaetica et Cartographica Sinica，2011，40（2）：249－255.（龔俊，朱慶，張葉廷，等.顧及多細(xì)節(jié)層次的三維R－索引擴(kuò)展方法［J］.測(cè)繪學(xué)報(bào)，2011，40（2）：249－255.）

［10］ GONG Jun，ZHU Qing，ZHANG Hanwu，et al.An Adaptive Control Method of LODs for 3DScene Based on R－tree Index［J］.Acta Geodaetica et Cartographica Sinica，2011，40（2）：531－534.（龔俊，朱慶，章漢武，等.基于R樹(shù)索引的三維場(chǎng)景細(xì)節(jié)層次自適應(yīng)控制方法［J］.測(cè)繪學(xué)報(bào)，2011，40（4）：531－534.）

［11］ XIA Yu，ZHU Xinyan，LI Deren.Indexing Technology in Spatial Information Multi－grid［J］.Geospatial Information，2006，4（6）：4－7.（夏宇，朱欣焰，李德仁.空間信息多級(jí)網(wǎng)格索引技術(shù)研究［J］.地理空間信息，2006，4（6）：4－7.）

［12］ FU Yuchen，GUO Wei，ZHOU Dongru.Hybrid－tree：An Indexing Structure of Spatial Database［J］.Computer Engineering and Applications，2003，39（17）：41－42.（伏玉琛，郭薇，周洞汝.空間索引的混合樹(shù)結(jié)構(gòu)研究［J］.計(jì)算機(jī)工程與應(yīng)用，2003，39（17）：41－42.）

［13］ WANG Yanmin.A Study of Vector Spatial Data Organization for Multi－scale GIS［D］.Wuhan：Wuhan University，2002.（王晏民.多比例尺GIS數(shù)量空間數(shù)據(jù)組織研究［D］.武漢：武漢大學(xué)，2002.）

［14］ RUSINKIEWICZ S，LEVOY M.QSplat：A Multi－resolution Point Rendering System for Large Meshes［C］∥Proceedings of SIGGRAPH 2000，New Orleans：ACM Press，2000：343－352.

［15］ ZWICKER M.Splatting Fundamentals 3DEditing and Painting［C］∥Point－based Computer Graphics.Waltham：Morgan Kaufmann Publishers，2007.

［16］ PFISTER H，ZWICKER M，BAAR J V，et al.Surfels：Surface Elements as Rendering Primitives.Computer Graphics［C］∥Proceedings of SIGGRAPH 2000.New Orleans：ACM Press，2000：335－342.

［17］ REN L，PFISTER H，ZWICKER M.Object Space EWA Surface Splatting：A Hardware Accelerated Approach to High Quality Point Rendering［C］∥Proceedings of the Eurographics 2002.Oxford：Blackwell Publishers，2002：461－470.

［18］ MENG Fang.Studies on Interactive Rendering of Huge 3DPoint－based Models［D］.Beijing：Peking University，2005.（孟放.大型三維點(diǎn)云數(shù)據(jù)的交互繪制研究［D］.北京：北京大學(xué)，2005.）

［19］ ZHANG Long，DONG Zhao，CHEN Wei，et al.High Quality Real－time Rendering of Large Scale Point Model［J］.Chinese Journal of Computer，2005，28（2）：241－249.（張龍，董朝，陳為，等.大規(guī)模點(diǎn)模型的實(shí)時(shí)高質(zhì)量繪制［J］.計(jì)算機(jī)學(xué)報(bào)，2005，28（2）：241－249.）

［20］ W AND M，BERNER A，BOKELOH M，et al.EXGRT—EXTENSIBLE GRAPHICS TOOLKIT［EB／OL］.2006－06－11［2011－08－10］.http：／／www.gris.unituebingen.de／xgrt.

E－mail：wangyanmin58＠163.com

A Combined2D and3D Spatial Indexing of Very Large Point－cloud Data Sets

WANG Yanmin1，GUO Ming1，2
1.Key Laboratory for Urban Geomatics of National Administration of Surveying，Mapping and Geoinformation，Beijing University of Civil Engineering and Architecture，Beijing 100044，China；2.State Key Laboratory for Information Engineering in Surveying，Mapping and Remote Sensing；Wuhan University，Wuhan 430079，China

A database management algorithm based on combined2D and3D indexing of very large point－cloud data is proposed，for extracting the point cloud in need and improving the query efficiency.Single－station point－cloud is managed with 2D quad tree and3D MBB structure.Multi－station point－clouds are indexed with 3D－R tree.Finally the organized hierarchical model and other attribute data are stored in ralation－object database.The data storage，management and visualization of very large point－clouds are implimented on personal computer with massive point clouds from the ancient buildings such as Forbidden City.Result shows that the algorithm is able to manage more than 10 GB－level data and one billion effective points with satisfactory drawing efficiency.

terrestrial LiDAR；very large point－cloud data sets；spatial index；LOD

WANG Yanmin（1958—），male，professor，PhD supervisor，majors in theory and application of terrestrial LiDAR，close－range photogrammetry and 3D spatial data modeling.

WANG Yanmin，GUO Ming.A Combined 2Dand 3DSpatial Indexing of Very Large Point－cloud Data Sets［J］.Acta Geodaetica et Cartographica Sinica，2012，41（4）：605－612.（王晏民，郭明.大規(guī)模點(diǎn)云數(shù)據(jù)的二維與三維混合索引方法［J］.測(cè)繪學(xué)報(bào)，2012，41（4）：605－612.）

P235

A

1001－1595（2012）04－0605－08

北京市自然科學(xué)基金重點(diǎn)項(xiàng)目（B類(lèi)）（KZ200910016001）；北京市屬高等學(xué)校人才強(qiáng)教深化計(jì)劃“高層次人才資助計(jì)劃”（PHR20110511）

叢樹(shù)平）

2011－08－29

2011－12－22

王晏民（1958－），男，教授，博士生導(dǎo)師，研究方向?yàn)榈孛婕す饫走_(dá)、近景攝影測(cè)量和三維空間數(shù)據(jù)模型等方向的理論與應(yīng)用研究。