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

吳啟濤 黃捷 孫冠宇 劉雨晨

摘 要

在PDMS平臺(tái)設(shè)計(jì)了基于核級(jí)管道的碰撞檢查模塊，同時(shí)兼顧速度與精度的需求。本文分析了常見(jiàn)的碰撞檢查方法，設(shè)計(jì)了一種新的碰撞檢查流程，分別研究了BSP空間分割法及包圍盒算法的優(yōu)勢(shì)，將其應(yīng)用于新的檢查流程中，將碰撞檢查模塊中，采用并行包圍盒法檢查，得到碰撞檢查結(jié)果。

關(guān)鍵詞

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

中圖分類號(hào)： TP391.41 ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： 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 前言

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

1 算法基礎(chǔ)及比較

1.1 BSP二叉空間分割法

BSP二叉空間分割法，是一種自適應(yīng)空間剖分法，它的基本思想是基于任何平面都可以將空間分割成兩個(gè)半空間這樣一個(gè)事實(shí)。在運(yùn)行時(shí)使用一個(gè)預(yù)先計(jì)算好的樹(shù)來(lái)得到多邊形從后向前的列表。所有位于這個(gè)平面一側(cè)的點(diǎn)定義一個(gè)半空間，位于另一側(cè)的點(diǎn)定義為另一個(gè)半空間。在任何半空間中有一個(gè)平面，會(huì)進(jìn)一步將此半空間分割為更小的兩個(gè)子空間。使用多邊形列表將這一過(guò)程一直進(jìn)行下去，將子空間分割得越來(lái)越小，直到構(gòu)造成一個(gè)二叉樹(shù)。在這個(gè)樹(shù)中，進(jìn)行分割的多邊形被存儲(chǔ)在樹(shù)的節(jié)點(diǎn)，所有位于子空間中的多邊形都在相應(yīng)的子樹(shù)上，這一規(guī)則適用于樹(shù)中每一個(gè)節(jié)點(diǎn)。選擇一個(gè)平面投影，將多邊形映射為直線段，如圖1所示，從多邊形A開(kāi)始構(gòu)造一個(gè)BSP樹(shù)。

通過(guò)A平面的分割得到BSP樹(shù)，如圖2所示。

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

1.2 層次包圍盒法

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

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

沿坐標(biāo)軸的包圍盒AABB：指包含對(duì)象且邊平行于坐標(biāo)軸的最小長(zhǎng)方體。當(dāng)兩個(gè)AABB包圍盒在三個(gè)坐標(biāo)軸上的投影區(qū)間同時(shí)重疊時(shí)，則相交。

方向包圍盒OBB：指包含對(duì)象且相對(duì)于坐標(biāo)軸方向任意的最小長(zhǎng)方體。包圍盒的方向的選擇與效率息息相關(guān)。

k-dop包圍盒：包含當(dāng)前對(duì)象為要求。自身所有面的法向量均來(lái)自一個(gè)固定的方向集合的凸包，固定方向集的選取對(duì)包圍盒效率有著直接影響。

2 碰撞檢查流程設(shè)計(jì)

核級(jí)管道碰撞檢查要求精確度高響應(yīng)快，再根據(jù)碰撞檢查算法各自的性能特點(diǎn)，現(xiàn)設(shè)計(jì)一種新的碰撞檢查流程。

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

3 仿真與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

基于PDMS平臺(tái)，開(kāi)發(fā)針對(duì)管道的碰撞檢查功能模塊，將新設(shè)計(jì)的碰撞檢查流程植入功能模塊中。主要實(shí)現(xiàn)管道模型在布置過(guò)程中實(shí)時(shí)的完成與周圍建筑物的碰撞檢查，包括管道、支吊架、設(shè)備、土建等9個(gè)級(jí)別的檢查。

用實(shí)例驗(yàn)證新碰撞檢查流程的性能優(yōu)勢(shì)。選擇實(shí)際工程中6根管道作為實(shí)驗(yàn)對(duì)象，對(duì)比單一的包圍盒算法與新碰撞檢查流程，通過(guò)耗時(shí)及碰撞結(jié)果對(duì)比得到新設(shè)計(jì)流程的優(yōu)勢(shì)。

3.2 結(jié)果分析

6根管道經(jīng)過(guò)新的碰撞檢查流程，同時(shí)對(duì)比精度最高的k-dop包圍盒及速度最快的Sphere包圍盒，時(shí)間對(duì)比結(jié)果如圖4所示。

通過(guò)三種碰撞檢查算法用時(shí)對(duì)比，新的碰撞檢查算法用時(shí)趨近于構(gòu)造代價(jià)最小的Sphere包圍盒法，遠(yuǎn)遠(yuǎn)小于k-dop包圍盒法。接下來(lái)對(duì)比碰撞檢查效果，對(duì)比結(jié)果如圖5所示。

通過(guò)碰撞檢查效果對(duì)比，新碰撞檢查流程接近于k-dop包圍盒算法，再通過(guò)時(shí)間對(duì)比的結(jié)果分析，新碰撞檢查流程的效率要優(yōu)于現(xiàn)有單一的碰撞檢查算法，并行包圍盒算法發(fā)揮了作用，減輕了設(shè)計(jì)人員工作的時(shí)間成本。

4 結(jié)束語(yǔ)

針對(duì)管道設(shè)計(jì)中的碰撞檢查問(wèn)題，本文通過(guò)對(duì)目標(biāo)模型進(jìn)行BSP分割預(yù)處理，將模型拆分為速度和效率兩類模型，用K-dop和AABB包圍盒并行檢查。通過(guò)新的碰撞檢查算法流程，解決了碰撞檢查效率低等問(wèn)題，隨著模型體量的增加，新的碰撞檢查算法的效率優(yōu)勢(shì)愈發(fā)明顯。本文通過(guò)實(shí)驗(yàn)證明了算法的可行性和有效性，說(shuō)明新的碰撞檢查算法應(yīng)用于核級(jí)管道設(shè)計(jì)效果顯著。

參考文獻(xiàn)

[1]黃曉康.基于BSP和四叉樹(shù)的場(chǎng)景管理研究[D].南京理工大學(xué)，2008.

[2]喬云婷，張弘.基于BSP樹(shù)的三維場(chǎng)景渲染方法研究[J].渭南師范學(xué)院學(xué)報(bào)，2014，29（15）：86-89.

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

[4]鄧峻生，毛世峰，劉旭峰，葉民友.基于AABB樹(shù)的聚變堆形變部件碰撞檢測(cè)算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2018，27（11）：161-167.

[5]劉超，蔣夏軍，施慧彬.基于OBB包圍盒碰撞檢測(cè)算法的改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，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]鄭延斌，郭凌云，劉晶晶.基于混合包圍盒的碰撞檢測(cè)優(yōu)化算法[J].計(jì)算機(jī)工程與科學(xué)，2013，35（04）：87-92.