基于空間分解與混合包圍盒的碰撞檢測算法*

宋濤，舒濤，梅朝，張衛東

（空軍工程大學防空反導學院，西安710051）

基于空間分解與混合包圍盒的碰撞檢測算法*

宋濤，舒濤，梅朝，張衛東

（空軍工程大學防空反導學院，西安710051）

針對如何提高碰撞檢測效率的問題，提出一種基于空間分解法和混合包圍盒的碰撞檢測算法。首先利用均勻剖分法確定相鄰對象，然后只對相鄰對象構建混合層次包圍盒樹，最后引入任務樹的概念加速包圍盒樹的遍歷過程。在包圍盒碰撞檢測中，提出了一種頂層采用AABB，其他層采用OBB的混合層次包圍盒結構。實驗結果表明，該算法有效提高了碰撞檢測的效率和實時性。

碰撞檢測，空間分解，包圍盒，任務樹

0 引言

碰撞檢測（Collision Detection，CD）也稱為干涉檢測或者接觸檢測，是系統仿真、虛擬現實技術等領域中的關鍵性問題。顧名思義，其任務就是根據現實中一對或多對對象不能在同一時刻占有相同區域的事實來檢測虛擬場景中的對象是否發生碰撞或穿透現象，這對于虛擬場景的真實感和實時性有著重大作用。空間分解法和層次包圍盒法是兩類經典的碰撞檢測算法［1］。空間分解法是將空間劃分為不同的區域，找到占據同一區域的相鄰對象，只對相鄰對象進行檢測，常用的空間分解方法有樹、均勻網格和空間排序等；層次包圍盒的思想是用體積略大而幾何特征簡單的包圍盒來代替復雜的幾何對象進行碰撞檢測，只需對包圍盒重疊的對象進行進一步碰撞檢測，常用的包圍盒有Spheres，AABB，OBB和k-DOPs等［2］。……