GJKアルゴリズムについて調べたことのまとめ

3072 ワード
Physics 3D Simulator 3D テキストリンク

物体の衝突判定を高速に行いたい物理エンジン界隈の人たちは，GJKアルゴリズムというのを使っているらしく，調べたのでメモする．

名前はいかついものの，実は簡単なアルゴリズムになっている．
分かりやすい記事は以下．

ミンコフスキー和（差という人もいる）

  • ミンコフスキー和という，形状同士の足し算の概念がまずある
  • 形状Aと形状Bが接触している場合は，AとBは少なくとも内部の1点を共有している
  • つまり，Aと-Bのミンコフスキー和が原点を含んでいることになる

形状Aと形状Bが接触しているかどうか，つまり，
True / Falseの情報は，A-Bのミンコフスキー和が原点を含むか否かという話と等価であることになる．
そして，ミンコフスキー和が原点を含むかどうかは，高速に判定するアルゴリズムがあって，それがGJKアルゴリズム．

ただし，実際にミンコフスキー和は求めない！というのがポイント．
ここでは，形状AとBを凸であるとする．
Aを構成するvertexが$n_A$個，Bを構成するvertexが$n_B$個であるとすると，A-Bのミンコフスキー和を構成するvertexは$n_A \times n_B$個ある．（実際はそのconvex hullとなる）
これは計算量が多いということで，サポート写像という考え方をして，実際にミンコフスキー和を求めること無く話を進めることができるというからくりになっている．

以上のことは https://www.youtube.com/watch?v=Qupqu1xe7Io を見ればすぐ分かる．

simplex: 単体

simplexは2Dなら三角形，3Dなら四角錐のことを指していて，ミンコフスキー和が原点を含むかどうかを考える際にsimplexが原点を含むかどうかという捉え方をする．

GJKアルゴリズム

http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/ に載っている説明を可視化してみた．
一番最初のサポート写像の方向は，AとBの中心を結ぶ方向ベクトルが良いらしいので，そうした．

上のブログのコメントにも書いてあるが，サポート写像の求め方は，形状Aのvertex$n_A$個のそれぞれの内積の最大値と形状Bのvertex$n_B$個のそれぞれの内積の最小値の差分となって，$n_A + n_B$回の計算が必要となる．
もし，形状がprimitiveの場合，例えば円の場合はサポート写像は自明に求まることを利用すると，計算が早くなるのもポイント．
なので，URDFとかではvisualize用のモデルとcollision用のモデルが分かれているのかなと思う．

https://www.medien.ifi.lmu.de/lehre/ss10/ps/Ausarbeitung_Beispiel.pdf の3.3を読むと納得できる．

距離を計算するのはGJKアルゴリズムの外側の話になる