静止する２物体間の近接距離検出

ゲーム開発において、物体間の衝突検出以上に重要なのが、物体がどのくらい対象から離れているのかを検出する仕組みであろう。例えば、複数の敵との距離を測定し、最も近くにいる敵に自動的に照準を合わせるとか、ある一定距離以上離れている敵は無視するなど。他にも敵の移動する速度とキャラクター間の最近接距離が把握できれば、未来のどの時点で衝突が発生するかを正確に判定することができ、回避するか防御するかといった、キャラクターが次にとるべき行動を決定する際の判定に使うことができる。

高速に移動するキャラクターや乗り物を地形に沿ってスムーズに移動させたいときにも役立つ。乗り物の進行方向に配置された壁との距離を正確に測定できれば、その距離分は衝突せずに乗り物を移動させることができる。接触地点で進行方向を壁面に沿うように曲げてやり、再度次の接触までの距離を測定する。これを繰り返すことで、壁の凹凸に引っかからないスムーズな移動を実現できる。例えば、乗り物がある一定の速度で移動しているとすると、１フレームで移動できる距離を計算し、総移動距離がこの距離に達するまで、最近接距離を測りながら地形に沿って移動させていく。

このような物体間の距離の測定においては、両物体が静止しているか、一方が動いているか、もしくは両方が同時に動いているかでその検出難易度が変わってくる。つまり利用するアルゴリズムも、状況に応じて変える必要がある。重要なポイントは、いずれの状況においても、２つの形状を結ぶ最短となる距離を検出しなければならないということである。

もっともシンプルな形状間距離検出は静止している２つの球体間の距離を測るものだろう。これは単純に２つの球の中心間の距離を計算し、半径の合計分を引くだけでよい。球とカプセルの組み合わせでは、衝突検出のときに用いた幾何学計算アルゴリズムをそのまま再利用できる。この場合、２つの形状が交差していないとき、同様の計算から貫通深度がプラス（正）の値として得られる。

より複雑な凸包やボックス、円柱などの形状については、分離軸判定法やGJKを利用して形状間の距離を検出できる。どの手法を使うにしても、検出結果として、最近接距離だけでなく近接点と方向（法線ベクトル）を取得することができる。このような情報は、ゲームロジックの様々な判定で活用することができる。

分離軸判定法を利用する最近接距離検出

分離軸判定法は、多少の改良を加えるだけで2物体間の最近接距離を検出することができる。分離軸判定法のプロセスでは、分離軸候補となる軸を列挙し、２つの形状を個々の軸に対して投影し、その領域を記録する。この際、通常の衝突検出では、投影領域の交差しない軸が見つかった時点で、２つの形状が交差しないことが判明するため、早期に処理を終了することができる。しかし、最近接距離を検出するときは、そもそも前提として2つの形状は交差していないため、このような軸があろうがなかろうが、すべての分離軸候補に対して投影判定を行わなければならない。判定するのは下図のMinB～MaxA間の距離であり、これが最小となる軸が分離軸となる。なお、MinB-MaxAが負のとき（軸上でMaxA < MinB）、形状は交差している。

あとの処理は、衝突検出時とほぼ変わらない。分離軸判定からは互いに近接する面や辺といった特徴部を知ることができる。最近接距離は分離軸上に投影したMinB～MaxA間の距離に一致する。座標と法線が必要であれば、得られた特徴部間の最近接点を計算すればよい。

GJKを利用する最近接距離検出

衝突検出にGJKを使う際は、補助アルゴリズムEPAと組み合わせる必要があった。しかし、GJKは本来、最近接距離を検出するアルゴリズムである。最近接距離を測定する際は、EPAを必要としない。

以前の記事に書いたように、衝突検出におけるGJKではシンプレックスが完成した時点で、原点がシンプレックスに含まれるかどうかを判定し、含まれていればEPAに移行して衝突点を検出、含まれていなければ衝突はないものとして、処理は終了となった。最近接距離を検出する際は、原点がシンプレックスに含まれる場合は、２つの形状が交差しているため早期終了し、そうでなければ処理をそのまま続行する。シンプレックスがミンコフスキー差の表面に到達するまで、シンプレックス更新プロセスを繰り返す。

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

もし上記プロセス４の時点でシンプレックスが表面に到達しない場合、原点から最も遠い点を除いて、再度処理を３から繰り返す。最終的に、原点からシンプレックスまでの最近接距離が、２つの形状間の最近接距離を表す。

まとめ

衝突検出アルゴリズムの実装さえできていれば、最近接距離を検出できるようにすることはさほど難しくない。最近接距離が検出できるようになると、ゲーム内の様々な判定に活用できるようになるため、実用上の価値は高い。分離軸判定は実装しやすいが、分離軸の候補すべてに対しての処理が必要なため、パフォーマンス的には無駄が多い。特にポリゴンモデルのような、曲面部のない多面体形状では、GJKは非常に少ない判定回数で適切な解に収束する。今回はまずは静的な物体のみを対象とした。いずれ動的な物体の判定についても扱ってみたいと思う。

凸包x分離軸法のアルゴリズム最適化

凸包は三角形面もしくは四角形面を組み合わせた多面体であり、すべての面は頂点もしくは辺によって他の面と接続される。そして、凸包内の任意の点と点を結ぶ線は、決してどの面とも交差しない。一般的に、衝突検出アルゴリズムは凸形状のみを対象とするが、凹形状を扱えないというわけではなく、複数の凸形状を合成した形状として表現できる。つまり、凸包さえサポートできれば、相当な種類の形状を扱えるということであり、特に曲面を必要としなければ、その適用範囲は広い。

凸包の例（凸包内部の任意の2点間は決して表面と交わらない）

凸包でない形状の例（このような形状は、事前に凸包に分解しておく）

分離軸判定法の最適化

凸包同士の衝突を検出するアルゴリズムとして、分離軸法、GJK+EPA、MPR等、いくつか方法がある。このうち、比較的シンプルに実装できるのは分離軸法であろう。

しかし、分離軸法を凸包に適用するケースでは、面数の多い複雑な形状になるほど、判定しなければならない分離軸の候補数が一気に膨れ上がり、演算負荷が指数関数的に増加することが問題となる。可能な限り、判定する軸の数を減らすことが、パフォーマンスをキープする上で重要になる。

判定対象となる２つの凸包をそれぞれA、Bとすると、列挙される分離軸候補はAの面法線、Bの面法線、Aの辺とBの辺の外積方向となる。面法線の場合、その数はAの面数とBの面数を足した数に一致するが、辺と辺の外積の場合は、その組み合わせ総数はAの辺数×Bの辺数となり、判定数が膨れ上がる。

しかし、すべての候補となる組み合わせが、必ずしも分離軸になるわけではない。位置関係によってはあらかじめ候補から排除できる場合が多い。つまり、分離軸になり得ない組み合わせをあらかじめ排除することができれば、不要な計算量を大幅に減らすことができるはずだ。以下、ここで紹介する方法は、凸包にのみ適用できる分離軸判定法の最適化である。

近接部のみ判定対象とする方法

２つの凸包が接触している場合、接触部は当然お互いに最も近い部位となるはずである。とすると、離れている部位どうしは接触に何も影響しない可能性が高い。衝突検出実行前に、あらかじめこのような部位を排除しておくことで、無駄な判定を省けることが想定できる。

そこで、まずは２つの凸包のバウンディングボックスを比較し、交差する領域を大雑把に絞り込む。次に、その交差領域に重ならない面（とその頂点と辺）を判定対象から排除する。実際の衝突検出では、無駄な面が省かれた…、つまり一部分が欠けた凸包で処理を続行する。このような形状でも分離軸判定は正しく衝突を検出できる。もし、交差領域がない場合は、そもそも交差していないので、衝突検出する必要がない。

アイデアは単純だが、この仕組みで無駄な判定を効果的に排除できる。

Gauss Mapを利用する方法

判定不要な辺と辺の組み合わせを効率よく排除できるアルゴリズムとして、Gauss Map（ガウス写像）を利用する手法が考案されている。Gauss Mapとは、半径１の単位球上に、形状をマッピングしたものであり、具体的には凸包を以下のようにマッピングする。

1. 凸包の面法線を、単位球上の頂点にプロットする。
2. 辺を共有する２つの面に対応する単位球上の頂点をつなぎ、弧を描く。これがGauss Map上に投影された凸包の辺を表す。

このような操作をすべての面と辺に対して行う。つまり、単位球上の頂点は元の凸包の面が、弧は辺がGauss Map上にマッピングされたものとなる。

そして、２つの凸包を分離軸判定する際に、それぞれ２つのGauss Mapを同一単位球上に合成してみる。ただし、形状をA,Bとしたとき、Bの面法線は反転させてから合成する。このとき、それぞれの辺に対応する２つの弧が交差しているときのみ分離軸判定の候補となる。つまり、対応する弧が交差していない辺と辺の組み合わせは、分離軸判定から排除できることになる。

このことはミンコフスキー差の考え方からも理解できる。２つの凸包に対して、弧が交差している辺と辺の組み合わせだけが、合成した際にミンコフスキー差上に面を作るため、これ以外の辺の組み合わせは分離軸候補にはならない。（ミンコフスキー差の面法線＝分離軸候補）

弧の交差の判定方法は、平面の表裏判定で実装できる。２つの凸包の弧ABと弧CDが交差しているとすると、頂点CとDが弧ABの作る平面のそれぞれ別の領域にあり、かつ頂点AとBが弧CDの作る平面のそれぞれ別の領域にある場合、２つの弧は交差していると判定できる。式にすると、以下のようになる。外積で平面の法線を計算し、内積で表裏判定を行う。

さらに２つの弧は同一半球上になければならないという条件を加えなければならない。

２つの弧が同一半球上にない場合、明らかに2つの辺は交差しないため、判定対象から排除できる

これはBとCを通る平面に対し、頂点AとDが同じ側にあるかどうかで判定できる。そして、上記判定と同様に式を立てる。この式を、スカラー三重積を利用して変形すると、前の２つの計算で得られた値がそのまま使える。

式変形すると

あとは、この３つの条件に合うかどうかをすべての弧の組み合わせに対して実行すればよい。実際に試すと、この手法で8～9割ほどの不要な分離軸判定が排除でき、パフォーマンスへの貢献は大きいことがわかる。

※Gauss Mapの詳細な説明は下記で検索

GDC2013 The Separating Axis Test between Convex Polyhedra

まとめ

ここで紹介した2つの最適化手法はそれぞれ単独ではなく、組み合わせて使うことができる。実装はアイデアをそのまま直接的になぞるだけであり、効果も大きく、実用性は高い。

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

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

ミンコフスキー差？

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

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

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

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

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

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

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

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

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

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の処理の概略は以下のようになる。

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

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

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

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

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

＊WikipediaのMPR説明

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

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

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

分離軸判定法による衝突検出

分離軸？分離平面？

分離軸という言葉からは、何かを分けるための軸？のような意味合いが感じられるが、分離平面（分離軸＝この平面の法線）のほうが直感的にはイメージしやすい。２つの凸形状が接触していないのであれば、その間に必ず平面を挟み込める。この平面のことを分離平面と呼び、この平面の法線を分離軸と呼ぶ。もし、２つの物体が接近し、ギリギリで接していてお互いに交差していないのであれば、この平面は２つの物体をそれぞれの領域に分けることのできる平面となり、各物体はそれぞれ平面の片側にのみ存在し、平面上の１点で接している。図にしてみると以下のようになる。

どちらも凸形状の場合、平面（線）を２つの物体間に挟み込める

2次元では分離線、3次元では分離平面になる 

直感的にも、２つの物体が接していれば、どのような姿勢をとったとしても、この間に平面を挟み込めることがイメージできるのではないだろうか。これが貫通深度０の衝突になる。もし、物体の形状が凸形状でない場合、表面のどこかにへこんでいる箇所があることになり、平面を挟むことができない状態があり得る。つまり、2つの物体がどちらも凸形状でなければ、平面を挟み込むことはできない。

さらに、２つの物体が接近し、交差する場合を考えてみる。先ほどの接している状態から、一方の物体を平面に垂直な方向に動かしてみた状態をイメージしてみる。三角形のほうは、平面を越えて球側に食い込んでいる。この食い込んだ距離分、平面に垂直な方向、かつ球と逆方向に三角形を動かすと、衝突は解消できることがわかる（三角形を食い込ませたのと逆方向に動かしただけだから当たり前ではあるが…）。つまり、平面を越えて食い込んだ距離が貫通の深さになり、平面の向きはお互いを引き離す方向に一致している。そして、平面から元の領域を越えて、お互いに最も食い込んだ部分が、それぞれの衝突点を表している。

実際の衝突検出プロセスはこの平面の法線ベクトル（＝分離軸上）で行われる。分離軸上に２つの物体の形状を下図のように投影すると、形状AはMinA~MaxAに、形状BはMinB~MaxBにプロットされる。それぞれの投影範囲のうち、交差する部分(MinB~MaxA間)が貫通の深さを表している。また、MinBとMaxAがそれぞれ分離軸に沿って最も相手側に食い込んだ点であるため、つまりMinBとMaxAに対応するそれぞれの物体上の点が衝突点を表していることになる。分離軸に沿って、お互い逆向きに貫通距離分動かすと衝突を解消できることから、分離軸は衝突法線に一致する。

実際の判定処理は分離軸(Separating Axis)上で行われる。

要は、分離軸判定法のポイントとは、このような分離軸を2つの凸形状の間に見つけることであり。もし見つけることができれば、あとは2つの物体の分離軸上の投影範囲をチェックし、MinB < MinAであれば、交差していることが判定できる。そして、必要な衝突情報（衝突点、衝突法線、貫通深度）は分離軸から得られた情報をもとに計算することができる。

分離軸の見つけ方

分離軸の理屈自体は、シンプルで直感的でありイメージしやすい。では、実際にはどのように、2つの形状に対して、適切な分離軸を見つけることができるのだろうか？

演算負荷を一切無視できるのであれば、あらゆる方向の軸に対して、２つの凸形状を投影し、その交差範囲が最小となる軸（つまり貫通が最も浅くなる軸）を最適な分離軸として選び出せる。しかし、当然ながら無数に存在する軸をすべてチェックすることは現実的ではない。そこで実際には、あらかじめ想定される分離軸候補を絞り込んでから判定に進むようにする。

例えば、下図のように三角錐と球の判定であれば、想定されるすべての分離平面はあらかじめ列挙できる。これが分離軸のすべての候補となるため、他の方向は判定する必要がない。

• 球の中心から三角錐の各頂点へのベクトルx3
• 球の中心から三角錐の各辺へ垂直に引いたベクトルx6
• 三角錐の各面の法線ベクトルx4

この場合、合計3+6+4=13回の判定で、最適な分離軸を選び出せる。

メッシュのようにトライアングルから構成される凸包同士であれば、その形状の持つ幾何学特徴（頂点、辺、面）すべての組み合わせが分離軸の候補になる。つまり、頂点と頂点、頂点と辺、頂点と面、辺と辺、辺と面、面と面である。このうち、重複する同じ方向の組み合わせや、他でカバーできるケースを排除すると、最終的には、頂点と面、辺と辺が残る。最終的には、例えば三角錐同士の判定であれば、各面法線x8、辺と辺の外積ベクトルx36の合計44回で判定すればよい。

• 三角錐の面(x4)、2個分でx8
• 三角錐の辺(x6)と辺(x6)の組み合わせx36

なお、ボックスも凸包と同様の組み合わせから判定できるのだが、先にも述べたように、ボックスはローカル座標系の各XYZ軸に辺や面の向きが沿っているため、重複する面法線や辺の方向については一度だけの判定で済む。これを利用するとボックス形状同士の判定では、以下のようにトータルで15回と、大幅に判定回数を抑えられる。

• ボックスの面(x3)、2個分でx6
• ボックスの辺(x3)と辺(x3)の組み合わせx9

投影領域が重ならない分離軸が一つでも見つかった場合、２つの形状は交差しないことがその時点で判明するので、即座に処理を終了できる。もし、前回チェックしたときに、このような分離軸が見つかっていた場合、そのベクトルをキャッシュしておいて、次の判定に利用することができる。２つの物体の位置関係がそれほど変わっていない場合は、キャッシュしたベクトルによって早期に判定を終了できる可能性が高い。 

形状の分離軸上への投影

判定はすべて分離軸上で行われるため、凸形状がどのような形であっても、この軸上に投影することさえできればよい。

形状を軸上に投影する処理は形状毎に異なるが、以下のように大抵シンプルな実装で済む。これらの関数は、各形状のある軸上のもっとも最大となる点を返す。この点と分離軸の内積を計算し、軸上に投影した値が得られる。１形状に対し、判定軸axisと反転した-axisで２回呼び出せば投影範囲（とそのときの形状上の点）が得られる。複雑な幾何学計算などはまったく必要ない。注意点としては、以下は形状のローカル座標系で実行されることを想定している。つまり、axisはこれら関数を呼び出す前に、各形状のローカル座標系に変換されている必要がある（カプセルの向きはローカル座標系のX軸方向としている）

Vector3 ProjectSphereOnAxis(const Vector3& axis, const Sphere& sphere)
{
    return sphere.radius * axis;
}

Vector3 ProjectBoxOnAxis(const Vector3& axis, const Box& box)
{
    Vector3 position = box.extent;
    if( axis.x < 0.0 ) position.x *= -1.0;
    if( axis.y < 0.0 ) position.y *= -1.0;
    if( axis.z < 0.0 ) position.z *= -1.0;
    return position;
}

Vector3 ProjectCapsuleOnAxis(const Vector3& axis, const Capsule& capsule)
{
    Vector3 position;
    position.x = capsule.halfLength;
    position.y = 0.0;
    position.z = 0.0;

    if( axis.x < 0.0 )
    {
        position.x *= -1.0;
    }

    return position + capsule.radius * axis;
}

衝突点の計算

頂点と頂点の組み合わせで分離軸が決定されたのであれば、２つの形状はその頂点同士が最も相手側に食い込んでいることになり、これをそのまま衝突点として決定できる。それ以外の組み合わせの場合、例えば辺と辺、辺と面であれば、衝突点は計算によって求める必要がある。

衝突点の座標の求め方は、いろいろあると思うが、ここではひとつの方法を紹介する。分離軸判定の結果、衝突点における、衝突法線と貫通深度が取得できている。また、衝突している物体の最も食い込んでいる幾何学特徴の組み合わせもわかっている。そこで、両物体を貫通深度＋α、衝突法線方向にそれぞれ移動させる。これで衝突していない位置関係になり、ここから両特徴間の最近接点を計算する。特徴自体は大抵頂点や辺、面といった基礎的な幾何学形状であるから、その計算はシンプルに実装することができる。あとは、得られた点を、移動した分もとに戻せば、正しい衝突点の座標を求めることができる。

最終的な分離軸判定のプロセス

いままでの説明をもとにすべての処理を統合すると、全体的な分離軸判定の流れは以下のようになる。

1. 判定対象となる物体の形状から、分離軸の候補を絞り込む
2. 各分離軸候補に対し、それぞれの形状を投影して投影領域をチェック
   • もし、投影領域が交差していなければ、即座に処理を終了
   • 投影領域が交差しており、かつ交差距離が以前の軸より小さければ、この軸を記録
3. 最後まで残ったのが交差距離が最小となる軸であり、これが分離軸
4. 交差距離＋α、分離軸に沿って２つの形状を引き離す
5. 最近接点を計算し、衝突点を得る

なお、判定プロセスにおいて、形状毎に特化する処理は以下となる。

• 組み合わせ毎の分離軸候補の選定
• 形状の候補軸上への投影
• 最近接点取得

これらの処理ができるとわかれば、その形状には分離軸判定法による衝突検出を適用できる。例えば、球、ボックス、カプセル、円柱、凸包、など。

シンプルな衝突検出アルゴリズム

前回の記事では、基本的な衝突検出関数の形（入力と出力）について説明した。では、対応するプリミティブ形状の組み合わせ次第では膨大になるであろう、その関数の中身はいったいどう記述すればよいのだろうか？球と球であればシンプルな計算で事足りるが、ボックスやカプセル、もしくは複数の三角形から構成されるような複雑な形状にはどうやって対処すればよいのだろうか？

昔、何も知識がなかったころに、線や面の交差計算だけを組み合わせて、ボックスや三角錐などのシンプルな形状の衝突を検出してみたことがあった。衝突検出の結果を自前の物理演算に投入したところ、それっぽく動作したのだが、ある特定の位置関係になると、どうやっても正しい衝突法線と貫通深度を得ることができず、物体の挙動を安定させることはできなかった。やはり、ちゃんと理論的な裏付けのある手法でないと、安定した挙動を実現させることは難しいということを痛感させられた。

交差座標のみを検出する目的であれば、基礎的な点や線の交差を判定する幾何学的計算を組み合わせれば対処することができる。しかし、リアルタイムゲームというのは、基本的に実時間と同様に未来に向かって進んでいく。ここで衝突検出から知りたい情報は、衝突後、物体をどの方向にどのくらいの距離動かすと交差を解消できるのか、である。これがわからないと、後続のゲーム的表現には繋がらない。つまり交差点≠衝突点であり、線や面の交差判定では正しい結果を得ることができないのは当然だった。

交差点（左）と衝突点（右）の違い

交差点には、交差を解消するための情報はない！

凸形状同士の交差判定手法

凸形状同士の衝突を検出する一般的に使われる手法としては、おおまかに以下のように分けられる。

• 幾何学的な特徴を利用する方法
• 分離平面を利用する方法

幾何学的な特徴を利用する方法は、各形状ごとのユニークな特性を利用して、衝突を検出する。そのため、アルゴリズムは個々の判定ごとに異なる。つまり、判定対象となる組み合わせごとにまったく違う実装となる。その代わり、演算コストは低く抑えることができる。一方の分離平面を利用する方法では、形状毎の違いを最小限にとどめ、全体としては汎用的な仕組みで衝突を検出できる。その分、演算コストは高くなりがちである。

幾何学的な特徴を利用する方法

幾何学的な特徴を利用する方法とは、点と線分や線分間の近接距離計算などの基礎的な幾何学計算を利用して解く方法である。球と球の判定であれば、前の記事に書いたように、お互いの中心点間の距離と半径の合計の差分から、衝突を検出することができる。このとき、反発する方向は２つの中心を結ぶ直線方向に一致する。

|C1-C2| < r1+r2のとき、２つの球は衝突している。

衝突法線（球１を押す方向）：(C1-C2)/|C1-C2|

衝突点１（球１）：C1-r1*衝突法線

衝突点２（球１）：C2+r2*衝突法線

貫通深度：|C1-C2|-(r1+r2)

また、カプセル形状は厚みのある線分として扱うことができるため、球とカプセルの衝突検出は、点と線分の最近接距離を求め、２つの半径の合計と比較し、これよりも近接している場合は、衝突していることがわかる。反発する方向は球の中心点と、線分上の最近接点を結んだ方向に一致する。

|C-P| < r1+r2のとき、球とカプセルは衝突している。CPは衝突の方向を表す。

(Pは点Cから線分への最近接点)

衝突法線（球を押す方向）：(C-P)/|C-P|

衝突点１（球）：C-r1*衝突法線

衝突点２（カプセル）：P+r2*衝突法線

貫通深度：|C-P|-(r1+r2)

カプセルとカプセルの判定では、２つの線分の最近接距離を求め、同様に２つの半径の合計と比較する。そして、半径の合計よりも近接している場合は交差している。反発方向は、線分上の最近接点を結んだ方向となる。

|P1-P2| < r1+r2のとき、２つのカプセルは衝突している。P1P2は衝突の方向を表す。(P1,P2は２つの線分の最近接点)

衝突法線（カプセル１を押す方向）：(P1-P2)/|P1-P2|

衝突点１（カプセル１）：P1-r1*衝突法線

衝突点２（カプセル２）：P2+r2*衝突法線

貫通深度：|P1-P2|-(r1+r2)

いずれも必要となる幾何学計算は基本的な、点と点、点と線分、線分と線分の判定アルゴリズム（距離と最近接点の取得）のみで済む。次のフレームで交差を解消したい場合は、貫通深度分、それぞれの形状を衝突法線に沿って、お互い逆方向に動かせばよい。(２つの形状が交差しているとき、貫通深度は負の値になることに注意)

また、衝突が検出されなかった場合でも、衝突点をお互いの形状の最近接点として取得できる。貫通深度は正の値となり、２つの形状の最近接距離として扱える。

ゲーム登場するキャラクター等、その形状が球とカプセルのみで済む場合は、比較的シンプル且つ高速な判定アルゴリズムのみで事足りることがわかる。このようなアルゴリズムは演算コストが低く、導入しやすい。複雑な形状を採用する前に、簡単な形状の組み合わせのみで賄えるかどうかを検討することには充分意味がある。例えば複雑な形状にしても、球とカプセルの組み合わせだけで、近似的に表現することもできなくはない。

分離平面を利用する方法

一方、ボックスや円柱等の形状は、球やカプセルで用いたような点や線などの基本的な判定アルゴリズムの組み合わせだけでは対処できない。このようなケースでは分離平面の考え方を利用するのがよい。

分離平面を利用する有名なアルゴリズムとしてボックス形状同士の衝突検出アルゴリズムがある。ボックスはローカル座標系の各XYZ軸に辺や面の向きが沿っているため、効率よく判定を進めることができる。しかし、実際には、分離平面の考え方はボックスだけに限定されるものではなく、より複雑な他の凸形状にも広げることができる。（球とカプセルにも適用可）

分離平面による凸形状同士の衝突を検出する一般的な手法として、分離軸判定法(SAT:Separating Axis Theorem Method)と、ミンコフスキー差(Minkowski Difference)を利用する方法が考案されている。分離軸判定法は、直観的にわかりやすく、比較的ストレートに実装できるのが利点である。一方、ミンコフスキー差は、考え方そのものはシンプルで、分離軸法よりも汎用的に使える一方、技巧的なアルゴリズムの実装が要求される。ミンコフスキー差を利用する衝突検出法として、GJK+EPA、MPRといったアルゴリズムが考案されている。 

これらの手法では、形状を、ある軸上へ投影することによって間接的にアクセスする。また、基本的に凸形状のみを処理の対象としており、衝突点を一点だけ検出することができる。

＊幾何学的な計算の詳細については以下の書籍を参考

ゲームプログラミングのためのリアルタイム衝突判定 | Christer Ericson, 達也, 中村 |本 | 通販 | Amazon

https://realtimecollisiondetection.net/

ゲームの衝突検出の基本

衝突検出とは何か？

衝突検出は主に、ゲーム内のキャラクターやオブジェクト、地形等が互いに当たっているかどうかを判定するために使われる。具体的な例としてあげられるのは、戦闘機の撃った弾やキャラクターのパンチが敵に当たったか？球がプレイヤーのラケットやバットに当たったか？もしくはそれらが、環境内の壁や地面に当たったか？など。そして、衝突検出の結果は物理エンジンやゲームのロジック計算部に渡され、衝突の勢いと関連する物理属性をもとに、反発力を計算し、次のフレームにおける各物体の位置が決定される。

リアルタイムゲームでは、大抵ゲーム内の世界も現実世界と同様に、過去から未来へと時間を進めていく

それ以外にも、キャラクターの進行方向の障害物の有無を確認し、移動経路を決めるとか、敵視野内にプレイヤーがいるかどうかを判定して、AIの判断材料にするなど、アクション性のあるゲームであれば、様々な場面で活用される。古典的なコンピュータゲームから、最新のゲームに至るまで、程度の差はあれ、ゲームの体裁を整えるために、何かしら衝突を検出する機能を実装しているはずである。このように、衝突検出はゲーム内の様々なシステムにコンピュータ内に構築された仮想世界の”形”に関連する情報を伝える、という役割を担っている。

コンピュータが扱う”モノの形”

では、いったいどうやってコンピュータに物体間の衝突を検出させるのか？まず、コンピュータが扱えるのは、いわゆるプリミティブと呼ばれる幾何学形状だけである。こういった形状はパラメトリックに表現でき、判定対象となる形状の特徴をうまく利用することで、交差する点を計算することができる。そして、衝突検出は与えられたプリミティブの組み合わせに合致する関数を選び出し、交差を検出する。例えば、球は中心位置と半径で表すことができ、球と球の交差は、２つの球の中心位置の距離と半径の和から計算することができる。

|C1-C2| < r1+r2のとき、２つの球は衝突している。

プリミティブの例：球、ボックス、カプセル、三角形、凸包(Convex hull)など

struct Sphere
{
    float radius;
};

struct Box
{
    Vector3 extent;
};

struct Capsule
{
    float radius, halfLength;
};

結局のところ、ゲーム内に登場する一見複雑に見えるキャラクターも、コンピュータの解釈する世界では、このようなプリミティブ形状の組み合わせでしかない。最終的に画面にレンダリングされる絵と比べ、かなり簡素な感じに見えるだろう。

交差検出関数の例：球とボックス、カプセルと円柱、ボックスとボックスなど 

プリミティブ形状の組み合わせごとに必要となるアルゴリズムは違うため、このような判定関数はすべての組み合わせに対して個々に用意しなければならない。もし、ゲームに登場する物体がすべてボックスと球体だけで構成されているとすると、必要な衝突検出の組み合わせは、ボックスと球、ボックスとボックス、球と球の3通りだけとなる。

また、3Dゲームであれば、位置は要素数３のベクトル、姿勢は３ｘ３マトリクスかクォータニオンで表現される。もしくは位置と姿勢を１つの４ｘ４マトリクスとして表すこともできる。いずれにしても、衝突検出関数に必要なのは、２つのプリミティブを表現するためのパラメータと、その位置と姿勢である。

struct Vector3
{
    float x,y,z;
};

struct Quaternion
{
    float x,y,z,w;
};

struct Matrix3
{
    float elem[9];
};

ゲームに必要な情報

通常、ゲームでは２つの物体の衝突する点だけが得られたところで、衝突検出の情報としては不十分である。知りたいことは、どこで衝突しているのか、だけではない。どの方向に、どのくらい引き離せばその衝突を解消できるのか、という情報がなければ、後のゲーム的な表現には繋がっていかない。プレイヤーキャラクターの放ったパンチが敵に当たったとき、敵を当たった位置からパンチの逆方向に動かさなければ、当たった感が得られない。車がガードレールにぶつかった際も、衝突と逆方向に車を動かさなければ、車はそのままガードレールを突き破ってしまう。つまり交差検出関数は、衝突した座標以外に、交差の深さ（貫通深度）、そして衝突の解消する方向（衝突法線）を情報として返す必要がある。

P1が球C1の衝突点、ベクトルの方向は衝突法線、大きさが貫通深度を表す。

衝突法線方向に貫通深度の大きさだけ球C1を動かすと貫通が解消される。

衝突検出関数の最終形

まとめると、２つのプリミティブ形状の衝突を検出する最終的な関数は以下のような形式になる。このような関数は、ゲームエンジンや衝突検出システム全体からすると最下層にあって、衝突検出プロセスの最後に呼ばれる。

入力：２つのプリミティブ情報、それぞれの位置と姿勢

出力：衝突点、衝突法線、貫通深度