張東升，李國柱，馬 波

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

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

張東升1,2，李國柱1,2，馬 波1

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

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

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

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

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

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

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

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

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

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

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

圖1 一個簡單的空間四叉劃分及其對應(yīng)的四叉樹

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

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

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

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

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

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

圖3 LOD計算示意圖

2 算法實現(xiàn)

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

3 實例分析

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

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

圖4 針對建筑物掃描的點云數(shù)據(jù)

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

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

4 結(jié) 語

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

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

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

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

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

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

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

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

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

P228

B

1672-4623（2016）09-0032-03

10.3969/j.issn.1672-4623.2016.09.010

張東升，碩士，工程師，研究方向為三維激光掃描。

2015-06-01。

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