鄭尊鵬

青島科技大學(xué)，山東青島 266042

機器人仿真系統(tǒng)中碰撞檢測算法的優(yōu)化

鄭尊鵬

青島科技大學(xué)，山東青島 266042

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

仿真系統(tǒng)；碰撞檢測；層次包圍盒；混合包圍盒

0 引言

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

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

1 碰撞檢測算法

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

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

2 層次包圍盒類型

2.1 AABB

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

2.2 包圍球

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

2.3 OBB

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

2.4 k-DOP

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

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

3 混合包圍盒

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

一般來說，AABB較適合于橢長形但與坐標(biāo)軸夾角不大的物體，OBB則適合于橢長形且與坐標(biāo)軸有一定夾角的物體；而包圍球較適合于三個坐標(biāo)軸上分布比較均勻或經(jīng)常發(fā)生旋轉(zhuǎn)運動的物體，k-DOP則適合用在表面結(jié)構(gòu)比較復(fù)雜但不發(fā)生旋轉(zhuǎn)的物體上。

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

4 結(jié)論

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

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

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

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

TP24

A

1674-6708（2011）48-0191-01