分離軸判定法による衝突検出
分離軸？分離平面？
分離軸という言葉からは、何かを分けるための軸？のような意味合いが感じられるが、分離平面（分離軸＝この平面の法線）のほうが直感的にはイメージしやすい。２つの凸形状が接触していないのであれば、その間に必ず平面を挟み込める。この平面のことを分離平面と呼び、この平面の法線を分離軸と呼ぶ。もし、２つの物体が接近し、ギリギリで接していてお互いに交差していないのであれば、この平面は２つの物体をそれぞれの領域に分けることのできる平面となり、各物体はそれぞれ平面の片側にのみ存在し、平面上の１点で接している。図にしてみると以下のようになる。
どちらも凸形状の場合、平面（線）を２つの物体間に挟み込める
2次元では分離線、3次元では分離平面になる
直感的にも、２つの物体が接していれば、どのような姿勢をとったとしても、この間に平面を挟み込めることがイメージできるのではないだろうか。これが貫通深度０の衝突になる。もし、物体の形状が凸形状でない場合、表面のどこかにへこんでいる箇所があることになり、平面を挟むことができない状態があり得る。つまり、2つの物体がどちらも凸形状でなければ、平面を挟み込むことはできない。
さらに、２つの物体が接近し、交差する場合を考えてみる。先ほどの接している状態から、一方の物体を平面に垂直な方向に動かしてみた状態をイメージしてみる。三角形のほうは、平面を越えて球側に食い込んでいる。この食い込んだ距離分、平面に垂直な方向、かつ球と逆方向に三角形を動かすと、衝突は解消できることがわかる（三角形を食い込ませたのと逆方向に動かしただけだから当たり前ではあるが…）。つまり、平面を越えて食い込んだ距離が貫通の深さになり、平面の向きはお互いを引き離す方向に一致している。そして、平面から元の領域を越えて、お互いに最も食い込んだ部分が、それぞれの衝突点を表している。
実際の衝突検出プロセスはこの平面の法線ベクトル（＝分離軸上）で行われる。分離軸上に２つの物体の形状を下図のように投影すると、形状AはMinA~MaxAに、形状BはMinB~MaxBにプロットされる。それぞれの投影範囲のうち、交差する部分(MinB~MaxA間)が貫通の深さを表している。また、MinBとMaxAがそれぞれ分離軸に沿って最も相手側に食い込んだ点であるため、つまりMinBとMaxAに対応するそれぞれの物体上の点が衝突点を表していることになる。分離軸に沿って、お互い逆向きに貫通距離分動かすと衝突を解消できることから、分離軸は衝突法線に一致する。
実際の判定処理は分離軸(Separating Axis)上で行われる。
要は、分離軸判定法のポイントとは、このような分離軸を2つの凸形状の間に見つけることであり。もし見つけることができれば、あとは2つの物体の分離軸上の投影範囲をチェックし、MinB < MinAであれば、交差していることが判定できる。そして、必要な衝突情報（衝突点、衝突法線、貫通深度）は分離軸から得られた情報をもとに計算することができる。
分離軸の見つけ方
分離軸の理屈自体は、シンプルで直感的でありイメージしやすい。では、実際にはどのように、2つの形状に対して、適切な分離軸を見つけることができるのだろうか？
演算負荷を一切無視できるのであれば、あらゆる方向の軸に対して、２つの凸形状を投影し、その交差範囲が最小となる軸（つまり貫通が最も浅くなる軸）を最適な分離軸として選び出せる。しかし、当然ながら無数に存在する軸をすべてチェックすることは現実的ではない。そこで実際には、あらかじめ想定される分離軸候補を絞り込んでから判定に進むようにする。
例えば、下図のように三角錐と球の判定であれば、想定されるすべての分離平面はあらかじめ列挙できる。これが分離軸のすべての候補となるため、他の方向は判定する必要がない。
この場合、合計3+6+4=13回の判定で、最適な分離軸を選び出せる。
メッシュのようにトライアングルから構成される凸包同士であれば、その形状の持つ幾何学特徴（頂点、辺、面）すべての組み合わせが分離軸の候補になる。つまり、頂点と頂点、頂点と辺、頂点と面、辺と辺、辺と面、面と面である。このうち、重複する同じ方向の組み合わせや、他でカバーできるケースを排除すると、最終的には、頂点と面、辺と辺が残る。最終的には、例えば三角錐同士の判定であれば、各面法線x8、辺と辺の外積ベクトルx36の合計44回で判定すればよい。
なお、ボックスも凸包と同様の組み合わせから判定できるのだが、先にも述べたように、ボックスはローカル座標系の各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; }
衝突点の計算
頂点と頂点の組み合わせで分離軸が決定されたのであれば、２つの形状はその頂点同士が最も相手側に食い込んでいることになり、これをそのまま衝突点として決定できる。それ以外の組み合わせの場合、例えば辺と辺、辺と面であれば、衝突点は計算によって求める必要がある。
衝突点の座標の求め方は、いろいろあると思うが、ここではひとつの方法を紹介する。分離軸判定の結果、衝突点における、衝突法線と貫通深度が取得できている。また、衝突している物体の最も食い込んでいる幾何学特徴の組み合わせもわかっている。そこで、両物体を貫通深度＋α、衝突法線方向にそれぞれ移動させる。これで衝突していない位置関係になり、ここから両特徴間の最近接点を計算する。特徴自体は大抵頂点や辺、面といった基礎的な幾何学形状であるから、その計算はシンプルに実装することができる。あとは、得られた点を、移動した分もとに戻せば、正しい衝突点の座標を求めることができる。
最終的な分離軸判定のプロセス
いままでの説明をもとにすべての処理を統合すると、全体的な分離軸判定の流れは以下のようになる。
- 判定対象となる物体の形状から、分離軸の候補を絞り込む
- 各分離軸候補に対し、それぞれの形状を投影して投影領域をチェック
- もし、投影領域が交差していなければ、即座に処理を終了
- 投影領域が交差しており、かつ交差距離が以前の軸より小さければ、この軸を記録
- 最後まで残ったのが交差距離が最小となる軸であり、これが分離軸
- 交差距離＋α、分離軸に沿って２つの形状を引き離す
- 最近接点を計算し、衝突点を得る
なお、判定プロセスにおいて、形状毎に特化する処理は以下となる。
- 組み合わせ毎の分離軸候補の選定
- 形状の候補軸上への投影
- 最近接点取得
これらの処理ができるとわかれば、その形状には分離軸判定法による衝突検出を適用できる。例えば、球、ボックス、カプセル、円柱、凸包、など。
