spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Quellcode

D3DXMATRIXA16                       mInvMatrixA;
D3DXMATRIXA16                       mInvMatrixB;

/*
    D3DXMATRIX* D3DXMatrixInverse(          D3DXMATRIX* pOut,                   FLOAT* pDeterminant,
    CONST D3DXMATRIX* pM
    ); 
*/
    D3DXMATRIXA16   mSourceMatrixA;
    D3DXMATRIXA16   mSourceMatrixB;
    mSourceMatrixA  = (*iteMeshes1)->getMeshMatrix();
    mSourceMatrixB  = (*iteMeshes2)->getMeshMatrix();
    D3DXMatrixInverse(&mInvMatrixA, NULL, &mSourceMatrixA);
    D3DXMatrixInverse(&mInvMatrixB, NULL, &mSourceMatrixB);

    BOOL bCollision = this->checkModelHitsModel((*iteMeshes1),
                    mSourceMatrixA,
                    mInvMatrixA,
                    (*iteMeshes2),
                    mSourceMatrixB,
                    mInvMatrixB);   

    if (bCollision)
    {
    ATLTRACE(">-> collision between " + strMesh1 + " and " + strMesh2 + " detected\n","");
    return TRUE;
    }

Quellcode

BOOL checkModelHitsModel(CXMesh* pModelA,
        const D3DXMATRIXA16& mMatrixA,
        const D3DXMATRIXA16& mInvMatrixA,
        CXMesh* pModelB,
        const D3DXMATRIXA16& mMatrixB,
        const D3DXMATRIXA16& mInvMatrixB)
{
    // die positionen der beiden modelle aus den matrizen ablesen
    D3DXVECTOR3     vModelA(mMatrixA._41, mMatrixA._42, mMatrixA._43);
    D3DXVECTOR3     vModelB(mMatrixB._41, mMatrixB._42, mMatrixB._43);
    float           fRadiusA;
    float           fRadiusB;
    fRadiusA        = pModelA->getBoundingSphereRadius();
    fRadiusB        = pModelB->getBoundingSphereRadius();

    // prüfen ob sich die umgebungskugeln der beiden modelle schneiden.
    // falls sie es nicht tun, braucht man erst gar nicht mehr weiter zu testen.
    if (!this->checkSphereHitsSphere(vModelA, fRadiusA,
        vModelB, fRadiusB))
    {
        return FALSE;
    }

    // die rekursive Funktion aufrufen, mit den wurzelknoten beider modelle
    return (this->checkModelHitsModelRec(pModelA, mMatrixA, mInvMatrixA, pModelA->m_pcOctree,
        pModelB, mMatrixB, mInvMatrixB, pModelB->m_pcOctree));
}

BOOL checkModelHitsModelRec(CXMesh* pModelA,
        const D3DXMATRIXA16& mMatrixA,
        const D3DXMATRIXA16& mInvMatrixA,
        const COctree* pNodeA,
        CXMesh* pModelB,
        const D3DXMATRIXA16& mMatrixB,
        const D3DXMATRIXA16& mInvMatrixB,
        const COctree* pNodeB)
{
    // 1. schritt: schneiden sich die beiden bounding-boxes ?
    // schneiden sich die 2 umgebungsquader der beiden knoten ?
    // falls sie es nicht tun, kann es hier keine kollision geben
    /*
    if (!this->checkBoxHitsBox2(pNodeA->m_vBoundingBoxMin, 
        pNodeA->m_vBoundingBoxMax, 
        mMatrixA,
        pNodeB->m_vBoundingBoxMin, 
        pNodeB->m_vBoundingBoxMax, 
        mMatrixB))
    {
                // zurueck 
            return FALSE;
    }*/

    if (!this->checkBoxHitsBox(pNodeA->m_vBoundingBoxMin, 
        pNodeA->m_vBoundingBoxMax, 
        mMatrixA,
        pNodeB->m_vBoundingBoxMin, 
        pNodeB->m_vBoundingBoxMax, 
        mMatrixB, 3))
    {
                // zurueck 
            return FALSE;
    }

    // 2. schritt: fallunterscheidung:
    //      1. beide knoten sind endknoten
    //      2. knoten A ist ein endknoten, knoten B aber nicht
    //      3. knoten B ist ein endknoten, knoten A aber nicht
    //      4. beide knoten sind KEINE endknoten, haben also noch unterknoten

    // FALL 1:
    // die umgebungsquader schneiden sich
    // wenn beide knoten endknoten sind, muss man die Kollision der Dreieck überprüfen.
    if (pNodeA->m_bIsLeaf && pNodeB->m_bIsLeaf)
    {
        // einer der beiden knoten muss in jedem falls transformiert werden.
        // hier wurde knoten B gewählt. hat knoten B mehr dreiecke als knoten A, 
        // wird getauscht.
        if (pNodeB->m_dwNumTriangles > pNodeA->m_dwNumTriangles)
        {
            // tauschen
            return checkModelHitsModelRec(pModelB, mMatrixB, mInvMatrixB, pNodeB,
                pModelA, mMatrixA, mInvMatrixA, pNodeA);
        }

        // die vektoren von knoten B werden später beim test transformiert.
        // sie sollen zuerst absolut und dann relativ zu modell A umgerechnet werden.
        // es ist also die Transformation mit der Matrix von Modell B und anschließend
        // mit der inversen Matrix von Modell A nötig.

        D3DXMATRIXA16                       mTransformation;
        ZeroMemory(&mTransformation, sizeof(D3DXMATRIXA16));
        D3DXMatrixMultiply(&mTransformation, &mMatrixB, &mInvMatrixA);
        
        D3DXVECTOR3 vTriA;
        D3DXVECTOR3 vTriB;
        D3DXVECTOR3 vTriC;

        ATLTRACE(">-> \tchecking triangles\n","");

        // alle Dreiecke von Knoten B durchgehen
        for (UINT tb = 0; tb < pNodeB->m_dwNumTriangles; tb++)
        {
            // die drei vektoren dieses dreiecks transformieren
            D3DXVec3TransformCoord(&vTriA, &pNodeB->m_vectorTriangles.at(tb).vPointA, &mTransformation);
            D3DXVec3TransformCoord(&vTriB, &pNodeB->m_vectorTriangles.at(tb).vPointB, &mTransformation);
            D3DXVec3TransformCoord(&vTriC, &pNodeB->m_vectorTriangles.at(tb).vPointC, &mTransformation);

            // alle dreiecke von knoten A durchgehen
            for (UINT ta = 0; ta < pNodeA->m_dwNumTriangles; ta++)
            {
                if (this->checkTriangleHitsTriangle(pNodeA->m_vectorTriangles.at(ta).vPointA,
                    pNodeA->m_vectorTriangles.at(ta).vPointB,
                    pNodeA->m_vectorTriangles.at(ta).vPointC,
                    vTriA, vTriB, vTriC, NULL, NULL))
                {
                    // sofort abbrechen !
                    return TRUE;
                }
            }
        }
    }
    // FALL 2 und FALL 3:
    // Wenn Knoten A ein endknoten ist und knoten B nicht (Fall 2), dann geht man einfach jeden
    // unterknoten von knoten B durch und testet ihn auf kollision mit knoten A durch einen
    // rekursiven funktionsaufruf.
    else if (pNodeA->m_bIsLeaf && !pNodeB->m_bIsLeaf)
    {
        // knoten A ist ein Endknoten, Knoten B aber nicht.
        // man ruft die funktion für jeden untergeordneten knoten von B erneut auf.
        for (UINT i = 0; i < 8; i++)
        {
            if (this->checkModelHitsModelRec(pModelA, mMatrixA, mInvMatrixA, pNodeA,
                pModelB, mMatrixB, mInvMatrixB, pNodeB->m_apChild[i]))
            {
                // es gab eine kollision - sofort abbrechen
                return TRUE;
            }
        }
    }
    else if (!pNodeA->m_bIsLeaf && pNodeB->m_bIsLeaf)
    {
        // knoten A ist ein Endknoten, Knoten B aber nicht.
        // man ruft die funktion für jeden untergeordneten knoten von B erneut auf.
        for (UINT i = 0; i < 8; i++)
        {
            if (this->checkModelHitsModelRec(pModelA, mMatrixA, mInvMatrixA, pNodeA->m_apChild[i],
                pModelB, mMatrixB, mInvMatrixB, pNodeB))
            {
                // es gab eine kollision - sofort abbrechen
                return TRUE;
            }
        }
    }
    else 
    {
        // beide knoten sind KEINE endknoten
        // man testet nun knoten A mit allen unterknoten von knoten B
        for (UINT i = 0; i < 8; i++)
        {
            if (checkModelHitsModelRec(pModelA, mMatrixA, mInvMatrixA, pNodeA,
                pModelB, mMatrixB, mInvMatrixB, pNodeB->m_apChild[i]))
            {
                // es gab eine kollision! sofort abbrechen
                return TRUE;
            }
        }
    }
    return FALSE;
}

C-/C++-Quelltext

BOOL checkBoxHitsBox2(const D3DXVECTOR3& vBox1Min,
                      const D3DXVECTOR3& vBox1Max,
                      const D3DXMATRIXA16& mBox1Transformation,
                      const D3DXVECTOR3& vBox2Min,
                      const D3DXVECTOR3& vBox2Max,
                      const D3DXMATRIXA16& mBox2Transformation)
{
    D3DXMATRIXA16                   mT1;
    D3DXMATRIXA16                   mT2;
    mT1                             = mBox1Transformation;
    mT2                             = mBox2Transformation;
    

    D3DXVECTOR3                     vTemp;
    ZeroMemory(&vTemp, sizeof(D3DXVECTOR3));

    // Ausdehnung der ersten BoundingBox berechnen

    const D3DXVECTOR3 vBox1Extents((vBox1Max - vBox1Min) * 0.5f);
    vTemp                           = vBox1Max - vBox1Extents;
    D3DXVec3TransformCoord(&vTemp, &vTemp, &mT1);   
    const D3DXVECTOR3 vBox1Position(vTemp);

    // Ausdehnung der zweiten BoundingBox berechnen

    const D3DXVECTOR3 vBox2Extents((vBox2Max - vBox2Min) * 0.5f);
    vTemp                           = vBox2Max - vBox2Extents;
    D3DXVec3TransformCoord(&vTemp, &vTemp, &mT2);   
    const D3DXVECTOR3 vBox2Position(vTemp);

    // v = Mittelpunkt von 2 - Mittelpunkt von 1

    const D3DXVECTOR3 v(vBox2Position - vBox1Position);
    const D3DXVECTOR3 T(vector3Dot(v, D3DXVECTOR3(&mBox1Transformation._11)),
                      vector3Dot(v, D3DXVECTOR3(&mBox1Transformation._21)),
                      vector3Dot(v, D3DXVECTOR3(&mBox1Transformation._31)));

    // Projektionsmatrizen

    float                           R[3][3];
    float                           ra, rb, t;
    int                             i, k;
    float                           n1[16];
    float                           n2[16];

    n1[0]               = mBox1Transformation._11;
...
    n1[15]              = mBox1Transformation._44;

    for(i = 0; i < 3; i++)
    {
        for(k = 0; k < 3; k++)
        {
            R[i][k] = vector3Dot(D3DXVECTOR3(n1 + i * 4),
                                   D3DXVECTOR3(n1 + k * 4));
        }
    }
    for(i = 0; i < 3; i++)
    {
        if (i == 0)
        {
            ra = vBox1Extents.x;
        }
        else if (i==1)
        {
            ra = vBox1Extents.y;
        }
        else if (i==2)
        {
            ra = vBox1Extents.z;
        }

        rb = vBox2Extents.x * fabsf(R[i][0]) +
             vBox2Extents.y * fabsf(R[i][1]) +
             vBox2Extents.z * fabsf(R[i][2]);
        if (i==0)
        {
            t = fabsf(T.x);
        }
        else if (i==1)
        {
            t = fabsf(T.y);
        }
        else if (i==2)
        {
            t = fabsf(T.z);
        }
        
        if(t > ra + rb) 
            return FALSE;
    }

    for(k = 0; k < 3; k++)
    {
        ra = vBox1Extents.x * fabsf(R[0][k]) +
             vBox1Extents.y * fabsf(R[1][k]) +
             vBox1Extents.z * fabsf(R[2][k]);
        if (k == 0)
        {
            rb = vBox2Extents.x;
        }
        else if (k == 1)
        {
            rb = vBox2Extents.y;
        }
        else if (k == 2)
        {
            rb = vBox2Extents.z;
        }       
        
        t = fabsf(T.x * R[0][k] + T.y * R[1][k] + T.z * R[2][k]);
        if(t > ra + rb) 
            return FALSE;
    }

    ra = vBox1Extents.y * fabsf(R[2][0]) + vBox1Extents.z * fabsf(R[1][0]);
    ra = vBox2Extents.y * fabsf(R[0][2]) + vBox2Extents.z * fabsf(R[0][1]);
    t = fabsf(T.z * R[1][0] - T.y * R[2][0]);
    if(t > ra + rb) 
        return FALSE;

    ra = vBox1Extents.y * fabsf(R[2][1]) + vBox1Extents.z * fabsf(R[1][1]);
    rb = vBox2Extents.x * fabsf(R[0][2]) + vBox2Extents.z * fabsf(R[0][0]);
    t = fabsf(T.z * R[1][1] - T.y * R[2][1]);
    if(t > ra + rb) 
        return FALSE;

    ra = vBox1Extents.y * fabsf(R[2][2]) + vBox1Extents.z * fabsf(R[1][2]);
    rb = vBox2Extents.x * fabsf(R[0][1]) + vBox2Extents.y * fabsf(R[0][0]);
    t = fabsf(T.z * R[1][2] - T.y * R[2][2]);
    if(t > ra + rb)
        return FALSE;

    ra = vBox1Extents.x * fabsf(R[2][0]) + vBox1Extents.z * fabsf(R[0][0]);
    rb = vBox2Extents.y * fabsf(R[1][2]) + vBox2Extents.z * fabsf(R[1][1]);
    t = fabsf(T.x * R[2][0] - T.z * R[0][0]);
    if(t > ra + rb) 
        return FALSE;

    ra = vBox1Extents.x * fabsf(R[2][1]) + vBox1Extents.z * fabsf(R[0][1]);
    rb = vBox2Extents.x * fabsf(R[1][2]) + vBox2Extents.z * fabsf(R[1][0]);
    t = fabsf(T.x * R[2][1] - T.z * R[0][1]);
    if(t > ra + rb) 
        return FALSE;

    ra = vBox1Extents.x * fabsf(R[2][2]) + vBox1Extents.z * fabsf(R[0][2]);
    rb = vBox2Extents.x * fabsf(R[1][1]) + vBox2Extents.y * fabsf(R[1][0]);
    t = fabsf(T.x * R[2][2] - T.z * R[0][2]);
    if(t > ra + rb) 
        return FALSE;

    ra = vBox1Extents.x * fabsf(R[1][0]) + vBox1Extents.y * fabsf(R[0][0]);
    rb = vBox2Extents.y * fabsf(R[2][2]) + vBox2Extents.z * fabsf(R[2][1]);
    t = fabsf(T.y * R[0][0] - T.x * R[1][0]);
    if(t > ra + rb) 
        return FALSE;

    ra = vBox1Extents.x * fabsf(R[1][1]) + vBox1Extents.y * fabsf(R[0][1]);
    rb = vBox2Extents.x * fabsf(R[2][2]) + vBox2Extents.z * fabsf(R[2][0]);
    t = fabsf(T.y * R[0][1] - T.x * R[1][1]);
    if(t > ra + rb) 
        return FALSE;

    ra = vBox1Extents.x * fabsf(R[1][2]) + vBox1Extents.y * fabsf(R[0][2]);
    rb = vBox2Extents.x * fabsf(R[2][1]) + vBox2Extents.y * fabsf(R[2][0]);
    t = fabsf(T.y * R[0][2] - T.x * R[1][2]);
    if(t > ra + rb) 
        return FALSE;

    return TRUE;