徐勝攀，劉正軍，左志權(quán)

（1.中國(guó)測(cè)繪科學(xué)研究院，北京100830；2.蘭州交通大學(xué) 測(cè)繪與地理信息學(xué)院，甘肅 蘭州730071）

0 引 言

在三維交互式圖形系統(tǒng)中，拾取是一項(xiàng)重要功能。在通常情況下，三維交互式圖形系統(tǒng)不僅要將三維圖形或事物的三維模型可視化，還要提供簡(jiǎn)單的方式使得用戶能夠直接操縱三維物體，以完成對(duì)三維物體形狀、位置、顏色、紋理等屬性的查詢和編輯。用戶通過(guò)鼠標(biāo)在圖形系統(tǒng)中捕捉圖形對(duì)象的操作叫拾取，交互式三維圖形系統(tǒng)對(duì)圖形對(duì)象的增、刪、改等操作都是以拾取為基礎(chǔ)的［1，2］。

當(dāng)前關(guān)于三維拾取的研究中，較多的是對(duì)圖形對(duì)象的拾取，對(duì)點(diǎn)云拾取的研究則較少。隨著LiDAR系統(tǒng)在測(cè)繪和地理信息系統(tǒng)中的發(fā)展，以點(diǎn)云為基本圖元對(duì)象的研究不斷增多，以點(diǎn)云為基礎(chǔ)的地理信息提取、地理事物建模日益受到重視［3］。因此，研究出一套準(zhǔn)確可行的、針對(duì)三維點(diǎn)云的拾取方法具有十分重要的意義。

計(jì)算機(jī)三維圖形拾取的基本方法，從原理上說(shuō)主要可分為兩類：場(chǎng)景幾何相關(guān)的拾取方法和場(chǎng)景幾何無(wú)關(guān)的拾取方法［4］。場(chǎng)景幾何相關(guān)的拾取方法是目前廣泛采用的拾取方法，其基本思想是將鼠標(biāo)輸入點(diǎn)轉(zhuǎn)換到三維空間形成一條射線，然后利用此射線在三維空間對(duì)場(chǎng)景內(nèi)的圖元求交。在這方面較有代表性的是王劍等［5］和姚繼權(quán)等［6］的工作，此外2008年朱明亮等［7］提出三維場(chǎng)景中基于視口空間的拾取算法，將基于三維場(chǎng)景的相交檢測(cè)將維至二維平面，有效地提高了拾取效率。場(chǎng)景幾何無(wú)關(guān)的拾取方法基本思想是對(duì)場(chǎng)景作一次特殊的渲染，將物體的信息按顏色編碼渲染到后臺(tái)紋理，通過(guò)讀取紋理上相應(yīng)屏幕坐標(biāo)的顏色值就可以得到對(duì)應(yīng)物體的信息［4，7］。OpenGL選擇模式作為一種主要的拾取方法，目前也有大量研究［8－10］，基本思想是利用鼠標(biāo)在視口中確定一個(gè)矩形，通過(guò)此矩形計(jì)算得到一個(gè)特殊的視景體 （這一步由OpenGL實(shí)現(xiàn)），然后基于此視景體對(duì)場(chǎng)景進(jìn)行投影變換和裁剪變換，與視景體有交集的圖元即為拾取圖形。

三維點(diǎn)作為一種特殊的圖形對(duì)象，其拾取方法與普通的三維圖形有相通之處，但也有顯著不同。首先點(diǎn)是一種沒(méi)有大小的圖形對(duì)象，直接的幾何相關(guān)拾取方法或幾何無(wú)關(guān)拾取方法并不適用于點(diǎn)云的拾?。黄浯卧趯?shí)際應(yīng)用中，點(diǎn)云拾取常常并不限于對(duì)單個(gè)點(diǎn)的拾取，而且是對(duì)點(diǎn)集的拾取，這與普通三維圖形拾取中針對(duì)單個(gè)圖形對(duì)象的拾取并不一致；第三，點(diǎn)云的在空間的分布呈離散狀態(tài)，這恰為合理的點(diǎn)云組織以便加速點(diǎn)云拾取提供了空間。

基于此，本文系統(tǒng)研究三維空間點(diǎn)云的拾取問(wèn)題，提出面向大規(guī)模點(diǎn)云數(shù)據(jù)的快速拾取算法。

1 三維點(diǎn)云拾取基本方法

1.1 點(diǎn)云拾取問(wèn)題分類

在實(shí)際應(yīng)用中，通常有兩類典型的點(diǎn)云拾取問(wèn)題：第一類是鼠標(biāo)在屏幕上給定一點(diǎn)，要求找到場(chǎng)景中離給定點(diǎn)距離最近的點(diǎn) （稱這類問(wèn)題為單點(diǎn)拾取問(wèn)題），這種情況在通過(guò)鼠標(biāo)查詢場(chǎng)景中點(diǎn)的三維坐標(biāo)、點(diǎn)之間的距離量測(cè)等時(shí)會(huì)遇到；第二類是鼠標(biāo)在屏幕上確定一個(gè)多邊形，要求找到場(chǎng)景中落在這個(gè)多邊形范圍內(nèi)的點(diǎn) （稱這類問(wèn)題為多點(diǎn)拾取問(wèn)題），這類問(wèn)題在LiDAR數(shù)據(jù)處理中，對(duì)點(diǎn)云進(jìn)行手工分類、觀察局部地形剖面等時(shí)會(huì)遇到，如圖1所示。

圖1 點(diǎn)云拾取典型問(wèn)題分類

1.2 三維點(diǎn)云拾取基本方法

上文對(duì)計(jì)算機(jī)三維圖形基本拾取方法及其對(duì)點(diǎn)云拾取的適用性進(jìn)行了簡(jiǎn)單分析。事實(shí)上，從OpenGL選擇模式需要用到命名棧這一點(diǎn)出發(fā)，決定了這種方法并不適合于點(diǎn)云的拾?。涣硗?，這種方法只能對(duì)按即時(shí)模式繪制的圖元進(jìn)行拾取，當(dāng)圖元以緩沖區(qū)對(duì)象等形式組織時(shí)，這種拾取方式顯得無(wú)能為力。對(duì)于場(chǎng)景幾何無(wú)關(guān)的拾取方法，由于點(diǎn)云不具備面狀特征，且離散分布，以讀取渲染圖像像素顏色來(lái)識(shí)別圖元的方式?jīng)Q定了它不適合用來(lái)拾取點(diǎn)云。

場(chǎng)景幾何無(wú)關(guān)的方式是一個(gè)值得考慮的方法，為減小相交檢測(cè)計(jì)算的復(fù)雜度，本文采取文獻(xiàn) ［7］中的方法——基于視口空間來(lái)進(jìn)行點(diǎn)云拾取。基本思路是將點(diǎn)云由三維場(chǎng)景映射到屏幕，然后在屏幕上進(jìn)行點(diǎn)的相交檢測(cè)。在單點(diǎn)拾取時(shí)，只需計(jì)算各點(diǎn)的屏幕坐標(biāo)到鼠標(biāo)點(diǎn)擊位置的距離，距離最短者即為拾取點(diǎn)；在進(jìn)行多點(diǎn)拾取時(shí)，對(duì)各點(diǎn)的屏幕坐標(biāo)與由鼠標(biāo)所確定的多邊形進(jìn)行相交檢測(cè)，落在多邊形內(nèi)的點(diǎn)即為拾取點(diǎn)。

另外，單點(diǎn)拾取基本方法中涉及到 “距離最短”對(duì)應(yīng)點(diǎn)的查找，原則上需要這樣做，但在實(shí)際的三維點(diǎn)云可視化中，當(dāng)視點(diǎn)離場(chǎng)景很遠(yuǎn)時(shí)，點(diǎn)云在屏幕上的顯示非常密集，此時(shí)尋找距離最短對(duì)應(yīng)點(diǎn)既十分費(fèi)時(shí)，也沒(méi)有必要。同時(shí)，在有些情況下，距離最短原則也不一定總是正確，例如當(dāng)視點(diǎn)離場(chǎng)景很近時(shí)，點(diǎn)云在屏幕上的顯示非常分散，此時(shí)拾取到的距離最短對(duì)應(yīng)點(diǎn)有可能離鼠標(biāo)點(diǎn)擊位置距離很遠(yuǎn)，拾取結(jié)果并不是用戶所需要的點(diǎn)。

可以對(duì)單點(diǎn)拾取算法進(jìn)一步修改，設(shè)計(jì)一個(gè)最小可識(shí)別距離 （minimum identifiable distance，MID）和最小容忍距離 （minimum tolerance distance，MTD），拾取時(shí)將三維點(diǎn)向屏幕投影，如果投影點(diǎn)到鼠標(biāo)點(diǎn)擊位置小于MID，則該點(diǎn)即為拾取點(diǎn)，拾取結(jié)束；如果投影點(diǎn)到鼠標(biāo)點(diǎn)擊位置大于MID而小于MTD，則該點(diǎn)作為被比較對(duì)象，后續(xù)計(jì)算中選取距離最小的點(diǎn)；如果投影點(diǎn)到鼠標(biāo)點(diǎn)擊位置大于MTD，則結(jié)束該點(diǎn)的計(jì)算，判斷后續(xù)點(diǎn)。

在具體算法設(shè)計(jì)中MID、MTD的值可以靈活選取。當(dāng)MID＝MTD時(shí)，拾取過(guò)程變?yōu)檫x取任意一個(gè)落在以MID為半徑的圓內(nèi)的點(diǎn)。

2 基于四叉樹(shù)的層次包圍盒技術(shù)

2.1 四叉樹(shù)的引入

在實(shí)際應(yīng)用中，系統(tǒng)面對(duì)的通常是大規(guī)模的三維點(diǎn)云數(shù)據(jù)，如果進(jìn)行點(diǎn)云拾取時(shí)對(duì)三維場(chǎng)景中的點(diǎn)一一進(jìn)行坐標(biāo)轉(zhuǎn)換和相交檢測(cè)，勢(shì)必給系統(tǒng)帶來(lái)較大的運(yùn)算負(fù)荷，影響交互速度。層次包圍盒［2］是一種能有效提高拾取效率的技術(shù)，在拾取時(shí)，從層次包圍盒上層結(jié)點(diǎn)出發(fā)，逐步向下判斷，如果到達(dá)某個(gè)結(jié)點(diǎn)時(shí)與拾取射線或拾取多邊形無(wú)交集，則其子結(jié)點(diǎn)的相交情況無(wú)需再判斷；當(dāng)?shù)竭_(dá)最底層結(jié)點(diǎn)時(shí)，則進(jìn)行基本的相交檢測(cè)。

為了構(gòu)建層次包圍盒，點(diǎn)云數(shù)據(jù)需按樹(shù)形組織。目前常用于構(gòu)建空間數(shù)據(jù)索引的樹(shù)形結(jié)構(gòu)包括四叉樹(shù)、八叉樹(shù)、K－D樹(shù)［11］、R樹(shù)［12］等。K－D樹(shù)、R樹(shù)缺點(diǎn)是結(jié)構(gòu)復(fù)雜、構(gòu)建速度較慢；八叉樹(shù)雖然可以快速構(gòu)建，但它對(duì)點(diǎn)云數(shù)據(jù)按三維劃分，而在進(jìn)行點(diǎn)云拾取時(shí)，一條拾取射線往往會(huì)貫穿八叉樹(shù)內(nèi)的多層結(jié)點(diǎn)，所以對(duì)于點(diǎn)云拾取而言，這種劃分實(shí)際上沒(méi)有必要，而且對(duì)于大規(guī)模的點(diǎn)云數(shù)據(jù)，按八叉樹(shù)的空間劃分往往會(huì)造成大量的空的結(jié)點(diǎn)，浪費(fèi)較多內(nèi)存。

相比于上述數(shù)據(jù)結(jié)構(gòu)而言，四叉樹(shù)表現(xiàn)出獨(dú)特的優(yōu)勢(shì)。首先，四叉樹(shù)僅對(duì)數(shù)據(jù)進(jìn)行二維劃分，符合大規(guī)模點(diǎn)云數(shù)據(jù)的尺度變化的特點(diǎn)；其次，當(dāng)對(duì)四叉樹(shù)進(jìn)行規(guī)則劃分時(shí)，四叉樹(shù)各結(jié)點(diǎn)與其父結(jié)點(diǎn)的形狀、位置等表現(xiàn)出嚴(yán)格的數(shù)量關(guān)系，這有利于結(jié)點(diǎn)形狀、位置等的計(jì)算，可以為四叉樹(shù)的存儲(chǔ)節(jié)省大量?jī)?nèi)存；另外，在下文將可以看到，利用本文提出的高效四叉樹(shù)處理策略，整個(gè)四叉樹(shù)的構(gòu)建過(guò)程可以大幅度地加速。

基于此，本文利用四叉樹(shù)構(gòu)建點(diǎn)云層次包圍盒，解決大規(guī)模三維點(diǎn)云數(shù)據(jù)的快速拾取問(wèn)題。

2.2 高效四叉樹(shù)處理策略

考慮到點(diǎn)云數(shù)據(jù)的海量性，四叉樹(shù)可能具有龐大的索引結(jié)構(gòu)，因此，減少四叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)量、加速四叉樹(shù)構(gòu)建過(guò)程具有十分重要的意義。本文采用靜態(tài)方式構(gòu)建四叉樹(shù)（先建立四叉樹(shù)，再填充點(diǎn)云數(shù)據(jù)），對(duì)點(diǎn)云數(shù)據(jù)塊沿軸向劃分 （行沿X方向，列沿Y方向），采用帶葉子結(jié)點(diǎn)索引的規(guī)則劃分滿四叉樹(shù)結(jié)構(gòu) （見(jiàn)圖2）。

圖2 點(diǎn)云數(shù)據(jù)塊劃分與四叉樹(shù)結(jié)點(diǎn)組織

四叉樹(shù)經(jīng)過(guò)這樣處理后，在以下方面具有顯著優(yōu)勢(shì)：

首先，對(duì)于任一結(jié)點(diǎn)，只要知道其遍歷路徑，便可快速計(jì)算出結(jié)點(diǎn)所代表數(shù)據(jù)塊的X、Y坐標(biāo)范圍，這可以為四叉樹(shù)的存儲(chǔ)節(jié)省大量的空間；其次，當(dāng)四叉樹(shù)規(guī)則劃分時(shí)，頂點(diǎn)所在的葉子結(jié)點(diǎn)行列號(hào)可以直接計(jì)算得到，當(dāng)對(duì)葉子結(jié)點(diǎn)按行列號(hào)建立二維索引后，頂點(diǎn)數(shù)據(jù)就可以直接加入四叉樹(shù)，而不必自根結(jié)點(diǎn)逐步判斷，這可以大大加速四叉樹(shù)的初始化過(guò)程，提高系統(tǒng)運(yùn)行效率。

2.3 四叉樹(shù)結(jié)點(diǎn)點(diǎn)云包圍盒的計(jì)算

點(diǎn)云包圍盒是一個(gè)在空間內(nèi)包含點(diǎn)云數(shù)據(jù)塊所有點(diǎn)的最小長(zhǎng)方體，點(diǎn)云包圍盒由中心 （Center）、3個(gè)軸向 （Axis）以及3個(gè)沿軸向方向的延伸尺度 （Extent）定義，其模型如圖3所示。

圖3 點(diǎn)云包圍盒的幾何模型

本文中建立點(diǎn)云包圍盒時(shí)，取V0、V1、V2分別沿X、Y、Z軸，當(dāng)結(jié)點(diǎn)中點(diǎn)云的X、Y、Z最大值和最小值均確定，點(diǎn)云包圍盒的形狀和位置隨之確定。結(jié)點(diǎn)的Z最大值和最小值直接存儲(chǔ)，X、Y最大值和最小值則根據(jù)結(jié)點(diǎn)遍歷路徑計(jì)算確定。這樣既可以節(jié)省內(nèi)存，又可以使得所有點(diǎn)云包圍盒中心并不落在同一平面上，更好地適應(yīng)空間中點(diǎn)云的形狀分布，減少點(diǎn)云包圍盒的無(wú)效面積［2］。

3 基于四叉樹(shù)的大規(guī)模三維點(diǎn)云快速拾取算法

3.1 基于四叉樹(shù)的單點(diǎn)拾取算法

結(jié)合單點(diǎn)拾取基本方法，本算法基本思想是先利用四叉樹(shù)尋找基本的點(diǎn)云數(shù)據(jù)塊 （即葉子結(jié)點(diǎn)），然后對(duì)于葉子結(jié)點(diǎn)執(zhí)行基本的單點(diǎn)拾取算法，如果找到滿足條件的點(diǎn)，則返回拾取結(jié)果，退出；否則，更新查找記錄，對(duì)當(dāng)前結(jié)點(diǎn)的兄弟結(jié)點(diǎn)繼續(xù)執(zhí)行上述查找。

在尋找基本數(shù)據(jù)塊時(shí)，需要對(duì)數(shù)據(jù)塊與鼠標(biāo)確定點(diǎn)進(jìn)行相交檢測(cè)，方法為先求取鼠標(biāo)確定點(diǎn)在場(chǎng)景空間對(duì)應(yīng)的射線，然后對(duì)射線與點(diǎn)云包圍盒進(jìn)行相交檢測(cè)。三維空間內(nèi)射線與長(zhǎng)方體的相交檢測(cè)是一個(gè)簡(jiǎn)單的計(jì)算幾何算法，其過(guò)程為首先確定射線起點(diǎn)是否在長(zhǎng)方體內(nèi)，如果是則相交；否則，求取長(zhǎng)方體中心與射線的垂線，如果垂足在射線起點(diǎn)的反方向，則不相交；否則，求取長(zhǎng)方體中心到垂足的向量在長(zhǎng)方體各軸向 （axis）的投影長(zhǎng)度，如果各投影長(zhǎng)度均小于相應(yīng)軸向的延伸尺度 （extent）則相交，否則不相交。

算法流程圖如圖4所示。

圖4 基于四叉樹(shù)的單點(diǎn)拾取算法

算法中，初始當(dāng)前結(jié)點(diǎn)為四叉樹(shù)根結(jié)點(diǎn)。

3.2 基于四叉樹(shù)的多點(diǎn)拾取算法

算法基本思想是首先逐步對(duì)四叉樹(shù)結(jié)點(diǎn)與鼠標(biāo)所確定的屏幕多邊形進(jìn)行相交檢測(cè)，找到與多邊形有交集的基本點(diǎn)云數(shù)據(jù)塊，然后再對(duì)結(jié)點(diǎn)執(zhí)行多點(diǎn)拾取基本算法 （即將基本點(diǎn)云數(shù)據(jù)塊內(nèi)的點(diǎn)投影到屏幕上，即點(diǎn)在屏幕上的投影在多邊形內(nèi)的點(diǎn)加入查找集合）。

四叉樹(shù)結(jié)點(diǎn)與鼠標(biāo)所確定的屏幕多邊形的相交檢測(cè)過(guò)程是先將四叉樹(shù)結(jié)點(diǎn)的點(diǎn)云包圍盒投影到屏幕形成一個(gè)凸多邊形，然后對(duì)該多邊形與鼠標(biāo)所確定的多邊形進(jìn)行相交檢測(cè)運(yùn)算，這是一個(gè)基本的計(jì)算幾何算法。本過(guò)程中涉及到的另一個(gè)計(jì)算幾何算法是點(diǎn)是否在多邊形內(nèi)的判斷。

為加速基本數(shù)據(jù)塊的查找，在對(duì)結(jié)點(diǎn)包圍盒進(jìn)行投影之前可以先對(duì)結(jié)點(diǎn)包圍盒與視景體進(jìn)行相交檢測(cè)，相交檢測(cè)可以有條件地進(jìn)行，例如，當(dāng)視點(diǎn)與場(chǎng)景近到一定程度時(shí)才進(jìn)行相交檢測(cè)，同時(shí)相交檢測(cè)算法也可以簡(jiǎn)化，篇幅所限，這部分內(nèi)容本文不作詳細(xì)論述。

算法的流程圖如圖5所示。

圖5 基于四叉樹(shù)的多點(diǎn)拾取算法

算法中，初始當(dāng)前結(jié)點(diǎn)為四叉樹(shù)根結(jié)點(diǎn)。

4 實(shí)驗(yàn)與評(píng)價(jià)

為檢驗(yàn)本文算法的拾取效率和拾取準(zhǔn)確性，采用大小約為240M （10 346 373個(gè)點(diǎn)）的LAS（由美國(guó)攝影測(cè)量與遙感協(xié)會(huì)制定的一種機(jī)載激光雷達(dá)數(shù)據(jù)專有格式）文件設(shè)計(jì)了一組實(shí)驗(yàn)，實(shí)驗(yàn)中，對(duì)對(duì)云數(shù)據(jù)分別在分布密集、分布較密和分布稀疏3種狀態(tài) （如圖6所示）下進(jìn)行單點(diǎn)拾取和多點(diǎn)拾取。對(duì)單點(diǎn)拾取，采用統(tǒng)計(jì)1000個(gè)隨機(jī)點(diǎn)的累計(jì)拾取時(shí)間計(jì)算平均拾取時(shí)間；對(duì)多點(diǎn)拾取，分別采用尺寸大約為視口尺寸的1／102、1／52、1／32的隨機(jī)多邊形 （頂點(diǎn)個(gè)數(shù)在10個(gè)點(diǎn)以內(nèi)）進(jìn)行拾取，統(tǒng)計(jì)拾取時(shí)間。每組實(shí)驗(yàn)進(jìn)行10次，結(jié)果取平均值。表1為拾取時(shí)間統(tǒng)計(jì)表，實(shí)驗(yàn)中，取MID＝5，MTD＝15。

圖6 點(diǎn)云分別狀態(tài)

表1 拾取實(shí)驗(yàn)時(shí)間統(tǒng)計(jì)

為檢驗(yàn)拾取精度，采用相同的數(shù)據(jù)和相同的運(yùn)行環(huán)境，針對(duì)單點(diǎn)拾取和多點(diǎn)拾取分別進(jìn)行實(shí)驗(yàn)，以下為實(shí)驗(yàn)效果圖。圖7進(jìn)行距離量測(cè)時(shí)，鼠標(biāo)從一個(gè)拾取點(diǎn)移動(dòng)到另一個(gè)拾取點(diǎn)，實(shí)現(xiàn)了對(duì)兩個(gè)點(diǎn)的正確捕捉；圖8中用鼠標(biāo)圍繞一座建筑物確定一個(gè)多邊形，將這些點(diǎn)從未定義類劃分到建筑物類，實(shí)現(xiàn)了多點(diǎn)拾取。

圖7 單點(diǎn)拾取效果

從實(shí)驗(yàn)結(jié)果可以看到，當(dāng)點(diǎn)的數(shù)據(jù)量達(dá)到千萬(wàn)級(jí)以后，單點(diǎn)拾取均能保持很高的拾取速度。多點(diǎn)拾取在點(diǎn)云分布密集和較密集的情況下，對(duì)于尺寸分別為1／102、1／52、1／32的任意多邊形都能進(jìn)行較為快速的拾取；當(dāng)點(diǎn)云分布稀疏時(shí)，多點(diǎn)拾取速度有所下降，但仍不至于有過(guò)長(zhǎng)的時(shí)間延遲。從拾取效果上看，單點(diǎn)拾取和多點(diǎn)拾取均能正確地完成拾取，取得了比較好的效果。

圖8 多點(diǎn)拾取效果

5 結(jié)束語(yǔ)

拾取是交互式圖形系統(tǒng)的重要功能，是許多交互式操作的基礎(chǔ)。由于生產(chǎn)應(yīng)用的限制，目前對(duì)三維點(diǎn)云拾取的研究并不多見(jiàn)，隨著LiDAR系統(tǒng)的發(fā)展，對(duì)大規(guī)模三維點(diǎn)云拾取的研究具有重要意義。本文在系統(tǒng)總結(jié)當(dāng)前計(jì)算機(jī)三維圖形拾取基本方法的基礎(chǔ)上，討論了常用拾取方法與三維點(diǎn)云拾取的適用性問(wèn)題，進(jìn)一步提出適合于三維點(diǎn)云拾取的基本方法。針對(duì)實(shí)際LiDAR點(diǎn)云數(shù)據(jù)處理中往往為大規(guī)模點(diǎn)云數(shù)據(jù)，通過(guò)層次包圍盒的思想引入四叉樹(shù)，提出了基于四叉樹(shù)的大規(guī)模三維點(diǎn)云快速拾取系列算法，試驗(yàn)證明算法在大規(guī)模點(diǎn)云拾取速度和精度上均達(dá)到了較好效果。另外，雖然本文所提出的四叉樹(shù)是針對(duì)點(diǎn)云拾取設(shè)計(jì)的，但是由于該四叉樹(shù)考慮了點(diǎn)的三維特性，采取了有利于節(jié)省內(nèi)存和提高速度的高效策略，且能較好地適應(yīng)三維點(diǎn)云的空間分布，將該四叉樹(shù)用于海量點(diǎn)云數(shù)據(jù)的場(chǎng)景管理以及LOD （level of details）實(shí)現(xiàn)同樣具有借鑒意義。

［1］YUE Wenli，WANG Jian，DAI Yiru.Research on algorithm for picking up graph in interactive graphics systems［J］.Development ＆ Innovation of Machinery ＆ Elemctrical Products，2008，21（2）：3－4 （in Chinese）.［岳文理，王堅(jiān)，戴毅茹.交互式圖形系統(tǒng)中圖形拾取算法的研究與應(yīng)用 ［J］.機(jī)電產(chǎn)品開(kāi)發(fā)與創(chuàng)新，2008，21（2）：3－4.］

［2］ZHANG Xiaohong.Airborne laser radar measurement technology theory and method［M］.Wuhan：Wuhan University Press，2007：1－14 （in Chinese）.［張小紅.機(jī)載激光雷達(dá)測(cè)量技術(shù)理論與方法 ［M］.武漢：武漢大學(xué)出版社，2007：1－14.］

［3］GUO Yanxia，HOU Tongpu，DU Yuanyuan.Picking entities in 3Dscene based on DirectX ［J］.Journal of Liaoning Univer－sity of Petrol Eum ＆ Chemical Technology，2009，29 （3）：77－80（in Chinese）.［郭艷霞，侯彤璞，杜園園.基于DirectX的三維場(chǎng)景實(shí)體的拾取 ［J］，遼寧石油化工大學(xué)學(xué)報(bào)，2009，29（3）：77－80.］

［4］ZHANG Jiahua，LIANG Cheng，LI Guiqing.3Dprimitive picking on GPU ［J］.Journal of Engineering Graphics，2009 （1）：46－52（in Chinese）.［張嘉華，梁成，李桂清.GPU三維圖元拾取 ［J］.工程圖學(xué)學(xué)報(bào)，2009 （1）：46－52.］

［5］WANG Jian，LU Guodong，TAN Jianrong.The selection method of graphics at 3Dgraphic browser［J］.Machine，2004（7）：29－32 （in Chinese）.［王劍，陸國(guó)棟，譚建榮.三維場(chǎng)中圖形對(duì)象的拾取方法 ［J］.機(jī)械，2004 （7）：29－32.］

［6］YAO Jiquan，LI Xiaohuo.Research on 3－dimension pick－up of human－computer intersection in computer graphics［J］.Journal of Engineering Design，2006，13 （2）：116－120 （in Chinese）.［姚繼權(quán)，李曉豁.計(jì)算機(jī)圖形學(xué)人機(jī)交互中三維拾取方法的研究 ［J］.工程設(shè)計(jì)學(xué)報(bào)，2006，13 （2）：116－120.］

［7］ZHU Mingliang，DONG Bing，WANG Yi，et al.Algorithm for picking in 3Dscenes based on viewport space［J］.Enginee－ring Graphics，2008 （2）：94－97 （in Chinese）.［朱明亮，董冰，王祎，等.三維場(chǎng)景中基于視口空間的拾取算法 ［J］.工程圖學(xué)學(xué)報(bào)，2008 （2）：94－97.］

［8］HE Jianying，XU Qianghua，YOU Jia.A 3Dpicking method based on OpenGL［J］.Computer Engineering ＆Science，2006，28 （1）：45－46 （in Chinese）.［何健鷹，徐強(qiáng)華，游佳.基于OpenGL的一種三維拾取方法 ［J］.計(jì)算機(jī)工程與科學(xué)，2006，28 （1）：45－46.］

［9］SUN Nifang，YANG Zhiqiang，CHEN Cheng，et al.Control the 3Dmodels interactively in OpenGL ［J］.Computer Applications and Software，2007，24 （10）：207－209 （in Chinese）.［孫妮芳，楊志強(qiáng)，陳誠(chéng)，等.OpenGL實(shí)現(xiàn)3D模型的交互控制［J］.計(jì)算機(jī)應(yīng)用與軟，2007，24 （10）：207－209.］

［10］ZHU Jincai，CHENG Zhiyong，HUANG Xuefei.On－machine measurement software development based on selection mode of OpenGL［J］.Mechanical ＆ Electrical Engineering，2010，39（5）：13－14 （in Chinese）.［諸進(jìn)才，程智勇，黃學(xué)飛.基于OpenGL拾取技術(shù)交互式在機(jī)檢測(cè)軟件的開(kāi)發(fā) ［J］.機(jī)電工程技術(shù)，2010，39 （5）：13－14.］

［11］LIU Yu，XIONG Youlun.Algorithm for searching nearest－neighbor based on the bounded k－d tree［J］.J Huazhong Univ of Sci ＆Tech （Natural Science Edition），2008，36 （7）：73－76 （in Chinese）.［劉宇，熊有倫.基于有界k－d樹(shù)的最近點(diǎn)搜索算法 ［J］.華中科技大學(xué)學(xué)報(bào) （自然科學(xué)版），2008，36 （7）：73－76.］

［12］YU Dengfeng.The research and implement of spatial data index technology base on R－Tree［D］.Wuhan：China University of Geosciences，2006：14－24 （in Chinese）.［余登峰.基于R樹(shù)的空間數(shù)據(jù)索引技術(shù)研究與實(shí)現(xiàn) ［D］.武漢：中國(guó)地質(zhì)大學(xué)，2006：14－24.］