摘 要： 針對(duì)Android手持終端中復(fù)雜游戲場(chǎng)景的碰撞檢測(cè)需求，提出了一種基于包圍球和AABB的實(shí)時(shí)碰撞檢測(cè)算法。該算法針對(duì)不同的虛擬對(duì)象構(gòu)建不同的包圍盒，并將改進(jìn)后的包圍盒投影排序分組方法應(yīng)用其中。將該算法與使用包圍盒投影排序分組方法的包圍球算法與AABB算法比較,實(shí)驗(yàn)表明,該算法在保持更高精度的前提下仍能滿足復(fù)雜場(chǎng)景中實(shí)時(shí)碰撞檢測(cè)的要求。
關(guān)鍵詞： Android ；碰撞檢測(cè)；包圍球；AABB

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

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

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

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

    由于用堆排序法替代了希爾排序法，并將靜態(tài)包圍盒的分組固定，只實(shí)時(shí)更新動(dòng)態(tài)包圍盒的組別，隨著包圍盒數(shù)量的不斷增加,改進(jìn)算法比參考文獻(xiàn)[5]中的算法效率更高。尤其是當(dāng)場(chǎng)景越來(lái)越復(fù)雜時(shí)，改進(jìn)算法完成碰撞檢測(cè)所需的時(shí)間并沒(méi)有明顯地增加，具有更加優(yōu)越的實(shí)時(shí)性能。 通常游戲場(chǎng)景所需的最低幀率一般為20 f/s~30 f/s。本文算法在保證了更高精度的前提下仍能與包圍球算法和AABB算法一樣滿足復(fù)雜場(chǎng)景的實(shí)時(shí)性需求。
    針對(duì)Android手持終端的復(fù)雜游戲場(chǎng)景的需求，本文在I-Collide算法庫(kù)及其改進(jìn)算法的基礎(chǔ)上，提出了一種基于包圍球和AABB層次包圍盒的碰撞檢測(cè)算法。把傳統(tǒng)的基于AABB的投影排序法應(yīng)用在該算法中并進(jìn)行優(yōu)化，從而排除了大量不可能相交的對(duì)象對(duì)，提高了算法的實(shí)時(shí)性。但該算法沒(méi)有對(duì)變形體或旋轉(zhuǎn)體的包圍盒重構(gòu)提出快速的解決方案，有待在以后的研究中解決這些問(wèn)題。隨著嵌入式芯片的高速發(fā)展和實(shí)際應(yīng)用的需要，以后的研究中還應(yīng)該考慮使用OBB[1]或k-DOPs[1]等更加緊密的包圍盒算法或基于GPU的碰撞檢測(cè)算法[6]及其他的精確碰撞檢測(cè)算法來(lái)滿足各種場(chǎng)合的苛刻需求。
參考文獻(xiàn)
[1] 鄒益勝，丁國(guó)富，許明恒，等.實(shí)時(shí)碰撞檢測(cè)算法綜述[J].計(jì)算機(jī)應(yīng)用研究，2008,25(1)：8-12.
[2] 董峰，王同洋.虛擬環(huán)境中的快速碰撞檢測(cè)算法[J].計(jì)算機(jī)工程與應(yīng)用，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包圍盒的碰撞檢測(cè)算法[J].計(jì)算機(jī)工程與科學(xué)，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.