王晏民，郭 明，2

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

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

王晏民1，郭 明1，2

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

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

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

1 引 言

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

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

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

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

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

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

2.1 QMBB樹空間索引

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

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

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

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

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

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

2.2 多級混合空間索引的構建與數(shù)據(jù)存儲

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

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

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

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

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

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

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

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

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

4 試驗與分析

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

圖7 單視點圖像LOD顯示效果Fig.7 LOD display of grid point－cloud

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

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

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

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

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

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

5 結 論

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

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

［1］ LI Deren.3DVisualization of Geospatial Information：Graphics Based or Imagery Based［J］.Acta Geodaetica et Cartographica Sinic，2010，39（2）：111－114.（李德仁.論地球空間信息的三維可視化：基于圖形還是基于影像［J］.測繪學報，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.（張帆，黃先鋒，李德仁.基于球面投影的單站地面激光掃描點云構網(wǎng)方法［J］.測繪學報，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)技術綜述［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空間索引技術研究［J］.地理與地理信息科學，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ù)的實時獲取、建模與可視化［M］.武漢：武漢大學出版社，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.（龔俊，朱慶，張葉廷，等.顧及多細節(jié)層次的三維R－索引擴展方法［J］.測繪學報，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樹索引的三維場景細節(jié)層次自適應控制方法［J］.測繪學報，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.（夏宇，朱欣焰，李德仁.空間信息多級網(wǎng)格索引技術研究［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.（伏玉琛，郭薇，周洞汝.空間索引的混合樹結構研究［J］.計算機工程與應用，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］.武漢：武漢大學，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.（孟放.大型三維點云數(shù)據(jù)的交互繪制研究［D］.北京：北京大學，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ī)模點模型的實時高質(zhì)量繪制［J］.計算機學報，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ī)模點云數(shù)據(jù)的二維與三維混合索引方法［J］.測繪學報，2012，41（4）：605－612.）

P235

A

1001－1595（2012）04－0605－08

北京市自然科學基金重點項目（B類）（KZ200910016001）；北京市屬高等學校人才強教深化計劃“高層次人才資助計劃”（PHR20110511）

叢樹平）

2011－08－29

2011－12－22

王晏民（1958－），男，教授，博士生導師，研究方向為地面激光雷達、近景攝影測量和三維空間數(shù)據(jù)模型等方向的理論與應用研究。