機器人仿真系統中碰撞檢測算法的優化

鄭尊鵬

青島科技大學，山東青島 266042

機器人仿真系統中碰撞檢測算法的優化

鄭尊鵬

青島科技大學，山東青島 266042

碰撞檢測是機器人仿真系統中的重要問題之一。本文介紹了碰撞檢測算法的基本分類，對層次包圍盒的幾種基本算法進行了分析比較，重點闡述了混合包圍盒法，并將其應用于仿真系統中碰撞檢測問題的解決，提高了檢測速度、優化了檢測算法。

仿真系統；碰撞檢測；層次包圍盒；混合包圍盒

0 引言

在物理模型中檢測運動物體是否相互碰撞的過程稱為碰撞檢測（Collision Detection,CD），也稱為干涉檢測或接觸檢測。碰撞檢測是基于現實生活中一個普遍存在的事實：兩個不可穿透的對象不可能共享相同的空間區域。

在機器人仿真系統中，經常需要對多個機器人在同一工作單元中的協同作業進行仿真。為避免因機器人的工作空間之間存在重疊交叉區域而發生相互干涉的問題，要引入碰撞檢測來判定多個機器人在給定時間域內的同一時刻是否占有相同區域。碰撞檢測是機器人仿真系統不可回避的問題之一，快速而有效的碰撞檢測功能是仿真系統成功的關鍵。

1 碰撞檢測算法

由于碰撞檢測問題由來已久，在不同領域涌現出了許多碰撞檢測算法。在這些算法中比較經典的研究成果包括空間分割法（space decomposition）和層次包圍盒法（hierarchical bounding bolumes）及其一系列改進算法等。

空間分割法是將包含物體的虛擬空間分割為多個體積相等的小單元格，每個物體對應于一個或多個小單元中，碰撞檢測時只需對占據同一單元格或相鄰單元格的幾何對象進行相交測試。比較典型的方法有k-d樹、八叉樹、BSP（binary space partitioning）樹、四面體網和規則網格等。層次包圍盒法是用幾何特性簡單的包圍盒近似地描述虛擬場景中復雜的幾何對象，進而通過構造樹狀層次結構逐步逼近對象的幾何模型，直到幾乎完全獲得對象的幾何特性。典型的類型有沿坐標軸包圍盒AABB（axis-aligned bounding box）、包圍球（spheres）、方向包圍盒 OBB（oriented bounding box）、離散方向多面體k-DOP（k-discrete orientation polytopes）等。前者適用于對象較少且均勻分布的空間；后者適用于復雜環境中的碰撞檢測，且應用廣泛。

2 層次包圍盒類型

2.1 AABB

AABB是指一個包含給定對象且各邊平行于坐標軸的最小六面體，它需要6個標量來描述，即組成物體基本幾何元素的頂點x、y、z坐標的最大值和最小值。AABB的緊密性相對較差，但計算十分簡單。AABB的相交測試是比較簡單的，兩個對象當且僅當它們在3個坐標軸上的投影區間均重疊即相交；也是最快的，最多只需要6次比較運算。AABB間的相交測試和包圍盒的更新速度比其他算法效率高，因此使用也最廣泛。

2.2 包圍球

包圍球被定義為包含該對象的最小的球體，僅需兩個標量描述，即球心和半徑。包圍球的計算時間多于AABB，但存儲一個包圍球只需兩個浮點數，縮小了包圍盒所需的存儲空間。包圍球的相交測試比較簡單，是用球體包圍整個幾何體。包圍球緊密性最差，故使用較少。

2.3 OBB

一個給定對象的OBB被定義為包含該對象且相對于坐標軸方向任意的最小的正六面體。OBB的緊密性最好，因其方向的任意性使它可以根據被包圍對象的形狀特點盡可能緊密地包圍對象，大大提高了算法的效率。但這也使其相交測試變得復雜，不能有效處理變形體的碰撞檢測。一般來說，OBB的總體性能優于前兩種方法，并且實時性較高。

2.4 k-DOP

由于AABB和包圍球的緊密性較差，而OBB的重疊測試和節點修改耗費又較高，所以提出了一種折中的k-DOP算法。k-DOP是一個凸多面體，它使用k/2對平行平面來包圍物體。當k值取足夠大時，k-DOP就發展成物體的凸包。

K的取值要根據碰撞檢測的不同需要而定，通過調整k值，k-DOP可以在碰撞檢測的簡單性和包裹物體的緊密性之間靈活取舍，以滿足特定的要求。k-DOP的緊密性要優于AABB，相交測試的復雜度要小于OBB，從而提高了碰撞檢測的效率。

3 混合包圍盒

對層次包圍盒法來說，其自身的簡單性和所包圍物體的緊密性是相互矛盾的。簡單性是指包圍盒要比被包圍的幾何對象簡單，既要求幾何形狀簡單易于計算，又要求相交測試算法簡單運算快速；緊密性則要求包圍盒盡可能貼近被包圍的對象。事實上，一種包圍盒的簡單性越高則緊密性越差，反之亦然，很難達到一定的平衡。

一般來說，AABB較適合于橢長形但與坐標軸夾角不大的物體，OBB則適合于橢長形且與坐標軸有一定夾角的物體；而包圍球較適合于三個坐標軸上分布比較均勻或經常發生旋轉運動的物體，k-DOP則適合用在表面結構比較復雜但不發生旋轉的物體上。

為了既能利用包圍盒的優點，又能避免它們的不足，可以采用混合包圍盒法。即根據同一物體上不同的幾何特征選用不同的包圍盒，縮減可能發生碰撞的范圍，并通過包圍盒之間的求交運算，優化碰撞檢測算法，提高碰撞檢測的時效性。

4 結論

檢測速度的提高是機器人仿真系統碰撞檢測的核心問題。我們在七自由度機器人仿真控制系統中，結合機器人動作的軌跡采用了AABB-OBB混合包圍盒法。在包圍盒樹的頂層采用AABB，在樹的其他層次采用OBB，使AABB簡單性好和OBB緊密性好的優點有效結合。從而實現了碰撞檢測算法的優化，加快了檢測的速度，提高了檢測的實時性和可靠性。實驗結果表明，比OBB算法提高了大約10%～15%。此算法可應用于形狀復雜剛體的實時碰撞檢測，并且場景規模越大，算法改進的效果越明顯。

[1]崔漢國，陳軍，王大宇.虛擬環境中優化的OBB碰撞檢測算法研究[J].計算機工程與設計，2007(11)：2524-2526.

[2]申玉斌，蔡勇，華才健.虛擬環境中的碰撞檢測技術的研究與應用[J].交通與計算機，2005(1)：23.

[3]蔡文軍，陳虎.基于混合模型的碰撞檢測優化算法研究[J].計算機與現代化，2006(7)：49-52.

TP24

A

1674-6708（2011）48-0191-01