信息科技
作者：鄭尊鵬
摘要 碰撞檢測是機器人仿真係統中的重要問題之一。本文介紹了碰撞檢測算法的基本分類，對層次包圍盒的幾種基本算法進行了分析比較，重點闡述了混合包圍盒法，並將其應用於仿真係統中碰撞檢測問題的解決，提高了檢測速度、優化了檢測算法。
關鍵詞 仿真係統；碰撞檢測；層次包圍盒；混合包圍盒
中圖分類號TP24 文獻標識碼A 文章編號 1674-6708（2011）48-0191-01
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，但存儲一個包圍球隻需兩個浮點數，縮小了包圍盒所需的存儲空間。包圍球的相交測試比較簡單，是用球體包圍整個幾何體。包圍球緊密性最差，故使用較少。