OBBによるリアルタイム衝突判定は何をしているの？

三次元空間でのオブジェクト同士の衝突判定に何かと使える、OBB対OBBのリアルタイム衝突判定についての説明です。

はじめに

OBBはオブジェクトを囲む境界ボックス(図1)です。 任意の軸を持っているため、座標系の各軸にボックスの面が平行である必要がないので、 様々な姿勢での衝突判定を行うことが可能です。 OBBは様々な表現ができますが、ここではOBBの中心座標、各軸の1/2の大きさ、 OBBの姿勢を表すクォータニオンを使って表現したOBBを使用します。 各軸の1/2の大きさは、図2の赤緑青の線のように、OBBのローカル座標系でOBBの中心からの各軸の大きさです。

スクリーンショット (図1) スクリーンショット (図2)

衝突判定

衝突判定を行う各オブジェクトのOBBをOBB1とOBB2とし、それぞれ次のような構造体で管理することにします。

//OBB構造体
struct TOBB{
    D3DXVECTOR3 m_vec3Center;            //OBBのローカル座標系での中心座標
    D3DXVECTOR3 m_vec3Size;              //OBBの各軸の1/2サイズ
    D3DXQUATERNION m_qPosture;           //OBBのローカル座標系での姿勢
    //-----
    D3DXVECTOR3 m_vec3WorldCenter;       //OBBのワールド座標系での中心座標
    D3DXQUATERNION m_qWorldPosture;      //OBBのワールド座標系での姿勢
};

TOBB OBB1;        //OBB1
TOBB OBB2;        //OBB2

まずは、計算しやすいように、OBB2の中心座標をOBB1の座標系へ変換します。

D3DXVECTOR3 vec3OBB2Center;           //OBB1の座標系でのOBB2の中心
D3DXQUATERNION qInversePosture;       //OBB1の姿勢の共役クォータニオン
D3DXMATRIX matPosture;                //姿勢行列

vec3OBB2Center = (OBB2.m_vec3Center + OBB2.m_vec3WorldCenter)
                    - (OBB1.m_vec3Center + OBB1.m_vec3WorldCenter);
D3DXQuaternionInverse(&qInversePosture, &(OBB1.m_qPosture * OBB1.m_qWorldPosture));
D3DXMatrixRotationQuaternion(&matPosture, &qInversePosture);
D3DXVec3TransformCoord(&vec3OBB2Center, &vec3OBB2Center, &matPosture);

中心座標の変換ができたら、次はOBB2の各軸もOBB1の座標系に変換します。

//OBB1の軸
D3DXVECTOR3 avec3OBB1Axis[3] = {
            D3DXVECTOR3(1.0f, 0.0f, 0.0f),       //X軸
            D3DXVECTOR3(0.0f, 1.0f, 0.0f),       //Y軸
            D3DXVECTOR3(0.0f, 0.0f, 1.0f)        //Z軸
};
D3DXVECTOR3 avec3OBB2Axis[3];    //OBB2の軸(0:X軸 1:Y軸 2:Z軸)

D3DXMatrixRotationQuaternion(&matPosture, &(OBB2.m_qPosture * OBB2.m_qWorldPosture * qInversePosture));
D3DXVec3TransformCoord(&avec3OBB2Axis[0], &avec3OBB1Axis[0], &matPosture);
D3DXVec3TransformCoord(&avec3OBB2Axis[1], &avec3OBB1Axis[1], &matPosture);
D3DXVec3TransformCoord(&avec3OBB2Axis[2], &avec3OBB1Axis[2], &matPosture);

OBB2の中心座標と各軸を、OBB1の座標系に変換できたら、いよいよ衝突判定に移ります。 衝突判定は、OBB1とOBB2の各軸を分離軸として、それぞれの分離軸に射影する事で衝突を判定します。 まずは、OBB1の軸を分離軸としてチェックします。

コードを短くするために、ループで処理していますが、実際にはOBB1の座標系で計算してるので、 fProjectOBB1の計算は無駄が多いです。 実際の射影は、OBB1.m_vec3Size.xがOBB1のX軸を分離軸としてみた場合の射影の大きさで、 OBB1.m_vec3Size.yがY軸を分離軸とした場合、OBB1.m_vec3Size.zがZ軸を分離軸とした場合の大きさになります。

float fProjectOBB1;                  //OBB1の射影の長さ
float fProjectOBB2;                  //OBB2の射影の長さ
float fProjectOBB1OBB2Center;        //OBB1とOBB2の中心の射影の距離

//OBB1の軸を分離軸としてチェック
for(int i = 0; i <= 2; ++i){
    fProjectOBB1 = fabsf(D3DXVec3Dot(&avec3OBB1Axis[i], &(avec3OBB1Axis[0] * OBB1.m_vec3Size.x)))
                    + fabsf(D3DXVec3Dot(&avec3OBB1Axis[i], &(avec3OBB1Axis[1] * OBB1.m_vec3Size.y)))
                    + fabsf(D3DXVec3Dot(&avec3OBB1Axis[i], &(avec3OBB1Axis[2] * OBB1.m_vec3Size.z)));
    fProjectOBB2 = fabsf(D3DXVec3Dot(&avec3OBB1Axis[i], &(avec3OBB2Axis[0] * OBB2.m_vec3Size.x)))
                    + fabsf(D3DXVec3Dot(&avec3OBB1Axis[i], &(avec3OBB2Axis[1] * OBB2.m_vec3Size.y)))
                    + fabsf(D3DXVec3Dot(&avec3OBB1Axis[i], &(avec3OBB2Axis[2] * OBB2.m_vec3Size.z)));
    fProjectOBB1OBB2Center = fabsf(D3DXVec3Dot(&avec3OBB1Axis[i], &vec3OBB2Center));
    if(fProjectOBB1OBB2Center > fProjectOBB1 + fProjectOBB2){
        //衝突していない
        break;
    }
}

このチェックは具体的には、図3のようにOBB1のある軸に着目すると、 OBB1の対象軸の大きさ(薄い赤の線の射影でProjOBB1とします)と、 OBB2の軸をOBB1の対象軸に射影した大きさ(薄い緑の線の射影でProjOBB2とします)の合計が、 OBB1の中心からOBB2の中心までのベクトルをOBB1の対象軸に射影した大きさ(薄い青の線の射影でProjOBB2Centerとします)以上なら、 OBB同士は衝突している可能性があり、小さければ衝突していない事になります(以下のコード参照)。

if(ProjOBB1 + ProjOBB2 >= ProjOBB2Center){
    //衝突の可能性あり
}
else{
    //衝突していない
}
スクリーンショット (図3)

もちろん、ひとつの軸に対して衝突の可能性がある事がわかっても、完全に衝突しているかどうかわからないので、 これをOBB1とOBB2の各軸を分離軸として全て調べる必要があります。 すべての分離軸に対して、このチェックがパスされれば、OBB同士は衝突している事になります。

同様にして、今度はOBB2の軸を分離軸として調べます。

//OBB2の軸を分離軸としてチェック
for(int i = 0; i <= 2; ++i){
    fProjectOBB1 = fabsf(D3DXVec3Dot(&avec3OBB2Axis[i], &(avec3OBB1Axis[0] * OBB1.m_vec3Size.x)))
                    + fabsf(D3DXVec3Dot(&avec3OBB2Axis[i], &(avec3OBB1Axis[1] * OBB1.m_vec3Size.y)))
                    + fabsf(D3DXVec3Dot(&avec3OBB2Axis[i], &(avec3OBB1Axis[2] * OBB1.m_vec3Size.z)));
    fProjectOBB2 = fabsf(D3DXVec3Dot(&avec3OBB2Axis[i], &(avec3OBB2Axis[0] * OBB2.m_vec3Size.x)))
                    + fabsf(D3DXVec3Dot(&avec3OBB2Axis[i], &(avec3OBB2Axis[1] * OBB2.m_vec3Size.y)))
                    + fabsf(D3DXVec3Dot(&avec3OBB2Axis[i], &(avec3OBB2Axis[2] * OBB2.m_vec3Size.z)));
    fProjectOBB1OBB2Center = fabsf(D3DXVec3Dot(&avec3OBB2Axis[i], &vec3OBB2Center));
    if(fProjectOBB1OBB2Center > fProjectOBB1 + fProjectOBB2){
        //衝突していない
        break;
    }
}

最後に、OBB1とOBB2の各軸に直交する軸を分離軸としてチェックします。

D3DXVECTOR3 vec3CrossAxis;        //OBB1とOBB2の各軸に直交する軸

//OBB1とOBB2の各軸に直交する軸を分離軸としてチェック
for(int i = 0; i <= 8; ++i){
    D3DXVec3Cross(&vec3CrossAxis, &avec3OBB1Axis[i / 3], &avec3OBB2Axis[i % 3]);
    D3DXVec3Normalize(&vec3CrossAxis, &vec3CrossAxis);
    fProjectOBB1 = fabsf(D3DXVec3Dot(&vec3CrossAxis, &(avec3OBB1Axis[0] * OBB1.m_vec3Size.x))) +
                    fabsf(D3DXVec3Dot(&vec3CrossAxis, &(avec3OBB1Axis[1] * OBB1.m_vec3Size.y))) +
                    fabsf(D3DXVec3Dot(&vec3CrossAxis, &(avec3OBB1Axis[2] * OBB1.m_vec3Size.z)));
    fProjectOBB2 = fabsf(D3DXVec3Dot(&vec3CrossAxis, &(avec3OBB2Axis[0] * OBB2.m_vec3Size.x))) +
                    fabsf(D3DXVec3Dot(&vec3CrossAxis, &(avec3OBB2Axis[1] * OBB2.m_vec3Size.y))) +
                    fabsf(D3DXVec3Dot(&vec3CrossAxis, &(avec3OBB2Axis[2] * OBB2.m_vec3Size.z)));
    fProjectOBB1OBB2Center = fabsf(D3DXVec3Dot(&vec3CrossAxis, &vec3OBB2Center));
    if(fProjectOBB1OBB2Center > fProjectOBB1 + fProjectOBB2){
        //衝突していない
        break;
    }
}

以上全部で15のチェック全てをパスした場合、OBB同士は衝突しているという事になります。

最後に

OBB同士の衝突判定は、ややコストが多めですが、OBBでの衝突判定を行う前にコストの低い境界球で衝突判定を行い、 それをパスしたらOBBでの衝突判定を行うなどの工夫をすれば、リアルタイムでも十分に使えます。

また、サンプルコードは無駄が多いので、その無駄をそぎ落とすと、まだまだ高速化できます。 OBBによるリアルタイム衝突判定は、公開されているデモ６で実際に確認できます。

誤りなどを見つけましたら、ご連絡ください。

(文： 2008/6/18 ラメイジュ 田中)

この文章は、予告なく改編される場合がございます。

この文章の無断での転用を禁止いたします。

このページへのリンクは大歓迎です。