Javaゲーム制作記

物理演算で必要な凸包同士の衝突判定の解説です。

凸包というのは画像のように凹んでいる部分がない多角形です。





凸包の衝突判定は、性質上非凸形状よりも判定が容易です。

凸包の場合、局所的な最接近点は、必ず大域的にも最接近点となりますが、
凸包でない場合、必ずしもそうなるとは限りません。





また、二つの凸包が衝突を起こしていない場合、必ず二凸包を分ける分離軸が存在しますが、
衝突を起こしている場合、分離軸は必ず存在しません。





従って、二つの凸包の衝突の有無を調べるということは、分離軸を探すことになります。

ここで重要なのは、分離軸は必ずどちらかの凸包の一辺に平行であるということです。

つまり二凸包のすべての辺に対し分離軸かどうかのチェックを行えば判定ができます。
分離軸が一つも見つからなかった場合、その凸包は衝突しています。

ある辺が分離軸であるかどうかを調べるには、その辺からなる平面と凸包の衝突判定で可能です。
もし衝突があれば分離していないので分離軸ではないことになります。

(平面と凸包の衝突判定は凸包の各頂点と平面とのめり込み判定となり単純ですので省略します。
この辺はググれば沢山出てきます)





これで衝突自体の判定はできるようになりましたが、
物理演算には詳しい情報(法線ベクトル、めり込み距離、衝突点etc...)が必要です。

長いので続きからです↓

すべての辺に対して分離軸を計算して、それでも分離軸がなかった場合…





その凸包の組は衝突しています。
なので、衝突の詳しい情報を得る作業に入ります。


まず、各凸包に対して一番めり込みが少なかった分離軸候補(以下辺と呼びます)と、
その辺に対して一番めり込んでいた頂点を探します。

この場合は以下の二つです。







さらにこの二つの頂点のめり込み距離を比較し、めり込みが少ないほうの辺を選びます。
距離が微妙ですが今回は青色の頂点という事にします。





そしてその辺の両端の頂点を、衝突候補点として選びます。





そしてその辺の法線ベクトルに対し、
法線ベクトルの向きが一番真逆に近い(内積が -1 に近い)もう片方の凸包の辺を探します。
この場合左下の辺になります。





次にその辺の占めるボロノイ領域(画像で赤く示した部分です)で、





衝突候補点のある辺を切り取ります。

この段階で衝突候補点が完全に無くなってしまう(領域の外)場合があります。
その際は、めり込んでいますが衝突なしという判定をします…





もう完了したも同然です。
各頂点候補点の辺へのめりこみ具合をチェックし、
めり込んでいればその頂点と辺から、衝突点、法線ベクトル、めり込み距離の情報が得られます。
めり込んでいなければその衝突候補点は衝突がなかったということです。



お疲れ様でした。以上で終了です。
頭の中でいろいろな凸包の形状の場合のシミュレーションをしてみると納得がいくと思います。

これらをプログラムに書き起こすのも一苦労ですが…ｗ



P.S.明日からしばらく外出してます。一週間くらいで戻るかと。