基于二進制空間分區樹的井下巷道相交建模方法

王麗麗

（1.中煤科工集團常州研究院有限公司，常州 213000；2.天地（常州）自動化股份有限公司，常州 213000）

目前基于WebGL 的三維礦山巷道可視化系統絕大多數采用在客戶端完成數據采集、相交處理算法和建模成圖等過程，然后將大量成圖模型通過Object、JSON、GLTF 等主流模型文件格式導出，并在web 服務器端同步加載和渲染等過程以實現三維可視化[1-3]。這種方式實現三維可視化的場景模型其交互能力較弱，既無法做到參數化的動態建模和渲染過程，更不具備模型內部對象的操控和交互能力；而且系統在配置和維護方面，完全依賴于客戶端的建模成圖服務應用，需要比較專業的繪圖和維護人員完成中間過程才能應用到Web 服務器端，不屬于真正意義上的基于WebGL 的應用，而僅僅是基于WebGL 的模型渲染系統；要實現模型內部對象的操控和交互，就需要對模型按照細分粒度分類分割成較多的模型對象，增加了系統的建模和維護復雜度。對于井下巷道等大場景的系統，經過成圖后輸出的模型文件，一方面由于數量極大，另一方面由于井下水泵房、地面工廠等場景模型復雜，文件大小超1 G 以上，系統模型文件加載過程存在等待時間較長且極易阻塞情況，導致卡頓和交互體驗不佳等問題。為此，提出了基于二進制空間分區樹的井下巷道相交建模方法，構建礦井巷道虛擬環境在線建模和繪制渲染系統，可根據巷道拓撲參數動態建立巷道模型，避免了外部成圖和模型文件輸出的中間過程，可對模型內部的對象使用搜索、定位等方法實現更高要求的操控交互要求，解決了模型內部對象難以交互和操控的問題；并以此為基礎，提出一種基于web worker 多線程的大規模場景模型實時建模和加載方法，實施場景管理與建模分離策略，有效降低三維巷道系統的維護復雜度，避免因頂點數量和貼圖材質多等超1 G 大場景模型的建模和加載時間過長，導致用戶卡頓和交互體驗不佳等問題，提升系統場景管理和實時漫游等功能的性能。

1 巷道相交建模

1.1 二進制空間分叉樹（BSP）

二進制空間分叉樹（Binary Space Partitioning）是一種使用超平面遞歸劃分空間到凸集的一種方法。使用該方法劃分空間可以得到表示空間中對象的一個樹形數據結構。這個樹形數據結構被叫做BSP樹[4]。使用二進制空間劃分（BSP）來組織場景中的對象，可以根據觀察者的位置，快速地按照從前到后的順序進行場景中對象地訪問。在計算機輔助設計中，它被用來進行實體幾何的構造。在機器人、3D 游戲、光線追蹤中，它被用來進行碰撞檢測。由于BSP 的特性，它常常被用來處理復雜的空間場景[5-6]。為此，采用BSP 樹來對巷道模型進行實體幾何的構造。

1.2 巷道截面及巷道繪制

對井下巷道的三維繪制采用巷道截面和路徑掃描拉伸的方法實現。以半圓弧形截面為例，弧形巷道截面如圖1，圖1 中關鍵點坐標見表1。根據巷道截面及路徑繪制巷道如圖2，根據3D 直線繪制的巷道如圖3，根據3D 曲線繪制的巷道如圖4。

圖1 弧形巷道截面Fig.1 Curved roadway section

表1 關鍵點坐標Table 1 Key point coordinates

選取2 個空間點O 和O’，以O 和O’為原點，根據巷道的高h、寬w 以及巷道壁厚度t 為參數值，通過二維坐標到三維坐標的變換，以及平移、旋轉角度等矩陣變換，實現繪制出三維系統中的2 個巷道截面；2 個巷道截面中心點O 和O’連成的1 條3D直線，沿著這條直線的路徑，通過掃描拉伸的方式繪制成一段直線巷道（圖2 和圖3），而這段巷道的中心線也就是由這2 個空間點連成的1 條直線，這樣繪制的巷道是直線巷道。井下巷道系統錯綜復雜，并非都是直線巷道，同樣存在曲線延伸的巷道，這類巷道均采用貝塞爾曲線與Catmull-Rom 曲線插值算法從一系列點創建平滑的3D 曲線，再使用上文中類似的方法通過沿曲線路徑掃描拉伸繪制成蜿蜒的曲線巷道（圖4）。

圖2 根據巷道截面及路徑繪制巷道Fig.2 A roadway drawn according to the roadway section and path

圖3 根據3D 直線繪制的巷道Fig.3 A roadway drawn according to 3D straight lines

圖4 根據3D 曲線繪制的巷道Fig.4 A roadway drawn according to 3D curve

根據地測測繪采集的已知巷道空間點坐標及其拓撲關系等參數，通過上述方法，繪制出的基于WebGL 的三維井下巷道系統如圖5。

圖5 基于WebGL 的三維井下巷道系統Fig.5 Three-dimensional underground roadway system based on WebGL

1.3 巷道相交處理建模

井下巷道系統錯綜復雜，存在巷道與巷道之間相連接與相交的問題，通過前面方法建立的三維井下巷道，由于沒有處理巷道與巷道之間的相交等問題，會出現巷道互相相交疊加的情況，需要對巷道之間相互連接的地方進行巷道的相交算法處理，為此，采用了二進制空間分叉樹BSP 來對巷道相交進行實體幾何的構造和建模。巷道相交處理后俯視圖如圖6，巷道相交處理后巷道內部結構圖如圖7，巷道相交處理后巷道內部透視圖如圖8。

圖6 巷道相交處理后俯視圖Fig.6 Top view after roadway intersection processing

圖7 巷道相交處理后巷道內部結構圖Fig.7 Internal structure of roadway after roadway intersection processing

圖8 巷道相交處理后巷道內部透視圖Fig.8 Inside perspective view of roadway after roadway intersection processing

找出2 個物體間的分隔面的方法適合于判斷2個物體是否相交。如果分隔面存在，就沒有發生碰撞，因此遞歸地遍歷二叉樹并判斷分割面是否和包圍球或包圍盒相交，并還可以通過檢測每一個物體的多邊形來提高精確度[7]。進行這種檢測最簡單的方法是測試看看物體的所有部分是否都在分割面的一側，并用笛卡爾平面等式ax+by+cz+d=0 去判斷點（x，y，z）位于平面的哪一側，如果滿足等式，點在平面上；如果ax+by+cz+d＞0 那么點在平面的正面；如果ax+by+cz+d＜0 點在平面的背面[8]。在碰撞沒發生的時候有1 個重要的事情需要注意，就是1 個物體（或它的包圍盒）必須在分割面的正面或背面。如果在平面的正面和背面都有頂點，說明物體與這個平面相交。利用BSP 數據結構及其特性，可以很好地解決此類問題。

構造出符合實際情況的巷道拓撲相交，需要依據巷道的拓撲關系通過上文中描述的方法繪制的單段巷道和單段巷道之間，采用二進制空間分叉樹BSP 對相交的巷道模型進行并集、差集等布爾運算，構造出巷道相交部分的實體幾何，以實現巷道相交處理，并使用遞歸算法，依次對整個繪制的巷道實施相交處理、材質貼圖和渲染等建模過程。完成相交、材質貼圖和渲染的巷道內部視角圖如圖9。

雖然通過上述方法，系統可根據巷道拓撲參數動態建立巷道模型（圖9），但在實際礦井巷道大場景中，巷道模型擁有的頂點數、三角面以萬為單位計數，整個巷道相交建模的過程有著極大的計算量。這種在線建模耗費時間的復雜運算過程既依賴服務器電腦的CPU 性能，更需要服務器具有較高的GPU 渲染性能，這將給系統硬件帶來極大的限制和投入成本。除此之外，耗費時間的復雜運算極易阻塞主UI 線程，給用戶造成卡頓等較差的用戶體驗，上述問題亟需改善。

圖9 完成相交、材質貼圖和渲染的巷道內部視角圖Fig.9 Interior view of roadway after intersection,texture mapping and rendering

2 Web Worker 多線程非阻塞策略

在瀏覽器中JavaScript 的執行是單線程的，頁面上的計算在執行時會阻塞瀏覽器的響應，非常影響用戶的體驗效果。雖然Ajax 技術的應用使頁面在等待服務器響應的過程中不再發生阻塞，但還是沒有改變其單線程運行的本質，依然不適宜把耗費時間的復雜運算放在頁面上執行[9]。在需要等待計算結果或者大型文件加載的過程中，仍然容易出現阻塞的情況，為此提出了場景管理與建模過程分離的策略解決上述問題。采用Web Worker 多線程和分布式計算來實現分離策略。Web Worker 是內建在瀏覽器中的輕量級線程，允許把長時間運行和密集計算型的任務放在后臺執行而不會阻塞UI 線程[10-12]。使用分布式計算執行相交建模計算過程不會阻塞事件循環，使在線建模和渲染系統應用運行更加流暢。

將繪制的巷道模型擁有的就數以萬計的頂點和頂點，三角面和三角面之間的并集、差集等相交計算的過程，通過WebWorker 多線程，在后臺采用模型文件的切片和分布式計算，實現主UI 線程與復雜計算線程的分離，將WebGL 計算和渲染效果依賴于電腦的顯卡、內存和GPU 性能的因素降至最低，從而極大減輕了因計算量大而造成UI 阻塞而出現的界面渲染卡頓、掉幀的情況，并且更大程度地利用了分布式的性能特點[13-14]，解決相交建模過程中的因硬件條件有限的大算力計算等瓶頸問題。Web Worker 多線程策略如圖10。

圖10 Web Worker 多線程策略Fig.10 Web Worker multithreading strategy

Worker 線程之間不會共享作用域和資源，線程間的通信采用基于事件監聽機制的消息隊列。

服務器模塊負責客戶端、計算模塊等發送的數據并進行處理，承擔著JSON 格式模型文件切片、任務分解和分發、計算節點監控、計算結果的儲存和匯總等分布式調度功能。計算節點作為守護程序監控計算模塊程序實時狀態，并且負責傳遞計算任務給計算模塊。

計算模塊負責處理計算任務，調用相應動態鏈接庫或算法庫完成計算過程，計算完畢后傳輸數據給計算節點。

客戶端模塊是用戶與系統應用的交互，當用戶進行UI 交互和數據查詢時，服務器處理數據并返回給客戶端，客戶端接收數據并顯示。

3 時效性能測試

本次巷道建模Web Worker 分布式計算過程的性能測試采用4 臺虛擬機在網絡帶寬100 M 環境下進行測試。虛擬機單臺配置為單核，內存2 G，WIN10 操作系統。測試結果如下，在不進行分布式處理計算耗時為1 082 s，計算過程耗時很長嚴重阻塞界面UI。為了形成對比，將計算任務分配給不同數量的計算節點下進行測試。通過計算耗時分析整個建模分布式計算過程的計算效率，并以節點個數為1 的計算時間為基準計算時間。計算效率=理想計算消耗時間/實際計算時間=基準計算時間/（實際計算時間×計算節點個數），理想計算消耗時間=基準計算時間/計算節點個數。計算耗時折線圖如圖11，計算效率拆線圖如圖12。

圖11 計算耗時折線圖Fig.11 Time-consuming line chart

圖12 計算效率折線圖Fig.12 Efficiency line chart

由圖11 和圖12 可知：與不采用分布式計算相比，采用WebWorker 分布式計算可以極大的減少相交建模計算過程的計算耗時；與此同時，隨著計算節點數量的增加，計算耗時有明顯的降低，而相同計算量的計算效率也會有一定的提升。

4 結 語

提出了基于二進制空間分叉樹構造巷道實體幾何實現巷道相交建模的方法和采用了WebWorker多線程技術，實施場景管理與建模分離的策略，實現了基于WebGL 礦井巷道虛擬環境的在線巷道建模和渲染系統。該系統根據參數動態建立巷道模型，有效地降低三維巷道系統在線建模的復雜度和維護難度，解決了模型內對象難以交互和操控的問題；場景管理與建模分離的策略，使建模過程明顯高效且縮短了大型場景模型的加載時間，緩解了用戶界面卡頓和操作不友好等阻塞問題，提升了場景交互和實時漫游的效果和性能。