碰撞檢測是檢測兩個或多個物體相交的計算問題。碰撞檢測是計算幾何學的一個經典問題，在各種計算領域都有應用，主要是在計算機圖形學、計算機游戲、計算機模擬、機器人和計算物理學中。碰撞檢測算法可以分為對2D和3D對象的操作。

物理模擬器的不同之處在于它們對碰撞的反應方式。有些使用材料的柔軟度來計算力，這將在以下時間步長中解決碰撞，就像在現實中一樣。由于某些材料的柔軟度較低，這會占用大量CPU。一些模擬器通過線性插值估計碰撞時間，回滾模擬，并通過更抽象的守恒定律方法計算碰撞。

一些迭代線性插值（牛頓法）以比模擬的其余部分更高的精度計算碰撞時間。碰撞檢測利用時間一致性來允許更精細的時間步長，而不會增加CPU需求，例如在空中交通管制中。

在非彈性碰撞之后，可能會出現滑動和靜止的特殊狀態，例如，開放動力學引擎使用約束來模擬它們。約束避免了慣性，從而避免了不穩定。通過場景圖實現休息避免了漂移。

換句話說，物理模擬器通常以兩種方式運行，其中碰撞是后驗（碰撞發生后）或先驗（碰撞發生前）檢測到的。除了后驗和先驗的區別之外，幾乎所有現代碰撞檢測算法都分為算法層次結構。通常使用術語“離散”和“連續”而不是后驗和先驗。

在后驗情況下，物理模擬前進一小步，然后檢查是否有任何對象相交或明顯被認為相交。在每個模擬步驟中，都會創建一個包含所有相交物體的列表，并且這些物體的位置和軌跡被“固定”以解決碰撞問題。這種方法被稱為后驗方法，因為它通常會錯過碰撞的實際瞬間，并且只在碰撞實際發生后才捕獲它。

在先驗方法中，有一種碰撞檢測算法，它將能夠非常精確地預測物理物體的軌跡。碰撞的瞬間以高精度計算，并且物理身體從未真正相互滲透。這被稱為先驗，因為碰撞檢測算法在更新物理物體的配置之前計算碰撞的瞬間。

后驗方法的主要優點如下。在這種情況下，碰撞檢測算法不需要知道無數的物理變量；一個簡單的物理物體列表被提供給算法，程序返回一個相交物體的列表。碰撞檢測算法不需要了解摩擦、彈性碰撞，或者更糟的是，非彈性碰撞和變形體。此外，后驗算法實際上比先驗算法簡單一維。一個先驗算法必須處理的時間的變量，它是從缺席的后驗問題。

另一方面，后驗算法會在“修復”步驟中引起問題，需要更正交叉點（物理上不正確）。此外，如果離散步長太大，碰撞可能無法檢測到，如果一個物體足夠快或足夠小，就會導致它穿過另一個物體。

先驗算法的好處是增加了保真度和穩定性。很難（但并非完全不可能）將物理模擬與碰撞檢測算法分開。然而，除了最簡單的情況外，提前確定兩個物體何時碰撞（給定一些初始數據）的問題沒有封閉形式的解決方案——通常涉及數值求根。

有些物體處于靜止接觸狀態，即碰撞，但既不會彈開，也不會相互穿透，例如放在桌子上的花瓶。在所有情況下，靜止接觸都需要特殊處理：如果兩個對象碰撞（后驗）或滑動（先驗）并且它們的相對運動低于閾值，則摩擦變為靜摩擦并且兩個對象都排列在場景圖的同一分支中。

對多個對象進行碰撞檢測的明顯方法非常緩慢。對照每個其他對象檢查每個對象當然是可行的，但是當對象數量非常大時，效率太低而無法使用。以明顯的方式檢查具有復雜幾何形狀的對象，通過檢查每個面與彼此的面，本身非常慢。因此，已經進行了大量的研究來加速這個問題。

電子游戲必須在多個任務之間分配非常有限的計算時間。盡管存在這種資源限制，并且使用了相對原始的碰撞檢測算法，但程序員已經能夠創建可信的（如果不準確的話）用于游戲的系統。

長期以來，電子游戲要處理的對象數量非常有限，因此檢查所有對不是問題。在二維游戲中，在某些情況下，硬件能夠有效地檢測和報告屏幕上精靈之間的重疊像素。在其他情況下，簡單地平鋪屏幕并將每個精靈綁定到它重疊的平鋪中就可以提供足夠的修剪，并且對于成對檢查，使用稱為命中框的邊界矩形或圓形被認為足夠準確。

三維游戲使用空間劃分方法，長期以來，每個實際3D對象使用一個或幾個球體進行成對檢查。除了在嘗試密切模擬現實的游戲中，精確檢查非常罕見。即便如此，也不一定在所有情況下都使用精確檢查。

因為游戲不需要模仿實際的物理，所以穩定性不是什么大問題。幾乎所有游戲都使用后驗碰撞檢測，并且碰撞通常使用非常簡單的規則來解決。例如，如果一個角色被嵌入墻壁中，他們可能會被簡單地移回他們最后一個已知的好位置。有些游戲會計算角色在嵌入墻壁之前可以移動的距離，并且只允許他們移動那么遠。

在許多視頻游戲的情況下，通過一個點來逼近角色就足以實現與環境的碰撞檢測。在這種情況下，二元空間分區樹提供了一種可行、高效且簡單的算法來檢查一個點是否嵌入到風景中。當角色在地面上奔跑時，這樣的數據結構也可以用來優雅地處理“休息位置”的情況。角色之間的碰撞，以及與射彈和危險的碰撞，是分開處理的。

一個強大的模擬器會以合理的方式對任何輸入做出反應。例如，如果我們想象一個高速賽車視頻游戲，從一個模擬步驟到下一個模擬步驟，可以想象汽車會沿著賽道前進很長一段距離。如果賽道上有一個較淺的障礙物（比如磚墻），賽車完全跳過它也不是完全不可能的，這是非常不可取的。在其他情況下，后驗算法要求的“修復”沒有正確實現，導致錯誤可以將角色困在墻壁中或允許他們穿過墻壁并陷入無盡的虛空，那里可能有也可能沒有致命的無底洞坑，有時也稱為“黑色地獄”、“藍色地獄”或“綠色地獄”，具體取決于主要顏色。這些是碰撞檢測和物理模擬系統失敗的標志。BigRigs:OvertheRoadRacing是一個臭名昭著的例子，游戲的碰撞檢測系統失敗或可能丟失。