《高級碰撞檢測技術(shù)》word版

1、.高級碰撞檢測技術(shù)高級碰撞檢測技術(shù)2020-06-14 10：02自從計算機游戲出現(xiàn)以來，程序員就不斷地想方法來更準確地模擬現(xiàn)實世界。就拿乒乓游戲為例子譯者：Pong-被譽為電子游戲的祖先，有幸見過一次：，能見到祖先做的游戲感覺真是爽啊，想看的可以到FTP上下載"地球故事"就可以看到了：，游戲中有一個象征性的小方塊球和兩支拍子，游戲者需要在恰當(dāng)?shù)臅r間將拍子挪動到恰當(dāng)?shù)牡攸c，將小球反彈回去。這個根本操作的背后以如今的標準來看就是最原初的碰撞檢測了。今天的游戲比"乒乓"要高級得多，并且根本上是基于3D的。3D游戲中的碰撞檢測比"乒乓"游戲

2、里的要更加難實現(xiàn)。玩一些早期模擬飛行游戲的體驗向我們展現(xiàn)出糟糕的碰撞檢測是如何消滅一個游戲的。當(dāng)穿過一座大山的尖頂?shù)臅r候仍然活著，感覺很不真實。即便是如今的一些游戲也還是有碰撞上的問題，許多玩家曾經(jīng)絕望地看著他們喜歡的英雄或女英雄的部分身體穿進了墻里。甚至更糟的是，許多玩家都有過這樣糟糕的體驗，就是被那些離得很遠的子彈或火箭擊中。因為游戲者們要求提升真實性，我們開發(fā)者就不得不絞盡腦汁想方法讓我們的游戲世界盡可能地接近現(xiàn)實世界。閱讀這篇文章前首先假設(shè)你對與碰撞檢測相關(guān)的幾何和數(shù)學(xué)知識已經(jīng)有了根本的理解。在文章的最后，我將提供一些這方面的參考資料，以免你對它們感覺有點陌生。另外我還假設(shè)你已經(jīng)讀過J

3、eff Lander的圖形專欄里關(guān)于碰撞檢測文章"Crashing into the New Year,"；"When Two Hearts Collide,"；和"Collision Response：Bouncy,Trouncy,Fun,"。我將首先進展一個大概的描繪，然后快速地切入到核心內(nèi)容里，通過這兩步從上至下地深化到碰撞檢測中。我將討論兩種類型的圖形引擎中的碰撞檢測：基于portal的和基于BSP的。每種引擎中多邊形的組織各不一樣，因此在world-object型的碰撞檢測上存在很大的差異。而object-object型的碰

4、撞檢測絕大多數(shù)地方在上述兩種引擎里的是一樣的，主要看你是如何實現(xiàn)的了。當(dāng)我們接觸到多邊形的碰撞檢測時，我們還會實驗如何將其擴展到我們學(xué)過的凸型物體上。預(yù)覽為了創(chuàng)立一個理想的碰撞檢測程序，我們不得不在開發(fā)一個游戲的的圖形管道的同時就開場方案并創(chuàng)立它的框架。在工程的最后參加碰撞檢測是相當(dāng)困難的。想在開發(fā)周期的末尾創(chuàng)立快速的碰撞檢測將很有可能會使整個游戲被毀掉，因為我們不可能使它能高效地運行。在好的游戲引擎中，碰撞檢測應(yīng)該是準確、有效并且非?？焖俚?。這些要求意味著碰撞檢測將要與場景的多邊形管理管道緊緊地聯(lián)絡(luò)起來。這也意味著窮舉法將無法工作今天的3D游戲中每幀處理的數(shù)據(jù)量很可能導(dǎo)致打格，當(dāng)你還在檢測一

5、個物體的各多邊形是否與場景中的其它多邊形碰撞時，時間已經(jīng)過去了。讓我們從根本的游戲引擎循環(huán)開場吧列表1?？焖匍喿x這些代碼來得到碰撞檢測的相關(guān)策略。我們先假設(shè)碰撞沒有發(fā)生，然后更新物體的位置，假設(shè)發(fā)現(xiàn)發(fā)生了碰撞，我們將把物體移回原來的位置不允許它穿越邊界或?qū)⑽矬w銷毀或執(zhí)行一些預(yù)防措施。然而，這個假設(shè)太過簡單因為我們無法得知物體原來的位置是否仍然有效。你必須為這種情況設(shè)計一個方案否那么你可能會體驗到墜機或被子彈擊中的感覺就是前面舉的例子。假設(shè)你是一個熱心的玩家，你可能已經(jīng)注意到了在一些游戲當(dāng)中，當(dāng)你挨著墻壁并試圖穿過去的時候，攝像機就開場震動。你正經(jīng)歷的就是將主角移回原位的情況。震動是因為取了較大

6、的時間片引起的。Listing 1.Extremely Simplified Game Loop while1process_input；update_objects；render_world；update_objectsforeach_objectsave_old_position；calc new_object_positionbased on velocity accel.etc.ifcollide_with_other_objectsnew_object_position=old_position；or if destroyed object remove it etc.Figure

7、1.Time gradient and collision tests.但是我們的方法有缺陷，我們忘了在等式中參加時間。圖1告訴我們時間太重要了不能忘了它。即便物體在t1或t2時刻沒有發(fā)生碰撞，它仍有可能在t時刻穿過邊界t1 tt2。這會在兩個連續(xù)幀中產(chǎn)生大幅度地跨越就好象擊中了燃料室或其它類似的東西。我們不得不找一個好的方法來解決這個問題。我們可以把時間看成是第四維并將所有運算在4維空間中進展。然而這可能會讓運算變得非常復(fù)雜，所以我們會避開這些。我們還可以創(chuàng)立一個以t1、t2時刻的物體為起始點的實心體，然后用它來與墻進展測試見圖2Figure 2.Solid created from the

8、 space that an object spans over agiven time frame.一個簡單的方法就是創(chuàng)立一個凸殼來罩住兩個不同時刻的物體。這種方法效率低下可能會明顯地降低你的游戲速度。以其創(chuàng)立一個凸殼，還不如創(chuàng)立一個圍繞實心體的包圍盒。我們學(xué)習(xí)其它的技術(shù)后再回來討論這個問題。有另一種比較容易執(zhí)行但精度較低的方法，就是把給定的時間段分為兩分，然后測試時間中點的相交關(guān)系。我們還可以遞歸地依次測定各段的時間中點。這個方法比先前的方法要快得多，但不能保證能捕捉到所有的碰撞情況。另一個暗藏著的問題是collide_with_other_objects方法的實現(xiàn)即判斷一個物體是否與場景

9、中的其它物體相交。假設(shè)場景中有很多的物體，這個方法可能消耗很大。假設(shè)要判斷各物體與場景中其它物體是否相交，我們將不得不進展大概N選2次比較。因此比較次數(shù)會是N的平方次冪或表示成ON2。但我們可以用幾種方法來防止進展ON2對的比較。舉個例子，我們可以把場景中的物體分成靜態(tài)的被撞物和動態(tài)的碰撞物即使它的速度為0也行。就好象房間中的墻壁是被撞物，而一個扔向墻壁的小球是碰撞物。我們可以創(chuàng)立兩棵獨立的樹每一棵對應(yīng)一類物體，然后測試那些物體可能會碰撞的樹。我們甚至可以對環(huán)境進展約定讓一些碰撞物之間不發(fā)生碰撞比方我們不需要在兩顆子彈之間進展判斷。如今在繼續(xù)之前，經(jīng)過改進之后我們可以說處理過程變得更加明晰了。

10、另一個減少場景中成對的比較的方法就是建立八叉樹。這已經(jīng)超出了這篇文章的范圍，你可以在Spatial Data Structures：Quadtree,Octrees and Other Hierarchical Methods文章中的For Further Info一節(jié)里讀到更多關(guān)于八叉的信息。如今讓我們來看一下基于Portal引擎，理解為什么在這類引擎中一提到碰撞檢測就會那么痛苦。Portal引擎和Object-Object型碰撞基于Portal的引擎把場景或世界分割成較小的凸方形區(qū)域。凸方形區(qū)域很適宜圖形管道因為它們能防止重繪現(xiàn)象。不幸的是，對碰撞檢測來說，凸方形區(qū)域會給我們帶來一些困難。

11、在我最近的一些測試中，一個引擎中平均大約有400到500個凸方形區(qū)域。當(dāng)然，這個數(shù)字會隨著不同的引擎而有所變化，因為不同的引擎使用不同的多邊形技術(shù)。而且多邊形的數(shù)目也會因場景的大小而有所不同。判斷一個物體的多邊形是否穿過了場景中的多邊形產(chǎn)生的運算量可能會很大。一個最簡單的碰撞檢測法就是用球形來近似地表示物體或物體的一部分，然后再判斷這些包圍球是否相交。這樣我們僅僅需要測試兩個球體中心的間隔 是否小于它們的半徑合這表示發(fā)生了碰撞。假設(shè)我們是用中心點間隔 的平方和半徑合的平方進展比較，那更好，這樣我們可以在計算間隔 時除去拙劣的開方運算。但是，簡單的運算也導(dǎo)致了準確度的降低見圖3。Figure 3

12、.In asphere-sphere intersection,the routine may report that collision has occurred when it really hasn't.但我們僅僅是將這個不太準確的方法做為我們的第一步。我們用一個大的球體代表整個對象，然后檢測它是否和其它的球體相交。假設(shè)檢測到發(fā)生了碰撞，那么我們就要進一步進步精度，我們可以將大的球體分割成一系列小的球體，并檢查與各小球體是否發(fā)生碰撞。我們不斷地分割檢查直到得到滿意的近似值為止。分層并分割的根本思想就是我們要盡可能到達適宜需要的理想的情況。Figure 4.Sphere subdi

13、vision.用球體去近似地代表物體運算量很小，但在游戲中的大多數(shù)物體是方的，我們應(yīng)該用方盒來代表物體。開發(fā)者一直用包圍盒和這種遞歸的快速方法來加速光線追蹤算法。在實際中，這些算法已經(jīng)以八叉和AABBaxis-aligned bounding boxes的方式出現(xiàn)了。圖5展示了一個AABB和它里面的物體。Figure 5.An object and its AABB.坐標軸平行"Axis-aligned"不僅指盒體與世界坐標軸平行，同時也指盒體的每個面都和一條坐標軸垂直。這樣一個根本信息就能減少轉(zhuǎn)換盒體時操作的次數(shù)。AABBs在當(dāng)今的許多游戲中都得到了應(yīng)用，開發(fā)者經(jīng)常用它們

14、作為模型的包圍盒。再次指出，進步精度的同時也會降低速度。因為AABBs總是與坐標思平行，我們不能在旋轉(zhuǎn)物體的時候簡單地旋轉(zhuǎn)AABBs-它們應(yīng)該在每一幀都重新計算過。假設(shè)我們知道每個對象的內(nèi)容，這個計算就不算困難并不會降低游戲的速度。然而，我們還面臨著精度的問題。假設(shè)我們有一個3D的細長剛性直棒，并且要在每一幀動畫中都重建它的AABB。我們可以看到每一幀中的包圍盒的都不一樣而且精度也會隨之改變。Figure 6.Successive AABBs for aspinning rodas viewed from the side.所以以其用AABBs，為什么我們不用任意方向能最小化空白區(qū)域的包圍盒呢

15、。這是一種基于叫oriented bounding boxes-OBBs的技術(shù)，它已經(jīng)廣泛用于光線追蹤和碰撞檢測中。這種技術(shù)不但比AABBs技術(shù)更準確而且還更強健。但OBBs實現(xiàn)起來比較困難，執(zhí)行速度慢，并且不太適宜動態(tài)的或柔性的物體。特別注意的是當(dāng)我們把一個物體分得越來越小的時候，我們事實上在創(chuàng)立一棵有層次的樹。我們是選擇AABBs還是選擇OBBs應(yīng)該根據(jù)我們所需的準確程度而定。對一個需要快速反響的3D射擊游戲來說，我們可能用AABB來進展碰撞檢測更好些我們可以犧牲一些精度來換取速度和實現(xiàn)的簡單化。這篇文章附帶的代碼已經(jīng)傳到Game Developer網(wǎng)頁上了。里面是從AABBs開場講起，同

16、時還提供了一些實現(xiàn)OBBs的碰撞檢測包里的代碼例子。好了，如今我們已經(jīng)有了關(guān)于每一部分是假設(shè)工作的認識了，下面我們來看看實現(xiàn)的細節(jié)。創(chuàng)立樹為任意的網(wǎng)格模型創(chuàng)立OBB樹可能是算法里最難的一個部分，而且它還要調(diào)整以適宜特定的引擎或游戲類型。圖7示出了從最初的模型創(chuàng)立一個OBB樹的整個過程?？梢钥吹剑覀儾坏貌徽页霭鼑o定模型的最近似的包圍盒或者其它3D體。Figure 7.Recursive build of an OBB and its tree.有幾種方法可以事先計算OBB，這其中包括了許多的數(shù)學(xué)運算。其中一個根本的方法是計算頂點分布的均值，將它作為包圍盒的中心，然后計算協(xié)方差矩陣。然后我們用

17、協(xié)方差矩陣的三個特征向量中的兩個把多邊形和包圍盒結(jié)合起來。我們可以凸盒方法進一步加速和優(yōu)化樹的創(chuàng)立。你可以在Gottschalk,Lin,和Manocha的文章中的"For Further Info"一節(jié)找到相關(guān)信息。建立AABB樹要簡單得多，因為我們不需要找出物體的最小的包圍體和它們的軸。我們只需決定在哪分開模型，而且包圍盒可以自由創(chuàng)立只要包圍盒平行于坐標軸并且包含分割面其中一側(cè)的所有頂點。如今我們得到了所有的包圍盒，下一步我們來構(gòu)造一棵樹。我們從最初的包圍盒開場從上至下地反復(fù)分割它。另外，我們還可以用從下至上的方式，逐步地合并小包圍盒從而得到最大的包圍盒。把大的包圍盒分

18、割成小的包圍盒，我們應(yīng)該遵守以下幾條原那么。我們應(yīng)該用一個面這個面垂直于包圍盒中的一條坐標軸來分割包圍盒上最長的軸，然后根據(jù)多邊形處在分割軸的哪一邊把多邊形別分開來如圖7。假設(shè)不能沿著最長的軸進展分割，那我們就沿第二長的邊分割。我們持續(xù)地分割直到包圍盒不能再分割為止。根據(jù)我們需要的精度比方，是否我們真的要判斷單個三角形的碰撞，我們可以按我們的選擇的方式如是按樹的深度或是按包圍盒中多邊形的數(shù)目以任意的條件停頓分割。正如你所看到的，創(chuàng)立階段相當(dāng)復(fù)雜，其中包括了大量的運算。很明顯不能實時地創(chuàng)立樹只能是事先創(chuàng)立。事先創(chuàng)立可以免去實時改變多邊形的可能。另一個缺點是OBB要求進展大量的矩陣運算，我們不得不

19、把它們定位在適當(dāng)?shù)牡胤?，并且每棵子樹必須與矩陣相乘。使用樹進展碰撞檢測如今假設(shè)我們已經(jīng)有了OBB或者AABB樹。那么我們該怎么進展碰撞檢測呢?我們先檢測最大的包圍盒是否相交，假設(shè)相交了，他們可能發(fā)生了碰撞，接下來我們將進一步地遞歸處理它們不斷地遞歸用下一級進展處理。假設(shè)我們沿著下一級，發(fā)現(xiàn)子樹并沒有發(fā)生相交，這時我們就可以停頓并得出結(jié)論沒有發(fā)生碰撞。假設(shè)我們發(fā)現(xiàn)子樹也相交了，那么要進一步處理它的子樹直到到達葉子節(jié)點，并最終得出結(jié)論。進展相交測試時，我們可以把包圍盒投影到空間坐標軸上并檢查它們是否線性相交。這種給定的坐標軸稱為別離坐標軸separating axis如圖8所示。Figure 8.

20、Separating axisintervals Aand Bdon't overlap.為了快速地判斷相交性，我們使用一種叫別離坐標的方法。這種方法告訴我們，只有15條潛在的別離坐標。假設(shè)跌交的情況在每一條別離坐標上都發(fā)生了，那么包圍盒是相交的。因此，很容易就能判斷出兩個包圍盒是否相交。有趣的是，前面提到的時間片大小的問題用別離坐標技術(shù)很容易就能解決。回憶一下關(guān)于在兩個給定時間內(nèi)是否發(fā)生碰撞的問題。假設(shè)我們把速度加上，并且在所有15條坐標軸上的投影都跌交，說明會發(fā)生碰撞。我們可以用類似于AABB樹那樣的數(shù)據(jù)構(gòu)造區(qū)分碰撞物和受碰物，并判斷他們是否有可能發(fā)生碰撞。這種運算可以快速地排除在

21、場景中的大多數(shù)情況，產(chǎn)生一個接近理想的O次冪N logN的效率?；贐SP樹的碰撞檢測技術(shù)BSP二叉空間分割樹是另一種類型的空間分割技術(shù)，其已經(jīng)在游戲工業(yè)上應(yīng)用了許多年Doom是第一個使用BSP樹的商業(yè)游戲。盡管在今天BSP樹已經(jīng)沒像過去那么受歡送了，但如今三個被認可的游戲引擎 Quake II,Unreal,and Lithtech譯者：這是2000年的文章，所以指出的這些游戲才這么老：仍在廣泛地采用這項技術(shù)。當(dāng)你看一下BSP在碰撞檢測方面那極度干凈漂亮和高速的效率，立即能讓你眼前一亮。不但BSP樹在多邊形剪切方面表現(xiàn)出色，而且還能讓我們有效地自由運用world-object式的碰撞檢測。B

22、SP樹的遍歷是使用BSP的一個根本技術(shù)。碰撞檢測本質(zhì)上減少了樹的遍歷或搜索。這種方法很有用因為它能在早期排除大量的多邊形，所以在最后我們僅僅是對少數(shù)面進展碰撞檢測。正如我前面所說的，用找出兩個物體間的分隔面的方法適宜于判斷兩個物體是否相交。假設(shè)分隔面存在，就沒有發(fā)生碰撞。因此我們遞歸地遍歷world樹并判斷分割面是否和包圍球或包圍盒相交。我們還可以通過檢測每一個物體的多邊形來進步準確度。進展這種檢測最簡單的一個方法是測試看看物體的所有部分是否都在分割面的一側(cè)。這種運算真的很簡單，我們用迪卡爾平面等式ax+by+cz+d=0去判斷點位于平面的哪一側(cè)。假設(shè)滿足等式，點在平面上；假設(shè)ax+by+cz+d 0那么