Game Tech Lounge (GTL)

ゲーム開発技術の情報共有

ミンコフスキー差を使う衝突検出法

衝突検出

分離軸判定法よりも、さらに汎用性の高い衝突検出アルゴリズムがミンコフスキー差を利用する方法である。この手法では、あらゆる凸形状を衝突検出の対象にできる。

ミンコフスキー差？

ミンコフスキー差(Minkowski Difference)とは、判定対象の形状のうち、一方を反転して合成した形状のことであり、衝突検出にとって非常にありがたい特性を持っている。この形状内に原点が含まれていれば２つの物体は交差していると判定でき、さらに、原点から最も近いミンコフスキー差表面上の点が、衝突点となる。原点からこの点へのベクトルがそのまま衝突法線と貫通深度を表す。なお、ミンコフスキー和というものもあるらしいが、その用途は不明である。少なくとも衝突検出では使わない。

f:id:pfxtech:20210822045943p:plain

  1. 交差する２つの凸形状AとB
  2. Bを反転
  3. 反転したBをAに合成する。この形状がミンコフスキー差となる
  4. 原点からの最近接点が衝突点、ベクトルは衝突法線と貫通深度を表す

凸形状AとBが共にメッシュである場合、以下のような処理でミンコフスキー差上の頂点を計算することができる。（ただし、頂点はすべてワールド座標系とする）

void calcMinkowskiPoints(const Vector3* pointsInMeshA, int numPointsInMeshA, const Vector3* pointsInMeshB, int numPointsInMeshB )
{
    for(int i=0;i<numPointsInMeshA;i++)
    {
        for(int j=0;j<numPointsInMeshB;j++)
        {
            Vector3 minkowskiPoint = pointsInMeshA[i] - pointsInMeshB[j];
        }
    }
}

ミンコフスキー差は２つの形状を合成した形状なので、ミンコフスキー差内にある点はすべて各形状内のローカルな点と対応付けされる。このため、検出されたミンコフスキー差上の衝突点は、それぞれの形状のローカルな衝突点を合成したものとなる。また、ミンコフスキー差内の面（２次元では辺）の法線ベクトルは、実は分離軸そのものである（つまり、ミンコフスキー差内のすべての面が分離軸候補）。ミンコフスキー差は２つの形状を合成したものなので、合成して面を作れるのは元になる形状の辺と面の組み合わせである。このことからも、分離軸判定法における分離軸候補が、辺と面の組み合わせから得られることがわかる。

ミンコフスキー差さえ構築できれば、あとは原点からの最近接点を計算してしまえばよいというのは理解できたとして、球やカプセル、円柱といった曲面のある形状が絡んだ場合、そう簡単にはミンコフスキー差を構築できそうにない。ポリゴンモデルであれば力業でなんとかなりそうだが…。

そこで、ミンコフスキー差を利用する衝突検出アルゴリズムとして、GJK+EPA, MPRといった手法が考案されている。これらの手法では、直接的にミンコフスキー差にアクセスすることを巧妙に回避している。GJKは考案者の頭文字らしいが、EPAのほうはExpanding Polytope Algorithmの略であり、そのままアルゴリズムの内容を表している。

GJK+EPA

ミンコフスキー差を用いる有名な手法としてGJKがある。しかし、GJK自体は形状間の最近接距離を検出することしかできない。衝突を検出するには、GJK処理中に物体の交差が判明した時点で、EPAという補助アルゴリズムに移行しなければならない。

GJKの流れは、ミンコフスキー差内の一点からスタートし、これをシンプレックス（単体）になるまで膨らませていくというプロセスになる。シンプレックス（単体）とは、その次元における最も簡素な多面体を表す。２次元では三角形、３次元では三角錐になる。この際、サポート写像という操作を通して各形状にアクセスし、ミンコフスキー差上の点を取得する。サポート写像の操作は、ある方向に対し、最も遠くにあるミンコフスキー差上の点を取得するというものである。これは要するに形状の分離軸上への投影と同じ処理であり、同じコードをそのまま再利用できる。

f:id:pfxtech:20211230085321p:plain

判定軸上で最も遠くにあるミンコフスキー差の点は、各形状のローカル座標系における最も遠くにある点の差から計算できる。

なお、GJKの処理の概略は以下のようになる。各プロセスにおいて、特定の方向におけるもっとも遠い点を検出する必要があり、ここで上記のサポート写像の操作が呼び出される。

f:id:pfxtech:20211003143218p:plain

  1. ミンコフスキー差内の適当な点から原点への方向で、もっとも遠い点P1を取得
  2. P1から原点に向かう方向で、もっとも遠い点P2を取得
  3. 線分P1P2上の原点からの最近接点を計算し、そこから原点に向かう方向で、最も遠い点P3を取得
  4. シンプレックス（三角形）P1P2P3に原点が含まれるため２つの形状は交差していることが判明。GJKはここでストップ。

もしシンプレックス内部に原点が含まれない場合、原点から最も遠い点を除いて、再度処理を３から繰り返す。原点を含まないままシンプレックスがミンコフスキー差の表面まで到達した場合は、ミンコフスキー差の外側に原点があり、つまり、２つの形状は交差していないことがわかる。この場合、原点からシンプレックスまでの最近接距離が、２つの形状間の最近接距離を表す。

この例では２Dのため、シンプレックスは３角形であるが、３Dのシンプレックスは三角錐となる。３Dではステップ４からさらに画面奥行方向に三角形を拡張し、三角錐を作り、原点がこの三角錐内に含まれているかどうかをチェックする。

シンプレックス内に原点が含まれていて、交差が判明した時点で、GJKは処理を続行できないため、衝突情報を検出するための補助アルゴリズムEPAを開始する。EPAは開始時に、GJKから得られた多面体（ポリトープ）を引き継ぎ、それを原点を含めた状態を維持しつつ、原点から最も近い表面へと拡張していく。なかなかわかりやすい説明が難しいが、要は最終的に求めたいのは、原点から最も近いミンコフスキー差上の点である。

続いて、EPAの処理の概略を以下に示す。

f:id:pfxtech:20211003143259p:plain

  1. GJKで得られたシンプレックスからスタートする。原点からシンプレックスへの最近接点を求め、その方向で、もっとも遠い点Q1を取得する。
    ※もし、GJKがシンプレックスで終了していない場合、シンプレックスとなるように、形状を拡張する。（線→三角形→三角錐）
  2. １で得られた点Q1を含むように、シンプレックスを多面体に拡張。原点から多面体への最近接点Vを算出する。
  3. ２で取得した点Vはミンコフスキー差上の点なので、これが衝突点となる。もし、この点がミンコフスキー差上の点でないならば、再度、Vの方向で、もっとも遠い点を取得し、多面体を拡張していく。

基本的に、どちらのアルゴリズムも同じ手順を繰り返すため、ある程度のカウントで処理を打ち切るのが一般的である。処理を打ち切った場合、そこまで計算した結果から、近似的な衝突点が得られる。

GJKのほうは、シンプレックス完成で処理が終わるが、EPAの多面体は探索完了まで、延々と拡張されていく。多面体を拡張していく過程は文章で書いた以上に込み入った実装になるため、バグの温床となりやすい。さらに、複雑な形状では、なかなか最適解まで収束しない可能性がある。このため、多面体の構築における精度的な安定性など、GJKと比べ気を配らなければならない部分が多く、繊細な実装が要求される。

＊以下のリンクのGJK+EPAの解説がわかりやすい

http://angra.blog31.fc2.com/blog-entry-115.html

＊GJK+EPA実装の詳細についてはオープンソース物理エンジン"Bullet"が参考になる

https://pybullet.org/wordpress/

https://github.com/bulletphysics/bullet3

参照先→bullet3/src/BulletCollision/NarrowPhaseCollision/

MPR(Minkowski Portal Refinement)

Game Programming Gems 7という書籍でMPR(Minkowski Portal Refinement)と呼ばれる、ミンコフスキー差から衝突を検出可能な別の手法が紹介されている。EPAのように多面体を作らずに、ポータルと呼ばれる構造を更新していくことで原点からミンコフスキー差への近接点を探索することができる。ポータルはシンプレックスであり、２Dでは三角形、３Dでは三角錐となる。サポート写像を通してミンコフスキー差にアクセスする部分は概ねGJKと同じだが、EPAのように多面体の拡張といった煩雑な操作を必要とせず、一気に衝突点へ収束させることができるのが実装上の大きな利点になる。

MPRの処理の概略は以下のようになる。

f:id:pfxtech:20211003144731p:plain

  1. ミンコフスキー差内の１点を決める。これをO1とする。
  2. そこから原点までの方向で、もっとも遠い点P1を求める。
  3. 原点から線分O1P1への最近接点を求める。この点から原点への方向で、もっとも遠い点をP2とする。
  4. 初期ポータルO1P1P2ができる。初期ポータルが原点を含んでいないときは、再度ポータルを作り直す。
  5. 次に、ポータルの辺P1P2から外側に向かう方向で、もっとも遠い点P3を取得する。
  6. 元のポータルをO1P1P3、O1P2P3に分割、原点を含むほうO1P1P3を残す。
  7. ポータルがミンコフスキー差の表面に到達したので、処理はここで完了する。原点からの最近接点を衝突点として取得する。

７でポータルの出口がまだミンコフスキー差の表面まで到達していないときは、到達するまで処理を５から繰り返す。

MPRは直観的にわかりやすいのだが、実装してみると、対処できないケースがあることがわかる。GJK+EPAと違い、最初の一点からポータルの判定を進める方向を一度決定すると、アルゴリズム上、最初に決めた点（O1）を調整する仕組みがなく、方向が間違っていても処理は止まらず、そのまま最適でない答え（つまり原点から最近接でないミンコフスキー差上の座標）に行き着いてしまう。場合によっては近似値とはいえないほどの結果になる。球体に近い形状よりも、一方向に引きのばされた形状では、この問題がより顕著になる。

f:id:pfxtech:20210825092945p:plain

最初の一点の決め方によって、最適でない衝突点が検出されるケース

最適でない結果が返された場合は、他の方向にポータルの方向を変えてやるという操作を追加で実装しなければならない。イメージとしては、ポータルをいろんな方向に向けてMPRプロセスを複数回実行し、最も貫通深度の浅いものを選べばよい。このように実用レベルで使う際は、補助的な仕組みを用意してやる必要があるとはいえ、EPAと比べ実装は直感的でわかりやすく、動作も高速で扱いやすい。またGJKと組み合わせて、EPAの代わりにMPRを使うことも可能だろう。

＊WikipediaのMPR説明

https://en.wikipedia.org/wiki/Minkowski_Portal_Refinement

＊MPRアルゴリズムの詳細はこちらのリンクがおすすめ

http://xenocollide.snethen.com/mpr2d.html