大規模點云內外存調度繪制技術

張 毅，呂秀琴

(武漢大學 a.測繪學院；b.資源與環境科學學院，武漢 430079)

1 概述

利用三維激光掃描技術獲取的點云是一種可直觀表達目標空間形態和分布的海量三維空間數據。空間數據一般會涉及 3類操作：存儲管理，處理計算和顯示繪制。對于顯示繪制技術，主要是旋轉、縮放和漫游等操作。在大數據量情況下，通常采取抽稀、細節層次模型(Level of Detail,LOD)[1-2]、建立數據金字塔結構[3-4]等技術進行實現。二維遙感影像和數字高程模型(Digital Element Model, DEM)具有規則的數據結構，三維模型和矢量數據僅需要繪制較少頂點。相比較而言，點云的空間排列不規則，密度不均勻，數據量異常龐大，因此，海量點云的快速顯示繪制有著特殊的技術要求。

有許多學者對海量點云快速顯示進行了研究。如采用磁盤映射方式讀取數據并引入分塊索引，實現1965449個點的顯示[5]。利用并行k最鄰近點(k-Nearest Neighbor, kNN)算法，實現數據總大小約為2.3 GB、共約9000萬點的顯示[6]。采用規則空間八叉樹與平衡二叉樹相結合的嵌套復合結構進行組織，實現178799個點的顯示[7]。利用基于視點的LOD及點云分塊技術實現最大1205000個點的繪制[8]。還有基于核外多分辨率海量點云數據的處理和交互編輯[9]、通過沿空間掃描和點排序的流技術點云處理方法[10]等。但就點云數據量而言，以上方法并沒有達到億級或更大規模的水平，在存儲結構和調度繪制方面都有可進一步挖掘的空間。一些商業軟件在海量點云的快速顯示繪制方面具有各自特點。Cyclone[11]、Realworks Survey、Polyworks[12]等采用的是動態抽稀技術，Rigel、XGRT[13]等采用的是八叉樹結構技術。其中一些軟件聲稱可以處理TB甚至PB級的點云數據。

海量點云快速繪制問題的關鍵在于如何利用有限的內存資源建立點云繪制的存儲結構和調度機制，實現任意范圍內點云數據的快速吞吐，并盡可能降低繪制流水線的CPU階段限制。點云只能首先存儲在外存中，如果完全依靠外存來建立內存結構和繪制，頻繁的I/O操作將嚴重降低效率，而又無法完全通過有限的內存來實現。因此，問題的核心是以多大的內存和時間代價來完成內存結構的建立和點云繪制。針對該問題，本文在研究建立點云數據的八叉樹存儲結構和內外存調度策略的基礎上，分析點云規模和節點規模對于內存結構建立和繪制的影響，通過從百萬級到億級點云的實驗，實現大規模點云數據的有效調度和繪制。

2 點云存儲結構及建立

點云數據無論是來自原始掃描文件，還是由處理軟件導出，都是以順序方式存儲。這種文件內的順序并不一定對應于空間關系上的順序。點云的空間關系對于點云繪制十分重要。在三維視圖中，利用點云空間關系可以提高點云調度的效率，方便可視判斷和LOD設計。點云的空間關系通過點云存儲結構來表達，可以采用的存儲結構有規則存儲、八叉樹存儲和K-D樹存儲等。規則存儲實現簡單，但空間冗余大。K-D樹存儲主要有利于鄰域查找，但在隨視點變化的三維繪制和LOD設計中存在一定問題。八叉樹結構按照從整體到局部的形式逐層進行點云存儲，空間關系通過父子節點進行連接，無空間冗余，比較適合三維繪制。

點云的存儲結構分為內存結構和外存結構，如圖 1所示。內存結構是嚴格的八叉樹結構，節點node包含了該節點的外包盒坐標、點號集合 ptID、點號集合對應的點記錄指針pt，以及8個子節點指針next[8]。其中，點號集合對應的點記錄指針pt在建立八叉樹過程中不占用內存空間，而是在從外存讀入數據后進行繪制時占用內存。因此，在八叉樹建立過程中真正占用內存空間的主要是點號集合ptID。在32位操作系統中，一個long型點號僅占用4 Byte，而一個點坐標需要3個float型，占用12 Byte，因而在八叉樹中存儲點號可以節約內存空間。外存結構是將內存按節點逐一進行存儲，通過文件指針偏移量offset來標記當前節點在整個文件中的位置，有利于快速查找。當八叉樹內存結構建立完成后，采用廣度優先遞歸方式遍歷整個樹結構，逐節點寫到外存文件中。當繪制點云時，根據需要可以將特定的節點及其點云讀入內存節點中。

圖1 點云內外存存儲結構

根據設計好的存儲結構，對點云分 2個步驟進行八叉樹的建立，如圖2所示。

圖2 點云內外存存儲結構的建立

點云內存結構的建立過程如下：

(1)建立點云八叉樹結構。即通過反復計算和剖分點云外包盒，在內存中構造出從根節點到葉節點的完整樹結構。根節點就是全部點云，而葉節點的形成需要指定一個結束條件，本文將節點內的點數上限M作為判斷條件。節點內點數上限對于建樹過程和實時繪制都具有重要影響。

八叉樹結構的建立步驟如下：

1)初始化八叉樹根節點為當前節點。

2)如果當前節點為空，則返回。

3)如果當前節點內點數小于設定值，執行步驟7)。

4)計算當前點所在子節點的索引號。

5)如果索引子節點為空，則創建一個節點內存空間并進行初始化為當前節點。

6)如果當前節點的所有點都分配到子節點中，則清空當前節點中的點。

7)對步驟2)～步驟6)進行遞歸操作。

點云八叉樹結構建立的結果是從根節點開始逐層將點云的點號分配到葉節點，根節點和其他子節點都沒有存儲點號信息。這樣做的目的有2個：1)為了節約內存使用，即在步驟 6)中清空當前節點內的點，使得整個建樹過程的內存開銷僅用于八叉樹節點結構體，而點號如同水流一般從根節點開始逐層擴散流向其他節點。2)為了便于在步驟 2)中平衡節點內的點數。

(2)向八叉樹填充點云。采取深度優先遍歷，從葉節點開始，以一定的比例抽取當前節點中的點，將其填充到上層父節點內，同時刪除當前節點中的已抽取點。抽取比例控制著點云在不同節點內的分布，是進行LOD設計的重要依據。顯然，抽取比例越大，點云越密集地分布到上層節點中；反之，點云越密集地分布到下層節點中。為了平衡整個八叉樹的點云分布，使視點在任意位置的動態繪制中都產生相對均衡的內存和時間消耗，本文的抽取比例為0.5。

經過以上 2個步驟后，點云的內存結構建立完畢。根據設計好的外存文件結構，將點云按節點單元寫到外存文件中。

在建立樹結構的過程中，雖然點記錄指針pt沒有賦值，但計算外包盒是需要點坐標的。而在建立外存文件過程中，點坐標是要全部寫出的。因此，整個過程都要求訪問原始點云數據。有以下3種方式：

(1)全內存訪問。該方式需要充足的內存資源，優點是建樹速度快。但在面臨海量點云數據的情況下，目前的內存資源都是無法勝任的。

(2)全外存訪問。該方式可以完成建樹過程，且不需要考慮內存情況。但頻繁的I/O操作會大大降低建樹速度。

(3)部分內存訪問。該方式根據當前內存的使用情況，通過調用一部分內存空間來實現點云數據訪問。每次訪問量可以是固定大小，也可以根據內存情況設置一個變量來控制。本文中采取每次直接將外存中10000個點一次讀入內存進行訪問，訪問完畢后從內存刪除。顯然，只有采取這種方式，才能真正實現海量點云數據由隨機順序的外存文件轉換為具有空間關系的內存結構和外存文件，在轉換效率上也得到提高。

3 點云內外存調度繪制

繪制過程采取廣度優先方式遞歸遍歷八叉樹。每一個節點的繪制包括3個主要環節：(1)對節點進行判斷分析，考查該節點是否真正需要繪制，這樣有利于提高整個場景的繪制速度。(2)內外存調度數據，即根據節點判斷分析結果，對節點可見范圍外的節點進行刪除，在內存中釋放節點數據；對節點可見范圍內的空節點，從外存中讀取節點數據。這樣可以保證繪制過程的整體內存消耗處于相對穩定的水平。(3)繪制點云實體。對3個環節進行合理連接，構成了點云內外存調度繪制的流程，如圖3所示。

圖3 點云內外存調度繪制流程

節點是否在可見范圍內的判斷是節點判斷的重要內容。在有限的屏幕范圍內，只有部分節點外包盒是可見的，對這部分節點內的點云進行繪制足夠表達場景內容。在三維場景中，視點和節點的空間關系決定著可見性判斷。在OpenGL世界坐標下，設視點坐標的為(ex, ey, ez)，視線向量為(lx, ly, lz)，節點中心坐標為(nx, ny, nz)，則可見性判斷的條件有2個：

(1)視點到節點中心的距離條件：(2)視點到節點中心向量與視線向量的夾角條件：

由于是以節點中心代替了節點內的所有點云進行可見性判斷，計算量大大減少，這在動態繪制過程中十分重要。但以偏概全的判斷存在點云漏繪制的問題。本文的解決方法是對每一個節點都設置一個可視半徑，為N(N>1)倍于節點的外包盒的最大邊長。八叉樹中不同節點的外包盒大小不同，因而節點可視半徑隨節點位置變化。以根節點為例：

(1)如果視點在整個根節點外包盒內，此時滿足距離條件，無論是否滿足夾角條件，根節點中的點都應該繪制。

(2)如果視點在整個根節點外包盒外，但仍滿足距離條件時，根節點中心是否可見等同于其中點云是否可見。若根節點中心在視線前方，即cosθ＞0，繪制根節點；若根節點中心在視線后方，即cosθ＜0，不繪制根節點。

(3)如果不滿足距離條件，即整個節點離視點太遠，則不繪制根節點。

其他節點的判斷與根節點一致。之所以將可視半徑設置為N倍于節點的外包盒的最大邊長，是考慮到視點在整個節點外包盒之外時，在該可視半徑內點云仍可以顯示，可以以一定距離來觀察整個節點內的點云。本文中N=5。

4 實驗結果與分析

實驗分成2類進行：(1)全內存訪問的點云數據；(2)部分內存訪問的點云數據。全內存訪問的點云數據選自Leica HDS6000三維激光掃描儀獲取的某廣場點云，點個數為7655936。部分內存訪問的點云數據由該廣場點云按照1×1、2×2、3×3、4×4的矩陣排列方式平移復制得到，點個數分別為7655936、30623744、68903424、122494976。實驗的目的是分析在不同量級點云數據情況下，點云內外存結構的建立過程和繪制過程中的內存和時間消耗。

實驗是在Visual C++ 6.0編譯環境下結合OpenGL進行編程實現。主要硬件配置為 Inter Core2 P96002.66 GHz CPU，4 GB內存，300 GB機械硬盤，Nvidia Quadro NVS 160 MB顯卡。

對于全內存訪問的點云數據實驗，主要是研究節點內點數上限對于建立內外存結構和內外存調度繪制的影響。本文通過統計分析節點內點數的變化，考查內外存結構的建立和調度繪制過程中內存和時間消耗的情況。表 1是分別設置節點內點數為 100、1000、10000、100000、1000000的情況下，八叉樹節點總數、建立八叉樹結構耗時、生成外存文件耗時、總耗時、外存文件大小等各項指標的統計結果。隨著節點內點數的倍增，八叉樹節點總數呈幾何級數減少，從而顯著降低了建立八叉樹結構的耗時。相比較而言，建樹過程內存峰值和外存文件大小并沒有比較大的變化。圖4是節點內點數上限為10000和1000000情況下的點云繪制結果。節點內點數越多，點云繪制越密集。以上結果說明本文的建樹方法內外存占用較小，而建樹效率取決于節點內的點數上限。

表1 節點內的點數對內外存結構建立各項指標的影響

圖4 點云繪制結果(7655936點)

建樹過程的結果只是一方面，還要考慮繪制過程的情況。相對應的，在節點內點數上限為1000、10000、100000、1000000的情況下，分別統計了點云繪制中的內存使用和幀率變化情況，如圖5和圖6所示。設計視點在場景中的勻速漫游和旋轉構成視點路徑，視點起點為點云中心，沿點云 Z坐標軸移動到根節點外包盒外，然后繞點云中將視點旋轉90°，再沿視線方向穿越整個點云場景。通過對比可以發現，在節點內點數為10000的情況下，內存使用最小(最高不超過380 MB)，而繪制幀率最高(最高時接近70 fps)。這就意味著繪制過程中存在一個節點內點數上限的平衡點，使得整個內外存調度繪制過程達到最優。而在繪制最優的意義上，內外存結構建立的效率并不是最優。但綜合而言，以節點內的點數上限作為判斷條件，以一定的建樹時間消耗作為代價，可以保證內外存結構建立的內存平衡，可以使得內外存調度繪制達到最佳。

將全內存訪問實驗的結果作為參考，進行部分內存訪問的大規模點云數據實驗，將節點內點數上限設置為10000。實驗結果證明了本文方法以較低內存消耗建立從百萬級到億級等大規模點云數據的內外存結構。表 2列出了4種點云的各項統計指標。從表2中可以看出，當點云在較大數量級時，無論是內存消耗，還是時間消耗，都呈倍數增長。以線性回歸粗略估計，在4 GB的物理內存條件下，本文方法可以完成的內外存調度繪制的點云最大規模為762115166。此外，值得注意的是，同為7655936個點的點云，在全內存訪問中的建樹時間和內存峰值分別為8.3s、155376 KB，而在部分內存訪問中分別為107.8 s、58300 KB。造成時間消耗增大的原因是用于點查找的ptID在內存中沒有全部記錄，只能通過移動外存文件指針進行定位，增加了I/O操作，一定程度上降低了訪問效率。

圖5 點云繪制中的內存使用情況

圖6 點云繪制中的幀率變化情況

表2 大數據量點云點數對內外存結構建立各項指標的影響

圖7～圖9是點數為122494976個點的點云在不同視點時的顯示。點云在內外存調度技術的支持下，從整體到局部都能流暢繪制。為了定量分析，采取和全內存訪問實驗相似的視點路徑，統計內存使用和幀率變化，如圖 10和圖 11所示。內存使用在 405 MB～430 MB之間，幀率在10 fps～75 fps之間。內存消耗較大的繪制幀，其幀率都對應降低，這是當視點移動到場景細節中，較多節點都處于可見性的情況。而其他繪制幀的幀率都維持在較高水平，內存占用都在可用范圍內，內外存結構建立和動態繪制的整個過程都不會因內存不足而導致程序崩潰。

圖7 大規模點云在視點1的顯示

圖8 大規模點云在視點2的顯示

圖9 大規模點云在視點3的顯示

圖10 大規模點云繪制中的內存使用情況

圖11 大規模點云繪制中的幀率變化情況

5 結束語

本文提出一種部分內存訪問方式下的平衡八叉數存儲結構，設計點與節點距離和夾角約束可見性判決條件下的點云內外存數據調度方案。根據對不同規模實測點云的實驗，得出以下結論：

(1)本文提出的內外存結構設計和調度繪制技術可以在有限的內存資源條件下，以較小的內存消耗實現上億級規模點云從整體到局部的流暢繪制。部分內存訪問策略是提高內外存結構建立的有效方式。

(2)節點內點數上限作為葉節點的形成條件，可以很好地控制內外存結構建立和動態繪制過程中的內存和時間消耗。內外存調度繪制過程中內存和幀率的平衡點是確定該上限值的依據。

(3)隨節點變化的可視半徑能將點云的可見行判斷轉換為節點的可見性判斷，從而大大提高繪制效率。

加速計算、繪制速度與減小內存占用始終是一對矛盾，目前解決這一矛盾的手段是以犧牲一方面為代價來換取另一方面。本文以建樹時間為代價，換取了較小的內存消耗和較高的繪制效率，實現了大規模點云的快速瀏覽。在全外存訪問方式下，建樹過程雖沒有內存上限約束，但建樹效率極低。隨著固態硬盤及高速磁盤陣列的普及，基于全外存的海量點云數據管理、處理和繪制將成為提高效率的一種途徑。

[1]馬曉晨, 孔小利.基于深度八叉樹的三維數據場LOD可視化[J].計算機應用, 2010, 30(1): 47-49.

[2]張兵強, 張立民, 張建廷.面向GPU的批LOD地形實時繪制[J].中國圖象圖形學報, 2012, 17(4): 582-588.

[3]馮 莎, 盧選民, 陶旺林, 等.基于高斯金字塔的海量超大圖像快速漫游算法[J].計算機應用研究, 2012, 29(3): 1141-1142.

[4]李建勛, 沈 冰, 姜仁貴, 等.面向影像金字塔的四叉樹空間索引算法[J].計算機工程, 2011, 37(10): 11-13.

[5]李 捷, 鐘若飛, 趙文吉.車載激光點云海量數據的管理與快速顯示[J].系統仿真學報, 2008, 20(S1): 33-35.

[6]王宗躍, 馬洪超, 徐宏根, 等.多核 CPU 的海量點云并行kNN算法[J].測繪科學技術學報, 2010, 27(1): 46-49.

[7]路明月, 何永健.三維海量點云數據的組織與索引方法[J].地球信息科學, 2008, 10(2): 190-193.

[8]孟 放, 查紅彬.基于LOD控制與內外存調度的大型三維點云數據繪制[J].計算機輔助設計與圖形學學報, 2006,18(1): 1-7.

[9]Wand M, Berner A, Bokeloh M, et al.Processing and Interactive Editing of Huge Point Clouds from 3D Scanners[J].Computers & Graphics, 2008, 32(2): 204-220.

[10]Pajarola R.Stream-processing Points[C]//Proc.of Conference on Visualization.Minneapolis, USA: IEEE Computer Society,2005.

[11]Leica Geosystems HDS, LLC.HDS Training Manual[EB/OL].(2006-01-01).http://hds.leica-geosystems.com/en/Downloads-Support-Downloads_27049.htm.

[12]InnovMetric Software Inc..PolyWorks Reference Guide Version 10.0 for Windows[EB/OL].(2007-01-01).http://www.polyworks.com.cn/3D-scanners/home.aspx.

[13]Wand M, Berner A, Bokeloh M, et al.The XGRT System[EB/OL].(2007-01-01).http://www.gris.uni-tuebingen.de/xgrt.