船舶維修中基于包圍盒的碰撞檢測算法

徐鵬 羅恒

摘 要：針對船舶維修中管路設(shè)備無三維放樣的情況，導(dǎo)致管路設(shè)備間存在一定的干涉，為便于維修過程中的施工、減少返工，急需一種基于包圍盒的碰撞檢測算法。根據(jù)艦船具體特點和實際需要，從管路設(shè)備的空間幾何位置關(guān)系出發(fā)，采用了基于球包圍盒和軸對稱包圍盒的混合層次包圍盒方法的碰撞檢測算法，在判斷碰撞分析時運(yùn)用基于混合積的線段相交判定方法。結(jié)果表明：混合層次包圍盒方法的碰撞檢測算法較傳統(tǒng)方法簡單易于實現(xiàn)，運(yùn)算速度快，可分析判斷管路設(shè)備的干涉情況，從而有效的避免維修中管路設(shè)備的干涉，該包圍盒碰撞檢測算法能極大縮短工程周期和節(jié)約成本。

關(guān)鍵詞：碰撞檢測;混合層次包圍盒;混合積;干涉

1引言

在船舶維修中經(jīng)常會遇到一些設(shè)備、管路被拆卸、重新制作、更換回裝，由于船舶上一些艙室部位設(shè)備、管路諸多且管路走向較為復(fù)雜，而重新制作的設(shè)備、管路會導(dǎo)致外形尺寸誤差，同時回裝時設(shè)備管路位置的變化會導(dǎo)致回裝時發(fā)生干涉。在船舶維修中一旦發(fā)生碰撞干涉現(xiàn)象，需對設(shè)備、管路進(jìn)行改進(jìn)或?qū)⑵浒惭b位置進(jìn)行變更，會導(dǎo)致工程的各種返工，同時維修性分析中碰撞檢測貫穿于產(chǎn)品設(shè)計的整個階段[1]，因此在船舶維修中對設(shè)備、管路間的干涉碰撞檢測的研究十分重要。

船舶中的設(shè)備管路間的干涉，對應(yīng)的是幾何空間上三維實體的的碰撞檢測。碰撞檢測是虛擬現(xiàn)實、計算機(jī)圖形學(xué)中最基本且非常重要的組成部分，在計算機(jī)和工業(yè)應(yīng)用領(lǐng)域應(yīng)用十分廣泛。針對碰撞檢測問題，國內(nèi)外已經(jīng)開展了大量的算法及其研究工作。根據(jù)三維空間上的物體，Lin[2]主要做的是靜態(tài)干涉檢測算法;國內(nèi)部分高校的研究，如清華大學(xué)[3]、上海交通大學(xué)[4]、浙江大學(xué)[5]等主要從事基礎(chǔ)研究工作，他們的研究均取得了一定的進(jìn)展。從物體的三維幾何特性出發(fā)，根據(jù)物體實際特點來進(jìn)行幾何計算，從而有了層次包圍盒法[6]和空間分割法等成熟算法[7-8]，但是這些研究的大部分碰撞檢測算法，基本都是根據(jù)具體的應(yīng)用場合來設(shè)定，從而應(yīng)用上具有一定的局限性，且算法的效率還不是很高。本文從三維實體的幾何空間角度出發(fā)，運(yùn)用球包圍盒和軸對稱包圍盒混合的層次包圍盒法，使碰撞檢測算法易于實現(xiàn)、簡單可靠且效率較高，實用性較強(qiáng)。

2基本原理

2.1碰撞檢測算法

一般情況下，根據(jù)時空來判斷檢測算法，該算法可以分為基于時間域的碰撞檢測算法和基于空間域的碰撞檢測算法兩類[9]。碰撞檢測在CAD/CAM、計算機(jī)動畫、機(jī)器人、路徑和運(yùn)動規(guī)劃、模擬駕駛等領(lǐng)域有著廣泛的應(yīng)用，而碰撞檢測是通過布爾運(yùn)算來判斷是否發(fā)生碰撞。一般工程應(yīng)用主要是空間域上的碰撞檢測算法，運(yùn)動過程中的碰撞檢測算法是基于時間域，其具體分類如圖1所示：

2.2包圍盒檢測方法

根據(jù)圖1，文章采用的碰撞檢測算法是基于空間域的，在空間域的碰撞檢測中，常用包圍盒方法有：包圍球（Sphere）、沿坐標(biāo)軸的軸向包圍盒（AABB Axis-Aligned Bounding Boxes）、方向包圍盒（OBB Oriented Bounding Box）、固定方向凸包（FDH Fixed? Direction Hull或K-Dops Discrete Orientation Polytope）等。三維空間實體中的AABB包圍盒具有表現(xiàn)形式為六面體、六面體中的每條邊都平行于一個坐標(biāo)平面的特點，故求取簡單，不僅適合于剛體的檢測，也應(yīng)用于軟體中，在大多數(shù)碰撞檢測算法中得到良好應(yīng)用。包圍球的相交測試通過球心和半徑來判斷，因此判斷起來較快速簡單，具有實時檢測過程中不再更新的特點，因此可以先通過該方法來快速判斷那些不相交的三維實體，極大縮短了相交判斷測試時間[5，10]。針對這些包圍盒適用范圍，結(jié)合實船設(shè)備管路幾何特點，本文采用包圍球和AABB包圍盒相結(jié)合的包圍盒檢測算法，可結(jié)合發(fā)揮這兩種方法的優(yōu)勢，提高運(yùn)算效率和縮短時間。

2.3 層次包圍盒樹檢測方法

所謂的層次包圍盒樹，根據(jù)其具體含義，即樹結(jié)構(gòu)樹節(jié)點數(shù)據(jù)值由包圍盒構(gòu)成，具體幾何定義為：假設(shè)給定物體W，集合S表示為W中所有包含基本幾何元素的集合，將該幾何元素集定義為一棵樹，樹是基于集合S上的包圍盒層次結(jié)構(gòu)，則稱為層次包圍盒樹，所具有的性質(zhì)[11]如下：

（1）樹中的每個節(jié)點v與S的一個子集相對應(yīng);

（2）節(jié)點v的數(shù)據(jù)值為集合S的包圍盒;

（3）根結(jié)點對應(yīng)于全集S，其數(shù)據(jù)值為全集S的包圍盒;

（4）樹中的每個葉節(jié)點指向的是物體W的幾何基本元素。

根據(jù)上述定義及性質(zhì)，將物體的多個包圍盒按照樹來進(jìn)行劃分，一棵層次包圍盒樹為完全的當(dāng)且僅當(dāng)該樹中每個葉節(jié)點對應(yīng)于S的一個單元素子集，也就是只包含一個基本幾何元素。由此可知，層次包圍盒樹與一般的樹形結(jié)構(gòu)不一樣，在構(gòu)造的時候，需要考慮每個節(jié)點上的基本幾何元素子集及包圍盒的幾何特性，這也是所需特別注意地方。

3算法實現(xiàn)

對于空間實物體，首先獲取實物的幾何數(shù)據(jù)，根據(jù)設(shè)計繪制的設(shè)備、管道三維實體提取得到三維數(shù)據(jù)，然后將三維數(shù)據(jù)導(dǎo)成STL數(shù)據(jù)，將實物用許多三角面片表示，如某三角形面片A，存儲表示為Triangle A（Point Pa，Point Pb，Point Pc，Point Pn，），其中Pa、Pb、Pc分別表示三角形的三個頂點，Pn表示三角形面片的法向量，Point表示為P（x，y，z）。因此可利用三角面片表示法來存儲空間任意三維實體。針對船舶維修中設(shè)備、管路的碰撞，本文采用了基于包圍球、包圍盒混合的碰撞檢測算法，主要是該算法構(gòu)造和相交測試都比較簡單、容易實現(xiàn)，并且具有算法計算速度較快等優(yōu)勢。采用的層次包圍盒方法，還可遞歸地對包圍盒進(jìn)行逐次劃分，將劃分后的包圍盒更加緊密地包圍物體，劃分越多表達(dá)越準(zhǔn)確，越能代表實物體。只有當(dāng)將兩物體包圍起來的包圍盒發(fā)生相交時，才需要進(jìn)一步對物體間進(jìn)行相交判斷測試。碰撞處理一般分為碰撞檢測、碰撞確定、碰撞響應(yīng)三步。算法實現(xiàn)的具體流程如圖2所示。

3.1步驟一：包圍球、AABB包圍盒間相交測試

對于給定的實體對象，依照前面三角面片表示方法，首先需分別計算所有三角面片中所有頂點的X坐標(biāo)、Y坐標(biāo)和Z坐標(biāo)均值，以確定包圍球的球心Q點，由球心Q與三個最大坐標(biāo)值所確定的點間距離來計算半徑r。判斷包圍球間的相交測試比較簡單，對于兩個包圍球Q1和Q2，只需要判斷兩球心距離和半徑之間的關(guān)系，如果球心Q1、Q2間的距離小于半徑之和：，則判定兩包圍球相交[12，13];反之，兩包圍球相離。

兩個AABB包圍盒相交當(dāng)且僅當(dāng)它們在三個坐標(biāo)軸上的投影區(qū)段都有重疊，所以這里將AABB包圍盒的相交測試轉(zhuǎn)化到一維空間來解決，通過對AABB包圍盒在x、y、z三個坐標(biāo)軸上的投影排序來確定相交的AABB包圍盒，可采用希爾排序[14]。

假設(shè)兩個實物對象的包圍矩形分別為P、Q，對應(yīng)的各自頂點參數(shù)為、，則兩物體是否相交判斷如下[11]：

（1）Ifor，then判斷兩矩形P和Q不存在相交;otherwise，If，then判斷矩形P和Q可能相交，需進(jìn)步判斷是否相交，轉(zhuǎn)入步驟（2）;

（2）Ifor，then矩形P和Q不相交;otherwise，，then矩形P和Q可能相交，需進(jìn)步計算判斷，此時轉(zhuǎn)入步驟（3）;

（3）Ifor，then矩形P和Q不相交;otherwise，，then判斷矩形P和Q一定相交。

3.2步驟二：層次包圍盒樹的遍歷

在眾多碰撞檢測算法中，基于層次包圍盒樹的碰撞檢測算法是目前運(yùn)用得較多也是相對比較成熟的碰撞檢測算法。此類算法一般流程如下圖3：

3.3步驟三：三角形之間的相交測試

首先將兩物體的包圍盒樹遍歷各自葉節(jié)點，判斷葉節(jié)點是否相交，此時碰撞檢測算法進(jìn)行算法的最底層--基本幾何元素間的相交測試。三角形之間的相交測試結(jié)果，將直接關(guān)聯(lián)到物體碰撞檢測的結(jié)果，即If三角形間相交，then判定兩物體發(fā)生碰撞;otherwise繼續(xù)進(jìn)行其它三角形對的相交測試判斷。最終相交測試結(jié)果：If所有三角形對間均為不相交，then判定兩物體不相交。碰撞檢測過程中，只要有一對三角形相交，則立即停止三角形對的相交測試，返回碰撞結(jié)果，觸發(fā)碰撞響應(yīng)[15]。

不妨假設(shè)頂點均已知的三角形對ABC、DEF，則對這兩個三角形按照下面給出的步驟判斷它們是否發(fā)生相交。

步驟1：判定其中一個三角形ABC的支撐超平面是否與另一個三角形DEF相交。

計算支撐超平面的法向量（設(shè)A點的坐標(biāo)為（，，），，同理可得到B、C、D、E、F的坐標(biāo)向量），令、、，對以下幾種情況進(jìn)行判斷：①若sd、se和sf全部為正值或者全部為負(fù)值，說明DEF的三個頂點都位于支撐超平面的相同的一側(cè)，因此兩個三角形不相交。②倘若sd、se和sf均為零值，說明兩個三角形共面，此時將兩個三角形投影到二維平面，從而轉(zhuǎn)換成二維空間的相交測試。

步驟2：計算出三角形ABC和三角形DEF所在平面間的交線，這條線段位于平面上。如果這條線段與三角形DEF相交，線段與三角形邊相交的判斷可用混合積法[3，16，17]，或者完全包含于三角形DEF中，則兩三角形相交，否則不相交。

3.4步驟四：得出碰撞檢測結(jié)果

一旦有檢測到有三角形發(fā)生相交，則立即停止碰撞檢測，輸出碰撞結(jié)果;以此類推，遍布實物體W1、W2中所有的三角形面片，若都不相交，則實物體也不相交。

4應(yīng)用及結(jié)論

根據(jù)系統(tǒng)設(shè)計要求，在Proe軟件中繪制三維實體，并將三維實體以三角形面片形式保存為STL格式的數(shù)據(jù)文件;然后將STL格式文件讀入到程序中，根據(jù)上述算法實現(xiàn)步驟及相關(guān)要求，先將一個個實物體按照三角面片且?guī)Хㄏ蛄縼泶鎯?對于多個實物體，需要構(gòu)建層次包圍盒樹，將樹的節(jié)點存儲為一個個實物對象;然后遍歷層次包圍盒樹，分別對要分析的實體進(jìn)行干涉碰撞情況判斷，管路設(shè)備的干涉情況具體如下圖4。

若發(fā)現(xiàn)管路設(shè)備存在干涉碰撞情況，可進(jìn)行如下處理：一是將干涉設(shè)備或者管路進(jìn)行移位，在不影響其他物體干涉碰撞情況下，將干涉物體間的距離變大，即可消除存在的干涉管路設(shè)備;另外一種方法，改變干涉部位的形狀，在不影響兩物體性能及要求情況下，對兩物體要干涉的局部部位形狀進(jìn)行改變，從而有效避免干涉碰撞?？傊?，在船舶維修中，經(jīng)常對船舶管路設(shè)備進(jìn)行局部維修，若未經(jīng)過判斷直接將管路設(shè)備安裝到船上，安裝后則很可能會出現(xiàn)干涉情況，從而導(dǎo)致設(shè)備管路安裝的返工，同時需要根據(jù)現(xiàn)場安裝情況進(jìn)步判斷干涉，這樣將會導(dǎo)致工程的返工，還有可能影響原來船上的管路設(shè)備，導(dǎo)致在安裝過程中，損壞原有部件，造成的損失不可估量。如果在管路設(shè)備安裝前，對管路設(shè)備的干涉進(jìn)行判斷，在制作管路設(shè)備時就考慮到干涉情況，即可避免工程的返工，大大縮短工程的周期，減少人力、物力等經(jīng)費(fèi)。

5結(jié)論

本文從幾何空間角度出發(fā)，分析了空間實物干涉碰撞的可能性，運(yùn)用球包圍盒和軸對稱包圍盒混合的層次包圍盒法，該方法易于實現(xiàn)、簡單可靠?；趲缀慰臻g位置的碰撞分析方法，引入了基于混合積的線段相交的判定方法，提高了碰撞分析的運(yùn)算速度;基于包圍盒的碰撞檢測算法有效地解決了船舶維修中三維實體干涉碰撞問題，能縮短工程周期及減少各項費(fèi)用。

參考文獻(xiàn)：

[1]湯鵬.維修性分析與仿真中的高效碰撞檢測算法研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，機(jī)械工程.

[2]Lin M C， Gottschalk S. Collision detection between geometric models： a survey[C].Proc of IMA Conference on Mathematics of Surfaces.1998： 37-56.

[3]王浩，張航義.一種適合多機(jī)空戰(zhàn)仿真的碰撞檢測算法及應(yīng)用[J].系統(tǒng)仿真學(xué)報，2004， 16（9）： 1931-1934.

[4]鄧琛，張琴舜.虛擬現(xiàn)實系統(tǒng)中碰撞檢測技術(shù)初探[J].微型電腦應(yīng)用，2002，19（8）：55-56.

[5]范昭煒.實時碰撞檢測技術(shù)研究[D].杭州：浙江大學(xué)，2003.

[6]胡祥瀟.一種三維碰撞檢測并行算法的設(shè)計與實現(xiàn)[D].武漢：華中科技大學(xué)，計算機(jī)應(yīng)用技術(shù).

[7]王志強(qiáng)，洪嘉振，楊輝.碰撞檢測問題研究綜述[J].軟件學(xué)報，1999，10（5）：545-551.

[8]李芙玲，張瑾.碰撞檢測技術(shù)研究[J].華北科技學(xué)院學(xué)報，2006，1（2）：71-73.

[9]姜光焱.基于包圍盒的碰撞檢測算法的研究及應(yīng)用[D].成都：電子科技大學(xué)，信號與信息處理.

[10]陳學(xué)文，丑武勝，劉靜華等.基于包圍盒的碰撞檢測算法研究[J]. 計算機(jī)工程與應(yīng)用， 2005，41（5）： 46-50.

[11]高玉琴.三維空間中碰撞檢測算法的研究[D].武漢：華中科技大學(xué)，計算機(jī)應(yīng)用.

[12]章勤，黃琨，李光明.一種基于OBB的碰撞檢測算法的改進(jìn).華中科技大學(xué)學(xué)報（自然科學(xué)版）， 2003.1（6）：52-58.

[13]Antonio Benitez， Maria del Carmen Ramirez， Daniel Vallejo.? Collision Detection Using Sphere-Tree Construction[C].In：Proceedings? of the 15th International Conference on Electronics， Communications? and Computers （CONIELECOMP05）.NW Washington， DC USA：? IEEE Computer Society，2005：286-291.

[14]王曉榮，王萌，李春貴.基于AABB包圍盒的碰撞檢測算法的研究[J].計算機(jī)工程與科學(xué)，2010，32（4）：59-61.

[15]鄒益勝，丁國富，何邕等.空間三角形快速相交檢測算法[J].計算機(jī)應(yīng)用研究，2008，25（10）：2906-2910.

[16]肖翔.基于幾何的三維地下供水管網(wǎng)碰撞分析[D].武漢：華中科技大學(xué)，模式識別與智能系統(tǒng).

[17]王舒鵬，方莉.混合積判斷線段相交的方法分析[J].電腦開發(fā)與應(yīng)用， 2006， 19（10）：34-35.