徐鵬 羅恒

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

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

1引言

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

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

2基本原理

2.1碰撞檢測(cè)算法

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

2.2包圍盒檢測(cè)方法

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

2.3 層次包圍盒樹(shù)檢測(cè)方法

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

（1）樹(shù)中的每個(gè)節(jié)點(diǎn)v與S的一個(gè)子集相對(duì)應(yīng);

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

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

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

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

3算法實(shí)現(xiàn)

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

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

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

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

假設(shè)兩個(gè)實(shí)物對(duì)象的包圍矩形分別為P、Q，對(duì)應(yīng)的各自頂點(diǎn)參數(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)步計(jì)算判斷，此時(shí)轉(zhuǎn)入步驟（3）;

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

3.2步驟二：層次包圍盒樹(shù)的遍歷

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

3.3步驟三：三角形之間的相交測(cè)試

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

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

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

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

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

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

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

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

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

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

5結(jié)論

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

參考文獻(xiàn)：

[1]湯鵬.維修性分析與仿真中的高效碰撞檢測(cè)算法研究[D].長(zhǎng)沙：國(guó)防科學(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)仿真的碰撞檢測(cè)算法及應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，2004， 16（9）： 1931-1934.

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

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

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

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

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

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

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

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

[12]章勤，黃琨，李光明.一種基于OBB的碰撞檢測(cè)算法的改進(jìn).華中科技大學(xué)學(xué)報(bào)（自然科學(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包圍盒的碰撞檢測(cè)算法的研究[J].計(jì)算機(jī)工程與科學(xué)，2010，32（4）：59-61.

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

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

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