從零開始手敲次世代遊戲引擎（四十五）

04-04

在從零開始手敲次世代遊戲引擎（四十四）當中，我們完成了凸包的演算法。現在我們可以進入基於凸包的碰撞檢測了。

基於凸包的碰撞檢測的著名演算法是GJK（Gilbert–Johnson–Keerthi distance algorithm，參考引用1）演算法。這個演算法利用了閔可夫斯基差的重要特性：如果兩個凸包相交，那麼它們的閔可夫斯基差必然包含坐標原點。

其實這是一個很顯然的事情。所謂閔可夫斯基差，就是兩個集合當中所有的元素的差組成的集合。如果兩個集合有交，那麼這兩個集合必然有共通的點，那麼這些點的差必然為零。

除此之外，如果兩個凸包的閔可夫斯基差不包括坐標原點，那麼這個差（依然是一個凸包）到原點最近的距離就代表了目前這兩個凸包之間最近的距離。

不過，如果我們要顯式計算閔可夫斯基差，就需要計算兩個集合當中任意兩個元素的差。這顯然是非常龐大的一個計算量。GJK演算法的優勢在於，它不需要計算整個閔可夫斯基差，而是能夠從任意一個閔可夫斯基差當中的點快速迭代逼近坐標原點（或者坐標原點本身）。

參考引用當中的文章對於GJK演算法進行了詳細的介紹。所以我這裡就簡單用中文介紹一下思路。

對於任意一個給定的方向，我們都可以在凸包上面找到一個點滿足這個點是凸包在這個方向上的極值點（也就是最遠的點）

那麼，顯然，對於兩個凸包（A，B），如果我們先按照某個方向d找到A到極值點，再按照d的反方向-d找到B的極值點，那麼這兩個極值點的差一定是A與B的閔可夫斯基差的凸包上的點（閔可夫斯基差的極值點）。我們命名這個點為P。

接下來，我們從這個點出發，尋找最接近坐標零點但是位於A與B的閔可夫斯基差內的點。方法是從P看坐標原點，得到一個方向。用這個方向再次找到A與B上的極值點，取它們的差，又得到另外一個閔可夫斯基差凸包上的點。如果這個點就是P，那麼說明P已經是距離坐標原點最近的點，且如果P不是原點，那麼說明A與B的閔可夫斯基差不包括原點，A與B不相交（沒有碰撞）。P點到坐標原點的距離就是A與B之間的最小距離。

如果新得到的點並不是P，我們將它命名為Q，那麼線段PQ一定比P更接近原點且PQ上所有的點都位於A與B的閔可夫斯基差的凸包內（根據凸包定義，凸包上任意兩點的連線必在凸包內）

那麼接下來我們就是計算PQ線段上離開原點最近的點，這個點可能是在PQ之間，也可能就是Q。無論哪種情況，我們都能得到一個與P不同的點。這個點到原點的方向就是繼續迭代的方向。

在這個過程中，每次迭代我們都會得到一個新的位於A與B的閔可夫斯基差的凸包上的點，比上一次迭代更加接近原點（如果不是，則說明上一次的點已經是最近點，迭代結束）。但是這裡我們需要注意的是，對於3D的情況，我們想要尋找的原點（或者最接近原點的點）可能位於A與B的閔可夫斯基差的凸包的頂點、邊、面甚至是內部。所以每次迭代的時候，我們需要首先移除之前迭代產生的無關的點，然後根據剩下的點的個數決定使用何種演算法找出本次迭代的最近點。

比如，我們第一次迭代，得到一個點，第二次就有兩個點了。如果第二次的最近點在這兩個點的連線上，那麼這兩個點都要保留；如果第二次的最近點就是第二次找到的點，那麼刪除第一次的點。

如果第二次保留了兩個點，那麼第三次迭代得到一個新點之後，就會有三個點。這時，我們需要計算的就是這三個點組成的三角形當中，到原點最近到點了。如果這個點位於三角形內部，那麼我們需要將這3個點都保留到下次迭代；如果最近點在三角形的一條邊上，那麼我們只需要保留這條邊的兩個頂點。

第四次迭代，如果第三次迭代保留了3個點，那麼加上這次的就是4個點了。這4個點組成了一個四面體。這時，原點要麼位於四面體內，要麼在其外。如果在四面體內，說明原點在A與B的閔可夫斯基差當中，A與B相交（碰撞），迭代結束。如果在四面體外，那麼它必然在某個表面的上方，我們保留這個表面（三角形），刪除不在這個表面的頂點，這樣又回到3個點的情況，可以繼續迭代了。

下面的視頻給出了隨機生成兩組點，然後對這兩組點各自計算其凸包，並且在每次凸包計算（迭代）之後通過GJK演算法檢測碰撞的過程。當發生碰撞的時候，凸包的顏色會變成黃色。

結合前一篇文章我們可以看到，無論是場景物體的凸包的計算，還是凸包之間碰撞的檢測（GJK演算法），都是迭代演算法。就如同我們視頻里的例子，雖然每組點集當中都有1000個點，但是我們還是可以通過短短數次迭代就檢測到兩個點集之間存在交集（即，兩個場景物體有碰撞）。這種可以逐步迭代且快速收斂的演算法特別適合遊戲這樣的應用。

https://www.zhihu.com/video/957281892085493760