静止する２物体間の近接距離検出
ゲーム開発において、物体間の衝突検出以上に重要なのが、物体がどのくらい対象から離れているのかを検出する仕組みであろう。例えば、複数の敵との距離を測定し、最も近くにいる敵に自動的に照準を合わせるとか、ある一定距離以上離れている敵は無視するなど。他にも敵の移動する速度とキャラクター間の最近接距離が把握できれば、未来のどの時点で衝突が発生するかを正確に判定することができ、回避するか防御するかといった、キャラクターが次にとるべき行動を決定する際の判定に使うことができる。
高速に移動するキャラクターや乗り物を地形に沿ってスムーズに移動させたいときにも役立つ。乗り物の進行方向に配置された壁との距離を正確に測定できれば、その距離分は衝突せずに乗り物を移動させることができる。接触地点で進行方向を壁面に沿うように曲げてやり、再度次の接触までの距離を測定する。これを繰り返すことで、壁の凹凸に引っかからないスムーズな移動を実現できる。例えば、乗り物がある一定の速度で移動しているとすると、１フレームで移動できる距離を計算し、総移動距離がこの距離に達するまで、最近接距離を測りながら地形に沿って移動させていく。
このような物体間の距離の測定においては、両物体が静止しているか、一方が動いているか、もしくは両方が同時に動いているかでその検出難易度が変わってくる。つまり利用するアルゴリズムも、状況に応じて変える必要がある。重要なポイントは、いずれの状況においても、２つの形状を結ぶ最短となる距離を検出しなければならないということである。
もっともシンプルな形状間距離検出は静止している２つの球体間の距離を測るものだろう。これは単純に２つの球の中心間の距離を計算し、半径の合計分を引くだけでよい。球とカプセルの組み合わせでは、衝突検出のときに用いた幾何学計算アルゴリズムをそのまま再利用できる。この場合、２つの形状が交差していないとき、同様の計算から貫通深度がプラス（正）の値として得られる。
より複雑な凸包やボックス、円柱などの形状については、分離軸判定法やGJKを利用して形状間の距離を検出できる。どの手法を使うにしても、検出結果として、最近接距離だけでなく近接点と方向（法線ベクトル）を取得することができる。このような情報は、ゲームロジックの様々な判定で活用することができる。
分離軸判定法を利用する最近接距離検出
分離軸判定法は、多少の改良を加えるだけで2物体間の最近接距離を検出することができる。分離軸判定法のプロセスでは、分離軸候補となる軸を列挙し、２つの形状を個々の軸に対して投影し、その領域を記録する。この際、通常の衝突検出では、投影領域の交差しない軸が見つかった時点で、２つの形状が交差しないことが判明するため、早期に処理を終了することができる。しかし、最近接距離を検出するときは、そもそも前提として2つの形状は交差していないため、このような軸があろうがなかろうが、すべての分離軸候補に対して投影判定を行わなければならない。判定するのは下図のMinB～MaxA間の距離であり、これが最小となる軸が分離軸となる。なお、MinB-MaxAが負のとき（軸上でMaxA < MinB）、形状は交差している。
あとの処理は、衝突検出時とほぼ変わらない。分離軸判定からは互いに近接する面や辺といった特徴部を知ることができる。最近接距離は分離軸上に投影したMinB～MaxA間の距離に一致する。座標と法線が必要であれば、得られた特徴部間の最近接点を計算すればよい。
GJKを利用する最近接距離検出
衝突検出にGJKを使う際は、補助アルゴリズムEPAと組み合わせる必要があった。しかし、GJKは本来、最近接距離を検出するアルゴリズムである。最近接距離を測定する際は、EPAを必要としない。
以前の記事に書いたように、衝突検出におけるGJKではシンプレックスが完成した時点で、原点がシンプレックスに含まれるかどうかを判定し、含まれていればEPAに移行して衝突点を検出、含まれていなければ衝突はないものとして、処理は終了となった。最近接距離を検出する際は、原点がシンプレックスに含まれる場合は、２つの形状が交差しているため早期終了し、そうでなければ処理をそのまま続行する。シンプレックスがミンコフスキー差の表面に到達するまで、シンプレックス更新プロセスを繰り返す。
- ミンコフスキー差内の適当な点から原点への方向で、もっとも遠い点P1を取得
- P1から原点に向かう方向で、もっとも遠い点P2を取得
- 線分P1P2上の原点からの最近接点を計算し、そこから原点に向かう方向で、最も遠い点P3を取得
- シンプレックス（三角形）P1P2P3が表面に到達したので、GJKはここでストップ。
もし上記プロセス４の時点でシンプレックスが表面に到達しない場合、原点から最も遠い点を除いて、再度処理を３から繰り返す。最終的に、原点からシンプレックスまでの最近接距離が、２つの形状間の最近接距離を表す。
まとめ
衝突検出アルゴリズムの実装さえできていれば、最近接距離を検出できるようにすることはさほど難しくない。最近接距離が検出できるようになると、ゲーム内の様々な判定に活用できるようになるため、実用上の価値は高い。分離軸判定は実装しやすいが、分離軸の候補すべてに対しての処理が必要なため、パフォーマンス的には無駄が多い。特にポリゴンモデルのような、曲面部のない多面体形状では、GJKは非常に少ない判定回数で適切な解に収束する。今回はまずは静的な物体のみを対象とした。いずれ動的な物体の判定についても扱ってみたいと思う。
