海量變電站點云實時渲染方法＊

楊雪飛，楊紹遠，向東偉，楊成城

（1.中國南方電網超高壓輸電公司柳州局，廣西 柳州 545006；2.武漢匯卓航科技有限公司，湖北 武漢 430070）

1 引言

隨著電力行業的快速發展，電網規模急速擴大，傳統的變電站安全運維手段需要消耗大量財力、人力去采集各金具實時溫度、避雷針偏移等數據，但往往精度很低，增加了變電站事故防范和變電站檢修的難度[1]。采用無人機機載激光掃描系統、可見光相機后處理三維重建等手段對變電站進行三維測量，幫助電網相關部門在最短時間內采集到變電站的三維信息，為變電站危險點智能檢測、運行情況評估等提供決策依據[2]。伴隨著變電站點云數據后處理技術在電力巡線中得到了廣泛的應用，而如何在有限的計算機內存容量下對海量點云數據進行高效組織管理并實時渲染顯示等處理已經成為阻礙變電站維護應用進一步發展的突出問題。

近年來，已經有許多國內外學者對LiDAR 點云三維可視化進行深入研究，形成了各具特色的方法案例。閆利等人[3]提出了車載LiDAR 海量點云數據管理與可視化方法，基于八叉樹結構構建LOD 索引，采用多線程動態調度技術實現基于視點的海量點云渲染與漫游。王磊等人[4]提出了基于改進的八叉樹索引與分層渲染的海量激光點云可視化研究，采用三維點云分塊，建立八叉樹索引數據文件，根據屏幕顯示范圍與視角變化實時讀取釋放點云索引數據。石祖旭等人[5]提出了基于樹形結構網格矢量量化的點云渲染算法，采用八叉樹構建索引，支持在線實時壓縮渲染。吳建軍等人[6]提出了電力巡線直升機激光掃描數據的高效組織與顯示，通過并行化閾值分割構建八叉樹結構，采用視點變化與分頁數據庫的內外存調度方法。李凍[7]提出了基于OSG的LAS 文件三維渲染方法，采用四叉樹存儲結構和內外存調度的方法，生成多個子節點的Las 文件，同時對多個文件讀寫消耗大量時間。以上相關研究的激光點云數據場景主要是城市激光掃描點云數據，而變電站點云數據相比城鎮激光掃描點云數據，存在場景中地物復雜，平面X、Y軸方向上跨度大，豎直平面Z軸方向點云分布稀少且不均勻等問題，針對海量變電站點云數據進行組織管理以及實時渲染顯示需要考慮這些特點。雖然吳建軍等人[6]的研究對象為電力場景點云數據，但是其采用八叉樹數據結構來對點云數據進行組織與調度，為保證八叉樹數據結構的動態性以及平衡性，對電力場景點云數據進行額外預處理，延長了點云分塊時間。

針對以上情況，本文在前人研究的基礎上，提出一種適用于海量變電站點云數據的快速可視化和實時渲染的方法。采用四叉樹構建索引，結合OSG[8]三維引擎的PagedLOD 技術[9]根據不同視域分頁顯示，并結合GLSL 著色語言對點云實時渲染。本文主要通過以下幾點對其說明：①快速構建四叉樹結構的LOD[10]索引，利用文件內存映射解決海量數據存儲問題，簡化分塊算法、縮短構建索引時間；②自定義PPCD 插件，基于OSG 的PagedLOD 技術，設置不同視域顯示相應的細節層次，采用多線程實現實時調度和加載；③利用GLSL 著色語言[11]實現點云實時渲染、裁剪等處理。

2 基于四叉樹結構的LOD 索引快速構建

目前，索引樹主要包括K-D 樹[12]、四叉樹[13-15]、八叉樹[16]、R 樹[17]等，其中，R 樹具有較強的調節性和靈活性，相關學者提出了一系列的改進方法。其中如BECKMANN通過對R 樹算法研究改進提出R*樹[18]，R*樹的優越性主要體現在查找方式和節點操作的多樣性，但是R*樹相對R 樹構建索引所需要的時間過長，不適合海量點云數據處理。K-D 樹結構為一種二叉樹，特別之處是每一層都存在選擇子節點，通過每一層的節點遍歷尋找其子節點并顯示，但是在可視化分頁顯示中對節點剔除、顯示的計算會顯得十分復雜，不利于海量點云數據的實時渲染。與結構相對簡單的四叉樹和八叉樹相比，R 樹節點之間存在交集，容易導致數據存儲冗余，過多消耗計算機性能。相對于城市建筑物的點云數據，變電站點云數據分布不均勻，直接采用八叉樹數據結構會導致葉節點不平衡，構建效率低。而利用四叉樹對變電站點云數據進行劃分，僅需考慮平面內X、Y方向的坐標而直接忽略Z方向坐標，處理簡單且四叉樹構建效率較高。經上述分析，本文采用四叉樹數據結構來對變電站點云數據創建索引。

四叉樹索引是將地理空間遞歸劃分為不同層次樹的結構。將已知范圍的空間等分成四個相等的子空間，如此遞歸下去，直到樹的層次達到一定深度后停止分割，如圖1 所示，四叉樹的查詢子節點效率較高，能更好實現點的快速查詢。

圖1 四叉樹結構的索引樹結構

由于海量點云數據的數量以千萬甚至億級作為計量單位，若是分塊算法顯得冗余，則會導致構建索引時間過長，消耗內存過大。本文解析的點云數據文件采用LAS、LAZ格式存儲，其中包含點云坐標值、顏色信息、分類信息、強度信息等相關信息。由于原本存儲的點云屬性豐富，導致構建索引樹時會占用大量內存，需重新定義點云數據結構，構建的數據結構如圖2 所示，其中包含簡單的三維點位置信息pos_x、pos_y、pos_z，顏色信息 rgb_r、rgb_g、rgb_b，quadrant表示四叉樹最底層節點編號。

圖2 自定義單個點數據結構

點云數據如何快速按照四叉樹索引結構分塊是基于四叉樹結構的LOD 索引構建的關鍵點。若是分塊算法在運算中煩瑣、冗余，則會導致處理速度大大降低。本文本著將分塊算法極簡化，解析LAS、LAZ 文件過程中便將點云按照四叉樹結構分塊完成。

算法輸入：點云集合，四叉樹最大深度（樹高）為H。

算法輸出：點云按照grid_id從小到大排序好。

具體步驟如下：①讀取LAS、LAZ 文件的頭文件獲取外圍包圍盒大小（Xlong，Ylong）X軸方向上最小值xmin，Y軸方向上最小值ymin；②根據N=4（n-1）計算出網格數，得到X軸、Y軸方向上的網格數n，根據并根據grid_id=（grid_x-1）×n+grid_y計算每個點的grid_id；④最后按照每個點記錄的grid_id值從小到大使用快速排序法排序；⑤退出算法。

根據提前構建的四叉樹，按照grid_id值有序放在對應的節點位置上。通過對四叉樹由下到上的遍歷，并寫入LOD索引文件中。

父節點按照子節點數據進行點云抽稀如圖3 所示，初始設置索引樹為4 層。第四層中5、7、6、6 分別代表此節點中所含有的將原始點云根據順序編碼值分塊之后的點云數量。將5、7、6、6 點云集構成一個集合，根據抽稀比例1∶4，得到父節點包含的點云數為8 個，以此類推遍歷完四叉樹。

圖3 父節點按照子節點數據進行點云抽稀

本文重點研究的是海量變電站點云的顯示及渲染，其數據規模通常遠大于千萬數量級，若僅僅依靠計算機內存來存儲構建索引樹過程中生成的臨時數據，會面臨因計算機內存不足而導致生成索引失敗的問題。若是采用邱炎等人[19]提出的基于外存八叉樹的三維激光點云實時渲染技術，將超過計算機內存容量的點云數據通過外部存儲器構建索引結構，則導致計算機一直對多個文件進行讀寫，嚴重影響構建索引樹的效率。由于上述原因，本文采用的文件內存映射[20]方法，將需存儲在物理內存的數據映射到特定地址范圍，然后通過指針訪問內存映射文件里的內容。一旦需讀取的LAS 文件被映射，就能訪問它，就像整個LAS 數據已經加載內存一樣，從而不需要對文件執行I/O 操作，這對LAS 文件解析并存儲效率較高，提高構建索引樹生成LOD 索引文件速率。

3 基于PPCD 插件的點云動態管理

基于OSG 和OpenGL 技術對點云可視化進行研究，采用C++平臺的程序接口（Application Pro-gramming Interface，API），能夠更加方便、快速地創建高性能、跨平臺的交互式圖形程序[21]。OSG 自帶插件（osgdb_las）支持對LAS 點云文件解析并顯示，但是osgdb_las 插件將點云數據一次性讀取并放入物理內存，若是點云數據過大，會導致點云交互卡頓甚是死機，因此osgdb_las 插件不能滿足大規模點云渲染的需求。

PPCD 插件需要滿足OSG 插件工作機制，如圖4 所示，嘗試使用osgDB 讀取或寫入文件時，根據文件的后綴名查找OSG 中已注冊的插件，若是存在成功執行I/O 操作，返回相應的數據；若是不存在則不能成功執行I/O 操作，返回失敗信息。

圖4 OSG 插件機制圖

PPCD 插件根據四叉樹模型，由上往下遍歷節點信息并顯示，在OSG 的場景樹管理結構中，專門提供了場景結點osg::PagedLOD 技術來展示不同的細節層次模型。其中，osg::PagedLOD 結點作為父結點，每個子節點作為單個細節層次展現，通過設置不同的視域，在不同的視域內顯示相應的細節層次，加載過程中有單獨的線程負責實時調度和加載，以此決定對物體渲染的資源分配與資源刪除，降低非重要物體模型的面數和細節度展示，獲得高效率的渲染運算。OsgDB::DatabasePager 負責執行場景動態調度工作，通過DatabasePager::registerPagedLOD（node）注冊 PagedLOD 節點，DatabasePager 實時遍歷場景中節點設置視域范圍，計算節點與窗口視域距離，將長期處于不在設置視域范圍內的節點認為不會立即顯現的場景元素，通過數據線程刪除。利用osg::Group、osg::Node、osg::Geometry、osgDB 等相關類實現顯示。其核心代碼如下。

osg::Geode*geode=new osg::Geode;

osg::Geometry*geometry=new osg::Geometry;

osg::Vec3Array*vertices=new osg::Vec3Array;

osg::Vec4ubArray*colours=new osg::Vec4ubArray;

for(int i=0;i

vertices->push_back(osg::Vec3(points[i].x, points[i].y,points[i].z));

colours->push_back(osg::Vec4ub(points[i].r, points[i].g,points[i].b,a));

}

geode->addDrawable(geometry);

osg::PagedLOD*plod=new osg::PagedLOD();

plod->addChild(geode);

plod->setRange(0,0,radius);

plod->setCenter(plod->getBound().center());

其中，points 為四叉樹節點點云集合，(0，radius)為視域范圍。

4 基于GLSL 的點云著色及剪裁

三維渲染引擎為了實現三維場景圖像的結構管理和繪制，包含至少兩個層次：構建層和交互層，前者提供三維空間中設計和完成需要的工具集，或者從外部加載復雜模型的數據接口；后者提供對三維空間及所含模型的裝配、渲染、優化和控制功能。通過場景視圖、圖形設備、渲染器、攝像機等聯合控制場景節點，詳細關系如圖5 所示。

圖5 窗口、攝像機、渲染器、場景圖等之間的關系

基于PPCD 插件的讀取點云顯示完成后，為了最大程度地保證點云數據實時渲染、交互流暢性。本文點云數據渲染采用GLSL 著色語言，其中點云實時渲染操作包括：點云裁剪、分類渲染、高程渲染。點云裁剪應用視錐體裁剪技術，設置顯示范圍區域，使用深度優先的遞歸遍歷對四叉樹節點進行遍歷，判斷節點是否在視錐體范圍內，如果在視錐體內則計算節點里的點云數據是否在視錐體范圍內。分類渲染主要是根據讀取點云屬性類別信息，根據不同的類別信息設置不同RGB 值。高程渲染主要是根據讀取點云Z軸方向上最大值與最小值，依次求取各點的高程值在最大值與最小值所在區間的比率，根據比率修改RGB 值，達到自上而下顏色漸變過程，具體思路流程如圖6 所示，最終加入到渲染隊列中完成渲染，渲染效果如圖7 所示。

5 實驗與分析

為了驗證本文海量點云組織管理方法能夠高效支持點云實時渲染、快速處理。基于Visual Studio2017 采用C++編程實現索引樹構建、文件內存映射、osg::PagedLOD 節點動態加載、點云實時渲染。主要硬件配置：CPU 為Inter CoreI7、32 GB 內存、顯卡為Nvidia GeForce GTX1080。

本文采用廣西壯族自治區柳州市某變電站的點云模型數據，總文件大小為17.1 GB，通過裁剪方式將LAS 文件分成665 MB、1.2 GB、3.21 GB、7.3 GB 等不同大小LAS 文件。將LAS 文件導入市面上流行的點云顯示軟件，如：CloudCompare、Lidar360、Displaz。通過對幾種軟件的海量點云顯示所需要進行比較，結果如表1 所示。

圖6 高程渲染-計算單個點RGB 值思路流程

圖7 高程、分類渲染，裁剪效果圖

由表1 分析得到當LAS 文件越來越大時，每個主流軟件構建索引樹并顯示所需要的時間呈直線上升。其中表1 中Lidar360、PPCD 插件顯示點云速度所需要時間是因為第一次打開該LAS 文件，需要構建索引書生成LOD 索引文件，之后打開該LAS 文件所需要顯示時間幾乎可以忽略不計。

基于OSG 三維引擎搭建的可視化平臺PowerModel，將17.1 G 的LAS 文件生成相應的LOD 索引文件，導入可視化平臺。由于該文件為激光數據，為了展示更好的效果，初始設置渲染為高程渲染，渲染效果如圖8 所示。

表1 各種三維平臺顯示點云速度

圖8 點云模型在三維平臺顯示

PowerModel 程序初始化占用內存130 MB；圖8（a）表示在PowerModel 中遠看點云數據模型時程序占用內存1.7 GB；圖8（b）表示在PowerModel 中近看點云數據模型時程序占用內存630.2 MB。從上面數據可以看出，當點云數據細節層次展示時不會加重計算機內存容量負擔，反而遠看點云數據模型全貌更消耗計算機內存容量。同時PowerModel 支持對點云數據的放大縮小、漫游、旋轉和全圖等操作。

6 結束語

為了滿足海量變電站點云數據的快速調度與后處理需求，本文提出一種支持海量點云快速構建四叉樹結構的LOD索引的方法，并在該方法上實現了高效的海量變電站點云數據的實時渲染。通過相關實驗表明，本文研究技術能夠支持大范圍海量變電站點云數據的動態調度顯示、交互操作等過程，支持對點云的分類、裁剪等相關后處理，具有一定的應用價值。海量點云數據的包圍盒大小與四叉樹最優深度的關系、海量點云生成LOD 索引文件速率是后續研究的重點，這些研究有望進一步提高變電站點云數據分析、處理系統的自動化程度、點云交互流暢性。