世界碰撞演算法原理和總結（sat gjk）
序言
此文出於作者的想法，從各處文章和論文中，總結和設計項目中碰撞結構處理方法。如有其它見解，可以跟作者商討。（楊子劍，[email protected]）。
在一個世界中，有多個物體，物體可以分為運動的物體和靜止的物體和地形。而世界是很寬廣的，本文致力在處理物體之間的碰撞，地形的碰撞後續處理。
處理流程
世界是寬廣的，同樣世界中物體也是多個的。每個物體一直頻繁的檢測是浪費效率的（畢竟運動的物體和根本碰不到的物體檢測完全沒必要）。
分為兩個階段：粗檢測（篩選出來會碰撞到的物體） – 細檢測（兩兩碰撞檢測）
GJK演算法
Gjk演算法最初是用來算兩個物體的具體，之後因為穩定和快捷，可以用來初檢測碰撞。
原理：是算兩個物體的頂點差，其實就是距離，得出頂點距離的集合，算出來的多邊形是否包含原點，當包含則兩物體相交。
SAT分離軸演算法
分離軸演算法，可以很好的檢測出來碰撞點和碰撞點的深度。
原理：當兩物體相交，那這兩物體從任意方向看過去都是相交的。對應的就是在各個方向的投影都有交疊。
粗檢測-空間分割
四叉樹
面分割方法，世界大小的正方體是根節點，同等分割四份如果一個物體在一個分支中，找到最小能容納他的正方體分支。一般情況是根據x y 來分割。
八叉樹
空間分割法，其實是比四叉樹多一個z的方向的分割，是三維的。
鬆散四叉樹/八叉樹
鬆散八叉樹其實是為了解決邊界問題，當一個物體在四叉樹邊緣不斷的從一個區域到另一個區域會導致節點不斷的更新節點，層級也會發生變化，為了解決這一問題，提出了兩個概念。
- 入口邊界，入口邊界等於四叉樹/八叉樹的真正邊緣。
- 出口邊界，出口邊界比四叉樹/八叉樹的真正邊緣大。
出口邊緣具體大多少沒有一個明確的定義，大多數為如果邊緣的2倍。
當物體移動時，先判斷是否出出口邊緣，如果沒出，則還在當前節點和深度，如果出了則從新尋找入口邊緣找到對應的深度和節點。
層次包圍盒樹
層次包圍樹用於精確檢測，當一個物體的形狀是複雜的，多個不規則多邊形組合在一起的時候，用此方法最好。例如人由頭、身體、手、腳組成，當各個部位運動時，從下往上遞歸改變父節點的包圍盒。
還有一種用法是，當其中一個物體在空間中改變位置的時候，pop形狀-刷新分支節點包圍盒-重新加入包圍盒樹，計算bvh。
一般包圍盒形狀是統一的，aabb、球、或者box。
球構造很快（圓心和半徑）。
碰撞檢測快，因為當父節點aabb不想交或者射線檢測不到，則子節點無需檢測。
細檢測-運動中物體檢測
當物體在程式碼中模擬運動的時候，是離散的狀態，每次經過dt的時間計算下一次的碰撞。碰撞的兩物體因為dt的時間長短，很有可能發生穿插的問題。下面介紹了兩種檢測方法。
連續碰撞檢測
把這段狀態積分化，或者函數化，求導數的極致，來求得最後在dt中某個時間的碰撞。大連理工大學機械工程學院《凸多面體連續碰撞檢測的運動軌跡分離軸演算法》- 2013
1月張應中發表，這篇論文實際是應用了gjk的理論，並加上射線檢測，求得最終的碰撞點。裡面的演算法名稱叫做lccd。
天津大學電氣與自動化工程學院《基於gjk的凸體快速連續碰撞檢測研究》-2014年10月劉麗發表，fccd演算法，用於連續檢測碰撞。
上述兩種檢測演算法，因為都需要模擬中間一段的求極值得過程，實際效率並不如下面的非連續碰撞檢測。優點則是可以準確的求得當前碰撞的時間和點。
非連續碰撞檢測
非連續碰撞其實跟當前dt一樣，求當前幀是否碰撞。但如果精度不夠，可以繼續縮小精度，當人物在dt的過程中，可以認為一切的變化都是線性的，所以可以通過線性求得dt/8(再細分8次)的過程的裝態，判斷8次中有沒有碰撞。如果精度不夠，則可以再繼續劃分精度，求得更精細的離散過程。中間當然可以先判斷是否有可能在離散過程中可能碰撞。
物體與場景碰撞
其實是物體跟三角形求出最近點，不讓穿透。射線檢測求相交。
物體形狀碰撞效率
多邊形和不規則多邊形的碰撞檢測，有規律的多邊形，一般為三角面，長方體(box),aabb包圍盒、球體、膠囊體。圓柱等。
不規則的多邊形需要是凸多邊形（gjk和sat演算法都需要是凸多邊形），如果不是，需要通過演算法來把一個物體變為多個形狀。
現有的演算法三角面、aabb、球體、膠囊體是可以通過他們的特殊性快讀求得相交。而其他的需要通過sat具體來算出交點。Sat是a邊型與b邊型求交， 如果不交，則很快能得出， 相交需要判斷O(a*b)。
總結
演算法最後還需要根據實際場景來選擇。
