基于四叉樹的大規(guī)模點(diǎn)云管理及實(shí)時(shí)渲染

張東升，李國(guó)柱，馬 波

（1. 昆明市測(cè)繪研究院，云南 昆明 650051；2. 昆明理工大學(xué) 國(guó)土資源工程學(xué)院，云南 昆明 650093）

基于四叉樹的大規(guī)模點(diǎn)云管理及實(shí)時(shí)渲染

張東升1,2，李國(guó)柱1,2，馬 波1

（1. 昆明市測(cè)繪研究院，云南 昆明 650051；2. 昆明理工大學(xué) 國(guó)土資源工程學(xué)院，云南 昆明 650093）

三維激光掃描儀能夠獲取非常詳盡的信息，但掃描儀的隨機(jī)軟件多數(shù)只能控制設(shè)備和數(shù)據(jù)顯示，缺乏足夠的點(diǎn)云后處理和空間分析功能。設(shè)計(jì)了一種基于四叉樹的大規(guī)模點(diǎn)云管理算法，使用四叉樹來對(duì)點(diǎn)云進(jìn)行管理，以期對(duì)大規(guī)模點(diǎn)云進(jìn)行高效管理并進(jìn)行實(shí)時(shí)渲染。

大規(guī)模點(diǎn)云；四叉樹；點(diǎn)云渲染；空間數(shù)據(jù)結(jié)構(gòu)

三維激光掃描儀能夠快速地獲取測(cè)站周圍一定距離內(nèi)的高密度點(diǎn)云數(shù)據(jù)，現(xiàn)已廣泛應(yīng)用于城市規(guī)劃、文物保護(hù)和測(cè)繪工程等領(lǐng)域。高密度點(diǎn)云中所包含的信息非常詳盡，但其數(shù)據(jù)是基于點(diǎn)的，而常規(guī)工作中的分析方法大多都是基于面的，且計(jì)算機(jī)圖形學(xué)中的可視剔除、背面消隱和光照處理也都是基于面片的。另外，空間點(diǎn)云數(shù)據(jù)中各點(diǎn)間不存在顯式的拓?fù)潢P(guān)系，所以從對(duì)點(diǎn)云進(jìn)行顯示渲染到簡(jiǎn)單的體積計(jì)算，再到復(fù)雜的空間分析都需要開發(fā)專門的算法。因此，利用傳統(tǒng)的數(shù)據(jù)處理軟件對(duì)空間點(diǎn)云數(shù)據(jù)進(jìn)行處理耗時(shí)太長(zhǎng)。

本文以大規(guī)模點(diǎn)云為研究對(duì)象，實(shí)現(xiàn)了一種基于四叉樹的大規(guī)模點(diǎn)云管理算法。在此基礎(chǔ)上又特別研究了點(diǎn)云的細(xì)節(jié)層次（LOD），旨在實(shí)現(xiàn)隨視點(diǎn)移動(dòng)點(diǎn)云自動(dòng)精簡(jiǎn)顯示，以達(dá)到對(duì)點(diǎn)云進(jìn)行實(shí)時(shí)渲染的目的，為之后開發(fā)生產(chǎn)和工作中所需的各種分析處理工具作準(zhǔn)備。

1 數(shù)據(jù)結(jié)構(gòu)及LOD計(jì)算

對(duì)于給定的點(diǎn)云，如果覆蓋范圍較小，則可將其坐標(biāo)投影到一個(gè)水平面上，不用考慮地球曲率的影響；如果覆蓋范圍很廣，則可以地球橢球?yàn)閰⒖紝?duì)象，對(duì)空間球面進(jìn)行格網(wǎng)剖分，直至每個(gè)子格網(wǎng)可視為平面為止。

對(duì)于三維激光點(diǎn)云而言，每個(gè)點(diǎn)都包含三維坐標(biāo)。點(diǎn)云的存儲(chǔ)管理有多種數(shù)據(jù)結(jié)構(gòu)可供選擇，如KD樹、四叉樹和八叉樹等。KD樹是一種二叉樹結(jié)構(gòu)，特殊之處在于每一層都有個(gè)選擇子，在對(duì)點(diǎn)云數(shù)據(jù)執(zhí)行插入操作時(shí)，根據(jù)每一層的選擇子選擇遍歷前進(jìn)的分支，每次只針對(duì)一個(gè)屬性進(jìn)行比較。使用KD樹管理點(diǎn)云數(shù)據(jù)具有很多優(yōu)勢(shì)，但可視剔除和關(guān)于LOD的計(jì)算會(huì)顯得比較復(fù)雜。四叉樹是一種典型的空間劃分結(jié)構(gòu)。八叉樹在理論上相較于四叉樹，對(duì)空間的劃分更為均勻，因其可充分考慮空間的3個(gè)維度。

從扇入扇出的角度來觀察，KD樹的扇出是最小的，八叉樹的扇出最大，四叉樹則居中。扇出意味著，樹形結(jié)構(gòu)每向下擴(kuò)充一層，會(huì)有更多的子節(jié)點(diǎn)產(chǎn)生。從另一個(gè)層面上來看，無論采用何種數(shù)據(jù)結(jié)構(gòu)，都旨在能夠?qū)崿F(xiàn)數(shù)據(jù)的快速篩選或剔除。以三維可視化中的視景體裁剪為例，這3種數(shù)據(jù)結(jié)構(gòu)的效率都非常高。當(dāng)視點(diǎn)距離點(diǎn)云較遠(yuǎn)時(shí)，這些點(diǎn)云會(huì)逐漸融合在一起；當(dāng)遠(yuǎn)到一定程度時(shí)，會(huì)在視覺上表現(xiàn)為一個(gè)點(diǎn)，這種現(xiàn)象可以使用LOD來模擬。四叉樹和八叉樹是很容易實(shí)現(xiàn)的，而KD樹在LOD實(shí)現(xiàn)上需要采用很多技巧。在對(duì)大規(guī)模點(diǎn)云進(jìn)行實(shí)時(shí)渲染時(shí)，隨著當(dāng)前視點(diǎn)位置的不同，在視點(diǎn)范圍內(nèi)的點(diǎn)云數(shù)量或多或少。例如，以俯視角度瀏覽點(diǎn)云全景時(shí)，視點(diǎn)范圍包含了全部的點(diǎn)云；當(dāng)視點(diǎn)位于點(diǎn)云內(nèi)部時(shí)，則只會(huì)看到部分點(diǎn)云。實(shí)際上，在對(duì)點(diǎn)云進(jìn)行實(shí)時(shí)渲染顯示時(shí)，完全沒有必要對(duì)全部點(diǎn)云進(jìn)行處理；如果只對(duì)點(diǎn)云中的可視部分進(jìn)行處理，則可極大提高速度。并且當(dāng)視點(diǎn)以宏觀俯視的角度觀察點(diǎn)云時(shí)，雖然全部點(diǎn)云位于視點(diǎn)范圍當(dāng)中，但由于視點(diǎn)較遠(yuǎn)，對(duì)于場(chǎng)景的細(xì)節(jié)信息查看得不是很明顯。另外，在四叉樹的內(nèi)部節(jié)點(diǎn)上可存放子點(diǎn)云的合并信息，所以使用四叉樹是非常有利于控制被處理的點(diǎn)云規(guī)模和細(xì)節(jié)信息的。

綜合考慮LOD、扇入扇出和空間劃分等因素后，選擇四叉樹為存儲(chǔ)激光點(diǎn)云的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)本文所研究的大規(guī)模點(diǎn)云。本文以空間點(diǎn)云所在的空間為對(duì)象，對(duì)其進(jìn)行四叉劃分，構(gòu)建四叉樹，最終在葉節(jié)點(diǎn)中存放該空間中所包含的點(diǎn)云。

圖1為一區(qū)域的四叉劃分及其樹形結(jié)構(gòu)，不難看出，四叉樹的檢索效率較高，實(shí)現(xiàn)點(diǎn)的快速定位時(shí)，從根節(jié)點(diǎn)開始，每次可以剔除約3/4的數(shù)據(jù)，從而可借助該結(jié)構(gòu)實(shí)現(xiàn)數(shù)據(jù)塊的大規(guī)模剔除。本文所實(shí)現(xiàn)的算法中，點(diǎn)云數(shù)據(jù)存放在葉節(jié)點(diǎn)中，中間節(jié)點(diǎn)存放LOD信息。

圖1 一個(gè)簡(jiǎn)單的空間四叉劃分及其對(duì)應(yīng)的四叉樹

圖2為使用視景體進(jìn)行可視剔除的示意圖。在構(gòu)建好四叉樹后，使用視景體進(jìn)行可視剔除其實(shí)就是個(gè)簡(jiǎn)單的幾何問題，從根節(jié)點(diǎn)開始遞歸向下遍歷，判斷是否在當(dāng)前視景體中，如果在，則對(duì)子節(jié)點(diǎn)進(jìn)行進(jìn)一步的遍歷；如果不在，則直接返回，直至達(dá)到葉節(jié)點(diǎn)位置。不難發(fā)現(xiàn)，當(dāng)視點(diǎn)遠(yuǎn)離點(diǎn)云時(shí)，在視覺效果上距離相近的點(diǎn)會(huì)逐漸融合在一起，如果能夠進(jìn)一步對(duì)該現(xiàn)象進(jìn)行模擬，則可使每幀中被處理的數(shù)據(jù)量穩(wěn)定在一個(gè)特定的水平上，這種現(xiàn)象可以通過LOD技術(shù)來模擬。

圖2 基于視景體的可視剔除

葉節(jié)點(diǎn)中包含了具體的點(diǎn)云數(shù)據(jù)，同時(shí)葉節(jié)點(diǎn)和中間節(jié)點(diǎn)中也設(shè)置了相應(yīng)的域用于存放該范圍內(nèi)點(diǎn)集所對(duì)應(yīng)的LOD信息。本算法所采用的方法是對(duì)于葉節(jié)點(diǎn)而言，設(shè)該葉節(jié)點(diǎn)中包含n個(gè)點(diǎn)，其中第i個(gè)點(diǎn)的信息為（xi，yi，hi，ri，gi，bi）。（xi，yi，hi）為點(diǎn)的坐標(biāo)信息；（ri，gi，bi）為該點(diǎn)的色彩屬性，對(duì)于某些類型的設(shè)備或通過算法處理的點(diǎn)云數(shù)據(jù)，還可能包括法線矢量屬性。LOD（xleaf，yleaf，hleaf，rleaf，gleaf，bleaf）各分量的計(jì)算公式為：

中間節(jié)點(diǎn)的LOD（xmid，ymid，hmid，rmid，gmid，bmid）則取子節(jié)點(diǎn)LOD信息的數(shù)學(xué)均值，即

需要特別說明的是，只有在理想情況下，中間點(diǎn)節(jié)才包含4個(gè)子節(jié)點(diǎn)，很多情況下都不一定包括4個(gè)子節(jié)點(diǎn)。在這種情況時(shí)，m為實(shí)際的子節(jié)點(diǎn)數(shù)目。這些LOD信息可在數(shù)據(jù)插入四叉樹之后，通過遞歸逆向計(jì)算得到。

圖3為某一子區(qū)域中點(diǎn)的LOD計(jì)算示意圖，其中紅色點(diǎn)為其余點(diǎn)通過上述公式所計(jì)算出的虛擬點(diǎn)。當(dāng)該子區(qū)域在視平面上的投影小于一定閥值時(shí)，便可直接使用該虛擬點(diǎn)代表該區(qū)域中的點(diǎn)集，而不影響視覺效果。通過這種方法可更進(jìn)一步減少數(shù)據(jù)量。

圖3 LOD計(jì)算示意圖

2 算法實(shí)現(xiàn)

算法實(shí)現(xiàn)的基礎(chǔ)是四叉樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，本文所采用的基礎(chǔ)結(jié)構(gòu)如表1、2所示，其中表1為單個(gè)點(diǎn)的信息結(jié)構(gòu)，表2為四叉樹節(jié)點(diǎn)的結(jié)構(gòu)。在此結(jié)構(gòu)體基礎(chǔ)上，實(shí)現(xiàn)了相應(yīng)的操作函數(shù)，如表3所示。

表1 PC_POINT結(jié)構(gòu)

表2 QUAD_TREE_NODE結(jié)構(gòu)

表3 四叉樹的操作函數(shù)

表1中結(jié)構(gòu)的信息域是自解釋的，其中除了包含點(diǎn)的三維坐標(biāo)外，還包括點(diǎn)的法線和顏色信息。表2中包含了豐富的信息，其中flag為標(biāo)記變量，用來標(biāo)識(shí)當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)還是中間節(jié)點(diǎn)；cur_node_info變量是PC_POINT類型的變量，在四叉樹的插入完成后，通過遍歷四叉樹，逆向計(jì)算每個(gè)節(jié)點(diǎn)的LOD信息，用于顯示時(shí)實(shí)現(xiàn)數(shù)據(jù)的快速渲染；pt_list是指針，指向一 個(gè)動(dòng)態(tài)申請(qǐng)的數(shù)組，用于存放該葉子節(jié)點(diǎn)包含的具體點(diǎn)云數(shù)據(jù)。其余的坐標(biāo)范圍數(shù)據(jù)只是用于標(biāo)識(shí)每個(gè)矩形區(qū)域的范圍，在視景體進(jìn)行可視測(cè)試時(shí)，輔助實(shí)現(xiàn)數(shù)據(jù)的快速剔除。

3 實(shí)例分析

圖4為筆者于2014年在昆明理工大學(xué)1號(hào)樓國(guó)土資源工程學(xué)院前側(cè)掃描得到的一站激光點(diǎn)云數(shù)據(jù)，使用了Leica的三維激光掃描儀，其中包含點(diǎn)數(shù)近200萬(wàn)。圖5和圖6為筆者使用立體相對(duì)處理算法對(duì)云南某山區(qū)的無人機(jī)航片進(jìn)行處理得到的點(diǎn)云數(shù)據(jù)，點(diǎn)云數(shù)量也是百萬(wàn)級(jí)。

本文利用圖4、圖5和圖6的數(shù)據(jù)對(duì)算法進(jìn)行了驗(yàn)證，在系統(tǒng)中漫游時(shí)，頻率可達(dá)60幀/s以上。在實(shí)時(shí)計(jì)算機(jī)圖形學(xué)中，渲染是按幀數(shù)進(jìn)行的，即每秒顯示器刷新的次數(shù)。由于視點(diǎn)位置不同，處理的點(diǎn)云規(guī)?？纱罂尚?，在規(guī)模較小時(shí)需處理的數(shù)據(jù)量較少；反之，需要處理的數(shù)據(jù)量則較大。因此，視點(diǎn)不同會(huì)導(dǎo)致交互漫游時(shí)出現(xiàn)忽快忽慢的閃爍效果。為了能夠使系統(tǒng)在處理不同級(jí)別的數(shù)據(jù)時(shí)保持穩(wěn)定，算法對(duì)幀頻進(jìn)行了鎖定，穩(wěn)定在60幀/s的水平上（與現(xiàn)今主流液晶顯示器的刷新頻率保持一致）。

圖4 針對(duì)建筑物掃描的點(diǎn)云數(shù)據(jù)

圖5 某山區(qū)的點(diǎn)云

圖6 某農(nóng)村區(qū)域的點(diǎn)云渲染效果

4 結(jié) 語(yǔ)

本文主要研究了使用四叉樹實(shí)現(xiàn)大規(guī)模點(diǎn)云數(shù)據(jù)的管理，并建立了相應(yīng)的LOD，用以輔助減少渲染時(shí)的數(shù)據(jù)量。在完成四叉樹的建樹及數(shù)據(jù)的載入后，通過視景體對(duì)不可見數(shù)據(jù)進(jìn)行快速剔除，根據(jù)視點(diǎn)的遠(yuǎn)近，進(jìn)一步利用LOD技術(shù)實(shí)現(xiàn)數(shù)據(jù)量的控制，將渲染的數(shù)據(jù)穩(wěn)定在了一定的水平線上。最后采用實(shí)例對(duì)文中的算法進(jìn)行了測(cè)試，效果達(dá)到了預(yù)期目標(biāo)，下一步可研究具體的建模算法和分析工具，以便于解決生產(chǎn)實(shí)踐中的具體問題。

[1] 惠文華,郭新城．三維GIS中的八叉樹空間索引研究[J]．測(cè)繪通報(bào),2003(1)∶25-27

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

[3] 徐景中,萬(wàn)幼川,張圣望．LiDAR地面點(diǎn)云的簡(jiǎn)化方法研究[J]．測(cè)繪信息與工程,2008,33(1)∶32-34

[4] 程效軍,李偉英,張小虎．基于自適應(yīng)八叉樹的點(diǎn)云數(shù)據(jù)壓縮方法研究[J]．河南科學(xué),2010,28(10)∶1 300-1 305

[5] 李娜,馬一薇,楊洋,等．利用RANSAC算法對(duì)建筑物立面進(jìn)行點(diǎn)云分割[J]．測(cè)繪科學(xué),2011,36(5)∶144-145

[6] 李必軍,方志祥,任娟．從激光掃描數(shù)據(jù)中進(jìn)行建筑物特征提取研究[J]．武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2003,28(1)∶65-70

[7] 鄭順義,蘇國(guó)中,張祖勛．三維點(diǎn)集的自動(dòng)表面重構(gòu)算法[J]．武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2005,30(2)∶154-157

[8] 李長(zhǎng)春,何榮,王寶山．LOD在大范圍復(fù)雜場(chǎng)景簡(jiǎn)化中的應(yīng)用[J]．河南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,26(2)∶181-184

P228

B

1672-4623（2016）09-0032-03

10.3969/j.issn.1672-4623.2016.09.010

張東升，碩士，工程師，研究方向?yàn)槿S激光掃描。

2015-06-01。

項(xiàng)目來源：住房和城鄉(xiāng)建設(shè)部科技示范資助項(xiàng)目（S52014016）。