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