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