碰撞檢測算法有哪些（物理碰撞算法）
孩子學(xué)習(xí)對(duì)于所有的家長來，最關(guān)心就是孩子的學(xué)習(xí)，對(duì)吧？如何幫孩子提升學(xué)習(xí)成績呢？影響孩子學(xué)習(xí)成績的因素有哪些？左養(yǎng)右學(xué)教育賴頌強(qiáng)團(tuán)隊(duì)13年的家庭教育服務(wù)經(jīng)驗(yàn)總結(jié)，影響孩子學(xué)習(xí)的主要因素有22條之多，家長你了解幾條呢？
如上文所述，基于包圍形的方法是一種粗略的碰撞檢測方法，基于外接圓形的方法運(yùn)算速度很快，但精度很差；基于軸對(duì)齊包圍矩形（AABB）的方法適合本身就是矩形的物體，其運(yùn)算速度非常快，但檢測精度還是不夠。
1、OBB
OBB 就是找一個(gè)最小的包圍物體的矩形，這在自動(dòng)駕駛系統(tǒng)中也是最常用的，感知模塊給出物體的輪廓通常就是此形狀。另外，為了準(zhǔn)確描述物體輪廓，感知模塊在 bounding box 的基礎(chǔ)上，通常還會(huì)給出 polygon（多邊形）的形式，如下圖所示。
2、向量的點(diǎn)乘
在介紹分離軸定理之前，還需要先理解向量點(diǎn)乘的數(shù)學(xué)定義和幾何意義，如下圖所示，若 a 向量為單位向量，則向量 a 和向量 b 的點(diǎn)乘可以理解為 b 向量投影到 a 向量上的長度。
有了上述背景知識(shí)，接下來我們介紹一種適用于 bounding box 和 polygon 的精細(xì)碰撞檢測算法：分離軸定理（Separating Axis Theorem，SAT）。
3、分離軸定理
分離軸定理的理論依據(jù)為超平面分離定理，即 令 A 和 B 是兩個(gè)不相交的非空凸集，那么存在一個(gè)非零向量 v 和 實(shí)數(shù) c，使得 <x, v> ≤ c 且 <y, v> ≥ c。其中，x 屬于 A，y 屬于 B。
簡單來說，就是對(duì)于兩個(gè)凸多邊形，若存在一條直線將兩者分開，則這兩個(gè)多邊形不相交。
上圖中的黑線為分離線（Seperating line），與之垂直的綠線為分離軸（Separating axis），圖中虛線表示的是多邊形在分離軸上的投影。
實(shí)際應(yīng)用中，遍歷所有角度的分離軸是不現(xiàn)實(shí)的，受益于多邊形的性質(zhì)，對(duì)于兩個(gè)都是多邊形的物體，只需要依次在每條邊的垂直線做投影即可，如下圖所示。
對(duì)于兩個(gè)都是矩形的物體，則更簡單，只需要做四次投影。
以下圖中的兩個(gè)多邊形 A 和 B 為例，分離軸定理的具體步驟為：
- 首先根據(jù)邊1的兩個(gè)頂點(diǎn)位置坐標(biāo)，計(jì)算出邊1的向量，設(shè)為（x，y）；
- 進(jìn)而求出邊1的法向量，作為分離軸，為（y, -x）或（-y，x）。若需要求兩個(gè)多邊形的最小分離距離，這里的法向量還需要化為單位向量；若只需判斷兩個(gè)多邊形是否相交，則不需要化為單位向量；
- 依次將多邊形 A 和 B 的所有頂點(diǎn)與原點(diǎn)組成的向量投影到這個(gè)分離軸上，并記錄兩個(gè)多邊形頂點(diǎn)投影到分離軸上的最小值和最大值（Pmin，Pmax），形成一個(gè)投影線段；
- 判斷這兩個(gè)投影線段是否發(fā)生重疊，若不重疊，則有 （PAmax < PBmin）||（PAmin > PBmax）；
- 若兩個(gè)投影線段不重疊，則代表存在這樣一條直線將兩個(gè)多邊形分開，兩個(gè)多邊形不相交，可以直接退出循環(huán)；
- 若兩個(gè)投影線段重疊，則回到步驟1，繼續(xù)以邊2的法向量作為分離軸，進(jìn)行投影計(jì)算；
- 當(dāng)兩個(gè)多邊形的所有邊都檢查完之后，找不到這樣一條分離的直線，則意味著兩個(gè)多邊形相交。
注意：分離軸定理是一種適用于凸多邊形的碰撞檢測算法，對(duì)于凹多邊形則不適用，如下圖所示，兩個(gè)多邊形沒有碰撞，但找不到這樣一條直線，能將兩者分開。所以如果是凹多邊形的話，需要先將其轉(zhuǎn)換成多個(gè)凸多邊形。
綜上，分離軸定理是一種適用于 bounding box 和 polygon 的精細(xì)碰撞檢測算法，其優(yōu)點(diǎn)是算法原理簡單，可準(zhǔn)確判斷兩個(gè)多邊形是否相交；缺點(diǎn)在于當(dāng)多邊形的邊數(shù)較多時(shí)，該算法的效率較低（當(dāng)兩個(gè)多邊形相交時(shí)，需要遍歷完所有邊進(jìn)行判斷）。
在實(shí)際應(yīng)用中，為了提高效率，通常先使用 基于軸對(duì)齊包圍矩形（AABB）的方法進(jìn)行粗略的碰撞檢測，然后再使用 分離軸定理（SAT）做精細(xì)碰撞檢測。
