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

徐鵬 羅恒

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

關鍵詞：碰撞檢測;混合層次包圍盒;混合積;干涉

1引言

在船舶維修中經常會遇到一些設備、管路被拆卸、重新制作、更換回裝，由于船舶上一些艙室部位設備、管路諸多且管路走向較為復雜，而重新制作的設備、管路會導致外形尺寸誤差，同時回裝時設備管路位置的變化會導致回裝時發生干涉。在船舶維修中一旦發生碰撞干涉現象，需對設備、管路進行改進或將其安裝位置進行變更，會導致工程的各種返工，同時維修性分析中碰撞檢測貫穿于產品設計的整個階段[1]，因此在船舶維修中對設備、管路間的干涉碰撞檢測的研究十分重要。

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

2基本原理

2.1碰撞檢測算法

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

2.2包圍盒檢測方法

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

2.3 層次包圍盒樹檢測方法

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

（1）樹中的每個節點v與S的一個子集相對應;

（2）節點v的數據值為集合S的包圍盒;

（3）根結點對應于全集S，其數據值為全集S的包圍盒;

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

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

3算法實現

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4步驟四：得出碰撞檢測結果

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

4應用及結論

根據系統設計要求，在Proe軟件中繪制三維實體，并將三維實體以三角形面片形式保存為STL格式的數據文件;然后將STL格式文件讀入到程序中，根據上述算法實現步驟及相關要求，先將一個個實物體按照三角面片且帶法向量來存儲;對于多個實物體，需要構建層次包圍盒樹，將樹的節點存儲為一個個實物對象;然后遍歷層次包圍盒樹，分別對要分析的實體進行干涉碰撞情況判斷，管路設備的干涉情況具體如下圖4。

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

5結論

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

參考文獻：

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

[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].系統仿真學報，2004， 16（9）： 1931-1934.

[4]鄧琛，張琴舜.虛擬現實系統中碰撞檢測技術初探[J].微型電腦應用，2002，19（8）：55-56.

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

[6]胡祥瀟.一種三維碰撞檢測并行算法的設計與實現[D].武漢：華中科技大學，計算機應用技術.

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

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

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

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

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

[12]章勤，黃琨，李光明.一種基于OBB的碰撞檢測算法的改進.華中科技大學學報（自然科學版）， 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].計算機工程與科學，2010，32（4）：59-61.

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

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

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