3D衝突編
その16 直線と移動する球の衝突場所と時刻を得る
固定した直線に球が近づいてきて衝突する。両者が衝突しているか否かを判定するのは距離を測れば良いだけなのでとても簡単です。ここではもう1歩先へ進み、衝突判定、衝突場所そして衝突時刻を一度に算出する式を導いてみましょう。式がどどっと出てきますが、丁寧に見ていけば大丈夫です。
① まずは直線と固定点で小手調べ
いきなり本題は大変なので、まずは時を止めて、固定した点と固定した直線の関係について考えてみる事にしましょう。最終目的は「固定点から直線上の点に向かう垂線のベクトルを求める事」です。このベクトルをNとしておきましょう。Nさえ求まれば、後はNの長さを求めて距離を測ることができます。
点をSとします。この点は後で球の中心にもなります。ちなみに、太文字はすべてベクトルとします。要はS = OS = (Sx-0,Sy-0,Sz-0)=(Sx,Sy,Sz)という事です（位置ベクトルというやつですね）。直線は方向ベクトルと直線上の一点で表現できます。直線の方向ベクトルをV（標準化して下さい）、線上の一点をQとしておきます。点Sが直線に含まれていなければ、点Sからは必ず1本の垂線が引けます。これは簡単にイメージできると思います。その垂線の足の座標をHとしておきましょう。以上を図示するとこうなります：
点Hは直線上にあります。これを表すために、uという数値（スカラー）を用いる事にしましょう。uと直線の方向である標準化ベクトルVを使うと、Hは次のように表せます：
点Qから方向Vにu倍進むとHにたどり着く、そんなイメージです。uを定めれば、もちろんHが決まります。
今点Hは垂線の足としましたので、ベクトルNとVは垂直です。垂直という事は、その内積は0になります。すなわち、
です。この内積の式をどどっと展開します：
内積は結合法則、分配法則、交換法則が成り立ちます。「なんだっけ？」という方は以下をどうぞ：
結合法則： u * Dot( a ,b ) = Dot( u * a , b )
分配法則： Dot( a, b + c ) = Dot( a, b ) + Dot( a, c )
交換法則： Dot( a, b ) = Dot( b, a )
高校の時にやった記憶がある人はラッキーです。上の展開はこれを利用しています。Dot(V,V)=1に注意すると、最終的にはかなり簡単な式になりました。
今私たちがやりたいのはベクトルNを求める事で、それにはuが分れば良いのでした。上の式からuは、
と既存の値だけから求められます。ここから、最終的なベクトルNは、
と算出されます。ちなみに、R=Q-Sです。
さて、ここまで来ると話はだいぶ見えて来るはずです。Sを球の中心とすると、そこから直線に下ろした垂線のベクトルNの長さが直線までの距離になります。長さが半径rよりも長いか短いかで、衝突がわかるわけです。ここに「球が動く」という事象を追加する（時間を追加する）と、位置と時刻の話が出てきます。
② 動く球と直線の衝突位置と時刻
動く球に突入です。まず、球の中心点Sが等速直線運動をすると仮定します。その動き始めを点S(t=0)、動き終わりを点S(t=1)とします。tは時刻を表す数値（スカラー）です。球はt=0からt=1にかけてまっすぐ進みます。その進む方向をE=S(1)-S(0)としておきましょう。
Eを用いると、ある時刻tでの球の位置は、
と表せます。t=0の時は点S(0)に、t=1の時は点S(1)にあるのが分ると思います。
先程、一点Sから直線に下ろした垂線の交点Hを H = Q + u*Vと表し、そのuが①の最後の方に示した簡単な内積で計算できる事を示しました。この一点SをそっくりS(t)に置き換えると、ベクトルNを求める式は次のように表されます：
tの関数になるわけです。
上の式を、ここであえて展開してみます。
途中はあまり気にしなくて結構です。大切なのは一番下とその上です。一番下のA,Cはその上の中括弧をまとめたものです。中括弧の中はすべて既存の情報から求められるベクトルです。この式は「動く点から直線に下ろす垂線のベクトルNは線形に変化する！！」という大変興味深い性質を物語ってくれています。
さて、垂線ベクトルNの長さ（のべき乗）は、：
と求まります。ここで球の半径rを持ち出します。上の式から出るのはある時刻tでの球の中心から直線までの距離のべき乗です。よって、上の式の両辺をr^2でマイナスすると、「球の表面から直線までの最短距離」に変わります：
もう記号が無くなってきました(^-^;。この式が0になるtがあるとすると、それはその時刻で球の表面と直線が接触する事を意味します。どのtの範囲でも0以上にしかならないのであれば、球と直線はそもそも接触しない事を意味します。つまり「tの解があれば接触、なければ非接触」と判定できるわけです。
上の式を0として解の公式を利用すると、tの解はこうなります：
ルートの中がマイナスならば解が無いので接触しない、0ならば接触の瞬間がある、そしてプラスならば接触してめり込んで抜け出る（2回接する）という状態である事がわかります。tがわかれば球の位置が定まるわけで、ここに「衝突位置と時刻」の両方がめでたく算出できてしまいました！
αが0になるのは、球が止まっている時です（E=(0,0,0))。この時は時刻も衝突場所も特定できませんのでご注意下さい。
③ 球と直線の衝突判定関数
最後はいつものように上の理屈を組み込んだ関数の公開です。以下のプログラムはコピペして直ぐに使えます：
球と直線の衝突判定関数（CalcSphereLineCollision関数） #pragma comment( lib, "d3dx9.lib" )
#include <math.h>
#include <d3dx9.h>
#define IKD_EPSIRON 0.00001f // 誤差
///////////////////////////////////////////////////
// 球と直線の衝突判定・時刻・位置算出関数
// r : 球の半径
// pPre_pos : 球の前の位置
// pPos : 球の次の到達位置
// pLinePoint : 直線上の一点
// pLineDirect : 直線の方向ベクトル
// pOut_t : 衝突時間を格納するFLOAT型へのポインタ
// pOut_colli : パーティクルの衝突位置を格納するD3DXVECTOR型へのポインタ
// 戻り値 : 衝突(true), 非衝突(false)
bool CalcSphereLineCollision(
float r,
D3DXVECTOR3* pPre_pos,
D3DXVECTOR3* pPos,
D3DXVECTOR3* pLinePoint,
D3DXVECTOR3* pLineDirect,
float *pOut_t,
D3DXVECTOR3* pOut_colli
)
{
D3DXVECTOR3 E = *pPos - *pPre_pos;
D3DXVECTOR3 V;
D3DXVec3Normalize( &V, pLineDirect );
D3DXVECTOR3 R = *pLinePoint - *pPre_pos;
D3DXVECTOR3 A = D3DXVec3Dot( &E, &V ) * V - E;
D3DXVECTOR3 C = R - D3DXVec3Dot( &R, &V ) * V;
float Alpha = D3DXVec3LengthSq( &A );
float Beta = D3DXVec3Dot( &A, &C );
float Omega = D3DXVec3LengthSq( &C ) - r*r;
// 衝突判定
float tmp = Beta * Beta - Alpha * Omega;
// 衝突しないか止まっている場合は不正値を返す
if( fabs( Alpha ) <= IKD_EPSIRON || tmp < 0 ) {
*pOut_t = FLT_MAX;
*pOut_colli = *pPre_pos; // 始めの位置を一応返す
if( Omega < 0.0f ) {
// 既にめり込んでいる場合は衝突を返す
return true;
}
return false;
}
// 衝突時刻を算出
*pOut_t = ( - sqrt( tmp ) - Beta ) / Alpha;
// 衝突時刻が0以上1以下ならば衝突
*pOut_colli = *pPre_pos + *pOut_t * E;
if( *pOut_t >= 0.0f && *pOut_t <= 1.0f )
return true;
// 現在の位置でめり込んでいるかチェック
if( Omega < 0.0f ) {
// 既にめり込んでいる場合は衝突を返す
return true;
}
// 指定の間では衝突しない
return false;
}
双方とも単純な図形ですが、こうして見ると意外と面倒な事がわかりました。必要な方はどうぞお使い下さい。
④ 謝辞
本章の話題を提供して頂いたMONOさんに感謝申し上げます。
