GJK & EPA 筆記

金秘書Contact Info為何那樣？

again 在這篇文章看到下面這張圖 

圖1

第1時間不太明白為何Contact Tangent長那樣？

還有Coliider B的Contact Point 為何是P_B？ 

只好請出Google 翻譯

老老實實把GJK和EPA認真讀過一遍

發現不少上次沒注意到的細節(知識綠洲) 🧐

GJK的適用對向

之前以為GJK只能用在2個凸多邊形

但其實它可以用在2個凸集

圓形也算是凸集，所以上面的圖1可以用GJK得出是否發生交疊

Minkowski差

就是下面的黃色區域 

在Allen Chou的文章裡又把它稱為CSO

玩看看

GJK的核心思想

2D版：

不需要一開始就建立整個CSO

而是利用Support Function逐步擴展Simplex

點 ⏩ 線 ⏩ 三角形 

如果三角形如果包含原點

就代表2個凸集交疊

否則就退化回到線

再重新擴展成三角形

詳細過程可以參考這篇文章GJK

3D版：

利用Support Function逐步擴展simplex

點 ⏩ 線 ⏩ 三角形 ⏩ 四面體

如果四面體如果包含原點

就代表2個凸集交疊

否則就退化回到三角形

再重新擴展成四面體

為什麼叫Support Function？

再次借用Allen Chou另一篇文章的圖片

兩本平行的書不斷靠近
最終可以夾住中間的茶壺
這不就是Support(支撐)嗎

類似上圖，Support Function(v)的目的是

找出CSO沿著某個方向的最遠端點

v方向的最遠端點是是E'

黃色是完整的CSO

使用Support Function即使不知道CSO的全貌

也能做到上面說的：逐步擴展simplex

CSO邊界和原點的最短距離

case 1

找出CSO邊界上和原點最靠近的最近邊 (黃色區域左下方的粉紅邊)

就可以得到最近點(和原點最接近)

紫色是最近距離

如同最近點是最近邊上的內插點

最近點是邊AD上的內插點

最近點就是Collider A的Contact Point

有了最近點，再移動紫色距離

就可以得到Collider B的Contact Point ➡️  F 

case 2

找出CSO邊界上和原點最靠近的最近邊 (黃色區域左上方的淡藍色邊)

就可以得到最近點

如同最近點是最近邊上的內插點

最近點是邊FG上的內插點

最近點就是Collider B的Contact Point

有了最近點，再移動紫色距離

就可以得到Collider A的Contact Point ➡️  A 

EPA(Expanding Polytope Algorithm)

2D版：

利用GJK找到的Simplex

逐步擴展成包含最近邊的Polytope

Simplex是三角形

Polytope是凸多邊形

詳細過程可以參考這篇文章EPA

3D版：

利用GJK找到的Simplex

逐步擴展成包含最近三角形的Polytope

Simplex是四面體

Polytope是凸多面體

CSO邊界和原點的最短距離(圓形vs多邊形)

前面提到EPA主要在找出最近邊

但在下面這種case

最近邊是圓弧上的點

玩看看

我用EPA試了一下

人工迭代幾次之後，發現似乎可以用圓形來加速 🤔

用圓形加速

既然最近邊是圓弧上的點

那就直接使用圓形來找出最近點！

原點到圓形的最近點
玩看看

這個方法在下面一些case真的有用

圓點在圓形內的case

圓點在2個圓形內的case
最近點找距離大的那個

圓點不在圓形內的case

但在這些case還需要額外的判定

case A
原點在圓內，但最近邊不在圓上
(最近邊和邊AB平行)
玩玩看

在上面這個case

原點投影到最近邊的投影點合法(投影點位在藍色最近邊內)

所以藍色最近邊是最近邊

粉紅色投影點是最近點

case B
原點在圓內，最近邊在圓上
玩玩看

在上面這個case

原點投影到最近邊的投影點不合法

所以藍色最近邊不是最近邊

紅色點才是最近點

現在，終於可以回到本篇一開始的問題

Contact Info為何那樣？

比對實驗結果

case A
左邊Collider的Contact Point位在邊上(就是最近點)

case B
左邊Collider的Contact Point位在頂點上(點B)

不管是case A還是case B

2個Contact Point的連線(紫色線段)方向，就是contact Normal的方向
2個Contact Point和右邊Collider的圓心會3點共線

圖1

但圖1裡2個Contact Point分別是P_B、P_A

P_B、P_A的連線方向，和contact Normal不一樣

2個Contact Point和右邊Collider的圓心也沒有3點共線

互換Collider B和Collider A

多邊形是Collider B、圓形是Collider A

土黃色是 Support(v,A) + Support(v,-B) 

草綠色是 Support(v,B) + Support(v,-A) 

看起來2種結果只是差在

沿著x軸進行一次鏡像、況著y軸進行一次鏡像

結語

2天前本來要放棄的我

回過神，現在又在這裡了 ⛳

有一種淡淡(蛋蛋)的味道叫做幸福 😋🤠 荷包蛋 like