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

張東升，李國柱，馬 波

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

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

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

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

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

大規模點云；四叉樹；點云渲染；空間數據結構

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

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

1 數據結構及LOD計算

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

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

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

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

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

圖1 一個簡單的空間四叉劃分及其對應的四叉樹

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

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

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

中間節點的LOD（xmid，ymid，hmid，rmid，gmid，bmid）則取子節點LOD信息的數學均值，即

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

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

圖3 LOD計算示意圖

2 算法實現

算法實現的基礎是四叉樹節點的數據結構，本文所采用的基礎結構如表1、2所示，其中表1為單個點的信息結構，表2為四叉樹節點的結構。在此結構體基礎上，實現了相應的操作函數，如表3所示。

表1 PC_POINT結構

表2 QUAD_TREE_NODE結構

表3 四叉樹的操作函數

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

3 實例分析

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

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

圖4 針對建筑物掃描的點云數據

圖5 某山區的點云

圖6 某農村區域的點云渲染效果

4 結 語

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

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

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

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

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

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

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

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

[8] 李長春,何榮,王寶山．LOD在大范圍復雜場景簡化中的應用[J]．河南理工大學學報(自然科學版),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。

項目來源：住房和城鄉建設部科技示范資助項目（S52014016）。