大規(guī)模三維點云快速拾取技術(shù)研究

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

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

0 引 言

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

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

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

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

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

1 三維點云拾取基本方法

1.1 點云拾取問題分類

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

圖1 點云拾取典型問題分類

1.2 三維點云拾取基本方法

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

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

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

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

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

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

2.1 四叉樹的引入

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

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

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

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

2.2 高效四叉樹處理策略

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

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

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

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

2.3 四叉樹結(jié)點點云包圍盒的計算

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

圖3 點云包圍盒的幾何模型

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

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

3.1 基于四叉樹的單點拾取算法

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

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

算法流程圖如圖4所示。

圖4 基于四叉樹的單點拾取算法

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

3.2 基于四叉樹的多點拾取算法

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

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

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

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

圖5 基于四叉樹的多點拾取算法

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

4 實驗與評價

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

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

表1 拾取實驗時間統(tǒng)計

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

圖7 單點拾取效果

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

圖8 多點拾取效果

5 結(jié)束語

拾取是交互式圖形系統(tǒng)的重要功能，是許多交互式操作的基礎(chǔ)。由于生產(chǎn)應(yīng)用的限制，目前對三維點云拾取的研究并不多見，隨著LiDAR系統(tǒng)的發(fā)展，對大規(guī)模三維點云拾取的研究具有重要意義。本文在系統(tǒng)總結(jié)當(dāng)前計算機(jī)三維圖形拾取基本方法的基礎(chǔ)上，討論了常用拾取方法與三維點云拾取的適用性問題，進(jìn)一步提出適合于三維點云拾取的基本方法。針對實際LiDAR點云數(shù)據(jù)處理中往往為大規(guī)模點云數(shù)據(jù)，通過層次包圍盒的思想引入四叉樹，提出了基于四叉樹的大規(guī)模三維點云快速拾取系列算法，試驗證明算法在大規(guī)模點云拾取速度和精度上均達(dá)到了較好效果。另外，雖然本文所提出的四叉樹是針對點云拾取設(shè)計的，但是由于該四叉樹考慮了點的三維特性，采取了有利于節(jié)省內(nèi)存和提高速度的高效策略，且能較好地適應(yīng)三維點云的空間分布，將該四叉樹用于海量點云數(shù)據(jù)的場景管理以及LOD （level of details）實現(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）.［岳文理，王堅，戴毅茹.交互式圖形系統(tǒng)中圖形拾取算法的研究與應(yīng)用 ［J］.機(jī)電產(chǎn)品開發(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á)測量技術(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的三維場景實體的拾取 ［J］，遼寧石油化工大學(xué)學(xué)報，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é)報，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）.［王劍，陸國棟，譚建榮.三維場中圖形對象的拾取方法 ［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ī)圖形學(xué)人機(jī)交互中三維拾取方法的研究 ［J］.工程設(shè)計學(xué)報，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）.［朱明亮，董冰，王祎，等.三維場景中基于視口空間的拾取算法 ［J］.工程圖學(xué)學(xué)報，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ī)工程與科學(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)，陳誠，等.OpenGL實現(xiàn)3D模型的交互控制［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ī)檢測軟件的開發(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樹的最近點搜索算法 ［J］.華中科技大學(xué)學(xué)報 （自然科學(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ù)據(jù)索引技術(shù)研究與實現(xiàn) ［D］.武漢：中國地質(zhì)大學(xué)，2006：14－24.］