碰撞偵測

碰撞偵測（Collision detection）或稱為碰撞檢測通常是指一種判斷兩個或多個對象是否產生交集的的方法。往往應用於電子遊戲和其他計算物理學當中，也應用於人工智慧當中。除了確定兩個對象是否已經碰撞，碰撞偵測也可以用於計算衝擊的時間（TOI），以及回報對象交叉的位置。 碰撞響應一旦偵測到碰撞則處理類比（物理引擎，布娃娃系統）。解決碰撞偵測問題需要使用廣泛的概念，如線性代數和計算幾何。

概述

撞球碰撞的類比是碰撞偵測的經典例子。

在物理類比當中，如果驗證撞球產生的位置，則需要類比剛體運動和彈性碰撞。並且在初始化的時候賦予與撞球桌和球一些非常精確的物理描述，以及所有的球的初始位置。設定施於母球的力（可能是從一個玩家以球桿擊中球的得到數值），之後計算球的運動軌跡，並計算所有球的最終位置。

電子遊戲也應用碰撞偵測，但與類比真實世界的物理通常需要較多的計算，與類比真實世界的物理不一樣的地方是，通常電子遊戲當中都是採用可以實時且近似的計算來類比物理來滿足玩家。

演算法

GJK

GJK（Gilbert–Johnson–Keerthi distance algorithm）是確定兩個凸集之間的最小距離的一個方法。與其它的距離的演算法不同的是，它不需要對特定的形狀編寫代碼即可通用，僅依賴於一個支撐集功能，以迭代地生成單形以對兩個凸集求閔可夫斯基和。

分離軸定理

分離軸定理（Separating Axis Theorem，簡稱SAT），是判斷兩個凸集狀是否相交的方法。SAT是一個快速通用的演算法不必為每個形狀去編寫代碼由此減少和以便維護碰撞偵測的程式碼。

參見

• 四元樹
• 八元樹
• 包圍體
• 物理引擎