摘 要： 針對Android手持終端中復雜游戲場景的碰撞檢測需求，提出了一種基于包圍球和AABB的實時碰撞檢測算法。該算法針對不同的虛擬對象構建不同的包圍盒，并將改進后的包圍盒投影排序分組方法應用其中。將該算法與使用包圍盒投影排序分組方法的包圍球算法與AABB算法比較,實驗表明,該算法在保持更高精度的前提下仍能滿足復雜場景中實時碰撞檢測的要求。
關鍵詞： Android ；碰撞檢測；包圍球；AABB

    隨著移動互聯網的高速發展和快速普及,以及以ARM Cortex-A8、Cortex-A9為代表的高端嵌入式芯片的飛速發展，智能手機、平板電腦等手持PDA已經進入每一個人的生活，并且其性能越來越強大。基于Android的高端消費類電子產品更是以其開源性和通用性受到廣大消費者的青睞。游戲無疑是這些手持設備的一個重要應用，而且不是傳統的簡單2D游戲，而是越來越復雜的3D游戲，甚至是移植的PC經典游戲，如實況足球、極品飛車、CS等。為了使游戲更加逼真，場景中對象間的實時碰撞檢測[1]是一個必須要解決的問題。但是當前手持設備的3D游戲規模越來越龐大，場景越來越復雜，如何快速精確地實現移動手持設備中復雜游戲場景的實時碰撞檢測已經成為當前的研究熱點之一。
    在游戲場景中,一般采用各種包圍盒算法來替代對象進行相交測試，但假設游戲場景中有D個動態對象和S個靜態對象，如果直接用兩對象的包圍盒進行碰撞檢測，則必須經過CD2+DS次檢測才能最終確定整個場景的碰撞情況，當D和S都較大時，這將是一個龐大的計算量，從而嚴重影響游戲場景的實時性和真實性。基于Lin-Canny[2-4]算法的I-Collide[4-5]算法庫是一種經典的實時碰撞檢測算法，它使用一維區間排序法快速排除不相交的對象對，從而大大減少了精確求交的計算量。由于游戲場景對實時性的要求比較高,本文在I-Collide算法庫及其改進算法的基礎上提出了一種基于包圍球[1]和軸對稱包圍盒(AABB)[1]的快速碰撞檢測算法。
1 算法描述
1.1 I-Collide算法庫及其改進算法概述
　    三維空間的包圍盒間相交測試，常常是把包圍盒投影到坐標軸上轉化為一維或二維來處理，即通過降低維度來提高檢測的效率。基于AABB的經典I-Collide算法庫采用的是一維空間排序法，即將AABB投影到某一坐標軸上，如圖1所示，然后使用插入排序法對投影列表排序確定包圍盒的交疊情況，從而將沒有相交的包圍盒快速略去。I-Collide算法庫比以往的其他碰撞檢測算法更加高效，但它忽略了碰撞檢測的局部性，將排序后的所有包圍盒兩兩進行相交測試。董峰等[2]對該排序算法進行了改進，使用二維投影排序的方法，即將所有物體的包圍盒投影到x-y坐標面，然后用矩形排序算法進行篩選，最后驗證交迭的矩形對在z軸上的相交情況。王曉榮[5]又進行了改進，她不僅把包圍盒投影到二維x-y平面，而且采用了效率更高的希爾排序法對投影序列實時排序,并將坐標軸劃分為一系列包含相同數目的投影子段(如果投影區間數不能被均勻劃分，讓最后一個子段的投影區間數小于前面每個子段中的投影區間數，且前面的每個投影子段包含的投影區間數應相同)。

1.2 算法改進
　    隨著虛擬場景的實時更新，如果每次都用希爾排序法對所有包圍盒實時排序，會消耗大量的時間，從而降低算法的效率。如圖2所示，本文對比進行了改進，使用了排序效率更高的堆排序法對某一軸上的投影序列排序，并將初次劃分后投影子段(該文中稱之為“組”)的邊界固定，之后將運動對象更新后包圍盒的投影值與之前包圍盒所在組的邊界值進行比較，如果仍在邊界之內，則繼續留在本組內，否則，與下一組的邊界值比較，依次類推，直到找到新的歸屬組；然后在每組內使用堆排序法對投影值進行實時排序，快速排除沒有交疊的對象對；最后，對交疊的對象對(其中至少有一個對象是動態的)進行相交測試。其實，在很短的時間間隔內包圍盒的位移量是有限的，因此，包圍盒分組時往往只要與本組及相鄰組進行比較即可。這樣隨著場景的實時更新，很可能某些組所包含的對象全部都是靜態的，因而整個組都可以不用進行相交測試了。即：相交測試只在有動態對象存在的組內進行，這大大提高了檢測的效率。

　該算法需要注意以下問題：(1)當某一包圍盒的一部分已進入新的投影子段，而另一部分仍然留在原投影子段時(如圖2中虛線框圖所示)，包圍盒在兩個投影子段所屬組都需參與碰撞檢測。并且當某兩個相交對象在坐標軸劃分階段都被分為兩個部分、當對兩個對象左邊部分對應的x軸和y軸子列表進行相交測試時，已經知道兩對象重疊，算法就不再對兩個對象的右邊部分的投影進行相交測試，從而減少了算法的執行時間。(2)如果場景中有體積非常大的物體，在執行碰撞檢測之前必須先將物體分解為體積較小的子塊，再將各子塊分別進行碰撞測試。
1.3 新算法描述
    由于游戲場景中幾何物體的形狀各異，不同對象用不同的包圍盒來近似模擬時會出現截然不同的效果，不合理使用包圍盒會使碰撞檢測效率大幅降低。例如，一個球體如果用AABB來模擬，會出現較大的誤差；而一個長條形物體用包圍球模擬，碰撞檢測的精度也會很差。一種好的碰撞檢測系統應該根據不同對象的形狀特征提供不同的解決方案。因此，本文用包圍球來模擬近似球狀的對象，其余的對象都用AABB代替參與相交測試,并將上述改進后的包圍盒投影排序分組算法應用在該算法中，從而快速完成場景的碰撞檢測。
    整個算法的執行過程是：首先對包圍球和AABB投影排序并分組，這樣可以迅速排除不可能發生碰撞的對象對；然后，對各組中的潛在碰撞檢測集進行相交測試，即最終的碰撞檢測就轉化為球與球的相交測試、球與AABB的相交測試以及AABB間的相交測試。
2 包圍盒間的相交測試
    包圍球之間的相交測試很容易實現，只需根據球心之間的距離和兩球的半徑之和的差值就可以判斷相交情況。兩個AABB相交，則它們在3個坐標軸上的投影也必然相交，因此，AABB間的相交測試完全可以轉化為坐標軸上投影區間的相交測試，只要有一個軸上的投影不相交，就可以直接判定兩包圍盒不相交，從而結束相交測試。
    包圍球與AABB的相交測試，如果使用常規的幾何分析方法會非常復雜。一類簡單可行的方法是求取包圍球到AABB的最近距離點對，但如果使用常規的暴力遍歷算法來求解幾何體之間的最近點對，效率太低。而Lin- Canny算法求解凸包間的最近點對是非常高效的。Lin-Canny算法高效實現的關鍵是引入了Voronoi域的思想,通過遍歷AABB的Voronoi特征域獲取球心在某一特征(頂點、邊或面)上的投影點，這個投影點就是AABB到球心的最近點，再求出這個最近點到球心的距離并與包圍球的半徑(實際使用平方值)進行比較，如果這個距離小于半徑，則包圍球與AABB相交；否則，不相交。
    如圖3所示，假設P為球心位置，A為AABB，A包圍盒中頂點Q的Voronoi域、邊MQ的Voronoi域和面S的Voronoi域分別如圖中不同顏色所示。則A上到P的最近點可以通過下面的方法獲得：在某一軸上將P限定在A的邊界上。存在3種限定P的情況：(1)如果P點位于A的某表面的Voronoi域，則截取操作將P限定在A的該表面上; (2)如果P點位于A的某頂點的Voronoi域，則截取操作將視該頂點為所求點; (3)如果P點位于A的某邊的Voronoi域，則截取操作為該邊上的正交投影。其偽代碼實現如下：

　    /*p為球心，a為AABB*/
Point  findNearestDistancePoint(Point p,
                         AABBBox a)
{
    Point  q;                                      /*所求點q*/
    for(int i=0;i<3;i++)
    {
        float v=p[i];
        if(v小于a在某一軸上投影的最小值)
            v=這個最小值;
        if(v大于a在某一軸上投影的最大值)
            v=這個最大值;
        q[i]=v;
    }
    end for;
    return q;                                            /*返回q點*/
}
3 實驗結果及分析
    在小米M1手機上實現該算法,其系統為Android OS 4.0；CPU為高通驍龍MSM-8260(雙核)1.5 GHz；GPU為Adreno220；RAM為1 GB；圖形API接口為OpenGL ES 2.0。首先，在多個包含不同對象個數的場景中，將改進算法與參考文獻[5]中的算法(只進行包圍盒相交測試，省去了葉子節點的相交測試)進行比較，結果如圖4所示。再將改進后的包圍盒投影排序分組方法應用到包圍球算法和AABB算法中，并與本文提出的新算法進行對比分析，結果如表1所示。

    由于用堆排序法替代了希爾排序法，并將靜態包圍盒的分組固定，只實時更新動態包圍盒的組別，隨著包圍盒數量的不斷增加,改進算法比參考文獻[5]中的算法效率更高。尤其是當場景越來越復雜時，改進算法完成碰撞檢測所需的時間并沒有明顯地增加，具有更加優越的實時性能。 通常游戲場景所需的最低幀率一般為20 f/s~30 f/s。本文算法在保證了更高精度的前提下仍能與包圍球算法和AABB算法一樣滿足復雜場景的實時性需求。
    針對Android手持終端的復雜游戲場景的需求，本文在I-Collide算法庫及其改進算法的基礎上，提出了一種基于包圍球和AABB層次包圍盒的碰撞檢測算法。把傳統的基于AABB的投影排序法應用在該算法中并進行優化，從而排除了大量不可能相交的對象對，提高了算法的實時性。但該算法沒有對變形體或旋轉體的包圍盒重構提出快速的解決方案，有待在以后的研究中解決這些問題。隨著嵌入式芯片的高速發展和實際應用的需要，以后的研究中還應該考慮使用OBB[1]或k-DOPs[1]等更加緊密的包圍盒算法或基于GPU的碰撞檢測算法[6]及其他的精確碰撞檢測算法來滿足各種場合的苛刻需求。
參考文獻
[1] 鄒益勝，丁國富，許明恒，等.實時碰撞檢測算法綜述[J].計算機應用研究，2008,25(1)：8-12.
[2] 董峰，王同洋.虛擬環境中的快速碰撞檢測算法[J].計算機工程與應用，2003,39(8)：66-67.
[3] Lin Ming, CANNY J. A fast altorithm for incremental distance calculation[C].Proceedings of the 1991 IEEE International Conference on Robotics and Automation，1991:1008-1014.
[4] COHEN J D， LIN M C， MANOCHAL D. I-CoLLIDE： an  interactive and exact collision detection system for largescale environments[C]. Proceedings of ACM Interactive 3D Graphics Conference，1995:189-196.
[5] 王曉榮，王萌，李春貴.基于AABB包圍盒的碰撞檢測算法[J].計算機工程與科學，2010，32(4)：59-61.
[6] Tang Min，MANOCHA D，Jiang Lin，et al. Collisionstreams：fast GPU-based collision detection for deformable models[M].ACM SIGGRAPH Symposium on Interactive 3D Graphics  and  Games (I3D)，2011:63-70.