碰撞檢測算法有哪些（物理碰撞算法）

孩子學習對于所有的家長來，最關心就是孩子的學習，對吧？如何幫孩子提升學習成績呢？影響孩子學習成績的因素有哪些？左養右學教育賴頌強團隊13年的家庭教育服務經驗總結，影響孩子學習的主要因素有22條之多，家長你了解幾條呢？

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

1、OBB

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

2、向量的點乘

在介紹分離軸定理之前，還需要先理解向量點乘的數學定義和幾何意義，如下圖所示，若 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的向量，設為（x，y）；
進而求出邊1的法向量，作為分離軸，為（y, -x）或（-y，x）。若需要求兩個多邊形的最小分離距離，這里的法向量還需要化為單位向量；若只需判斷兩個多邊形是否相交，則不需要化為單位向量；
依次將多邊形 A 和 B 的所有頂點與原點組成的向量投影到這個分離軸上，并記錄兩個多邊形頂點投影到分離軸上的最小值和最大值（Pmin，Pmax），形成一個投影線段；
判斷這兩個投影線段是否發生重疊，若不重疊，則有（PAmax < PBmin）||（PAmin > PBmax）；
若兩個投影線段不重疊，則代表存在這樣一條直線將兩個多邊形分開，兩個多邊形不相交，可以直接退出循環；
若兩個投影線段重疊，則回到步驟1，繼續以邊2的法向量作為分離軸，進行投影計算；
當兩個多邊形的所有邊都檢查完之后，找不到這樣一條分離的直線，則意味著兩個多邊形相交。