三維視景仿真的包圍盒碰撞檢測算法優化

李成景，王 潔 ，肖強明，施冬健 ，2

（1.空軍工程大學 導彈學院，陜西 三原 710038；2.95196部隊，廣東 清遠 513000）

0 引言

近年來，隨著三維視景仿真的發展，碰撞檢測問題成為一項重要課題，廣泛應用于教育、國防、醫學等多個領域。精確的碰撞檢測對于如何準確、快速地表現虛擬場景中物體的運動規律和相互關系，保證仿真環境的逼真度有著至關重要的作用。而虛擬環境的復雜性和實時性也要求碰撞檢測具有很高的效率。如何保證精確并短時間內完成碰撞檢測實際上成為了實時仿真系統的瓶頸之一[1]。目前，國內外研究人員已對虛擬環境下三維視景仿真的碰撞檢測進行了深入的研究，并形成一些較為成熟的算法[2]。其中，層次包圍盒方法在碰撞檢測算法中被廣泛使用，一般分為全局搜索與局部檢測兩個階段。

層次包圍盒方法在全局搜索階段快速排除多數明顯不相交的對象對。在局部檢測階段，首先會遍歷對象對的層次包圍盒樹，逐一檢測節點之間是否相交，直到葉節點，以保證能夠精確地檢測葉節點中所包圍的多邊形面片是否相交。常用的包圍盒中，軸向包圍盒（Axis Aligned Bounding Boxes，AABB）的優勢在于構造簡單，相交測試和包圍盒更新迅速，在實際中經常被使用。目前常采用AABB的碰撞檢測庫主要有I-Collide[3]和Q-Col?lide[4]。I-Collide用于大量運動體間的碰撞檢測，Q-Col?lide是對其改進，當檢測的幾何模型復雜時，I-Collide會大大提高效率。此外，通用的碰撞檢測系統SOLID[5]涉及了模型變形，可適用于變形體間的碰撞檢測。I-Collide算法利用包圍盒排序法來優化全局搜索過程，文獻[6]提出了對排序的改進方法。SOLID算法的局部檢測過程采用AABB樹進行精確的碰撞檢測。本文將利用時空相關性來改進全局搜索過程，并從相交判斷算法的角度進行優化，減少執行時間，提高算法效率。

1 碰撞檢測優化算法

本文對全局搜索與局部檢測兩個階段分別進行分析，在時空相關性，從相交測試算法兩方面對算法進行優化。

1.1 全局搜索過程

1.1.1 傳統包圍盒算法全局搜索過程

在虛擬現實仿真中，傳統包圍盒法[2]是把復雜的幾何對象包裹起來，在進行碰撞檢測時，首先進行包圍盒之間的相交測試，如果相交，則進行幾何對象之間精確的碰撞檢測。設虛擬仿真場景中有N個運動對象和M個靜止對象，該算法實際上是對（N/2+NM）個對象對分別進行檢測，復雜度為O(n2)，并且鑒于AABB的矩形包圍盒與包圍對象之間往往存在較大空隙，該算法搜索的結果并不是真正的相交，加大了局部檢測情況的復雜度。例如，兩個幾何對象的AABB包圍盒在XOY平面的投影如圖1所示，盡管包圍盒相交，但是兩個對象之間并沒有相交，使用基本的包圍盒算法時，將會繼續進行精確的碰撞檢測。此時，由于誤判導致了無謂的計算，影響算法效率。

1.1.2 包圍盒樹的構建

在從眾多對象中排除不可能相交的對象后，碰撞檢測算法會對可能相交的對象對進行精確的碰撞檢測。這就需要為對象建立層次包圍盒，即包圍盒樹。一個幾何對象的包圍盒是包含該對象的一個簡單的幾何體。對組成對象的基本元素（在本文研究環境下，即為三角形）的集合構造包圍盒樹一般分為自頂向下和自底向上兩種方法。自頂向下的方法在碰撞檢測中較常使用，計算成熟，因此本文以此種劃分方法為基礎進行分析。

該方法選擇根節點為全集S，對這個節點進行劃分以形成其子節點，直到到達葉節點（基本組成元素）。由于二叉樹的相對優勢，在通常情況下，選擇的包圍盒樹都為二叉樹。該方法構造包圍盒樹，實際上就是將全集的子集合SV以數目為2劃分子集，直到不可劃分的基本幾何元素為止。

1.1.3 改進的全局搜索過程

為了改善復雜度O(n2)，就需要對場景中的對象進行全局優化搜索，排除當前幀不可能發生碰撞的對象行，只對可能碰撞或上一幀已碰撞的情況進行考察，提高檢測效率。針對此思路，本文在包圍盒樹的根節點處增加Cache字段來存放檢測結果（Cache字段包括Cache1和Cache2，分別存儲碰撞記錄和發生碰撞的幾何信息，Cache1以堆棧形式存儲固定幀數內的碰撞信息，Cache2實時更新），在本幀的全局搜索階段，利用上一幀或前幾幀局部碰撞檢測的結果快速進行碰撞搜索，避免了不必要的碰撞測試，優化了全局搜索過程。

在實時繪制的虛擬環境中，幀與幀之間具有很強的關聯性，運動對象的位置和狀態不可能急劇變化，比如虛擬手的操作，這就意味著物體從一幀變化到另一幀時是相對靜止的。因此，當兩個虛擬對象之間發生碰撞時，很可能下一幀中在這兩個對象之間發生新的碰撞。測試碰撞時可以首先測試上一幀發生碰撞的地方，同時把上一幀發生碰撞的相關信息緩存在其Cache中，供本次測試使用。改進算法全局搜索的具體步驟為：

1）將場景中對象按序編號，進行活動對象的相交測試。若包圍盒相交，則把編號大的對象放入編號小的對象Cache1中。

2）檢查運動對象的Cache1字段，若為空，進行下一對象的檢測。

3）檢測該對象Cache2中是否有相關碰撞的信息。若能檢測到對象間的碰撞信息，則直接構造包圍盒樹，對上次發生碰撞的幾何元素及其兄弟子樹進行檢測。否則，用傳統的層次包圍盒間的碰撞算法進行檢測。若無碰撞，進行下一對象檢測。

4）若檢測到碰撞，把碰撞信息覆蓋到Cache2中，并在Cache1中記錄當前碰撞。返回步驟2），繼續循環。

隨著碰撞次數的增加，Cache中存放的碰撞信息將會保證能夠較早檢測到碰撞，因此減少了參與搜索的包圍盒數，節省了檢測的時間，并且如果步驟3）中檢測到精確的碰撞信息，則可省去對該對象的局部精確檢測過程。

1.2 局部檢測過程

1.2.1 傳統包圍盒局部檢測過程

包圍盒方法在從眾多復雜的對象中排除不可能相交的對象后，將構造包圍盒樹，對可能相交的對象對進行進一步的碰撞檢測。傳統算法局部檢測過程的核心就是通過遍歷檢測對象的包圍盒樹，確定在當前兩個對象是否發生碰撞。算法用一個對象的包圍盒樹的根節點遍歷另一個對象的包圍盒樹，若能到達葉節點，再用該葉節點遍歷第一個對象的包圍盒樹，如果同樣能到達葉節點，則繼續進行基本元素的相交測試。如果兩個節點上的包圍盒不相交，就不需對其中的元素再做進一步的相交測試。

1.2.2 基于垂線的相交測試算法

傳統包圍盒法葉節點的遍歷過程主要是檢測碰撞雙方的AABB樹的葉節點與葉節點、葉節點與內部節點、內部節點與內部節點。若是葉節點相交，則顯然增加了時間開銷。本文提出的基于垂線的相交測試算法即為三角形與內部節點之間的快速測試算法。應用基于垂線的相交測試算法，可直接進行三角形與內部節點間的相交測試，省去兩葉節點包圍盒求交的計算過程，提高檢測效率。

基于垂線的相交測試算法是將待檢測的對象坐標平面進行投影，通過碰撞標志Flag（默認為0）的值，判斷物體模型是否發生了碰撞：Flag=1，發生碰撞；Flag=0，未發生碰撞。分別記為Flag1（XOY平面），Flag2（XOZ平面），Flag3（YOZ平面），當三者同時為1時，則Flag=1。設檢驗對象為A和B，基本步驟為：

1）對象A的三角形遍歷B內部節點包圍盒進行相交測試，若不相交，Flag=0，退出循環。

2）將三角形與B包圍盒在XOY軸投影，在相交區域內以等距作Y軸（或X軸）垂線，如圖2所示，計算等距線與物體投影線的交點個數。

3）若第n條垂線與兩物體的投影線只有一個交點，畫出兩條投影線的包圍矩形，減小區域。

4）若第n條垂線與物體A和物體B的投影線都有交點，分別記為PAi(x,yAi)和PBi(x,yBi)，其中i=1或2。判斷i的取值。（1）當i=1時。若yA1

5）若有Flagi=0，Flag=0，結束算法。否則算法轉到尚未檢測的坐標平面從步驟1）繼續判斷，若Flag1=Flag2=Flag3=1，Flag=1，結束算法。

1.2.3 優化算法描述

節點之間的相交測試流程程序如下：

2 三維視景仿真結果及分析

實驗使用通用SOLID軟件包，由Van den Bergen[5]研究并發布，采用AABB包圍盒法。將代碼修改為本文算法，在根節點增加Cache字段，并利用基于垂線的相交測試算法來簡化計算。在PC平臺（CPU為Pentium43.0 GHz，內存為1 Gbyte）構造立方體在有限空間內進行隨機運動的場景來測試算法的有效性。其中一個場景如圖3所示，其三角面數16 461，紅色立方體對表示發生碰撞。將本文的改進算法與SOLID軟件包提供的AABB包圍盒碰撞檢測算法進行對比測試。

三角面片數與平均檢測時間變化曲線如圖4所示，可以看出，隨著三角面片數的增加，優化算法的平均碰撞檢測時間較之傳統AABB算法碰撞檢測時間的上升緩慢，并且優勢愈見明顯，并且由于利用了時空相關性原理，在多運動物體碰撞檢測條件下更具優勢。實驗結果體現了該算法的優越性。

3 小結

本文針對層次包圍盒方法，利用時空關聯性，增加Cache字段存儲碰撞信息，優化全局搜索階段，并利用快速相交測試減少局部檢測的時間，提高了檢測速度。在多面片多運動對象的復雜場景中，改進效果更明顯。由仿真實驗可知，該算法有效可行，是一種效率較高的三維視景仿真碰撞檢測算法。

[1]李芙玲，張瑾.碰撞檢測技術研究[J].華北科技學院學報，2004（2）：71-73.

[2]LI C F，FENG Y T，OWEN D R J.SMB：collision detection based on temporal coherence[J].Computer Methods in Applied Mechanics and Engineering，2006，195：2252-2269.

[3]PONAMIG M，MANOCHA D，LIN M.Incremental algorithm for collision detection between polygonal models[J].IEEE Trans.Visualization and Computer Graphics，1997，3（1）：51-64.

[4]CHUNG K.An efficient collision detection algorithm for polytopes in virtual environments[EB/OL].[2011-02-21].http：//i.cs.hku.hk/GraphicsGroup/projects/collision/chung_thesis96.pdf.

[5]VAN DEN BERGEN G.Efficient collision detection of complex deformable models using AABB trees[EB/OL].[2011-02-21].http：//www.cs.cmu.edu/～djames/pbmis/etc/jgt98deform_AABB.pdf.

[6]董峰，王同洋.虛擬環境中的快速碰撞檢測算法[J].計算機工程與應用，2003（8）：66-67.