為了創建壹個理想的碰撞檢測程序，我們必須開始規劃和創建它的框架，同時為遊戲開發圖形管道。在項目的最後添加碰撞檢測是相當困難的。試圖在開發周期結束時創建壹個快速的碰撞檢測可能會毀了整個遊戲，因為我們無法讓它高效地運行。在壹個好的遊戲引擎中，碰撞檢測應該是準確、有效和非常快的。這些要求意味著碰撞檢測將與場景的多邊形管理管道密切相關。這也意味著窮舉法是行不通的。在當今的3D遊戲中，每幀處理的數據量可能會導致網格斷裂。當妳還在檢測壹個物體的每個多邊形是否與場景中的其他多邊形發生碰撞的時候，時間已經過去了。
先說基本的遊戲引擎循環(清單1)。快速瀏覽這些代碼，獲得碰撞檢測的相關策略。我們假設碰撞沒有發生，然後更新物體的位置。如果發現有碰撞，我們會把物體移回到原來的位置，不允許它越界(或者破壞物體或者采取壹些預防措施)。但是，這個假設太簡單了，因為我們無法知道物體的原始位置是否仍然有效。妳必須為這種情況設計壹個計劃(否則妳可能會經歷崩潰或被子彈擊中的感覺，就像前面的例子壹樣)。如果妳是壹個熱情的玩家，妳可能已經註意到，在壹些遊戲中，當妳靠近墻壁並試圖穿過它時，相機開始抖動。妳正在經歷的是把主角搬回原來位置的情況。振動是由於取了較大的時間片而引起的。
清單1。極度簡化的遊戲循環
while(1){
process_input()。
update _ objects()；
render _ world()；
}
update_objects(){
對於(每個對象)
save_old_position()。
計算新對象位置
{基於速度加速度。等等。}
if (collide_with_other_objects())
new_object_position =舊_ position()；
{或者，如果被破壞的對象移除它，等等。}
圖1。時間梯度和碰撞測試。
但是我們的方法是有缺陷的，我們忘記了在等式中加入時間。圖1告訴我們，時間太重要了，不能忘記。即使物體在t1或t2處沒有碰撞，它仍可能在T (t1)處越過邊界
我們可以把時間看作第四維，在四維空間中進行壹切操作。不過這可能會讓操作變得非常復雜，所以我們會避開這些。我們還可以從t1和t2處的對象開始創建壹個實體，然後用它與墻進行測試(見圖2)。
壹個簡單的方法是創建壹個凸包來覆蓋不同時間的兩個對象。這種方法的低效可能會明顯降低妳的遊戲速度。要創建凸殼，最好在實體周圍創建壹個邊界框。我們會在學習完其他技術後再回來討論這個問題。
另壹種更容易實現但不太精確的方法是將給定的時間段分成兩部分，然後測試時間點之間的相交關系。我們也可以依次遞歸確定每個片段的時間中點。這種方法比前壹種方法快得多，但不能保證所有碰撞都能被捕獲。
另壹個隱藏的問題是collide_with_other_objects()方法的實現，就是判斷壹個物體是否與場景中的其他物體相交。如果場景中有許多對象，這種方法可能會非常昂貴。如果我們要判斷場景中的每個對象是否與其他對象相交，我們將不得不進行兩次左右的比較。所以比較的次數會是n的平方？(或表示為O(N2))。但是我們可以用幾種方法避免比較O(N2)對。例如，我們可以將場景中的對象分為靜態(被撞擊的對象)和動態(即使碰撞對象的速度為0)。就好像房間裏的墻被撞了，壹個扔向墻的小球被撞了。我們可以創建兩個獨立的樹(每種類型的對象壹個),然後測試對象可能發生碰撞的那些樹。我們甚至可以就環境達成協議，讓壹些碰撞的物體不發生碰撞。例如，我們不需要在兩顆子彈之間進行判斷。現在，在我們繼續之前，我們可以說這個過程已經變得更加清晰了。另壹種減少場景中成對比較的方法是構建八叉樹。這超出了本文的範圍。妳可以在空間數據結構:四叉樹，八叉樹和其他層次方法的更多信息部分閱讀更多關於八叉樹的信息。現在讓我們來看看基於門戶的引擎，以理解為什麽在這種引擎中提到碰撞檢測是如此痛苦。
門戶引擎和對象-對象碰撞
基於門戶的引擎將場景或世界分成更小的凸方形區域。凸方形區域適用於圖形管道，因為它們可以避免重繪。不幸的是，對於碰撞檢測，凸正方形區域會給我們帶來壹些困難。在我最近的壹些測試中，壹臺發動機平均有大約400到500個凸方形區域。當然，這個數字會隨著不同的引擎而變化，因為不同的引擎使用不同的多邊形技術。多邊形的數量會隨著場景的大小而變化。
判斷壹個物體的多邊形是否穿過場景中的多邊形，可能會導致計算量很大。最簡單的碰撞檢測方法之壹是用球體近似表示壹個物體或物體的壹部分，然後判斷這些包圍球是否相交。這樣，我們只需要測試兩個球體的中心之間的距離是否小於它們的半徑(這意味著碰撞)。如果比較中心點距離的平方和半徑的平方就更好了，這樣在計算距離的時候就可以排除平方根運算差的情況。然而，簡單的操作也會導致精度下降(見圖3)。
圖3。在球體與球體相交的情況下，例程可能會報告碰撞已經發生，而實際上並沒有發生。
但我們只是把這種不精確的方法作為我們的第壹步。我們用壹個大球體來代表整個物體，然後檢查它是否與其他球體相交。如果檢測到碰撞，那麽我們需要進壹步提高精確度。我們可以把壹個大球體分成壹系列小球體，檢查每個小球體是否有碰撞。我們不斷地劃分和檢查，直到得到滿意的近似值。分層和劃分的基本思想是，要盡力達到適合自己需求的理想狀況。
圖4。球體細分。
用壹個球體來近似表示壹個物體，需要的計算量很小，但是遊戲中的大部分物體都是方形的，所以我們要用壹個方形的盒子來表示物體。開發人員壹直在使用包圍盒和這種遞歸的快速方法來加速光線跟蹤算法。？補習學校？妳在做什麽?壹瞬間，ABB(軸對齊邊界框)出現了。圖5顯示了壹個AABB及其對象。圖5。壹個對象及其AABB。
軸對齊不僅意味著長方體平行於世界坐標軸，還意味著長方體的每個面都垂直於坐標軸。這樣的基本信息可以減少換箱時的操作次數。AABBs在當今很多遊戲中都有應用，開發者經常把它作為模型的包圍盒。再次指出，提高精度也會降低速度。因為AABBs永遠是平行於坐標思維的，所以旋轉物體的時候不能簡單的旋轉AABBs——每壹幀都要重新計算。如果知道每個對象的內容，這個計算並不難，也不會拖慢遊戲。然而，我們仍然面臨著準確性的問題。假設我們有壹個三維細長剛性直桿，我們想在動畫的每壹幀重建它的AABB。我們可以看到，每壹幀中的包圍盒是不同的，精度也會相應變化。