ホーム＜ゲームつくろー！＜衝突判定編＜ 移動する２つの球の衝突場所と時刻を得る

3D衝突編
その９　移動する２つの球の衝突場所と時刻を得る



　衝突の基本はパーティクルです。大抵が2つの球で表されるパーティクルの衝突は、移動が離散的であるという点で問題が起こる事があります。現実的には当たっているにもかかわらず、すり抜けてしまうことがあります。これを防ぐには移動前と移動後の位置を記録しておいて「球体スウィープ」として当たり判定を計算する必要が出てきます。

　この章では、そんな2つの移動する球がどこで当たるのか、そしていつ当たるのかを算出できる関数を作ってしまいます。これがあれば、もう球の衝突は怖いもの無しなんです！



① 球体スウィープボリューム

　まん丸の球を移動させることで出来る薬のカプセルのような境界ボリュームの事を「球体スウィープボリューム（sphere-swept volume:SSV）」と言います。今回考えるパーティクルのような球がある点から別の点まで直線的に移動すると、球体スウィープボリュームができあがります。球体スウィープボリュームの交差は、実はそれほど難しくありません。しかし、その応用範囲はかなりに広いため、非常に有用なんです。



② パーティクルの位置を時間で表現する

　今回は、2つのパーティクルがいつどこで衝突するかを得るのが目的です。そのために、次のような状況を想定します。2つのパーティクルはA、Bとしましょう。その半径はrA、rBとします。また、移動前のパーティクル位置をA(t=0)、移動後をA(t=1)などと表わすとします。

　球体スウィープが接しているかそうでないか？その判断はずばり上の緑色のベクトルの長さが2つのパーティクルの半径の合計よりも長いが短いかで決まります。緑色のベクトルは、パーティクルAとBを連続的に線分で結んだものです。上の図の場合、あるところまではベクトルが短くなり、また広がっている様子が分かると思います。この緑色のベクトルは時間tと共に変化します。ですから、それをうまく記述できれば、長さも時間の関数として求められることになります。この章の中心はその関数の導出です。ちょっと面倒な点もありますが、詳しくじっくり見ていきましょう。


　まず、ある時刻tにおける緑色のベクトルを、

と表わすことにします。XYZの各成分は、AからBへのベクトルであるため、

となります。ここまでは何も難しいことは無いですね。それぞれの座標がtの関数になっているのが独特です。A(t)及びB(t)は、直線的に移動すると考えていますので、次のように表わすことができます。

tが増えるほど前の位置から次の位置へ移動しているのがわかると思います。

　ベクトルc(t)の長さは、各座標値を2乗して足し、そのルートを取れば算出されます。ただ、ルートはちょっと面倒なのでここでは長さの2乗を得ると考えましょう。それは、こんな式になります。

　さて、この式に上に挙げた幾つかの式を代入して、丁寧に丁寧に展開していきます。どばっと出ますが気にしないで下さいね。

　途中経過は良いとして、最後をご覧下さい。ベクトルc(t)の長さは最終的には時間の2次関数となることがわかります。これがポイントなんです！P、Q、Rはそれぞれ、

です。見てお分かりのように、どこにもtは入っていませんので、これらは完全に「定数」です。

　この長さを算出する2次式が決まってしまえば、後は簡単です。



③ パーティクルの衝突とその時刻・位置の算出

　パーティクルが衝突するというのは、両者の距離が半径の合計と一緒になったことと同じ意味です。今、時刻tに対して両者の距離を算出する2次式を求めました。そこで、次のように方程式を書いてみます。

左辺に両パーティクルの半径の合計を2乗した値、右辺に時刻tでの両者の距離を算出する式を置きます。下段は、それをまとめたものです。上段の式が成り立つ時刻tが、パーティクルが衝突した時刻と言えますね。このtを解くには、高校の教科書に出てくる「解の公式」をそのまま利用できます。すなわち、

となるわけです。

　さて、上式はルートの中の状態によって3通りに分類できます。ルートの中がマイナスになる場合、実数解を持ちません。これは「衝突しない」事を表わします。ルートの中がちょうど0になる場合、これはt=-Q/Pという時刻に両者が接することを表わします。そしてルートの中がプラスになる時、tは2つの解を持ちます。接する点が2箇所あるわけです。これは両者が接して、めり込んで、抜けるという状態がある事を表わします。まとめると以下のようになります。

　P、Q、Rの値を求めておけば、上の式を用いてたちどころに交差判定を行うことが出来るのです。これは、非常にお手軽です。もちろん、tも求められますので、前の位置から衝突までにかかる時間がとても簡単にわかるわけです。

　③で衝突までの時刻がわかれば、②の最初の方で示しました以下の式、

から、衝突の位置もたちどころに分かってしまいます。一つ注意することですが、もしtが0以下及び1以上であれば、それは今回の移動範囲内では衝突しないことを表わします。



④ 決定版！2つのパーティクルの衝突位置算出関数

　②と③で式を展開してきました。これを踏まえて衝突判定・位置・時間を一度に算出して提供してくれるマルチな関数を作ってしまいます。そこで、②の最後に置き換えたP、Q、Rをもう一度見てみます。

C(0)及びC(1)というのはそれぞれベクトルです。Pを見るとベクトルの各成分を引き算していますね。これはベクトルの引き算をしていることにほかなりません。今、

と置いてしまうと、上のP、Qは次のようになります。

えらいすっきりしました。しかも、意味がとても明白になりました。まずPはベクトルdの各成分を2乗して足し算していますね。これは「ベクトルdの長さのべき乗」です。要は長さを求めれば良いだけです。次にQですが、これはベクトルc(0)の各成分とベクトルdの各成分を掛け合わせて足しています。この形はどこかでみたことがあります。そう「内積」です。実はQは内積なんです！そしてR。これは一目瞭然ですが「ベクトルc(0)の長さのべき乗」です。これを踏まえると、実装は驚くほど簡単になってしまいます。幾つかの判定フラグを追加した実装は以下のようになります（以下の関数はコピペすると完全に使えます！）。

2パーティクル衝突判定・位置・時間算出関数
///////////////////////////////////////////////////
// パーティクル衝突判定・時刻・位置算出関数
//   rA          : パーティクルAの半径
//   rB          : パーティクルBの半径
//   pre_pos_A   : パーティクルAの前の位置
//   pos_A       : パーティクルAの次の到達位置
//   pre_pos_B   : パーティクルBの前位置
//   pos_B       : パーティクルBの次の到達位置
//   pout_t0 : 最初の衝突位置時間を格納するFLOAT型へのポインタ
//   pout_t1 : 2度目の衝突位置時間を格納するFLOAT型へのポインタ
//   pout_colli_A : パーティクルAの衝突位置を格納するD3DXVECTOR型へのポインタ
//   pout_colli_B : パーティクルAの衝突位置を格納するD3DXVECTOR型へのポインタ

bool CalcParticleCollision(
   FLOAT rA, FLOAT rB,
   D3DXVECTOR3 *pPre_pos_A, D3DXVECTOR3 *pPos_A,
   D3DXVECTOR3 *pPre_pos_B, D3DXVECTOR3 *pPos_B,
   FLOAT *pOut_t0,
   FLOAT *pOut_t1,
   D3DXVECTOR3 *pOut_colli_A,
   D3DXVECTOR3 *pOut_colli_B
)
{
   // 前位置及び到達位置におけるパーティクル間のベクトルを算出
   D3DXVECTOR3 C0 = *pPre_pos_B - *pPre_pos_A;
   D3DXVECTOR3 C1 = *pPos_B - *pPos_A;
   D3DXVECTOR3 D = C1 - C0;

   // 衝突判定用の2次関数係数の算出
   FLOAT P = D3DXVec3LengthSq( &D ); if(P==0) return false; // 同じ方向に移動
   FLOAT Q = D3DXVec3Dot( &C0, &D );
   FLOAT R = D3DXVec3LengthSq( &C0 );

   // パーティクル距離
   FLOAT r = rA + rB;

   // 衝突判定式
   FLOAT Judge = Q*Q - P*(R-r*r);
   if( Judge < 0 ){
      // 衝突していない
      return false;
   }

   // 衝突時間の算出
   FLOAT t_plus = (-Q + sqrt(Judge))/P;
   FLOAT t_minus = (-Q - sqrt(Judge))/P;


   // 衝突位置の決定
   *pOut_colli_A = *pPre_pos_A + t_minus * (*pPos_A - *pPre_pos_A);
   *pOut_colli_B = *pPre_pos_B + t_minus * (*pPos_B - *pPre_pos_B);

   // 衝突時間の決定（t_minus側が常に最初の衝突）
   *pOut_t0 = t_minus;
   *pOut_t1 = t_plus;

  // 時間内衝突できるか？
   // t_minusが1より大きいと届かず衝突していない
   // t_plus、t_minusが両方ともマイナスだと反対方向なので衝突しない
   if( (t_minus > 1) || (t_minus < 0 && t_plus < 0) )
      return false;

   return true; // 衝突報告

}


　この関数には10つの引数があります。ちょっと多いのですが必要なのでしかたありません。引数の意味はコメントをご覧下さい。2つのパーティクルが時間内に衝突しない場合、この関数はfalseを返します。衝突する場合はtrueを返します。pOut_t0とpOut_t1には衝突時刻、pOut_colli_AにパーティクルAの衝突位置（中心座標）、pOut_colli_BにパーティクルBの衝突位置が返ります。大きな計算はありませんので比較的高速です。

　この関数があると、パーティクルの衝突位置検出に非常に役立ちます。それ以外にも色々なところで使える関数ですから、どうぞご利用下さい。