?????? 自從計算機游戲出現以來，程序員就不斷地想辦法來更精確地模擬現實世界。就拿乒乓游戲為例子（譯者：Pong—被譽為電子游戲的祖先，有幸見過一次：），能見到祖先做的游戲感覺真是爽啊，想看的可以到FTP上下載“地球故事”就可以看到了：），游戲中有一個象征性的小方塊（球）和兩支拍子，游戲者需要在恰當的時間將拍子移動到恰當的地點，將小球反彈回去。這個基本操作的背后（以現在的標準來看）就是最原初的碰撞檢測了。今天的游戲比“乒乓”要高級得多，并且基本上是基于3D的。3D游戲中的碰撞檢測比“乒乓”游戲里的要更加難實現。玩一些早期模擬飛行游戲的體驗向我們展現出糟糕的碰撞檢測是如何毀滅一個游戲的。當穿過一座大山的尖頂的時候仍然活著，感覺很不真實。即便是現在的一些游戲也還是有碰撞上的問題，許多玩家曾經失望地看著他們喜愛的英雄或女英雄的部分身體穿進了墻里。甚至更糟的是，許多玩家都有過這樣糟糕的體驗，就是被那些離得很遠的子彈或火箭擊中。因為游戲者們要求提升真實性，我們開發者就不得不絞盡腦汁想辦法讓我們的游戲世界盡可能地接近現實世界。
閱讀這篇文章前首先假設你對與碰撞檢測相關的幾何和數學知識已經有了基本的了解。在文章的最后，我將提供一些這方面的參考資料，以免你對它們感覺有點生疏。另外我還假設你已經讀過 Jeff Lander 的圖形專欄里關于碰撞檢測文章（“Crashing into the New Year,” ; “When Two Hearts Collide,”;和 “Collision Response: Bouncy, Trouncy, Fun,”）。我將首先進行一個大概的描述，然后快速地切入到核心內容里，通過這兩步從上至下地深入到碰撞檢測中。我將討論兩種類型的圖形引擎中的碰撞檢測：基于 portal 的和基于 BSP 的。每種引擎中多邊形的組織各不相同，因此在 world-object 型的碰撞檢測上存在很大的差別。而object-object 型的碰撞檢測絕大多數地方在上述兩種引擎里的是一樣的，主要看你是如何實現的了。當我們接觸到多邊形的碰撞檢測時，我們還會實驗如何將其擴展到我們學過的凸型物體上。
預覽
為了創建一個理想的碰撞檢測程序，我們不得不在開發一個游戲的的圖形管道的同時就開始計劃并創建它的框架。在項目的最后加入碰撞檢測是相當困難的。想在開發周期的末尾創建快速的碰撞檢測將很有可能會使整個游戲被毀掉，因為我們不可能使它能高效地運行。在好的游戲引擎中，碰撞檢測應該是精確、有效并且十分快速的。這些要求意味著碰撞檢測將要與場景的多邊形管理管道緊緊地聯系起來。這也意味著窮舉法將無法工作――今天的3D游戲中每幀處理的數據量很可能導致打格，當你還在檢測一個物體的各多邊形是否與場景中的其它多邊形碰撞時，時間已經過去了。
讓我們從基本的游戲引擎循環開始吧（列表1）。快速瀏覽這些代碼來得到碰撞檢測的相關策略。我們先假設碰撞沒有發生，然后更新物體的位置，如果發現發生了碰撞，我們將把物體移回原來的位置不允許它穿越邊界（或將物體銷毀或執行一些預防措施）。然而，這個假設太過簡單因為我們無法得知物體原來的位置是否仍然有效。你必須為這種情況設計一個方案（否則你可能會體驗到墜機或被子彈擊中的感覺――就是前面舉的例子）。如果你是一個熱心的玩家，你可能已經注意到了在一些游戲當中，當你挨著墻壁并試圖穿過去的時候，攝像機就開始震動。你正經歷的就是將主角移回原位的情況。震動是因為取了較大的時間片引起的。
Listing 1. Extremely Simplified Game Loop
while(1){
??? process_input();
??? update_objects();
??? render_world();
}
update_objects(){
??? for (each_object)
??????? save_old_position();
??? calc new_object_position
{based on velocity accel. etc.}
if (collide_with_other_objects())
??? new_object_position = old_position();
{or if destroyed object remove it etc.}
Figure?1.?Time?gradient?and?collision?tests.
但是我們的方法有缺陷，我們忘了在等式中加入時間。圖1告訴我們時間太重要了不能忘了它。即便物體在 t1 或 t2 時刻沒有發生碰撞，它仍有可能在 t 時刻穿過邊界（t1<t<t2）。這會在兩個連續幀中產生大幅度地跨越（就好象擊中了燃料室或其它類似的東西）。我們不得不找一個好的方法來解決這個問題。
我們可以把時間看成是第四維并將所有運算在4維空間中進行。然而這可能會讓運算變得十分復雜，所以我們會避開這些。我們還可以創建一個以 t1、t2時刻的物體為起始點的實心體，然后用它來與墻進行測試（見圖2）
Figure 2. Solid created from the space that an object spans over a given time frame.
一個簡單的方法就是創建一個凸殼來罩住兩個不同時刻的物體。這種方法效率低下可能會明顯地降低你的游戲速度。以其創建一個凸殼，還不如創建一個圍繞實心體的包圍盒。我們學習其它的技術后再回來討論這個問題。
有另一種比較容易執行但精度較低的方法，就是把給定的時間段分為兩分，然后測試時間中點的相交關系。我們還可以遞歸地依次測定各段的時間中點。這個方法比先前的方法要快得多，但不能保證能捕捉到所有的碰撞情況。
另一個暗藏著的問題是collide_with_other_objects()方法的實現――即判斷一個物體是否與場景中的其它物體相交。如果場景中有很多的物體，這個方法可能消耗很大。如果要判斷各物體與場景中其它物體是否相交，我們將不得不進行大概N選2次比較。因此比較次數會是N的平方次冪（或表示成O(N2)）。但我們可以用幾種方法來避免進行O(N2)對的比較。舉個例子，我們可以把場景中的物體分成靜態的（被撞物）和動態的（碰撞物――即使它的速度為0也行）。就好象房間中的墻壁是被撞物，而一個扔向墻壁的小球是碰撞物。我們可以創建兩棵獨立的樹（每一棵對應一類物體），然后測試那些物體可能會碰撞的樹。我們甚至可以對環境進行約定讓一些碰撞物之間不發生碰撞――比如我們不需要在兩顆子彈之間進行判斷。現在在繼續之前，（經過改進之后）我們可以說處理過程變得更加清晰了。（另一個減少場景中成對的比較的方法就是建立八叉樹。這已經超出了這篇文章的范圍，你可以在Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods文章中的For Further Info一節里讀到更多關于八叉的信息）。現在讓我們來看一下基于 Portal 引擎，了解為什么在這類引擎中一提到碰撞檢測就會那么痛苦。
Portal引擎和Object-Object型碰撞
基于 Portal 的引擎把場景或世界分割成較小的凸方形區域。凸方形區域很適合圖形管道因為它們能避免重繪現象。不幸的是，對碰撞檢測來說，凸方形區域會給我們帶來一些困難。在我最近的一些測試中，一個引擎中平均大約有400到500個凸方形區域。當然，這個數字會隨著不同的引擎而有所變化，因為不同的引擎使用不同的多邊形技術。而且多邊形的數目也會因場景的大小而有所不同。
判斷一個物體的多邊形是否穿過了場景中的多邊形產生的運算量可能會很大。一個最簡單的碰撞檢測法就是用球形來近似地表示物體或物體的一部分，然后再判斷這些包圍球是否相交。這樣我們僅僅需要測試兩個球體中心的距離是否小于它們的半徑合（這表示發生了碰撞）。如果我們是用中心點距離的平方和半徑合的平方進行比較，那更好，這樣我們可以在計算距離時除去拙劣的開方運算。但是，簡單的運算也導致了精確度的降低（見圖3）。
Figure 3. In a sphere-sphere intersection, the routine may report that collision has occurred when it really hasn’t.
但我們僅僅是將這個不太精確的方法做為我們的第一步。我們用一個大的球體代表整個對象，然后檢測它是否和其它的球體相交。如果檢測到發生了碰撞，那么我們就要進一步提高精度，我們可以將大的球體分割成一系列小的球體，并檢查與各小球體是否發生碰撞。我們不斷地分割檢查直到得到滿意的近似值為止。分層并分割的基本思想就是我們要盡可能達到適合需要的理想的情況。
Figure 4. Sphere subdivision.
用球體去近似地代表物體運算量很小，但在游戲中的大多數物體是方的，我們應該用方盒來代表物體。開發者一直用包圍盒和這種遞歸的快速方法來加速光線追蹤算法。在實際中，這些算法已經以八叉和AABB（axis-aligned bounding boxes）的方式出現了。圖5展示了一個AABB和它里面的物體。
Figure 5. An object and its AABB.
坐標軸平行（“Axis-aligned”）不僅指盒體與世界坐標軸平行，同時也指盒體的每個面都和一條坐標軸垂直。這樣一個基本信息就能減少轉換盒體時操作的次數。AABBs 在當今的許多游戲中都得到了應用，開發者經常用它們作為模型的包圍盒。再次指出，提高精度的同時也會降低速度。因為 AABBs 總是與坐標思平行，我們不能在旋轉物體的時候簡單地旋轉 AABBs --- 它們應該在每一幀都重新計算過。如果我們知道每個對象的內容，這個計算就不算困難并不會降低游戲的速度。 然而，我們還面臨著精度的問題。假如我們有一個3D的細長剛性直棒，并且要在每一幀動畫中都重建它的AABB。我們可以看到每一幀中的包圍盒的都不一樣而且精度也會隨之改變。
Figure 6. Successive AABBs for a spinning
rod (as viewed from the side).
所以以其用 AABBs，為什么我們不用任意方向能最小化空白區域的包圍盒呢。這是一種基于叫 oriented bounding boxes—OBBs 的技術，它已經廣泛用于光線追蹤和碰撞檢測中。這種技術不但比 AABBs 技術更精確而且還更健壯。但 OBBs 實現起來比較困難，執行速度慢，并且不太適合動態的或柔性的物體。特別注意的是當我們把一個物體分得越來越小的時候，我們事實上在創建一棵有層次的樹。
我們是選擇 AABBs 還是選擇 OBBs 應該根據我們所需的精確程度而定。對一個需要快速反應的3D射擊游戲來說，我們可能用 AABB 來進行碰撞檢測更好些――我們可以犧牲一些精度來換取速度和實現的簡單化。這篇文章附帶的代碼已經傳到 Game Developer 網頁上了。里面是從 AABBs 開始講起，同時還提供了一些實現 OBBs 的碰撞檢測包里的代碼例子。好了，現在我們已經有了關于每一部分是如果工作的認識了，下面我們來看看實現的細節。
創建樹
為任意的網格模型創建 OBB 樹可能是算法里最難的一個部分，而且它還要調整以適合特定的引擎或游戲類型。圖7示出了從最初的模型創建一個OBB樹的整個過程。可以看到，我們不得不找出包圍給定模型的最近似的包圍盒（或者其它3D體）。
Figure 7. Recursive build of an OBB and its tree.
有幾種方法可以事先計算OBB，這其中包括了許多的數學運算。其中一個基本的方法是計算頂點分布的均值，將它作為包圍盒的中心，然后計算協方差矩陣。然后我們用協方差矩陣的三個特征向量中的兩個把多邊形和包圍盒結合起來。我們可以凸盒方法進一步加速和優化樹的創建。你可以在Gottschalk, Lin, 和 Manocha的文章中的“For Further Info”一節找到相關信息。建立AABB樹要簡單得多，因為我們不需要找出物體的最小的包圍體和它們的軸。我們只需決定在哪分開模型，而且包圍盒可以自由創建（只要包圍盒平行于坐標軸并且包含分割面其中一側的所有頂點）。
現在我們得到了所有的包圍盒，下一步我們來構造一棵樹。我們從最初的包圍盒開始從上至下地反復分割它。另外，我們還可以用從下至上的方式，逐步地合并小包圍盒從而得到最大的包圍盒。把大的包圍盒分割成小的包圍盒，我們應該遵守以下幾條原則。我們應該用一個面（這個面垂直于包圍盒中的一條坐標軸）來分割包圍盒上最長的軸，然后根據多邊形處在分割軸的哪一邊把多邊形分離開來（如圖7）。如果不能沿著最長的軸進行分割，那我們就沿第二長的邊分割。我們持續地分割直到包圍盒不能再分割為止。依據我們需要的精度（比如，是否我們真的要判斷單個三角形的碰撞），我們可以按我們的選擇的方式（如是按樹的深度或是按包圍盒中多邊形的數目）以任意的條件停止分割。
正如你所看到的，創建階段相當復雜，其中包括了大量的運算。很明顯不能實時地創建樹――只能是事先創建。事先創建可以免去實時改變多邊形的可能。另一個缺點是OBB要求進行大量的矩陣運算，我們不得不把它們定位在適當的地方，并且每棵子樹必須與矩陣相乘。
使用樹進行碰撞檢測
現在假設我們已經有了OBB或者AABB樹。那么我們該怎么進行碰撞檢測呢？我們先檢測最大的包圍盒是否相交，如果相交了，他們可能發生了碰撞，接下來我們將進一步地遞歸處理它們（不斷地遞歸用下一級進行處理）。如果我們沿著下一級，發現子樹并沒有發生相交，這時我們就可以停止并得出結論沒有發生碰撞。如果我們發現子樹也相交了，那么要進一步處理它的子樹直到到達葉子節點，并最終得出結論。進行相交測試時，我們可以把包圍盒投影到空間坐標軸上并檢查它們是否線性相交。這種給定的坐標軸稱為分離坐標軸（separating axis）如圖8所示。
Figure 8. Separating axis (intervals
A and B don’t overlap).
為了快速地判斷相交性，我們使用一種叫分離坐標的方法。這種方法告訴我們，只有15條潛在的分離坐標。如果跌交的情況在每一條分離坐標上都發生了，那么包圍盒是相交的。因此，很容易就能判斷出兩個包圍盒是否相交。
有趣的是，前面提到的時間片大小的問題用分離坐標技術很容易就能解決。回憶一下關于在兩個給定時間內是否發生碰撞的問題。如果我們把速度加上，并且在所有15條坐標軸上的投影都跌交，說明會發生碰撞。我們可以用類似于AABB樹那樣的數據結構區分碰撞物和受碰物，并判斷他們是否有可能發生碰撞。這種運算可以快速地排除在場景中的大多數情況，產生一個接近理想的O次冪（N logN）的效率。
基于BSP樹的碰撞檢測技術
BSP（二叉空間分割）樹是另一種類型的空間分割技術，其已經在游戲工業上應用了許多年（Doom是第一個使用BSP樹的商業游戲）。盡管在今天BSP樹已經沒像過去那么受歡迎了，但現在三個被認可的游戲引擎――Quake II, Unreal, and Lithtech（譯者：這是2000年的文章，所以指出的這些游戲才這么老：）仍在廣泛地采用這項技術。當你看一下BSP在碰撞檢測方面那極度干凈漂亮和高速的效率，立刻能讓你眼前一亮。不但BSP樹在多邊形剪切方面表現出色，而且還能讓我們有效地自由運用world-object式的碰撞檢測。BSP樹的遍歷是使用BSP的一個基本技術。碰撞檢測本質上減少了樹的遍歷或搜索。這種方法很有用因為它能在早期排除大量的多邊形，所以在最后我們僅僅是對少數面進行碰撞檢測。正如我前面所說的，用找出兩個物體間的分隔面的方法適合于判斷兩個物體是否相交。如果分隔面存在，就沒有發生碰撞。因此我們遞歸地遍歷world樹并判斷分割面是否和包圍球或包圍盒相交。我們還可以通過檢測每一個物體的多邊形來提高精確度。進行這種檢測最簡單的一個方法是測試看看物體的所有部分是否都在分割面的一側。這種運算真的很簡單，我們用迪卡爾平面等式 ax + by + cz + d = 0 去判斷點位于平面的哪一側。如果滿足等式，點在平面上；如果ax + by + cz + d > 0那么點在平面的正面；如果ax + by + cz + d < 0點在平面的背面。
在碰撞沒發生的時候有一個重要的事情需要注意，就是一個物體（或它的包圍盒）必須在分割面的正面或背面。如果在平面的正面和背面都有頂點，說明物體與這個平面相交了。
不幸的是，我們還沒有一個很好的方法檢測在一個時間間隔內的碰撞（在文章開頭提到的方法現在仍在使用）。然而，我已經看到有另外的數據結構像BSP樹一樣開始廣泛使用了。
曲面物體及碰撞檢測
現在我們已經看到了兩種多邊形物體的碰撞檢測，下面一看看如何計算彎曲物體的碰撞。99年發布的幾款游戲已經大量地采用曲面了，因此在接下來幾年里高效的曲面碰撞檢測將變得十分重要。曲面碰撞檢測（要求有給定點上精確的曲面等式）運算開銷極大，所以我們要盡量避開它。實際上我們已經討論了幾種能用在這種情況下的方法。最明顯的方法就是用低網格來近似表示曲面，然后使用這個多面體進行碰撞檢測。甚至還有更簡單的（但精度比較低），就是在曲面的控制頂點（譯者：大概意思就是說每隔一定量的頂點就構造一個凸殼）上構造凸殼用來做碰撞檢測。在這種情況下，曲面的碰撞檢測十分近擬于傳統的多面體碰撞檢測。如圖9顯示了曲面及它在控制頂點上形成的凸殼。
Figure 9. Hull of a curved object.
是否我們可以結合這兩種技術形成一種混合方法？首先我們用凸殼進行碰撞檢測然后逐步在凸殼所屬的部分細分下去，這樣就增加了精度。
由你決定
現在我們已經瀏覽了一些高級的碰撞檢測（有一些也是基本的），你應該能夠決定什么樣的系統更適合你的游戲。你要決定的主要事情是精度、速度、實現的簡單程度及系統的適應性。
|