基于二進(jìn)制空間分區(qū)樹的井下巷道相交建模方法

王麗麗

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

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

1 巷道相交建模

1.1 二進(jìn)制空間分叉樹（BSP）

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

1.2 巷道截面及巷道繪制

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

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

表1 關(guān)鍵點坐標(biāo)Table 1 Key point coordinates

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

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

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

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

根據(jù)地測測繪采集的已知巷道空間點坐標(biāo)及其拓?fù)潢P(guān)系等參數(shù)，通過上述方法，繪制出的基于WebGL 的三維井下巷道系統(tǒng)如圖5。

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

1.3 巷道相交處理建模

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

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

圖7 巷道相交處理后巷道內(nèi)部結(jié)構(gòu)圖Fig.7 Internal structure of roadway after roadway intersection processing

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

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

構(gòu)造出符合實際情況的巷道拓?fù)湎嘟唬枰罁?jù)巷道的拓?fù)潢P(guān)系通過上文中描述的方法繪制的單段巷道和單段巷道之間，采用二進(jìn)制空間分叉樹BSP 對相交的巷道模型進(jìn)行并集、差集等布爾運算，構(gòu)造出巷道相交部分的實體幾何，以實現(xiàn)巷道相交處理，并使用遞歸算法，依次對整個繪制的巷道實施相交處理、材質(zhì)貼圖和渲染等建模過程。完成相交、材質(zhì)貼圖和渲染的巷道內(nèi)部視角圖如圖9。

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

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

2 Web Worker 多線程非阻塞策略

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

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

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

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

服務(wù)器模塊負(fù)責(zé)客戶端、計算模塊等發(fā)送的數(shù)據(jù)并進(jìn)行處理，承擔(dān)著JSON 格式模型文件切片、任務(wù)分解和分發(fā)、計算節(jié)點監(jiān)控、計算結(jié)果的儲存和匯總等分布式調(diào)度功能。計算節(jié)點作為守護(hù)程序監(jiān)控計算模塊程序?qū)崟r狀態(tài)，并且負(fù)責(zé)傳遞計算任務(wù)給計算模塊。

計算模塊負(fù)責(zé)處理計算任務(wù)，調(diào)用相應(yīng)動態(tài)鏈接庫或算法庫完成計算過程，計算完畢后傳輸數(shù)據(jù)給計算節(jié)點。

客戶端模塊是用戶與系統(tǒng)應(yīng)用的交互，當(dāng)用戶進(jìn)行UI 交互和數(shù)據(jù)查詢時，服務(wù)器處理數(shù)據(jù)并返回給客戶端，客戶端接收數(shù)據(jù)并顯示。

3 時效性能測試

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

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

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

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

4 結(jié) 語

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