??? 摘 要：在動(dòng)態(tài)場(chǎng)景中，碰撞檢測(cè)遇到的最明顯的問題就是需要對(duì)N個(gè)物體對(duì)進(jìn)行兩兩求交測(cè)試，其時(shí)間復(fù)雜度達(dá)到O(N2)。提出了一種簡(jiǎn)化球體的BSP剖分結(jié)構(gòu)的快速碰撞檢測(cè)算法。首先用一種調(diào)度算法估計(jì)BSP樹開始失衡的地方，再用一種策略來選擇分割面，新結(jié)構(gòu)在表示動(dòng)態(tài)場(chǎng)景中不需要重新構(gòu)建樹，而是在保持樹的平衡和合理的高度的同時(shí)通過自身的調(diào)節(jié)來達(dá)到更新。
??? 關(guān)鍵詞：碰撞檢測(cè)；動(dòng)態(tài)場(chǎng)景；BSP樹
?
??? 在動(dòng)態(tài)場(chǎng)景的模擬中，當(dāng)場(chǎng)景中物體的個(gè)數(shù)超過2個(gè)，碰撞檢測(cè)遇到的最明顯的問題就是需要對(duì)所有N個(gè)物體進(jìn)行兩兩求交檢測(cè)，其時(shí)間復(fù)雜度達(dá)到O(N2)。為此，加快這種檢測(cè)速度通常是用兩步算法[1]。所謂兩步法，就是在第一步(也稱初步檢測(cè)階段)，首先將多數(shù)明顯不相交的物體對(duì)進(jìn)行快速排除，找出潛在的相交區(qū)域或潛在的相交物體對(duì)；然后在第二階段根據(jù)已經(jīng)確定的潛在的相交區(qū)域或潛在的相交物體對(duì)幾何做進(jìn)一步的相交測(cè)試，這一步也稱詳細(xì)檢測(cè)階段。在處理動(dòng)態(tài)場(chǎng)景初步檢測(cè)時(shí)，BSP樹算法在快速排除明顯不發(fā)生碰撞的物體不夠理想，為此本文提出了一種基于BSP結(jié)構(gòu)的快速碰撞檢測(cè)算法。該算法是在BSP樹結(jié)構(gòu)的更新操作時(shí)，定義了5種操作算子，并通過一種調(diào)度策略執(zhí)行算子，保持BSP樹結(jié)構(gòu)的平衡。
1 BSP樹的構(gòu)建
??? BSP樹是最常用的空間剖分技術(shù)，F(xiàn)uchs 于1980 年首次將BSP技術(shù)中剖分平面的定側(cè)性質(zhì)應(yīng)用于多邊形場(chǎng)景的剖分[2]，BSP 樹是一個(gè)用來對(duì) n維空間內(nèi)多面體進(jìn)行排序和查找操作的標(biāo)準(zhǔn)的二叉樹。這個(gè)樹代表了整個(gè)場(chǎng)景，每一個(gè)葉節(jié)點(diǎn)代表著場(chǎng)景的1個(gè)凸集多邊形集合，每一個(gè)非葉節(jié)點(diǎn)包含一個(gè)分割平面，這個(gè)分割平面將1個(gè)子場(chǎng)景分成2個(gè)更小的場(chǎng)景。BSP 樹的構(gòu)造是這樣一個(gè)過程，已有一個(gè)子場(chǎng)景，用這個(gè)場(chǎng)景中1個(gè)多邊形所在的平面從內(nèi)部分割這個(gè)場(chǎng)景，結(jié)果又得到2個(gè)子場(chǎng)景然后繼續(xù)循環(huán)分割它們，直到所有子場(chǎng)景都是一個(gè)凸集多邊形集合為止。BSP樹就是一個(gè)二叉樹，葉節(jié)點(diǎn)存儲(chǔ)場(chǎng)景多邊形，非葉節(jié)點(diǎn)存儲(chǔ)分割面。圖1所示，為二維平面上的BSP樹結(jié)構(gòu)剖分。
?
??? BSP在計(jì)算碰撞檢測(cè)時(shí)有巨大的優(yōu)勢(shì)，它能夠很容易定位運(yùn)動(dòng)物體在BSP樹的具體位置，即場(chǎng)景中的具體位置。定位完成后，只有很少數(shù)目的多邊形需要檢測(cè)，即每一幀里只檢測(cè)物體是否穿過那些組成它所在葉節(jié)點(diǎn)的多邊形[3-4]。
2 簡(jiǎn)化球體BSP剖分結(jié)構(gòu)的分割面選取策略
??? 當(dāng)創(chuàng)建一個(gè) BSP 樹時(shí)，決定是否需要一個(gè)平衡樹，也就是說樹的左右分支的深度的差異不應(yīng)該太大，由于每一次分割都會(huì)產(chǎn)生新的多邊形，因此應(yīng)盡量減少分割的次數(shù)。如果在 BSP 樹的創(chuàng)建過程中產(chǎn)生了太多的新多邊形，顯示卡就要花更多的時(shí)間來處理多邊形的渲染，使一個(gè)不平衡的樹將用更長(zhǎng)的時(shí)間來進(jìn)行樹的遍歷。因此在選擇分割面時(shí)，應(yīng)該根據(jù)下面的標(biāo)準(zhǔn)(p為分割面) ：
??? population(p)由分割面所生成節(jié)點(diǎn)所包含物體的數(shù)目。
??? balance(p)被分割面分割成的左右子樹深度的比率。
??? redundancy(p)橫跨分割面的物體的數(shù)目。
??? 即在選擇分割面時(shí)，需要綜合考慮以上3個(gè)條件，選擇balance最大、redundancy最少的分割面。
????分割面的選取方法一般采用直接選擇平面法，是指從表示場(chǎng)景的多邊形集合中隨機(jī)選出一個(gè)多邊形，假定該多邊形在空間范圍內(nèi)無限延展，則平面將空間分成了2個(gè)子空間。在各自2個(gè)子空間內(nèi)，原有的場(chǎng)景多邊形分別位于其中，對(duì)于某一子空間，再從其中的多邊形集合中任意選取1個(gè)，作為該子空間的超平面。這一過程遞歸進(jìn)行，直到最終的子空間中只有唯一的景物為止。圖2給出了這一過程的圖形示意。
?
??? 圖2中，把各線段看作是垂直于紙面的平面，箭頭為該平面的法向量，箭頭所指方向?yàn)樵撈矫娴那懊?可見一側(cè))，其相反方向即為該平面的后面(不可見一側(cè))。圖2(a)給出了初始的場(chǎng)景多邊形集合以及每個(gè)多邊形的法向量，在圖2(b)中，首先選取面1為分割面，將空間分為A, B兩個(gè)子空間；在B子空間中選取面4為分割面，將B分為C, D兩個(gè)子空間；在D子空間中選取面2為分割面，將D分為E、F兩個(gè)子空間。至此，整個(gè)空間劃分完畢，每個(gè)子空間中只含有一個(gè)景物。
3 簡(jiǎn)化球體BSP剖分結(jié)構(gòu)的更新操作
??? 由于要保持動(dòng)態(tài)物體在動(dòng)態(tài)場(chǎng)景中的高效率的運(yùn)動(dòng)和一定的搜索特性，導(dǎo)致了BSP樹結(jié)構(gòu)的改變。如果重新構(gòu)造樹，額外的開銷將嚴(yán)重影響碰撞檢測(cè)的效率，因此，希望在原來樹的基礎(chǔ)上通過局部更新得到新的樹。在這種情況下，更新樹的過程時(shí)間開銷就相當(dāng)重要，如果更新樹所花費(fèi)的時(shí)間和完全重建差不多，更新就沒有什么意義了。更新操作必須能夠?qū)崟r(shí)完成。本文采用的方法是根據(jù)動(dòng)態(tài)物體的物理位置把它插入到BSP樹的相應(yīng)節(jié)點(diǎn)下，用BSP樹邏輯操作修改BSP樹的結(jié)構(gòu)。下面將介紹是如何被調(diào)度來執(zhí)行更新的。
3.1 分裂操作算子
??? 當(dāng)葉節(jié)點(diǎn)包含物體數(shù)量(population)大于給定的葉節(jié)點(diǎn)包含物體數(shù)量的閾值時(shí)，將該節(jié)點(diǎn)向下分裂，如圖3所示。這樣，一個(gè)新的分割面產(chǎn)生1個(gè)節(jié)點(diǎn)，同時(shí)生成兩個(gè)左右子樹。對(duì)于產(chǎn)生內(nèi)部節(jié)點(diǎn)的分割面的選取按照上一部分提到的分割面的選擇方法。對(duì)物體在候選分割面法線上的投影進(jìn)行分類支配著這個(gè)操作的開銷，為了減少這種開銷只考慮這些物體1個(gè)子集。
?
?
3.2 移除分裂操作算子
??? 這個(gè)操作通過用存儲(chǔ)在BSP樹中的葉結(jié)點(diǎn)的信息來降低因分類而導(dǎo)致的使用分裂操作的開銷。
??? 在BSP樹的構(gòu)造過程中，每個(gè)葉節(jié)點(diǎn)將被整個(gè)放入表中。也就是從根節(jié)點(diǎn)(內(nèi)節(jié)點(diǎn))開始在節(jié)點(diǎn)上沿著它的父分割面的法線放置物體。在這張表中可以找出另一個(gè)法線方向與父分割面法線方向相平行的分割面。如果這個(gè)新的分割面滿足分割面選擇標(biāo)準(zhǔn)，就可以用移除分裂操作來代替分裂操作，如圖4所示。
?
?
3.3 合并操作算子
??? 合并操作算子的作用是：當(dāng)一個(gè)葉節(jié)點(diǎn)連同它的兄弟所含物體數(shù)量之和還沒超過閾值時(shí)，將它們向上合并。而且當(dāng)由于物體的運(yùn)動(dòng)使分割面分割的區(qū)域出現(xiàn)空值時(shí)，它負(fù)責(zé)重新移動(dòng)此分割面，(如圖5)。
?
?
??? 所有存儲(chǔ)在合并節(jié)點(diǎn)的子樹的葉節(jié)點(diǎn)的物體的有序表需要合并成一個(gè)。左右子樹的節(jié)點(diǎn)自下而上合并，并且葉子節(jié)點(diǎn)代替原來的節(jié)點(diǎn)，如圖6所示。每一個(gè)表需要沿著新的方向分類。當(dāng)合并節(jié)點(diǎn)包含物體數(shù)量很少時(shí)，合并節(jié)點(diǎn)的子樹通常也很小。
?
?
3.4 平衡操作算子
??? 平衡操作算子的作用是：在原來樹的基礎(chǔ)上通過最小的改變來修復(fù)開始變得不平衡的節(jié)點(diǎn)。它適合于左右子樹的深度差異很大的節(jié)點(diǎn)，即1個(gè)節(jié)點(diǎn)的1個(gè)子樹所含物體數(shù)量很多而另一個(gè)子樹幾乎是空的。在這種情況下，利用平衡操作來取代合并子樹操作，并通過移動(dòng)分割面重新建立平衡，如圖7所示。如果這個(gè)移動(dòng)的分割面滿足選擇分割面的標(biāo)準(zhǔn)，可利用平衡操作來修改這個(gè)節(jié)點(diǎn)。
?
?
3.5 交換操作算子
??? 交換操作算子的作用是：它適合于當(dāng)平衡操作失敗于重新建立平衡時(shí)的情況，在合并操作之前使用交換操作。交換操作刪除不平衡的節(jié)點(diǎn)，用包含物體數(shù)量多的子樹的根節(jié)點(diǎn)代替刪除的不平衡節(jié)點(diǎn)結(jié)構(gòu)的調(diào)整所需要的只是將包含物體數(shù)量少的子樹插入，但這個(gè)操作很快，因?yàn)檫@個(gè)子樹幾乎是空的，如圖8所示。
?
?
4 簡(jiǎn)化球體BSP剖分結(jié)構(gòu)更新操作調(diào)度策略
??? BSP樹結(jié)構(gòu)的更新不同于物體位置的更新，因?yàn)闃浣Y(jié)構(gòu)更新的時(shí)間開銷很大，而且結(jié)構(gòu)更新的好壞會(huì)導(dǎo)致碰撞檢測(cè)對(duì)數(shù)目的增減，如果結(jié)構(gòu)更新失敗就會(huì)導(dǎo)致碰撞檢測(cè)對(duì)數(shù)目的增加。定義的更新是在規(guī)定時(shí)間間隔內(nèi)達(dá)到一個(gè)折中，即在更新的時(shí)間開銷和樹的高度之間。結(jié)構(gòu)操作執(zhí)行的時(shí)間順序是至關(guān)重要的。更新BSP樹結(jié)構(gòu)的結(jié)構(gòu)操作的調(diào)度策略說明如下：。
??? 平衡操作是通過調(diào)整分割面來改善平衡，但是它會(huì)產(chǎn)生改變物體分布的副作用。這可能影響其他操作，在某些情況下可能變得不必要了。因此，在其他操作之前應(yīng)該先考慮平衡操作，如圖9所示。
?
?
??? 分裂操作是非常關(guān)鍵的，因?yàn)樗且?個(gè)大的存放物體信息的順序表分成2個(gè)小表，以降低更新順序表的代價(jià)。首先是集中在所包含物體數(shù)量小于閾值的葉節(jié)點(diǎn)上，也就是通過對(duì)場(chǎng)景中的物體數(shù)量動(dòng)態(tài)調(diào)整葉節(jié)點(diǎn)。而移動(dòng)分裂操作是在分裂操作之前執(zhí)行，也就是只有當(dāng)移動(dòng)分裂操作失效時(shí)才開始執(zhí)行分裂操作。
??? 當(dāng)平衡操作失效時(shí)，交換操作開始執(zhí)行。這個(gè)操作也如同平衡操作一樣會(huì)產(chǎn)生副作用，通常導(dǎo)致小數(shù)量的物體移動(dòng)。
??? 合并操作是消除包含物體數(shù)量小于閾值的葉節(jié)點(diǎn)。這個(gè)操作不是很重要，因?yàn)閷?duì)于小的順序表的維持是很快的，而且額外的開銷是保持幾乎是空的節(jié)點(diǎn)和最小限度的葉節(jié)點(diǎn)。只有當(dāng)在模擬的更新周期期間有自由的時(shí)間，這個(gè)操作才會(huì)被執(zhí)行。
??? 更新BSP樹結(jié)構(gòu)的結(jié)構(gòu)操作調(diào)度策略如下：
??? 開始遍歷根節(jié)點(diǎn)為N的BSP樹：
??? (1) If 節(jié)點(diǎn)N是不平衡節(jié)點(diǎn)；
????(2) then評(píng)估平衡操作算子；
??? (3) If 平衡算子有效執(zhí)行平衡操作；
??? (4) Else 調(diào)用交換算子；
??? (5) 停止遍歷；
??? (6) End if ；
??? (7) 檢查移動(dòng)分裂操作，分裂操作，合并操作和調(diào)度時(shí)間表；
??? (8) if 所有事件已調(diào)度，停止遍歷；
??? (9) Else 重復(fù)執(zhí)行1～8步遍歷節(jié)點(diǎn)N的每個(gè)子樹；
??? (10) End if；
??? (11) 根據(jù)調(diào)度時(shí)間表估算被執(zhí)行的事件數(shù)目；
??? (12) 執(zhí)行移動(dòng)分裂操作；
??? (13) 執(zhí)行分裂操作；
??? (14) 執(zhí)行交換分裂操作；
??? (15) 執(zhí)行合并分裂操作。
5 實(shí)驗(yàn)結(jié)果與分析
??? 為了驗(yàn)證BSP算法的性能，與QT quad(tree)，Spatial Hash(SH)、LO loose(octrees)，SP sweep-and-(prune)這4種算法進(jìn)行了一系列比較實(shí)驗(yàn)。所有的實(shí)驗(yàn)都是在PIV2.5GHz、512MB內(nèi)存的PC機(jī)上進(jìn)行的。
??? 每個(gè)模擬實(shí)驗(yàn)按每秒25步被評(píng)估4 min。實(shí)驗(yàn)評(píng)估包括執(zhí)行效率(FPS)，碰撞檢測(cè)對(duì)的數(shù)目，初步碰撞檢測(cè)階段的時(shí)間，更新的時(shí)間(物體位置的更新時(shí)間和數(shù)據(jù)結(jié)構(gòu)的更新時(shí)間)。
??? 實(shí)驗(yàn)物體落入有限制的區(qū)域中，然后跟區(qū)域中的其他物體相互碰撞，這是利用了動(dòng)態(tài)和靜態(tài)物體之間的空間分割方法。因?yàn)殪o態(tài)物體對(duì)于提高執(zhí)行速度是至關(guān)重要的。這種情景最適合BSP。BSP的碰撞檢測(cè)時(shí)間最少，QT次之。SP的碰撞檢測(cè)時(shí)間最壞但是更新時(shí)間跟BSP差不多。LO更新時(shí)間最佳。SH的更新時(shí)間最壞。
??? 實(shí)驗(yàn)測(cè)試結(jié)果分別如 圖10、圖11、圖12、圖13所示。
?
?
?
?
?
??? 本文所介紹的方法主要目的是當(dāng)碰撞檢測(cè)對(duì)數(shù)目增加時(shí)，在計(jì)算碰撞檢測(cè)對(duì)的代價(jià)和在空間數(shù)據(jù)結(jié)構(gòu)中的結(jié)構(gòu)更新代價(jià)兩者之間建立一個(gè)折中的方法。實(shí)驗(yàn)結(jié)果表明，在初步碰撞檢測(cè)階段與SH、SP和LO方法相比，本文的方法是很有效的。雖然在碰撞檢測(cè)對(duì)數(shù)目上與QT相似，但與QT相比，文中的方法對(duì)靜態(tài)物體導(dǎo)致的空間分割模擬或者是高度集中的環(huán)境中產(chǎn)生太多碰撞的模擬是比較好的。文中各個(gè)更新BSP樹結(jié)構(gòu)的結(jié)構(gòu)操作和調(diào)度策略的設(shè)計(jì)可以更好地重新利用存儲(chǔ)在樹中的信息來重新定位分裂面和穩(wěn)定的執(zhí)行效率。初步碰撞檢測(cè)只是這種方法的一個(gè)應(yīng)用，用這種方法來加快其他幾何體的碰撞是今后要研究的另一個(gè)方面。
參考文獻(xiàn)
[1] HUBBARD P M. 1995. Collision detection for interactive graphics applications. IEEE Transactions on Visualization and Computer Graphics, 1995, 1(3): 124-133.
[2] ?FUCHS H, KEDEM Z M,NAYLOR B F. H1 On visible surface generation by a priori tree structure [J]. Computer Graphics ,1980 , 14 (3) : 124-133.
[3]?AR S, MONTAG G, TAL A. Deferred, self-organizing BSP trees. Computer Graphics Forum, 2002, 21(3): 269-278.
[4]?JAMES D L, PAI D K. BD-Tree: Output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics (SIGGRAPH), 2004, 23(3).