メニュー
トップ
開発環境
研究室
制作室(ブログ)
管理人プロフィール
リンク


3D衝突判定(当たり判定)

3D空間におけるオブジェクト同士の衝突判定(当たり判定)を行うためのサンプルコードを紹介します。
3D空間におけるOBBとの衝突判定には、衝突していない要素を見つければよいそうです。その判定方法に分離軸判定というものがありますが、正直に言うとあまり理解していません。
どうやって実装したのかと言えば、「ゲームプログラミングのためのリアルタイム衝突判定」という本に C 言語のサンプルが載っていたので、それを DirectX 用に変更しました。 ですので、詳細な理論はそちらの本に譲りまして、ここでは DirectX で実装可能なコードサンプルの提供と、説明が不足していると思われる部分について補足的に説明を加えることをしたいと思います。


OBB とは何ぞや?

ここでは OBB がなんであるか、と言うことと、OBB をどのように作ればよいかという点について説明したいと思います。それでは、いきなり OBB の構造体を見てみたいと思います。

struct OBB{
    D3DXVECTOR3 c;     //中心点の座標
    D3DXVECTOR3 u[3];  //XYZ の各座標軸の傾きを表す方向ベクトル
    D3DXVECTOR3 e;     //OBB の各座標軸に沿った長さの半分(中心点から面までの長さ)
};

OBB は Oriented Bounding Box の略で、日本語で表現すると有向境界ボックスとなります。OBB は大きく3つの要素、中心点の座標、各座標軸の傾きを表す方向ベクトル、OBB の各座標軸に沿った長さの半分を持ち、 3次元における任意の大きさと傾きを持った直方体を表現します。各要素の意味と求め方をそれぞれ解説します。その後、具体的な OBB 生成コードを見てみましょう。

中心点 c・・・中心点は、文字通り、OBB の中心の座標を表します。この中心点の求め方ですが、最初に全体の大きさを測るために AABB を作成するのと同じ手法を用います。 XYZ 各成分におけるメッシュの頂点座標の最大値と最小値を求めます。これにより、最大値と最小値をプラスして2で割ったものが中心点となります。ただ、回転などの要素を考慮した場合、 中心点がちょうど原点になるように、メッシュモデルを調整しておくことをお勧めします。OBB が原点から移動した場合、単にその座標を c に代入すればよいからです。

方向ベクトル u・・・方向ベクトルは、XYZ の各座標軸ごとの傾きを表します。これは回転行列から XYZ の各成分を抜き出して D3DXVECTOR3 構造体を生成すればよいです。 ここでも OBB の中心点が原点になるようにメッシュモデルを調整しておくことをお勧めします。原点で回転を行うことで、容易に回転行列を得ることができ、メッシュモデルの回転とも同期が容易だからです。

長さ e・・・各座標軸に沿った長さの半分です。最初の中心点を求める場合に生成した、頂点座標の最大値と最小値を使用すれば算出することができます。 最大値から最小値をマイナスし、それを2で割ったものが長さの半分になります。

それではコードサンプルを見てみましょう。

struct VERTEX
{
    D3DXVECTOR3 position, normal;
    float tu, tv;
}

void CreateOBB(OBB *obb)
{
    D3DXMATRIX matRot;

    //最大値、最小値の初期値設定
    D3DXVECTOR3 max = D3DXVECTOR3(-10000.0f, -10000.0f, -10000.0f);
    D3DXVECTOR3 min = D3DXVECTOR3(10000.0f, 10000.0f, 10000.0f);

    //メッシュの頂点データ取得
    VERTEX* vertexBuffer = NULL;
    m_pMesh->LockVertexBuffer(0, (void**)&vertexBuffer);
    //最大値、最小値取得ループ
    for(int i = 0; i < g_pMesh->GetNumVertices(); i++)
    {
        D3DXVECTOR3 pos = &vertexBuffer[i].position;
        if(pos.x < min.x)min.x = pos.x;
        if(pos.x > max.x)max.x = pos.x;
        if(pos.y < min.y)min.y = pos.y;
        if(pos.y > max.y)max.y = pos.y;
        if(pos.z < min.z)min.z = pos.z;
        if(pos.z > max.z)max.z = pos.z;
    }
    g_pMesh->UnlockVertexBuffer();

    //中心点取得
    obb->c = (min + max) * 0.5f + g_worldPos;

    //方向ベクトル取得
    D3DXMatrixRotationYawPitchRoll(&matRot, g_angleY, g_angleX, g_angleZ);
    obb->u[0] = D3DXVECTOR3(matRot._11,matRot._12,matRot._13);
    obb->u[1] = D3DXVECTOR3(matRot._21,matRot._22,matRot._23);
    obb->u[2] = D3DXVECTOR3(matRot._31,matRot._32,matRot._33);

    //長さ取得
    obb->e.x = fabsf(max.x - min.x) * 0.5f;
    obb->e.y = fabsf(max.y - min.y) * 0.5f;
    obb->e.z = fabsf(max.z - min.z) * 0.5f;
}

            
まず、新しい構造体VERTEXが出てきました。これはメッシュの頂点情報を格納するための構造体です。この構造体の position から座標の最大値、最小値を求めます。 初期値には、最初の比較に備えて、position が必ず最大値及び最小値になるように十分に小さな値と大きな値を設定しておきます。すべての頂点について比較を行い、目的の値を取得します。 メッシュから頂点情報を取得する際は、Lock と Unlock を忘れずに行いましょう。

準備が整ったら、OBB の各要素について値を取得します。

まず中心点です。先ほどの説明どおり、最大値と最小値をプラスして、2で割る(ここでは0.5を掛けていますが)ことで求めています。そこに OBB のワールド座標上の位置をプラスすることで、 中心点の位置を求めることができます。もし、この OBB が移動している場合、移動に際しこの中心点も移動する必要があります。もう一度同じ方法で求めるか、移動量をプラスするかは、 それぞれのプログラムにおける制約に依存しますが、当然、移動量をプラスするほうが計算量は少なくてすみます。中心点が原点の場合、ワールド座標を単に代入するだけで済みます。

方向ベクトルは、OBB の傾いている角度から、D3DXライブラリの回転行列を求める関数によって取得することができます。DirectX における行列は行ベクトルになっており、行方向に XYZW 成分、列方向に XYZ 軸を見ることができます。方向ベクトル u は配列になっていますが、1番目の要素が X 軸、2番目の要素が Y 軸、3番目の要素が Z 軸となっていますので、 コードのように行列の各要素に D3DXVECTOR3 構造体を代入します。OBB が回転するたびに、同じ方法で方向ベクトルを更新する必要があります。

最後に長さの取得ですが、頂点座標の最大値がマイナス値だった場合に備えて絶対値を求めていますが、先の説明どおり、最大値から最小値をマイナスし、2で割ることで取得することができます。



OBB に対する点の最接近点

いよいよ衝突判定です。まずは OBB と点の最接近点を求めています。この判定単体では衝突判定にはなりません。他の衝突判定の処理の一部になります。

void ClosestPtPointOBB(D3DXVECTOR3 *p, ST0001_OBB *b, D3DXVECTOR3 *q)
{
    D3DXVECTOR3 d = *p - b->c;
    *q = b->c;
    float dist;
    for(int i = 0; i < 3; i++)
    {
        dist = D3DXVec3Dot(&d, &b->u[i]);

        if(dist > b->e[i])
        {
            dist = b->e[i];
        }
        if(dist < -b->e[i])
        {
            dist = -b->e[i];
        }
        *q += dist * b->u[i];
    }
}

            
これは OBB の座標系に点の座標を変換する処理のようですが、よく理解してないのでテキストの内容を見てくださいとしか言えません。


OBB 対球の衝突判定

OBB と球の衝突判定です。球は中心点と半径だけで表現できるため、メモリ消費と計算量の両方において低コストな境界ボリュームです。球に近い形状の弾丸などに用いることができます。
struct SPHERE
{
    D3DXVECTOR3 c;
    float r;
};

int TestSphereOBB(SPHERE *s, OBB *b, D3DXVECTOR3 *p)
{
        ClosestPtPointOBB(&s->c, b, p);
        D3DXVECTOR3 v = *p - s->c;
        return D3DXVec3Dot(&v, &v) <= s->r * s->r;
}

        
OBB に対する点の再接近点を利用して、球との衝突判定を行っています。計算式の意味は分かりません。テキストをご覧ください。


OBB 対線分の衝突判定

OBB と線分の衝突判定(交差判定)です。マウスカーソルによるオブジェクトのピックなどに使用できます。私がピックを行う場合、カメラ位置を一方の端点、 視線ベクトルとFar Plane との交点をもう一方の端点としています。視線ベクトルについてはマウス関連のトピックで解説する予定です。

struct RAY
{
    D3DXVECTOR3 org;
    D3DXVECTOR3 dir;
};

int TestSegmentOBB(RAY *ray, OBB *obb)
{
    const float EPSILON = 1.175494e-37;

    D3DXVECTOR3 m = (ray->org + ray->dir) * 0.5f;
    D3DXVECTOR3 d = ray->dir - m;
    m = m - obb->c;
    m = D3DXVECTOR3(D3DXVec3Dot(&obb->u[0], &m), D3DXVec3Dot(&obb->u[1], &m), D3DXVec3Dot(&obb->u[2], &m));
    d = D3DXVECTOR3(D3DXVec3Dot(&obb->u[0], &d), D3DXVec3Dot(&obb->u[1], &d), D3DXVec3Dot(&obb->u[2], &d));

    float adx = fabsf(d.x);
    if(fabsf(m.x) > obb->e.x + adx) return 0;
    float ady = fabsf(d.y);
    if(fabsf(m.y) > obb->e.y + ady) return 0;
    float adz = fabsf(d.z);
    if(fabsf(m.z) > obb->e.z + adz) return 0;
    adx += EPSILON; 
    ady += EPSILON; 
    adz += EPSILON;
        
    if(fabsf(m.y * d.z - m.z * d.y) > obb->e.y * adz + obb->e.z * ady ) return 0;
    if(fabsf(m.z * d.x - m.x * d.z) > obb->e.x * adz + obb->e.z * adx ) return 0;
    if(fabsf(m.x * d.y - m.y * d.x) > obb->e.x * ady + obb->e.y * adx ) return 0;

    return 1;
}

            
上記のテキストにはこのサンプルコードは記載されていません。TestSegmentAABB という似た関数の記載はありますが、OBB のものではありません。
AABB 版との違いは、線分ベクトルを表すコード中の変数、m 及び d を OBB の座標系に射影する点です。これは方向ベクトルとの内積によって求められます。


OBB 対 OBB の衝突判定

OBB 対 OBB の衝突判定は、テキストどおりです。特に説明する部分はありません。

int TestOBBOBB(OBB *a, OBB *b)
{
    const float EPSILON = 1.175494e-37;

    float R[3][3], AbsR[3][3];
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            R[i][j] = D3DXVec3Dot(&a->u[i], &b->u[j]);
            AbsR[i][j] = fabsf(R[i][j]) + EPSILON;
        }
    }
        
    D3DXVECTOR3 t = b->c - a->c;
    t = D3DXVECTOR3(D3DXVec3Dot(&t, &a->u[0]), D3DXVec3Dot(&t, &a->u[1]), D3DXVec3Dot(&t, &a->u[2]));
        
    //軸L=A0, L=A1, L=A2判定
    float ra, rb;

    for(int i = 0; i < 3; i++)
    {
        ra = a->e[i];
        rb = b->e[0] * AbsR[i][0] + b->e[1] * AbsR[i][1] + b->e[2] * AbsR[i][2];
        if(fabsf(t[i]) > ra + rb)return 0;
    }
    //軸L=B0, L=B1, L=B2判定
    for(int i = 0; i < 3; i++)
    {
        ra = a->e[0] * AbsR[0][i] + a->e[1] * AbsR[1][i] + a->e[2] * AbsR[2][i];
        rb = b->e[i];
        if(fabsf(t[0] * R[0][i] + t[1] * R[1][i] + t[2] * R[2][i]) > ra + rb)return 0;
    }

    //軸L=A0 X B0判定
    ra = a->e[1] * AbsR[2][0] + a->e[2] * AbsR[1][0];
    rb = b->e[1] * AbsR[0][2] + b->e[2] * AbsR[0][1];
    if(fabsf(t[2] * R[1][0] - t[1] * R[2][0]) > ra + rb)return 0;

    //軸L=A0 X B1判定
    ra = a->e[1] * AbsR[2][1] + a->e[2] * AbsR[1][1];
    rb = b->e[0] * AbsR[0][2] + b->e[2] * AbsR[0][0];
    if(fabsf(t[2] * R[1][1] - t[1] * R[2][1]) > ra + rb)return 0;

    //軸L=A0 X B2判定
    ra = a->e[1] * AbsR[2][2] + a->e[2] * AbsR[1][2];
    rb = b->e[0] * AbsR[0][1] + b->e[1] * AbsR[0][0];
    if(fabsf(t[2] * R[1][2] - t[1] * R[2][2]) > ra + rb)return 0;

    //軸L=A1 X B0判定
    ra = a->e[0] * AbsR[2][0] + a->e[2] * AbsR[0][0];
    rb = b->e[1] * AbsR[1][2] + b->e[2] * AbsR[1][1];
    if(fabsf(t[0] * R[2][0] - t[2] * R[0][0]) > ra + rb)return 0;

    //軸L=A1 X B1判定
    ra = a->e[0] * AbsR[2][1] + a->e[2] * AbsR[0][1];
    rb = b->e[0] * AbsR[1][2] + b->e[2] * AbsR[1][0];
    if(fabsf(t[0] * R[2][1] - t[2] * R[0][1]) > ra + rb)return 0;

    //軸L=A1 X B2判定
    ra = a->e[0] * AbsR[2][2] + a->e[2] * AbsR[0][2];
    rb = b->e[0] * AbsR[1][1] + b->e[1] * AbsR[1][0];
    if(fabsf(t[0] * R[2][2] - t[2] * R[0][2]) > ra + rb)return 0;

    //軸L=A2 X B0判定
    ra = a->e[0] * AbsR[1][0] + a->e[1] * AbsR[0][0];
    rb = b->e[1] * AbsR[2][2] + b->e[2] * AbsR[2][1];
    if(fabsf(t[1] * R[0][0] - t[0] * R[1][0]) > ra + rb)return 0;

    //軸L=A2 X B1判定
    ra = a->e[0] * AbsR[1][1] + a->e[1] * AbsR[0][1];
    rb = b->e[0] * AbsR[2][2] + b->e[2] * AbsR[2][0];
    if(fabsf(t[1] * R[0][1] - t[0] * R[1][1]) > ra + rb)return 0;

    //軸L=A2 X B2判定
    ra = a->e[0] * AbsR[1][2] + a->e[1] * AbsR[0][2];
    rb = b->e[0] * AbsR[2][1] + b->e[1] * AbsR[2][0];
    if(fabsf(t[1] * R[0][2] - t[0] * R[1][2]) > ra + rb)return 0;

    return 1;
}

            
inserted by FC2 system