從零開始手敲次世代遊戲引擎（四十二）
接從零開始手敲次世代遊戲引擎（四十一），繼續完成我們自己的物理引擎的碰撞檢測。
上一篇我們為場景物體綁定了AABB碰撞盒，並實現了圖形化調試功能來顯示這些AABB碰撞盒。
通過這樣的可視化表示，我們很快就能意識到，AABB碰撞盒檢測雖然高效，但是是十分保守的，因為它與大多數場景物體之間的差異是很大的。
比如在我們上一篇場景當中的圓錐體，它與它的AABB碰撞盒之間存在大量的空隙。如果僅僅使用AABB碰撞盒進行碰撞檢測，這就意味著很多都是「False - Positive」，也就是誤報——明明沒有碰到，卻被報告為碰撞。
如果我們是在開發一款FPS遊戲，那麼這就意味著極高的命中率——哪怕子彈實際並沒有擊中敵人或者我們自己，遊戲也會判定為擊中。這顯然是很有問題的。
在早期的遊戲裡面，如街機的《雷電》系列（當然，它其實是一個2D遊戲），由於其玩法就是彈幕式玩法，在彈幕中穿梭是其主要的樂趣和炫技點。因此這個時候碰撞盒就不能夠太保守，否則根本無法在彈幕當中穿梭。然而那個時候的硬體水平也很難支持AABB之外更為複雜的碰撞演算法，所以實際上在早期版本當中採用的是縮小碰撞盒，也就是實際上碰撞盒並沒有包含飛機的全部，而只是包含了其機身的一部分的做法。所以在《雷電》或者類雷電系飛行射擊遊戲當中，我們經常可以看到子彈明明集中了機翼，但是沒事的情況。
當然，這種做法在今天已經顯得過於簡陋，並且對於非彈幕類型的遊戲，特別是FPS類型的遊戲，是完全不可以接受的。當今的遊戲所採用的物理碰撞檢測一般可以分為兩個階段：
- Broad Phase，也就是寬鬆檢測階段。這個階段因為需要檢測基本上所有可能的情況，所以一般採用較為輕量的演算法，如AABB，來首先找出所有可能發生碰撞的情況（包含False Positive)
- Narrow Phase，也就是逼近階段。這個階段目的在於排除False Positive。經過第一階段的檢測，我們需要處理的對象已經大大減少，因此這個時候可以採用更為精確（計算量較大）的方法進行更為精密的檢測
Broad Phase
AABB方法由於其本身所需的存儲空間小（對於每個包圍盒只需要存儲長寬高三個變數），以及重合檢測方便（只需要比較最大最小值），非常適合Broad Phase。然而，它所帶來的只是單次碰撞檢測方面的優化，對於需要檢測的次數並沒有任何優化。（依然是場景當中任意兩個對象的組合都需要檢測一次）
比如現在有一個物體位於三維空間的第一象限，並且正在朝X正方向進行移動。對於這種情況，顯然它在改變它自身的運動方向之前，不會與任何第一象限之外的象限當中的物體發生碰撞。
又比如一個FPS遊戲，我們位於一間倉庫的外面，而我們的敵人位於倉庫裡面。如果我們打出去的子彈不會穿過倉庫所在的空間，那麼我們的子彈是不可能會打中敵人。
上面這兩個例子說明實際上我們並沒有必要對所有的情況都進行碰撞檢測。第一個例子對應的是被稱為空間剖分的技術。象限就是被 這3個平面所剖分出的字空間。在三維空間當中，這樣的子空間是8個。如果我們再對子空間進行同樣的遞歸剖分，那就是所謂的空間八叉樹分割，是這種類型的代表演算法。
第二個例子所對應的就是被稱為層次包圍盒的概念。層次包圍盒就類似俄羅斯套娃，一個包一個。比如上面的例子，我們首先檢測子彈是否與倉庫的包圍盒有交，如果有，再檢測子彈是否與倉庫內的敵人群體的包圍盒有交，如果有，在檢測是否與某個具體的敵人有交，如果有，再檢測是與頭部有交還是身體，來決定是否是個爆頭射擊。
很容易可以想到，八叉樹空間剖分是將空間在每一個層級上進行均等的剖分，這種剖分是自頂向下固定並且與場景狀態無關的（雖然對於完全不含有場景物體的子空間我們沒有必要再進一步進行剖分）。它有著顯而易見的好處，那就是這個剖分結構是穩定的，不受場景結構變化的影響，而且其每個層次的子空間形狀大小固定，很容易迭代求交；然而問題也是明顯的，那就是對於較大的場景物體，在任何一個子層級上都可能會存在跨越多個子空間的情況，我們需要在每個子空間當中保存到它的引用，或者將場景物體進行進一步的切分。
而層次包圍盒方法則是基於場景結構的。它與場景結構本身咬合得比較緊，在同一個層級上也基本不會出現（應當避免出現）重疊的情況。在大多數情況下，層次包圍盒方法所形成的樹形結構無論是在寬度（degree）還是高度（height）上都要遠小於空間剖分法；但是同時，如果場景結構發生變化，那麼就需要重新構建這個樹形結構的全體或者一部分，這對於遊戲這樣的軟實時系統來說是一個不大不小的問題，需要靈活掌握。
Narrow Phase
通過Broad Phase篩選出的碰撞對（指任意一對可能會發生碰撞的場景對象），將進入Narrow Phase進行進一步的碰撞檢測，以排除由於碰撞盒和實際場景物體模型之間的差異所造成的False-Position，也就是誤報的情況。
如果場景模型本身就是簡單的幾何體（可以解析表達的幾何體），那麼我們可以之間通過求解方程組的方法來進行檢測。
但是更為一般的，我們的場景物體大多是通過一組頂點來進行描述的。整個模型並不可以被解析表達（至少不可以被連續光滑的函數進行表達），那麼就無法使用求解方程組的方式來檢測碰撞了。
對於這種情況，Bullet庫當中採用Convex Hull（凸包）來作為更為精確的碰撞盒來進行這一步的檢測。關於凸包的說明可以參考參考引用6，簡單的來說某個模型的凸包就是能夠包圍這個模型的所有頂點的最小凸多邊形。（也就是包圍盒，只不過不再局限為長方體，而是可以是任意凸多邊形）
什麼是凸多邊形？就是不是凹多邊形。。。好吧，等於沒解釋。。。就是任何一個地方都沒有凹坑的多邊形，這個解釋應該夠通俗了吧。如果還要繼續問什麼是多邊形的凹坑。。。從數學的定義上來說就是這個多邊形的任意兩個頂點之間的連線都是完全在多邊形的內部。。。更加通俗點兒來說就是如果每個頂點是一個胳膊肘子，那麼它們都是往外拐的。
那麼如何求出這個凸包呢？有很多演算法已經被提出，具體可以參考參考引用10。我們也會在後面具體實現的時候作進一步解釋。
然後一個需要介紹的就是閔可夫斯基和（Minkowski addition，參考引用5）。它描述了凸包一個很有用的特性，那就是任何一個大的實數向量集合（在我們這裡就是頂點集合）的凸包（在我們這裡就是凸多邊形碰撞盒）等於其子集（在我們這裡就是模型的各個部分）的凸包的閔可夫斯基和。通俗的來講，比如我們要求一個人的碰撞盒，我們可以分別求出這個人的手，腳，頭部等各個局部的碰撞盒，然後將他們（用閔可夫斯基和）組合起來。（大致講法，其實不對。因為人體並不是手腳等的閔可夫斯基和。用手腳合成人體實際是集合的求合集運算，非閔可夫斯基和）
在有了頂點組的凸包之後，我們就可以採用Gjk演算法（參考引用4）來完成任意兩個凸包之間的距離計算了，並使用閔可夫斯基和迭代逼近最終結果。（也就是碰撞檢測）
但是請注意，凸包依然是包圍盒，並不一定完全等同於場景模型，特別是對於有凹坑的模型。所以，這依然是一個捨棄精度的計算，只不過遠比AABB方法要精確得多了。
下一篇我們來將這些放入到我們自己的物理引擎裡面。
參考引用
Bounding volume hierarchy
https://www.codeproject.com/articles/832957/dynamic-bounding-volume-hiearchy-in-csharp
Convex hull - Wikipedia
Output-sensitive algorithm推薦閱讀：