基于BSP空間分割法的核級管道三維碰撞檢查方法研究

吳啟濤 黃捷 孫冠宇 劉雨晨

摘 要

在PDMS平臺設計了基于核級管道的碰撞檢查模塊，同時兼顧速度與精度的需求。本文分析了常見的碰撞檢查方法，設計了一種新的碰撞檢查流程，分別研究了BSP空間分割法及包圍盒算法的優勢，將其應用于新的檢查流程中，將碰撞檢查模塊中，采用并行包圍盒法檢查，得到碰撞檢查結果。

關鍵詞

碰撞檢查;BSP空間分割法;包圍盒算法;并行檢查

中圖分類號： TP391.41 ? ? ? ? ? ? ? ?文獻標識碼： A

DOI：10.19694/j.cnki.issn2095-2457 . 2020 . 17 . 69

Abstract

The collision check module based on nuclear-grade pipeline is designed on PDMS platform. At the same time， the requirements of speed and precision are considered. This paper analyzes the common collision inspection methods， designs a new collision inspection process， and studies the BSP spatial segmentation method. The advantage of the bounding box algorithm is applied to the new inspection process. In the collision check module， the parallel bounding box method is used to check the collision check result keywords： Collision check BSP spatial segmentation method bounding box algorithm parallel check.

Key words

Collision check; BSP spatial segmentation method; Bounding box algorithm; Parallel checking

0 前言

三維數字化設計已經在工程領域全面普及，PDMS等三維設計軟件成為管道設計中不可或缺的工具。伴隨著計算機硬件的迅猛發展，圖形處理性能不斷提升，基于三維空間的碰撞檢測算法的研究也越來越深入。在實際工程應用中，模型碰撞檢查工作需要設計校核人員進行大量煩瑣的工作。由于核級管道三維設計的嚴謹性，而且傳統的三維碰撞檢查流程不能同時兼顧速度與精度。通過研究，將空間分割法應用于碰撞檢查流程能將有效分配計算資源，該方法首先對三維模型分類，再根據分類結果進行并行包圍盒法碰撞檢查，同時兼顧了設計工作的精度與速度。在實際設計工作中，是否能夠快速地得到準確結果，將直接影響到設計人員工作進度。

1 算法基礎及比較

1.1 BSP二叉空間分割法

BSP二叉空間分割法，是一種自適應空間剖分法，它的基本思想是基于任何平面都可以將空間分割成兩個半空間這樣一個事實。在運行時使用一個預先計算好的樹來得到多邊形從后向前的列表。所有位于這個平面一側的點定義一個半空間，位于另一側的點定義為另一個半空間。在任何半空間中有一個平面，會進一步將此半空間分割為更小的兩個子空間。使用多邊形列表將這一過程一直進行下去，將子空間分割得越來越小，直到構造成一個二叉樹。在這個樹中，進行分割的多邊形被存儲在樹的節點，所有位于子空間中的多邊形都在相應的子樹上，這一規則適用于樹中每一個節點。選擇一個平面投影，將多邊形映射為直線段，如圖1所示，從多邊形A開始構造一個BSP樹。

通過A平面的分割得到BSP樹，如圖2所示。

BSP二叉空間分割法不但在多邊形剪切方面表現出色，而且還能有效地運用world-object式的碰撞檢測。BSP樹的遍歷是使用BSP的一個基本技術。碰撞檢測本質上減少了樹的遍歷或搜索。它能在早期排除大量的多邊形，所以在最后我們僅僅是對少數面進行碰撞檢測。

1.2 層次包圍盒法

碰撞檢查中普遍需用到包圍盒法進行計算。包圍盒樹構建的方法需要根據實際需求進行選取。根據包圍盒類型的不同，可以分為AABB層次包圍盒、k-dop層次樹等算法、Sphere包圍球、OBB層次包圍盒等算法。

包圍球Sphere：基本思想是根據目標的坐標計算出球心c，由此確定半徑r，得到一個最小的球體可以包住目標。

沿坐標軸的包圍盒AABB：指包含對象且邊平行于坐標軸的最小長方體。當兩個AABB包圍盒在三個坐標軸上的投影區間同時重疊時，則相交。

方向包圍盒OBB：指包含對象且相對于坐標軸方向任意的最小長方體。包圍盒的方向的選擇與效率息息相關。

k-dop包圍盒：包含當前對象為要求。自身所有面的法向量均來自一個固定的方向集合的凸包，固定方向集的選取對包圍盒效率有著直接影響。

2 碰撞檢查流程設計

核級管道碰撞檢查要求精確度高響應快，再根據碰撞檢查算法各自的性能特點，現設計一種新的碰撞檢查流程。

該流程利用BSP空間分割法將待檢查模型進行分割，將碰撞模型分為兩類，其中不需要高精度檢查的模型用速度較快的AABB包圍盒進行碰撞檢查，需要細致檢查的檢查模型用K-dop包圍盒進行碰撞檢查。既滿足時間復雜度的要求，也滿足核級管道精度高的特點。

3 仿真與結果分析

3.1 實驗設計

基于PDMS平臺，開發針對管道的碰撞檢查功能模塊，將新設計的碰撞檢查流程植入功能模塊中。主要實現管道模型在布置過程中實時的完成與周圍建筑物的碰撞檢查，包括管道、支吊架、設備、土建等9個級別的檢查。

用實例驗證新碰撞檢查流程的性能優勢。選擇實際工程中6根管道作為實驗對象，對比單一的包圍盒算法與新碰撞檢查流程，通過耗時及碰撞結果對比得到新設計流程的優勢。

3.2 結果分析

6根管道經過新的碰撞檢查流程，同時對比精度最高的k-dop包圍盒及速度最快的Sphere包圍盒，時間對比結果如圖4所示。

通過三種碰撞檢查算法用時對比，新的碰撞檢查算法用時趨近于構造代價最小的Sphere包圍盒法，遠遠小于k-dop包圍盒法。接下來對比碰撞檢查效果，對比結果如圖5所示。

通過碰撞檢查效果對比，新碰撞檢查流程接近于k-dop包圍盒算法，再通過時間對比的結果分析，新碰撞檢查流程的效率要優于現有單一的碰撞檢查算法，并行包圍盒算法發揮了作用，減輕了設計人員工作的時間成本。

4 結束語

針對管道設計中的碰撞檢查問題，本文通過對目標模型進行BSP分割預處理，將模型拆分為速度和效率兩類模型，用K-dop和AABB包圍盒并行檢查。通過新的碰撞檢查算法流程，解決了碰撞檢查效率低等問題，隨著模型體量的增加，新的碰撞檢查算法的效率優勢愈發明顯。本文通過實驗證明了算法的可行性和有效性，說明新的碰撞檢查算法應用于核級管道設計效果顯著。

參考文獻

[1]黃曉康.基于BSP和四叉樹的場景管理研究[D].南京理工大學，2008.

[2]喬云婷，張弘.基于BSP樹的三維場景渲染方法研究[J].渭南師范學院學報，2014，29（15）：86-89.

[3]靳雁霞，秦志鵬，李照.融合R-Sphere包圍球的變形體碰撞檢測算法[J].計算機工程與設計，2017，38（01）：92-96.

[4]鄧峻生，毛世峰，劉旭峰，葉民友.基于AABB樹的聚變堆形變部件碰撞檢測算法[J].計算機系統應用，2018，27（11）：161-167.

[5]劉超，蔣夏軍，施慧彬.基于OBB包圍盒碰撞檢測算法的改進[J].計算機技術與發展，2018，28（06）：43-48.

[6]Fang Zhigang， Jiang Jianxun， Xu Jie. Efficient Collision Detection Using a Dual K-DOP-Sphere Bounding Volume Hierarchy[P]. Information Technology and Applications （IFITA）， 2010 International Forum on，2010.

[7]鄭延斌，郭凌云，劉晶晶.基于混合包圍盒的碰撞檢測優化算法[J].計算機工程與科學，2013，35（04）：87-92.