碰撞檢測算法之包圍形法

如上文所述，基于包圍形的方法是一種粗略的碰撞檢測方法，基于外接圓形的方法運算速度很快，但精度很差；基于軸對齊包圍矩形（AABB）的方法适合本身就是矩形的物體，其運算速度非常快，但檢測精度還是不夠。

OBB 就是找一個最小的包圍物體的矩形，這在自動駕駛系統中也是最常用的，感知模塊給出物體的輪廓通常就是此形狀。另外，為了準确描述物體輪廓，感知模塊在 bounding box 的基礎上，通常還會給出 polygon（多邊形）的形式，如下圖所示。

向量點乘、叉乘的定義及幾何意義

向量法判斷點與線段的關系(一)

向量法判斷點與線段的關系(二)

在介紹分離軸定理之前，還需要先理解向量點乘的數學定義和幾何意義，如下圖所示，若 a 向量為單位向量，則向量 a 和向量 b 的點乘可以理解為 b 向量投影到 a 向量上的長度。

有了上述背景知識，接下來我們介紹一種适用于 bounding box 和 polygon 的精細碰撞檢測算法：分離軸定理（Separating Axis Theorem，SAT）。

分離軸定理的理論依據為超平面分離定理，即 令 A 和 B 是兩個不相交的非空凸集，那麼存在一個非零向量 v 和 實數 c，使得 <x, v> ≤ c 且 <y, v> ≥ c。其中，x 屬于 A，y 屬于 B。

簡單來說，就是對于兩個凸多邊形，若存在一條直線将兩者分開，則這兩個多邊形不相交。

上圖中的黑線為分離線（Seperating line），與之垂直的綠線為分離軸（Separating axis），圖中虛線表示的是多邊形在分離軸上的投影。

實際應用中，遍曆所有角度的分離軸是不現實的，受益于多邊形的性質，對于兩個都是多邊形的物體，隻需要依次在每條邊的垂直線做投影即可，如下圖所示。

對于兩個都是矩形的物體，則更簡單，隻需要做四次投影。

以下圖中的兩個多邊形 A 和 B 為例，分離軸定理的具體步驟為：

1. 首先根據邊1的兩個頂點位置坐标，計算出邊1的向量，設為（x，y）；
2. 進而求出邊1的法向量，作為分離軸，為（y, -x）或（-y，x）。若需要求兩個多邊形的最小分離距離，這裡的法向量還需要化為單位向量；若隻需判斷兩個多邊形是否相交，則不需要化為單位向量；
3. 依次将多邊形 A 和 B 的所有頂點與原點組成的向量投影到這個分離軸上，并記錄兩個多邊形頂點投影到分離軸上的最小值和最大值（Pmin，Pmax），形成一個投影線段；
4. 判斷這兩個投影線段是否發生重疊，若不重疊，則有 （PAmax < PBmin）||（PAmin > PBmax）；
5. 若兩個投影線段不重疊，則代表存在這樣一條直線将兩個多邊形分開，兩個多邊形不相交，可以直接退出循環；
6. 若兩個投影線段重疊，則回到步驟1，繼續以邊2的法向量作為分離軸，進行投影計算；
7. 當兩個多邊形的所有邊都檢查完之後，找不到這樣一條分離的直線，則意味着兩個多邊形相交。

注意：分離軸定理是一種适用于凸多邊形的碰撞檢測算法，對于凹多邊形則不适用，如下圖所示，兩個多邊形沒有碰撞，但找不到這樣一條直線，能将兩者分開。所以如果是凹多邊形的話，需要先将其轉換成多個凸多邊形。

綜上，分離軸定理是一種适用于 bounding box 和 polygon 的精細碰撞檢測算法，其優點是算法原理簡單，可準确判斷兩個多邊形是否相交；缺點在于當多邊形的邊數較多時，該算法的效率較低（當兩個多邊形相交時，需要遍曆完所有邊進行判斷）。

在實際應用中，為了提高效率，通常先使用 基于軸對齊包圍矩形（AABB）的方法進行粗略的碰撞檢測，然後再使用 分離軸定理（SAT）做精細碰撞檢測。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!