碰撞檢測算法

碰撞檢測算法有很多，直接檢測代價很大，一般使用多種算法進行優化。

首先會對物體生成包圍盒，例如AABB包圍盒，該盒的面平行于XYZ軸，對包圍盒是否碰撞進行檢測，如果包圍盒碰撞，那麼就需要進一步檢測。我們還會對物體生成凸多面體進行包圍。當然碰撞檢測一般針對的是動态物體和動态物體或者動态物體和靜态物體。

粗略階段：

1.利用空間劃分，例如使用八叉樹，劃分後不在同一節點的兩物體可以認為不會碰撞。

2.N個物體兩兩檢測的話代價為O(N²） 可以使用Sweep and Prune算法，該算法的思想是在X,Y,Z三個軸上對AABB包圍盒進行Overlap檢測，包圍盒隻有在三個軸上的投影重疊才算相交。做覆寫檢測前首先要對各個包圍盒按軸的坐标進行排序，代價為O(nlogn),但是可以利用幀間一緻性（這個思想是如果上一幀排序了，下一幀隻要對運動的物體進行插入排序即可，即插入排序）這樣代價為O(N)

中間階段：

将物體用複合包圍盒進行包圍，例如椅子可以用兩個不同大小的長方體包圍，周遊這些結構，找到可能碰撞的子包圍盒。

精确階段：

這一階段需要對凸多面體進行檢測，可以使用兩個算法。

1.分離軸定理(separating axis theorem) 。對凸多變體每個面作為可能的分離軸的面，作過原點的垂直于分離平面的線，求每個面在該線上投影，看是否重疊，如果所有情況下都重疊，則相交。

2.GJK算法。該算法依賴于闵可夫斯基差，即對AB兩物體每對點作減法，看做差後的點是否能形成一個過原點的四面體。GJK是一個疊代算法，即先随意找一個四面體，看哪個方向靠近原點，搜尋原點附近的點加入到目前點集中，不斷疊代直到找到一個過原點的單純體，或者失敗。