基于KD樹的點(diǎn)云數(shù)據(jù)自適應(yīng)屏幕精度高效顯示方法

楊建思，劉 華，林 鵬

(武漢大學(xué)城市設(shè)計(jì)學(xué)院，湖北武漢 430072)

基于KD樹的點(diǎn)云數(shù)據(jù)自適應(yīng)屏幕精度高效顯示方法

楊建思，劉 華，林 鵬

(武漢大學(xué)城市設(shè)計(jì)學(xué)院，湖北武漢 430072)

海量激光點(diǎn)云數(shù)據(jù)的快速顯示是目前一個(gè)技術(shù)瓶頸。本文提出一種基于KD樹的點(diǎn)云數(shù)據(jù)自適應(yīng)屏幕精度的高效顯示方法，采用類似LOD的技術(shù)將點(diǎn)云進(jìn)行KD樹的組織，并在KD樹節(jié)點(diǎn)上引入屏幕精度的概念，在點(diǎn)云數(shù)據(jù)顯示時(shí)，計(jì)算KD樹節(jié)點(diǎn)在屏幕上的投影范圍，進(jìn)而決定其是否顯示點(diǎn)云細(xì)節(jié)。試驗(yàn)證明，該算法在顯示大規(guī)模點(diǎn)云數(shù)據(jù)時(shí)，由于通過KD樹自適應(yīng)屏幕精度調(diào)度點(diǎn)云數(shù)據(jù)使繪制點(diǎn)的數(shù)據(jù)量大大減少，從而大大加快了點(diǎn)云的顯示速度。

點(diǎn)云組織；索引；KD樹；可視化

一、引 言

機(jī)載激光雷達(dá)(light detection and ranging，Li-DAR)是激光掃描與探測(cè)系統(tǒng)的簡(jiǎn)稱，它集激光、全球定位系統(tǒng)(GPS)和慣性導(dǎo)航系統(tǒng)(INS)3種技術(shù)于一體[1]，是一種通過位置、距離、角度等觀測(cè)數(shù)據(jù)直接獲取地球表面點(diǎn)三維坐標(biāo)，從而實(shí)現(xiàn)地物信息提取和三維場(chǎng)景重建的對(duì)地觀測(cè)技術(shù)[2]。

為了獲取被觀測(cè)物的詳細(xì)信息，LiDAR數(shù)據(jù)的密度往往很大，使得LiDAR數(shù)據(jù)量很大，其數(shù)量通常達(dá)到GB級(jí)，在顯示系統(tǒng)中將數(shù)據(jù)點(diǎn)顯示出來的圖像往往非常密集，因而形象稱其為點(diǎn)云(pointcloud)。

目前有大量關(guān)于點(diǎn)云數(shù)據(jù)組織與數(shù)據(jù)結(jié)構(gòu)的論文[3-10]，但大多數(shù)論文是關(guān)于點(diǎn)云數(shù)據(jù)結(jié)構(gòu)與索引的空間利用率、平均檢索速度、內(nèi)外存調(diào)度算法及平衡性等問題的，在點(diǎn)云數(shù)據(jù)的可視化方面，一般是使用視口裁切去除視口外點(diǎn)[11-13]。已有的關(guān)于大數(shù)據(jù)量簡(jiǎn)化顯示的辦法一般是基于三角面片的LOD，而對(duì)離散的LiDAR數(shù)據(jù)點(diǎn)云來說，傳統(tǒng)的LOD方法及遮擋面消除方法都不太適用。

本文提出一種基于KD樹的點(diǎn)云數(shù)據(jù)自適應(yīng)屏幕精度的高效顯示方法。該方法類似于LOD方法[14-16]，將點(diǎn)云進(jìn)行KD樹的組織，在KD樹節(jié)點(diǎn)上引入屏幕精度的概念；在點(diǎn)云數(shù)據(jù)顯示時(shí)，計(jì)算KD樹節(jié)點(diǎn)在屏幕上的投影范圍，進(jìn)而決定其是否顯示點(diǎn)云細(xì)節(jié)。由于通過KD樹自適應(yīng)屏幕精度調(diào)度點(diǎn)云數(shù)據(jù)可使繪制點(diǎn)的數(shù)據(jù)量大大減少，從而大大加快了點(diǎn)云的顯示速度。

二、KD樹

在數(shù)據(jù)組織結(jié)構(gòu)中，二叉樹是非常簡(jiǎn)單、高效且成熟的結(jié)構(gòu)，但它僅僅適用于單維數(shù)據(jù)。LiDAR數(shù)據(jù)是三維數(shù)據(jù)，不存在某種排序能同時(shí)兼顧3個(gè)方向的維度屬性，從而不能保證原來鄰近的數(shù)據(jù)在排序以后也有鄰近的特征。

基于二叉樹向多維空間中的擴(kuò)展，Bentley提出多維空間中的二叉樹索引，即KD樹[17]。KD樹將多維空間中的數(shù)據(jù)成功地在一個(gè)樹內(nèi)完成索引，但數(shù)據(jù)對(duì)插入順序非常敏感，樹的結(jié)構(gòu)往往缺乏平衡性。自適應(yīng)的KD樹[18]提出在建立KD樹時(shí)根據(jù)數(shù)據(jù)特征選取特定的劃分平面，使每次劃分都將空間分為數(shù)據(jù)相等的兩個(gè)子空間，但這種優(yōu)化只對(duì)靜態(tài)數(shù)據(jù)有用，對(duì)于數(shù)據(jù)的動(dòng)態(tài)更新，樹的結(jié)構(gòu)需要全部重新組織。

自適應(yīng)的KD樹像KD樹一樣，依次選取與坐標(biāo)軸垂直的平面將數(shù)據(jù)空間一分為二，其坐標(biāo)軸依次在3個(gè)坐標(biāo)軸之間選取；自適應(yīng)的KD樹在向KD樹插入數(shù)據(jù)之前，預(yù)先計(jì)算數(shù)據(jù)點(diǎn)在各個(gè)方向的排序，進(jìn)而選取特定的點(diǎn)，使得平面劃分的結(jié)果讓每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)包含的點(diǎn)數(shù)目最多相差1。

為了使該數(shù)據(jù)結(jié)構(gòu)能更好地適應(yīng)點(diǎn)云數(shù)據(jù)的顯示，本文對(duì)自適應(yīng)的KD樹作出以下改動(dòng)。

1)原始的KD樹算法對(duì)劃分平面的選取為依次選取3個(gè)方向的劃分平面，這樣保證了數(shù)據(jù)的公平性，但是也造成了數(shù)據(jù)區(qū)域形狀各異，很不規(guī)則。因而筆者將劃分平面定義為使劃分的結(jié)果區(qū)域最接近正方形的劃分方式，即對(duì)需要進(jìn)行劃分的區(qū)域分別計(jì)算區(qū)域在3個(gè)軸向的長(zhǎng)度Length_X、Length_Y、Length_Z，求出其中的最大值，本次劃分將數(shù)據(jù)區(qū)域沿該軸方向一分為二，這樣能保持每個(gè)節(jié)點(diǎn)內(nèi)的數(shù)據(jù)在空間位置上更加相近。

2)在傳統(tǒng)KD樹中，每個(gè)節(jié)點(diǎn)進(jìn)行細(xì)分一直到每個(gè)節(jié)點(diǎn)只包含一個(gè)數(shù)據(jù)點(diǎn)。對(duì)于海量點(diǎn)云數(shù)據(jù)來說，不需要將數(shù)據(jù)一直劃分到每個(gè)節(jié)點(diǎn)最多只有一個(gè)數(shù)據(jù)點(diǎn)才終止，KD樹的每個(gè)葉子節(jié)點(diǎn)可以有許多數(shù)據(jù)點(diǎn)，具體的點(diǎn)數(shù)或范圍可依應(yīng)用而定。

對(duì)KD樹節(jié)點(diǎn)是否再分的標(biāo)準(zhǔn)有兩種基本的判別方法(如圖1所示)：基于點(diǎn)的數(shù)目，即如果某個(gè)節(jié)點(diǎn)內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)小于等于N，則節(jié)點(diǎn)不需要再分；基于空間范圍，即如果節(jié)點(diǎn)數(shù)據(jù)的“尺寸”小于給定尺度R，則節(jié)點(diǎn)不需要再分。

圖1

基于點(diǎn)數(shù)的劃分標(biāo)準(zhǔn)在最近點(diǎn)的查找時(shí)優(yōu)勢(shì)明顯，基于空間范圍的劃分標(biāo)準(zhǔn)在優(yōu)化顯示時(shí)操作比較簡(jiǎn)單?？紤]到基于空間范圍的劃分標(biāo)準(zhǔn)在數(shù)據(jù)空間分析時(shí)會(huì)有很大優(yōu)勢(shì)，筆者采用的劃分策略為：確定一個(gè)相對(duì)較大的空間尺度，以這個(gè)大小為空間劃分的主要標(biāo)準(zhǔn)；預(yù)先確定每個(gè)節(jié)點(diǎn)最多能容納的點(diǎn)的個(gè)數(shù)nmax，經(jīng)過空間標(biāo)準(zhǔn)劃分以后，如果某個(gè)區(qū)域內(nèi)點(diǎn)個(gè)數(shù)大于nmax，繼續(xù)細(xì)分至點(diǎn)的個(gè)數(shù)小于nmax。

本文提出的自適應(yīng)屏幕精度的點(diǎn)云數(shù)據(jù)顯示算法不論是否采用內(nèi)外存調(diào)度策略，都能有效加快顯示速度。另一方面，自適應(yīng)的KD樹在建立KD樹時(shí)，通過預(yù)先的計(jì)算使樹保持良好的靜態(tài)平衡性，從而使樹的深度減小，減少了平均查找時(shí)間，加快了處理速度。為了體現(xiàn)屏幕精度對(duì)顯示效率的提高，本文不采用內(nèi)外存調(diào)度算法，而選用比較高效的自適應(yīng)的KD樹，以期更好地表現(xiàn)顯示屏幕精度算法的優(yōu)越性。

三、自適應(yīng)屏幕精度顯示算法

1.自適應(yīng)屏幕精度的概念

LOD最早是由Clark于1976年提出的[11]，其思想是當(dāng)模型在屏幕中占據(jù)較小區(qū)域時(shí)，可以使用較粗略的模型來代替原始模型進(jìn)行繪制，以便對(duì)復(fù)雜場(chǎng)景進(jìn)行快速繪制。其核心是不繪制那些對(duì)視點(diǎn)來說“微不足道”的模型或模型細(xì)節(jié)，這些模型或是因?yàn)榫嚯x很遠(yuǎn)，只需將復(fù)雜的物體用簡(jiǎn)單的體素來渲染，或是因?yàn)樘⑿《静贿M(jìn)行渲染。

對(duì)點(diǎn)云數(shù)據(jù)而言，對(duì)象是一個(gè)個(gè)數(shù)據(jù)點(diǎn)，不存在大小之分；每個(gè)點(diǎn)不論視點(diǎn)位置如何，投影到屏幕以后都是一個(gè)像素大小，沒有優(yōu)先之別，因而很難利用LOD算法。針對(duì)這個(gè)問題，筆者以自適應(yīng)的KD樹為結(jié)構(gòu)提出了樹模型中節(jié)點(diǎn)自適應(yīng)屏幕顯示精度的算法。

首先，針對(duì)點(diǎn)數(shù)據(jù)是一個(gè)個(gè)沒有大小沒有體積的個(gè)體，拋棄在點(diǎn)的顯示中一直把一個(gè)個(gè)點(diǎn)當(dāng)作獨(dú)立個(gè)體來看待的想法，將數(shù)據(jù)集合看作整體，即在數(shù)據(jù)組織時(shí)利用KD樹組織場(chǎng)景中的數(shù)據(jù)，在考慮場(chǎng)景中的LOD模型時(shí)把KD樹中的節(jié)點(diǎn)作為一個(gè)整體看待，考慮其投影到屏幕以后，如果節(jié)點(diǎn)內(nèi)所有點(diǎn)都在同一個(gè)像素區(qū)域內(nèi)，則可以將整個(gè)節(jié)點(diǎn)當(dāng)作單點(diǎn)看待；如果投影到屏幕以后節(jié)點(diǎn)最大距離不超過半個(gè)像素，可以直接對(duì)該節(jié)點(diǎn)進(jìn)行顯示。

因而，該思路將每個(gè)節(jié)點(diǎn)可以看成是一個(gè)模型，這個(gè)模型有3個(gè)細(xì)節(jié)層次：全細(xì)節(jié)模型、單點(diǎn)模型及零點(diǎn)模型。全細(xì)節(jié)模型即整個(gè)節(jié)點(diǎn)相對(duì)觀測(cè)點(diǎn)來說很大，需要將所有數(shù)據(jù)點(diǎn)顯示；單點(diǎn)模型是數(shù)據(jù)區(qū)域投影接近一個(gè)像素大小，可以將節(jié)點(diǎn)簡(jiǎn)化為一個(gè)數(shù)據(jù)點(diǎn)；零點(diǎn)顯示即投影范圍很小以至于不需要進(jìn)行處理。同時(shí)，注意到在樹狀結(jié)構(gòu)中有父子節(jié)點(diǎn)的結(jié)構(gòu)，因此對(duì)于全細(xì)節(jié)模型，實(shí)際上不需要顯示所有數(shù)據(jù)點(diǎn)，只需要分別對(duì)其子節(jié)點(diǎn)進(jìn)行模型檢驗(yàn)即可。這種樹形結(jié)構(gòu)的遞歸正是該模型只需區(qū)分3個(gè)細(xì)節(jié)層次的原因。

圖2顯示了一顆簡(jiǎn)單的KD樹，其中的數(shù)字用于標(biāo)明節(jié)點(diǎn)半徑大小，假設(shè)該樹離觀察者距離較遠(yuǎn)，通過計(jì)算發(fā)現(xiàn)所有半徑大于等于8的節(jié)點(diǎn)在屏幕上占據(jù)一個(gè)像素的范圍，則對(duì)于該樹的顯示，只會(huì)顯示其中的4個(gè)節(jié)點(diǎn)，對(duì)其他半徑小于8的節(jié)點(diǎn)，即使顯示，也只會(huì)被遮蓋，其顯示是沒有意義的。

2.自適應(yīng)屏幕精度的顯示算法

如上節(jié)所述，自適應(yīng)屏幕精度的顯示需要對(duì)每個(gè)節(jié)點(diǎn)的“大小”作一個(gè)定量的描述，以計(jì)算節(jié)點(diǎn)相對(duì)于觀察者來說占據(jù)了屏幕上多少像素的位置。對(duì)“大小”的計(jì)算，有基于節(jié)點(diǎn)的包圍盒和包圍球兩種屏幕精度算法。

圖2 采用節(jié)點(diǎn)半徑劃分KD樹的層次

(1)包圍盒投影法

節(jié)點(diǎn)的“大小”通過計(jì)算節(jié)點(diǎn)包圍盒到屏幕的投影范圍得到，即計(jì)算包圍盒的8個(gè)頂點(diǎn)投影到屏幕以后的屏幕坐標(biāo)，根據(jù)這8個(gè)點(diǎn)的屏幕坐標(biāo)確定節(jié)點(diǎn)是否需要細(xì)分。如果這8個(gè)二維坐標(biāo)中某兩點(diǎn)的水平或豎直坐標(biāo)差大于1.5個(gè)像素，則節(jié)點(diǎn)被定義為全細(xì)節(jié)；如果坐標(biāo)差大于0.5個(gè)像素，即定義節(jié)點(diǎn)為單點(diǎn)模型；否則為零點(diǎn)模型。

圖3是推導(dǎo)任意點(diǎn)在特定視點(diǎn)下投影坐標(biāo)的示意圖。圖中點(diǎn)O是觀察點(diǎn)，過點(diǎn)O沿視線方向是Z軸，向上的方向?yàn)閅軸，將Z軸與Y軸的外積作為X軸。點(diǎn)P是模型中的任意一點(diǎn)，設(shè)P在YZ、XZ的平面投影分別為E、A，A在Z軸和X軸上的投影為D、B，則AB(或DO)、PA、PE(或AD)分別為P到XY、XZ、YZ平面的距離。A′、P′、E′和D′分別是A、P、E、D投影到屏幕上的點(diǎn)，B′為A′在X軸的投影，C′為E′在Y軸的投影。

式中，AB、PA、PE分別為P到XY、XZ、YZ平面的距離；OD′為視點(diǎn)到屏幕的距離，在OpenGL中可根據(jù)gluPerspective函數(shù)參數(shù)求得。

(2)包圍球估算法

以上方法計(jì)算量比較大。實(shí)際上構(gòu)建KD樹時(shí)在預(yù)處理階段把節(jié)點(diǎn)半徑作為參數(shù)存儲(chǔ)，則顯示時(shí)可以通過節(jié)點(diǎn)半徑在屏幕上的大小作近似估計(jì)。

如圖4所示，通過KD樹中的節(jié)點(diǎn)半徑信息，可以認(rèn)為節(jié)點(diǎn)內(nèi)所有點(diǎn)都在圖中黑圓中。如果能用圓的直徑d代表節(jié)點(diǎn)尺度，則可以簡(jiǎn)化計(jì)算。事實(shí)上對(duì)于需要判別大小的節(jié)點(diǎn)而言，其距離一般離視點(diǎn)較遠(yuǎn)，用d來代替黑圓的誤差不大。通過計(jì)算可知，當(dāng)fovy為60°時(shí)，最大誤差僅7.7%；當(dāng)fovy為90°時(shí)，最大誤差也只有17%，這種誤差對(duì)節(jié)點(diǎn)大小的估計(jì)是允許的。

圖4 根據(jù)節(jié)點(diǎn)半徑估算屏幕精度

設(shè)圖中d(兩倍節(jié)點(diǎn)半徑)投影到屏幕以后的長(zhǎng)度為d′，容易看出

式中，AO為點(diǎn)到標(biāo)準(zhǔn)面的距離；BO即包圍盒投影法中的OD′，即

對(duì)屏幕精度的判別：若d′＜1或d′＜1.5，該節(jié)點(diǎn)被定義為“很小”，不需要顯示其子節(jié)點(diǎn)。

3.基于KD樹遮擋數(shù)據(jù)的裁切方法

按照以上方式可以減少很多點(diǎn)的顯示，加快顯示速度。引入KD樹以后，還可以采用點(diǎn)(節(jié)點(diǎn))的遮擋來加速繪制過程。

考慮到KD樹劃分時(shí)是在3個(gè)維度上劃分的，投影到二維平面時(shí)，在與二維平面垂直的深度上會(huì)有很多節(jié)點(diǎn)重疊投影到同一個(gè)像素上，樹越深，這種重疊引起的重繪越多。為了進(jìn)一步提高顯示效率，可以考慮在遍歷樹結(jié)構(gòu)時(shí)按照由前到后的順序遍歷，并對(duì)每個(gè)像素進(jìn)行遮擋判斷，即如果屏幕上的像素已經(jīng)被正確繪制，則屏蔽掉該像素塊后面所有節(jié)點(diǎn)的顯示。對(duì)于屏幕像素而言，一種簡(jiǎn)單的處理方式是引入一個(gè)BOOL型的屏幕緩沖區(qū)來存儲(chǔ)屏幕上的點(diǎn)是否已經(jīng)被繪制。

引入屏幕緩沖區(qū)以后，對(duì)每個(gè)節(jié)點(diǎn)的層次判斷可以再增加一個(gè)標(biāo)準(zhǔn)：如果該節(jié)點(diǎn)下所有點(diǎn)被某些已顯示的屏幕像素區(qū)域遮擋，則直接返回。在數(shù)據(jù)量很大而且屏幕像素比較多時(shí)，已繪制的屏幕像素比較密，這時(shí)遮擋會(huì)直接剔除很多遠(yuǎn)處數(shù)據(jù)點(diǎn)的計(jì)算。

四、試 驗(yàn)

本試驗(yàn)使用的是 Intel Pentium Dual E2140 CPU、1 GB內(nèi)存、NVIDIA GeForce 8600 GT顯卡的機(jī)器，采取的數(shù)據(jù)源為一個(gè)城市的部分模型，該文件有300多萬個(gè)數(shù)據(jù)點(diǎn)。筆者先采用原始的KD樹對(duì)數(shù)據(jù)進(jìn)行組織，并進(jìn)行常規(guī)的遍歷顯示，顯示的平均時(shí)間為76 ms；再采用包圍球估算法計(jì)算屏幕精度，分別采用1.2個(gè)像素和2個(gè)像素的精確度進(jìn)行顯示，結(jié)果發(fā)現(xiàn)顯示效果從視覺上幾乎都沒有區(qū)別，而顯示效率大大提高。點(diǎn)云顯示效果如圖5所示。

圖5 屏幕精度算法中的點(diǎn)云顯示結(jié)果

將3個(gè)顯示方案在不同距離視點(diǎn)的顯示時(shí)間繪制在圖6中。從圖中可以看出，原始的繪圖方式顯示時(shí)間不變，總是76 ms；兩種KD樹自適應(yīng)屏幕精度的繪圖方式顯示時(shí)間隨著視點(diǎn)與模型距離的增大而減小，而且采用2個(gè)像素的屏幕精度的繪制時(shí)間要比1.2像素的顯示時(shí)間少很多。由此可以證明，該算法能有效減少點(diǎn)云顯示中點(diǎn)的繪制個(gè)數(shù)，而且在屏幕精確度要求降低的情況下，其顯示速度的加速非常明顯。

圖6 3個(gè)方案的顯示時(shí)間對(duì)比

注意到圖6中兩種屏幕精度顯示曲線的變化趨勢(shì)相當(dāng)一致，因此制作了圖7所示的表，圖中顯示的是1.2個(gè)像素的精度與2個(gè)像素的精度在點(diǎn)的個(gè)數(shù)與顯示時(shí)間上的一致性。即盡管這兩個(gè)模型在同樣的場(chǎng)景下顯示時(shí)間差別很大，但它們都遵循著顯示時(shí)間與顯示點(diǎn)的個(gè)數(shù)成正比的規(guī)律，即對(duì)于任何顯示任務(wù)，顯示時(shí)間與顯示點(diǎn)的個(gè)數(shù)成正比。該結(jié)論也說明了筆者在數(shù)據(jù)處理過程中采取策略的正確性，即沒有對(duì)過多不需要顯示的點(diǎn)進(jìn)行額外計(jì)算。

圖7 1.2個(gè)像素的精度與2個(gè)像素的精度在個(gè)數(shù)與時(shí)間上的對(duì)比

通過對(duì)上面的兩組數(shù)據(jù)進(jìn)行分析，可以得出兩個(gè)結(jié)論：一是本文提出的基于KD樹的點(diǎn)云數(shù)據(jù)自適應(yīng)屏幕精度顯示方法大大加快了顯示速度；二是由于這種算法的顯示時(shí)間與顯示點(diǎn)的數(shù)目成正比，在最壞的情況下對(duì)1440像素×900像素分辨率的滿屏幕場(chǎng)景顯示，也僅需要顯示130萬個(gè)數(shù)據(jù)點(diǎn)，按照筆者的推算顯示時(shí)間最多只需要50 ms，也就是說對(duì)于任何大小的點(diǎn)云場(chǎng)景，通過該方式進(jìn)行精度控制，都可以實(shí)現(xiàn)每秒20幀的繪制效率。

五、結(jié)束語

本文所提出的算法通過對(duì)KD樹的改造，引入LOD算法，提出自適應(yīng)屏幕精度的顯示與裁切，大大減少了點(diǎn)云數(shù)據(jù)繪制中點(diǎn)的繪制數(shù)目，從而有效加快了點(diǎn)云顯示速度。該算法重在將樹結(jié)構(gòu)和傳統(tǒng)的LOD技術(shù)結(jié)合，提出的設(shè)計(jì)思路對(duì)所有層次模型都能有非常明顯的加速效果。

目前該算法亟待改進(jìn)的方面有：在建立KD樹的時(shí)候，節(jié)點(diǎn)特征的選取應(yīng)該根據(jù)模型本身特征選取特征點(diǎn)，以使其更適應(yīng)應(yīng)用的需求；對(duì)于建立 KD樹索引的標(biāo)準(zhǔn)，由于實(shí)際任務(wù)的不同，應(yīng)用所關(guān)心的屬性也不同，需要針對(duì)點(diǎn)的顏色、方向等難量化的屬性建立便于量化的索引機(jī)制，以使得本算法可以實(shí)現(xiàn)多屬性的查詢功能。

[1] 李清泉，李必軍，陳靜.激光雷達(dá)測(cè)量技術(shù)及其應(yīng)用研究[J].武漢測(cè)繪科技大學(xué)學(xué)報(bào)，2000，25(5)：387-392.

[2] 梁欣廉，張繼賢，李海濤，等.激光雷達(dá)數(shù)據(jù)特點(diǎn)[J].遙感信息，2005(3)：71-75.

[3] HENRICH A，SIX H W，WIDMAYER P.The LSD Tree： Spatial Access to Multidimensional Point and Non-point Objects[C]∥Proceeding of the 15th International Conference on Very Large Databases，1989：45-53.

[4] CLARK J H.Hierarchical Geometric Models for Visible Surface Algorithms[J].Communication of the ACM，1976(19)：547-554.

[5] BENTLEY J L.Multidimensional Binary Search Trees in Database Applications[J].IEEE Transactions on Software Engineering，2006(4)：333-340.

[6] GONG J，KE S N，ZHU Q，et al.An Efficient Point Cloud Management Method Based on a 3D R-Tree[J]. Photogrammetric Engineering＆Remote Sensing，2012， 78(4)：373-381.

[7] KOTHURI R，GODFRIND A.Pro Oracle Spatial for Oracle Database 11g[M].[S.l.]：Springer，2008.

[8] SCHN B，BERTOLOTTOA M.Storage，Manipulation，and Visualization of LiDAR Data[C]∥Proceedings of 3D-ARCH.Trento：[s.n.]，2009：25-28.

[9] RAVADA S，HORHAMMER M，BARIS M K.Point Cloud：Storage，Loading，and Visualization[C]∥National Science Foundation TeraGrid Workshop on Cyber-GIS.Washington DC：[s.n.]，2010：2-3.

[10] VOSSELMAN G.Automated Planimetric Quality Control in High Accuracy Airborne Laser Scanning Surveys[J]. ISPRS Journal of Photogrammetry and Remote Sensing，2012(74)：90-100.

[11] GEOSYSTEMS L.Leica Cyclone，3D Point Cloud Processing Software[EB/OL].2011-07-26.http：∥hds.leica-geosystems.com/en/6515.htm.

[12] 黃先鋒，陶闖.機(jī)載激光雷達(dá)點(diǎn)云數(shù)據(jù)的實(shí)時(shí)渲染[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，30(11)：975-978.

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

[20] 龔俊，柯勝男，朱慶，等.一種八叉樹和三維R樹集成的激光點(diǎn)云數(shù)據(jù)管理方法[J].測(cè)繪學(xué)報(bào)，2012，41 (4)：597-604.

[14] 王晏民，郭明.大規(guī)模點(diǎn)云數(shù)據(jù)的二維與三維混合索引方法[J].測(cè)繪學(xué)報(bào)，2012，41(4)：605-612.

[15] 徐文學(xué)，楊必勝，魏征，等.多標(biāo)記點(diǎn)過程的LiDAR點(diǎn)云數(shù)據(jù)建筑物和樹冠提取[J].測(cè)繪學(xué)報(bào)，2013，42 (1)：51-58.

[16] 鄭順義，周朗明.旋轉(zhuǎn)平臺(tái)點(diǎn)云數(shù)據(jù)的配準(zhǔn)方法[J].測(cè)繪學(xué)報(bào)，2013，42(1)：73-79.

[17] ROBINSON J T.The K-D-B-tree：A Search Structure for Large Multidimensional Dynamic Indexes[C]∥ Proceeding of ACM SIGMOD International Conference on Management of Data，1981：10-18.

A High Efficient Display Method Based on KD Tree Index for Point-cloud Data

YANG Jiansi，LIU Hua，LIN Peng

TP391.9

B

0494-0911(2014)07-0018-05

2014-01-13

國家863計(jì)劃(170325)；國家自然科學(xué)基金(61331016)

楊建思(1963—)，女，江西樟樹人，博士，副教授，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)與數(shù)字城市。

楊建思，劉華，林鵬.基于KD樹的點(diǎn)云數(shù)據(jù)自適應(yīng)屏幕精度高效顯示方法[J].測(cè)繪通報(bào)，2014(7)：18-22.

10.13474/j.cnki.11-2246.2014.0216