シンプルな衝突検出アルゴリズム
前回の記事では、基本的な衝突検出関数の形（入力と出力）について説明した。では、対応するプリミティブ形状の組み合わせ次第では膨大になるであろう、その関数の中身はいったいどう記述すればよいのだろうか？球と球であればシンプルな計算で事足りるが、ボックスやカプセル、もしくは複数の三角形から構成されるような複雑な形状にはどうやって対処すればよいのだろうか？
昔、何も知識がなかったころに、線や面の交差計算だけを組み合わせて、ボックスや三角錐などのシンプルな形状の衝突を検出してみたことがあった。衝突検出の結果を自前の物理演算に投入したところ、それっぽく動作したのだが、ある特定の位置関係になると、どうやっても正しい衝突法線と貫通深度を得ることができず、物体の挙動を安定させることはできなかった。やはり、ちゃんと理論的な裏付けのある手法でないと、安定した挙動を実現させることは難しいということを痛感させられた。
交差座標のみを検出する目的であれば、基礎的な点や線の交差を判定する幾何学的計算を組み合わせれば対処することができる。しかし、リアルタイムゲームというのは、基本的に実時間と同様に未来に向かって進んでいく。ここで衝突検出から知りたい情報は、衝突後、物体をどの方向にどのくらいの距離動かすと交差を解消できるのか、である。これがわからないと、後続のゲーム的表現には繋がらない。つまり交差点≠衝突点であり、線や面の交差判定では正しい結果を得ることができないのは当然だった。
交差点（左）と衝突点（右）の違い
交差点には、交差を解消するための情報はない！
凸形状同士の交差判定手法
凸形状同士の衝突を検出する一般的に使われる手法としては、おおまかに以下のように分けられる。
- 幾何学的な特徴を利用する方法
- 分離平面を利用する方法
幾何学的な特徴を利用する方法は、各形状ごとのユニークな特性を利用して、衝突を検出する。そのため、アルゴリズムは個々の判定ごとに異なる。つまり、判定対象となる組み合わせごとにまったく違う実装となる。その代わり、演算コストは低く抑えることができる。一方の分離平面を利用する方法では、形状毎の違いを最小限にとどめ、全体としては汎用的な仕組みで衝突を検出できる。その分、演算コストは高くなりがちである。
幾何学的な特徴を利用する方法
幾何学的な特徴を利用する方法とは、点と線分や線分間の近接距離計算などの基礎的な幾何学計算を利用して解く方法である。球と球の判定であれば、前の記事に書いたように、お互いの中心点間の距離と半径の合計の差分から、衝突を検出することができる。このとき、反発する方向は２つの中心を結ぶ直線方向に一致する。
|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
