ホーム＜ゲームつくろー！＜衝突判定編＜ OBBとOBBの衝突
3D衝突編
その13 OBBとOBBの衝突
衝突の本丸の1つ「OBBとOBB」の衝突です。大きさの違うお互いに3次元的に回転した直方体が衝突しているかどうかを調べるというのはやはり簡単ではありませんが、これができると多種多様な方面で役に立ちます。OBB同士の衝突として主流なのは「分離軸判定」と呼ばれる方法でして、ここでもそれについて見ていきます。ちょっと深呼吸してご覧下さい(^-^;
① 「分離軸」判定とは？
OBBの衝突には「分離軸」という物が登場します。これがいったい何なのか？まずは下の図をご覧下さい。
上のOBBは明らかに衝突していません。この時、両方のOBBを分ける直線が「絶対に」存在します。この直線は、ちょっと小難しい言葉で言うと分離超平面（Separating hyperplane）と呼ばれています。直線なのに平面というのは違和感があるかもしれませんが、これは「ある次元に対して1つ次元の少ない図形」の総称です。直線を分けるのは点、平面を分けるのは下図のように直線、空間を分けるのは平面です。いずれも分離する図形は1つ次元が少ないですよね（ですから、4次元を分けるのは立体なんです。イメージできないけど存在するので「超」なんです(^-^;）。ちなみに、これは分離軸ではありません。
もし両方のOBBが接触（進入）していたら、それを分ける直線はどう考えてもありません。このことから、平面であれ立体であれ、2つのOBBが衝突しているか否かを見つけるには、分離超平面を見つければ良い事がわかります。
しかしながら、例えば3次元のOBBを分離する平面を探すというのは、想像しただけでも大変そうです。まともに考えるとうまく行きません。そこで出てくるのが「分離軸」です。上の図の直線に対して垂直な直線を描き、「両方のOBBを垂直線上に投影」してみます。
上の図の緑色の直線が「分離軸」と呼ばれるものです。こうすると、平面のOBBが直線上の線として捉える事ができるようになります。しかも、分離軸に投影された2つの線分はやっぱり離れています。つまり、分離軸の投影直線の状態を見てもOBBが離れているか否かを判定できる事になります。
「分離軸と超平面と何が違うの？」と思われるかもしれません。分離軸の良い点は、次元の高いOBBでも「直線」として衝突の判定を行えるところにあります。3次元のOBBを分離軸に投影する事も出来ます。それが上の図のような状態ならば、3次元のOBBは離れている事になります。小さな次元の図形で判定できるというのは、それだけ楽で高速なんです。
② OBBの分離軸の探し方
衝突判定に便利な分離軸には探し方があります。
まず平面（直線で構成される図形）で考えて見ます。2つの平面が「触れる」というのは、上図のAとBの関係のように辺同士が交差する事に他なりません。ここで、辺Aに垂直な分離軸を設けると、辺A上にある全部の点を分離軸上の1点に凝縮できてしまいます。辺Bの投影線分の中にその凝縮点が含まれていれば、それは「平面が衝突している」可能性を示唆します。「可能性」というのは、次のような状態があるためです：
同様に辺Aに垂直な交差軸に投影すると、凝縮点は含まれますが辺は交差していません。つまり、1つの辺に垂直な分離軸だけを調べるだけでは不十分なんです。そこで、上の図の辺Bの分離軸も見てみましょう。
辺B側の分離軸だと、2辺が離れていることがはっきりします。このことから平面が確かに交差していない事を調べるには、各辺それぞれについての分離軸に平面を投影し、分離を確かめる必要がある事が分かります。
さて、OBBの場合は、その図形の性質からちょっとした節約ができます。平面のOBBは長方形ですから2辺は常に並行です。ということは、並行辺に垂直な分離軸が共通することになります。よって、判定回数を単純に半分に減らす事ができるんです。具体的には下図のように、2つの平面OBBだと調査する分離軸は4つとなります。
･･･まぁ、いっぺんに表すと、どうしてもこうなりますね(^-^;。でもOBBの方向軸に垂直な4分離軸だけで衝突判定が行えるというのは良くわかると思います。
③ OBBの投影線分と中心間の距離の比較が鍵
分離軸に投影した線分が離れている事を確認すれば良い事はわかりましたが、肝心の投影線分の長さはどうやって計算するのでしょうか？実はOBBの場合、比較的簡単にその距離を計算する事が出来ます。まずは下の図をご覧下さい。
OBBは通常「各軸の方向ベクトル」を持っています。上の図で言うとe1及びe2がそれに当たります。分離軸をLとしますと、実は投影した長さの「半分（rA）」は、各軸の方向ベクトルと分離軸との内積の絶対値を足したものになります。「なんでよ！」っと思う方は、上の図をじ～っとご覧下さい。なんとなくそんな感じがするのが分かるのではないでしょうか？もしちゃんとした証明が欲しいというかたはご一報下さい(^-^;。
上の式を用いますと、無条件に投影線分の距離が計算できます。では、2つのOBBの投影線分が重なっているかどうかを判定するにはどうしたらよいのか？引き続き下の図をご覧下さい。
Aの投影線分の長さをrAとします。これは先ほどの式で一発算出ですね。一方Bの投影線分の長さは、上の場合ですとeb2の大きさと等しくなります。これは、eb1に垂直な分離軸を考えているためです。この時、「両図形の中心点間の距離よりも半投影線分長さのの合計が小さければ、両者は分離している」と見ることができます。これは、OBBの中心点が常に投影線分の中点に来るためです。上の例を元にプログラムを仮組みするとこんな感じになるでしょうか。
OBB obbA; // OBB A （すでに回転などをしているとします）
OBB obbB; // OBB B (こちらも)
// OBBの方向ベクトルeb2を分離軸と設定（すでに標準化されているとします）
D3DXVECTOR3 L = ObbB.GetDirect(1);
// OBB Aの軸を取得（軸の長さに定数倍します）
D3DXVECTOR3 ea1 = ObbA.GetDirect(0) * ObbA.GetLen(0);
D3DXVECTOR3 ea2 = ObbA.GetDirect(1) * ObbA.GetLen(1);
// rAおよびrBを算出
FLOAT ra = fabs(D3DXVec3Dot(&L, &ea1)) + fabs(D3DXVec3Dot( &L, &ea2 ));
FLOAT rb = ObbB.GetLen(0); // これはeb2です
// 中心点間の距離を算出
FLOAT Interval = fabs(D3DXVec3Dot( &(obbA.GetPos()-ObbB.GetPos()), &L));
// 衝突判定
if( Interval < ra + rb )
return true; // 衝突
return fasle; // 衝突していない
後は、分離軸を変えて、これとほぼ同様の計算を分離軸の数だけ繰り返すだけです。平面のOBBの場合、分離軸は4つとなります。以下にそれをまとめた表を作りましたのでご参照下さい。
分離軸 rA rB L A.e1 A.e1 |Dot(B.e1,A.e1)|+|Dot(Be2,Ae1)| |Dot(A.Pos-BPos,A.e1)| A.e2 A.e2 |Dot(B.e1,A.e2)|+|Dot(Be2,Ae2)| |Dot(A.Pos-BPos,A.e2)| B.e1 |Dot(A.e1,B.e1)|+|Dot(Ae2,Be1)| B.e1 |Dot(A.Pos-BPos,B.e1)| B.e2 |Dot(A.e1,B.e2)|+|Dot(Ae2,Be2)| B.e2 |Dot(A.Pos-BPos,B.e2)|
分離軸ベクトル（標準化）は赤色で示しました。このように表にまとめるのは、実装漏れを防ぐためにも大切ですね。
④ 直方体OBBの衝突
さて、いよいよ本丸中の本丸、3次元空間でのOBB同士の衝突です。基本的には先ほどまで説明してきた平面OBBの衝突の拡張となりますし、計算方法もほぼ一緒です。ただ、分離軸がどばっと増えます。
平面の分離軸を決める時には「衝突対象」として辺と辺を考え、最終的にはOBBの方向ベクトルで良いことがわかりました。立体のOBBでもそれは同様です。立体のOBBの方向ベクトルは「3つ」あります。これが図形2つ分なので分離軸は全部で6つ…というわけでは無いようなんです。
「ゲームプログラミングのためのリアルタイム衝突判定（Christer Ericson著、中村達也 訳）」によりますと、3次元のOBBの場合、上の6つの他に「双方の方向ベクトルに垂直な分離軸」というのを定める必要があります。これは双方のOBBが持つ方向ベクトルの「外積」から得る事ができます。一方が3つでそれに対して3つの方向ベクトルが対応するのでこの外積による分離軸は3×3＝9本あることになります。つまり、立体のOBB同士の衝突は3+3+9=15本の分離軸の検査をします。この時の検査順番ですが、最初に各OBBの方向ベクトルを分離軸にします。これだけで90%以上は分離判定ができるのだそうです。残りの10％くらいを外積分離軸に頼ります。
この辺、言い回しがやけに他人行儀なのは、OBB同士に関して外積分離軸が必要になる局面がどうにも想像できないからなんです。3DソフトでOBBを作って色々配置してみるんですが、方向ベクトルを分離軸とすれば分離できてしまいそうな感じがしてなりません。OBB同士というのは特別なんじゃないのかと思ってしまうんですが、世の中がそう言っていますので、ここでは15の分離軸判定を要するという事で通します（もし外積軸でないと判定できないOBBの位置関係をご存知の方がいらっしゃいましたら、是非とも教えてください）。
(2008. 6. 27 追記)
↑とお尋ねした所、中川様より回答を頂きました。OBBが辺同士ひねった関係で近づくと方向ベクトルの分離軸では判定できなくなります。実際に3Dソフトで描画してみた下の図をご覧下さい：
これらの図はどちらかのOBBの面を正面に見るようにカメラのアングルを工夫したものです。左上の図をごらん頂くとわかるように、この2つのOBBは衝突していません。にもかかわらず、緑色の6本の分離軸に対してすべての判定が「衝突」を示しています。このような条件の時に残り9本の分離軸判定が必要になります。なるほどです。
⑤ 3次元のOBB衝突表
軸さえ決まれば、判定の方法は平面の時と変わりません。投影線分の長さの求め方も、各方向ベクトルと分離軸との内積の絶対値の和です。15本の分離軸それぞれについて、OBB Aの投影線分の長さ（rA）、OBB Bの投影線分の長さ（rB）、中心点の長さLを一覧表に示します。外積分離軸はA.e2×B.e1=C21のように略記します。
例えば分離軸C11についてですが、しっかり書くとこうなります。
分離軸 rA rB L C11 |Dot(A.e1,C11)|+|Dot(Ae2,C11)|+|Dot(Ae3,C11)| |Dot(B.e1,C11)|+|Dot(Be2,C11)|+|Dot(Be3,C11)| |Dot(A.Pos-BPos,C11)|
rAもrBも各方向ベクトルと分離軸の内積を足し算ています。ただ、よ～く考えると、分離軸C11はA.e1にもB.e1にも垂直です。垂直同士の内積は0になりますから、上の表は少し簡単になります。
分離軸 rA rB L C11 |Dot(Ae2,C11)|+|Dot(Ae3,C11)| |Dot(Be2,C11)|+|Dot(Be3,C11)| |Dot(A.Pos-BPos,C11)|
これでまともにやるよりも少し計算量を節約する事が出来ます。もちろん、他の分離軸についても同様の節約が可能です。規則性で見るなら、C23であればA.e2とB.e3の内積が無くなる、という感じで数字を照らし合わせれば間違いません。また、中心点間の長さを計算する時に「A.Pos-BPos」というのが全ての行に出現しますので、予め計算しておくべきです（Intervalとしておきます）。それらをどばっとまとめたのが以下の表です。
分離軸 rA rB L A.e1 A.e1 |Dot(B.e1,A.e1)|+|Dot(Be2,Ae1)|+|Dot(Be3,Ae1)| |Dot(Interval,A.e1)| A.e2 A.e2 |Dot(B.e1,A.e2)|+|Dot(Be2,Ae2)|+|Dot(Be3,Ae2)| |Dot(Interval,A.e2)| A.e3 A.e3 |Dot(B.e1,A.e3)|+|Dot(Be2,Ae3)|+|Dot(Be3,Ae3)| |Dot(Interval,A.e3)| B.e1 |Dot(A.e1,B.e1)|+|Dot(Ae2,Be1)|+|Dot(Ae3,Be1)| B.e1 |Dot(Interval,B.e1)| B.e2 |Dot(A.e1,B.e2)|+|Dot(Ae2,Be2)|+|Dot(Ae3,Be2)| B.e2 |Dot(Interval,B.e2)| B.e3 |Dot(A.e1,B.e3)|+|Dot(Ae2,Be3)|+|Dot(Ae3,Be3)| B.e3 |Dot(Interval,B.e3)| C11 |Dot(Ae2,C11)|+|Dot(Ae3,C11)| |Dot(Be2,C11)|+|Dot(Be3,C11)| |Dot(Interval,C11)| C12 |Dot(Ae2,C12)|+|Dot(Ae3,C12)| |Dot(B.e1,C12)|+|Dot(Be3,C12)| |Dot(Interval,C12)| C13 |Dot(Ae2,C13)|+|Dot(Ae3,C13)| |Dot(B.e1,C13)|+|Dot(Be2,C13)| |Dot(Interval,C13)| C21 |Dot(A.e1,C21)|+|Dot(Ae3,C21)| |Dot(Be2,C21)|+|Dot(Be3,C21)| |Dot(Interval,C21)| C22 |Dot(A.e1,C22)|+|Dot(Ae3,C22)| |Dot(B.e1,C22)|+|Dot(Be3,C22)| |Dot(Interval,C22)| C23 |Dot(A.e1,C23)|+|Dot(Ae3,C23)| |Dot(B.e1,C23)|+|Dot(Be2,C23)| |Dot(Interval,C23)| C31 |Dot(A.e1,C31)|+|Dot(Ae2,C31)| |Dot(Be2,C31)|+|Dot(Be3,C31)| |Dot(Interval,C31)| C32 |Dot(A.e1,C32)|+|Dot(Ae2,C32)| |Dot(B.e1,C32)|+|Dot(Be3,C32)| |Dot(Interval,C32)| C33 |Dot(A.e1,C33)|+|Dot(Ae2,C33)| |Dot(B.e1,C33)|+|Dot(Be2,C33)| |Dot(Interval,C33)|
これでも大分に節約したほうですが、やっぱり目がくらんでしまいます（笑）。この組み合わせすべての実装が必要になります。しかも同じような組み合わせというのが悲しいほどありませんので、静々とこの通りの計算をプログラミングします。多少のアルゴリズムの最適化は存在しますが、ここでは割愛致します。最適化について詳しくは「ゲームプログラミングのためのリアルタイム衝突判定（Christer Ericson著、中村達也 訳）」をご覧下さい。
⑥ 公開「OBBとOBBの衝突判定プログラム」
以下にOBBとOBBの衝突判定プログラムを全部公開致します。然るべき構造体（OBBクラス）を定義すればコピペですぐに使えますので、そのまま利用されるもよし、ご自分のクラスに照らし合わせて改変するも良し、ご自由にお使い下さい。
OBB同士衝突判定関数 // OBB v.s. OBB
bool ColOBBs( OBB &obb1, OBB &obb2 )
{
// 各方向ベクトルの確保
// （N***:標準化方向ベクトル）
D3DXVECTOR3 NAe1 = obb1.GetDirect(0), Ae1 = NAe1 * obb1.GetLen_W(0);
D3DXVECTOR3 NAe2 = obb1.GetDirect(1), Ae2 = NAe2 * obb1.GetLen_W(1);
D3DXVECTOR3 NAe3 = obb1.GetDirect(2), Ae3 = NAe3 * obb1.GetLen_W(2);
D3DXVECTOR3 NBe1 = obb2.GetDirect(0), Be1 = NBe1 * obb2.GetLen_W(0);
D3DXVECTOR3 NBe2 = obb2.GetDirect(1), Be2 = NBe2 * obb2.GetLen_W(1);
D3DXVECTOR3 NBe3 = obb2.GetDirect(2), Be3 = NBe3 * obb2.GetLen_W(2);
D3DXVECTOR3 Interval = obb1.GetPos_W() - obb2.GetPos_W();
// 分離軸 : Ae1
FLOAT rA = D3DXVec3Length( &Ae1 );
FLOAT rB = LenSegOnSeparateAxis( &NAe1, &Be1, &Be2, &Be3 );
FLOAT L = fabs(D3DXVec3Dot( &Interval, &NAe1 ));
if( L > rA + rB )
return false; // 衝突していない
// 分離軸 : Ae2
rA = D3DXVec3Length( &Ae2 );
rB = LenSegOnSeparateAxis( &NAe2, &Be1, &Be2, &Be3 );
L = fabs(D3DXVec3Dot( &Interval, &NAe2 ));
if( L > rA + rB )
return false;
// 分離軸 : Ae3
rA = D3DXVec3Length( &Ae3 );
rB = LenSegOnSeparateAxis( &NAe3, &Be1, &Be2, &Be3 );
L = fabs(D3DXVec3Dot( &Interval, &NAe3 ));
if( L > rA + rB )
return false;
// 分離軸 : Be1
rA = LenSegOnSeparateAxis( &NBe1, &Ae1, &Ae2, &Ae3 );
rB = D3DXVec3Length( &Be1 );
L = fabs(D3DXVec3Dot( &Interval, &NBe1 ));
if( L > rA + rB )
return false;
// 分離軸 : Be2
rA = LenSegOnSeparateAxis( &NBe2, &Ae1, &Ae2, &Ae3 );
rB = D3DXVec3Length( &Be2 );
L = fabs(D3DXVec3Dot( &Interval, &NBe2 ));
if( L > rA + rB )
return false;
// 分離軸 : Be3
rA = LenSegOnSeparateAxis( &NBe3, &Ae1, &Ae2, &Ae3 );
rB = D3DXVec3Length( &Be3 );
L = fabs(D3DXVec3Dot( &Interval, &NBe3 ));
if( L > rA + rB )
return false;
// 分離軸 : C11
D3DXVECTOR3 Cross;
D3DXVec3Cross( &Cross, &NAe1, &NBe1 );
rA = LenSegOnSeparateAxis( &Cross, &Ae2, &Ae3 );
rB = LenSegOnSeparateAxis( &Cross, &Be2, &Be3 );
L = fabs(D3DXVec3Dot( &Interval, &Cross ));
if( L > rA + rB )
return false;
// 分離軸 : C12
D3DXVec3Cross( &Cross, &NAe1, &NBe2 );
rA = LenSegOnSeparateAxis( &Cross, &Ae2, &Ae3 );
rB = LenSegOnSeparateAxis( &Cross, &Be1, &Be3 );
L = fabs(D3DXVec3Dot( &Interval, &Cross ));
if( L > rA + rB )
return false;
// 分離軸 : C13
D3DXVec3Cross( &Cross, &NAe1, &NBe3 );
rA = LenSegOnSeparateAxis( &Cross, &Ae2, &Ae3 );
rB = LenSegOnSeparateAxis( &Cross, &Be1, &Be2 );
L = fabs(D3DXVec3Dot( &Interval, &Cross ));
if( L > rA + rB )
return false;
// 分離軸 : C21
D3DXVec3Cross( &Cross, &NAe2, &NBe1 );
rA = LenSegOnSeparateAxis( &Cross, &Ae1, &Ae3 );
rB = LenSegOnSeparateAxis( &Cross, &Be2, &Be3 );
L = fabs(D3DXVec3Dot( &Interval, &Cross ));
if( L > rA + rB )
return false;
// 分離軸 : C22
D3DXVec3Cross( &Cross, &NAe2, &NBe2 );
rA = LenSegOnSeparateAxis( &Cross, &Ae1, &Ae3 );
rB = LenSegOnSeparateAxis( &Cross, &Be1, &Be3 );
L = fabs(D3DXVec3Dot( &Interval, &Cross ));
if( L > rA + rB )
return false;
// 分離軸 : C23
D3DXVec3Cross( &Cross, &NAe2, &NBe3 );
rA = LenSegOnSeparateAxis( &Cross, &Ae1, &Ae3 );
rB = LenSegOnSeparateAxis( &Cross, &Be1, &Be2 );
L = fabs(D3DXVec3Dot( &Interval, &Cross ));
if( L > rA + rB )
return false;
// 分離軸 : C31
D3DXVec3Cross( &Cross, &NAe3, &NBe1 );
rA = LenSegOnSeparateAxis( &Cross, &Ae1, &Ae2 );
rB = LenSegOnSeparateAxis( &Cross, &Be2, &Be3 );
L = fabs(D3DXVec3Dot( &Interval, &Cross ));
if( L > rA + rB )
return false;
// 分離軸 : C32
D3DXVec3Cross( &Cross, &NAe3, &NBe2 );
rA = LenSegOnSeparateAxis( &Cross, &Ae1, &Ae2 );
rB = LenSegOnSeparateAxis( &Cross, &Be1, &Be3 );
L = fabs(D3DXVec3Dot( &Interval, &Cross ));
if( L > rA + rB )
return false;
// 分離軸 : C33
D3DXVec3Cross( &Cross, &NAe3, &NBe3 );
rA = LenSegOnSeparateAxis( &Cross, &Ae1, &Ae2 );
rB = LenSegOnSeparateAxis( &Cross, &Be1, &Be2 );
L = fabs(D3DXVec3Dot( &Interval, &Cross ));
if( L > rA + rB )
return false;
// 分離平面が存在しないので「衝突している」
return true;
}
// 分離軸に投影された軸成分から投影線分長を算出
FLOAT LenSegOnSeparateAxis( D3DXVECTOR3 *Sep, D3DXVECTOR3 *e1, D3DXVECTOR3 *e2, D3DXVECTOR3 *e3 = 0 )
{
// 3つの内積の絶対値の和で投影線分長を計算
// 分離軸Sepは標準化されていること
FLOAT r1 = fabs(D3DXVec3Dot( Sep, e1 ));
FLOAT r2 = fabs(D3DXVec3Dot( Sep, e2 ));
FLOAT r3 = e3 ? (fabs(D3DXVec3Dot( Sep, e3 ))) : 0;
return r1 + r2 + r3;
}
冗長ですが、先ほどの表に淡々と従っているだけです。用意するOBBクラスには次のようなメソッドを持たせて下さい。
OBBクラス class OBB
{
protected:
D3DXVECTOR3 m_Pos; // 位置
D3DXVECTOR3 m_NormaDirect[3]; // 方向ベクトル
FLOAT m_fLength[3]; // 各軸方向の長さ
public:
D3DXVECTOR3 GetDirect( int elem ); // 指定軸番号の方向ベクトルを取得
FLOAT GetLen_W( int elem ); // 指定軸方向の長さを取得
D3DXVECTOR3 GetPos_W(); // 位置を取得
};
設定関数については派生されても追加されても良いと思います。特に方向ベクトルは標準化されていて、しかも互いに垂直関係で回転しなければなりませんので、設定時にそれらの計算をしてしまうと間違いないでしょう。
OBBとOBBの衝突ができるようになると、例えばスキンメッシュで動く人物の当たり判定、3Dシューティングでの機体と敵機の衝突、カーレーシングゲームでの車同士の衝突、etc...などありとあらゆる場所で衝突を扱えるようになります。四角で囲むというシチュエーションはゲームでは非常に多いんです。もちろん、もっと厳密な衝突を判定しなければならないとなるとOBBよりも複雑なプリミティブを扱わなければなりませんが、この段階で衝突の1つの壁を乗り越えたのは間違いありません。多くの場合、最初の方向ベクトル6分離軸で判定は終了しますので、そこそこのパフォーマンスは発揮できますが、突き詰めればもう少しアルゴリズムを最適化できますので、探究心がおありになる方は試してみて下さい。
⑦ 謝辞
外積分離軸が必要な状況につきましてご教授下さいました中川様にお礼申し上げます。
