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