Orientierte Bounding-Boxen (OBB), OBB-OBB-Kollisionstest

Spieleobjekte unterliegen beständigen Transformationen. Ändert sich beispielsweise ihre Orientierung, dann betrifft diese Änderung nicht allein das 3D-Modell; auch das verwendete Kollisionsmodell muss entsprechend transformiert werden.
Verwendet man ein Kollisionsmodell auf Basis von Bounding-Sphären, dann ändern sich dabei lediglich die Positionen der einzelnen Bounding-Sphären. Komplizierter ist die Situation bei einem Kollisionsmodell auf Basis von Bounding-Boxen, denn hier ändern sich zusätzlich dazu auch die Orientierungen der einzelnen Boxen. In diesem Zusammenhang spricht man von sogenannten orientierten Bounding-Boxen (OBB).

Da eine OBB im Raum beliebig orientiert sein kann, müssen wir zur Angabe ihrer Orientierung zusätzlich zur Ausdehnung der Box noch drei Normalenvektoren definieren, die zusammengenommen ein rechtwinkliges Dreibein bilden. Darüber hinaus müssen alle Normalen parallel bzw. senkrecht zu den Begrenzungsflächen der Bounding-Box orientiert sein:

 

struct COBB
{
    D3DXVECTOR3 Mittelpunkt;
    D3DXVECTOR3 Ausdehnung;
    D3DXVECTOR3 Normal[3];
};

Der OBB-OBB-Kollisionstest

Die Implementierung eines Kollisionstests für zwei achsenausgerichtete Bounding-Boxen haben wir bereits in einem früheren Artikel besprochen. Um nun die Funktionsweise eines Kollisionstests für zwei orientierte Bounding-Boxen verstehen zu können, müssen wir an dieser Stelle den Begriff der separierenden Achse einführen, der sich am Beispiel des AABB-AABB-Kollisionstests besonders gut veranschaulichen lässt:

Eine Kollision kann immer dann ausgeschlossen werden, wenn sich die beiden Boxen entlang mindestens einer ihrer separierenden Achsen nicht überlappen.

Im Falle von achsenausgerichteten Bounding-Boxen verlaufen die separierenden Achsen in x-, y- und z-Richtung, bei orientierten Boxen parallel zu den jeweiligen Box-Normalen.

Der OBB-OBB-Kollisionstest stellt eine logische Erweiterung des Kollisionstests zwischen achsenausgerichteten Bounding-Boxen dar. Aufgrund der beliebigen Orientierungsmöglichkeiten dieser Boxen ergeben sich nicht weniger als 15 potenzielle separierbare Achsen (2*3 Normalenvektoren der Boxen + 9 Vektorprodukte zwischen den Normalenvektoren), die nacheinander überprüft werden müssen.

Hinweis:

Die Funktion für den OBB-OBB-Kollisionstest, die wir im Folgenden besprechen, ist, von einigen wenigen Änderungen abgesehen, vollständig aus dem Artikel von Miguel Gomes: Simple Intersection Tests for Games, Gamasutra, October 1999 übernommen.

INLINE BOOL OBB_OBB_Collision(COBB* pBox1, COBB* pBox2)
{

    D3DXVECTOR3 v;

// Vektoren für Boxausdehnung und separierende Achse:
    float a[3];
    float b[3];
    float T[3];

    // Projektionsmatrizen:
    float R[3][3];
    float abs_R[3][3];

    long i, k;
    float ra, rb, t;

    a[0] = pBox1->Ausdehnung.x;
    a[1] = pBox1->Ausdehnung.y;
    a[2] = pBox1->Ausdehnung.z;

    b[0] = pBox2->Ausdehnung.x;
    b[1] = pBox2->Ausdehnung.y;
    b[2] = pBox2->Ausdehnung.z;

// Berechnung der Projektionskoeffizienten für die Projektion der
// Ausdehnung von Box2 auf die Normalen von Box1.
// Bei identischen Normalen ergibt sich die Einheitsmatrix:

    for(i = 0; i < 3; i++)
    {
        for(k = 0; k < 3; k++)
        {
        R[i][k] = D3DXVec3Dot(&pBox1->Normal[i], &pBox2->Normal[k]);
        abs_R[i][k] = (float)fabs(R[i][k]);
        }
    }

// Rücktransformation des Mittelpunktdifferenzvektors auf die
// Modellkoordinaten von Box1.
// Das Modellkoordinatensystem wird durch die Normalenvektoren von
// Box 1 aufgespannt.
// Für den Fall, dass Box1 achsenausgerichtet ist, zeigen die
// Normalenvektoren in x-, y- und z-Richtung und die Vektoren v und
// T sind identisch.

    v = pBox2->Mittelpunkt – pBox1->Mittelpunkt;
    T[0] = D3DXVec3Dot(&v, &pBox1->Normal[0]);
    T[1] = D3DXVec3Dot(&v, &pBox1->Normal[1]);
    T[2] = D3DXVec3Dot(&v, &pBox1->Normal[2]);

// Zunächst wird getestet, ob die Normalenvektoren der beiden
// Boxen eine separierende Achse bilden.
// Für zwei AABB vereinfachen sich die Ausdrücke, da gilt:
// R[i][k] = 1 wenn i = k, sonst R[i][k] = 0. Gleiches gilt auch
// für abs_R[i][k] => es ergibt sich der AABB-AABB-Kollisionstest
// in doppelter Ausführung.

    for(i = 0; i < 3; i++)
    {
        ra = a[i];

        // Projektion der Ausdehnung von Box2 auf die Normalen
        // von Box1:

        rb = b[0]*abs_R[i][0]+
             b[1]*abs_R[i][1]+
             b[2]*abs_R[i][2];

        t = (float)fabs(T[i]);

        if(t > ra + rb)
            return FALSE;
    }

    for(i = 0; i < 3; i++)
    {

        // Projektion der Ausdehnung von Box1 auf die Normalen
        // von Box2:

        ra = a[0]*abs_R[0][i]+
             a[1]*abs_R[1][i]+
             a[2]*abs_R[2][i];

        rb = b[i];

        t = (float)fabs(T[0]*R[0][i]+T[1]*R[1][i]+T[2]*R[2][i]);

        if(t > ra + rb)
            return FALSE;
    }

// Nun wird getestet, ob die Vektorprodukte aus den Normalenvektoren
// eine separierende Achse bilden:
// Für zwei AABB vereinfachen sich die Ausdrücke, da gilt:
// R[i][k] = 1 wenn i = k, sonst R[i][k] = 0. Gleiches gilt auch
// für abs_R[i][k].

    // L = pBox1->Normal[0] X pBox2->Normal[0]:
    ra = a[1]*abs_R[2][0] + a[2]*abs_R[1][0];
    rb = b[1]*abs_R[0][2] + b[2]*abs_R[0][1];
    t  = (float)fabs(T[2]*R[1][0] – T[1]*R[2][0]);

    if(t > ra + rb)
        return FALSE;

    // L = pBox1->Normal[0] X pBox2->Normal[1]:
    ra = a[1]*abs_R[2][1] + a[2]*abs_R[1][1];
    rb = b[0]*abs_R[0][2] + b[2]*abs_R[0][0];
    t  = (float)fabs(T[2]*R[1][1] – T[1]*R[2][1]);

    if(t > ra + rb)
        return FALSE;

    // L = pBox1->Normal[0] X pBox2->Normal[2]:
    ra = a[1]*abs_R[2][2] + a[2]*abs_R[1][2];
    rb = b[0]*abs_R[0][1] + b[1]*abs_R[0][0];
    t  = (float)fabs(T[2]*R[1][2] – T[1]*R[2][2]);

    if(t > ra + rb)
        return FALSE;

    // L = pBox1->Normal[1] X pBox2->Normal[0]:
    ra = a[0]*abs_R[2][0] + a[2]*abs_R[0][0];
    rb = b[1]*abs_R[1][2] + b[2]*abs_R[1][1];
    t  = (float)fabs(T[0]*R[2][0] – T[2]*R[0][0]);

    if(t > ra + rb)
        return FALSE;

    // L = pBox1->Normal[1] X pBox2->Normal[1]:
    ra = a[0]*abs_R[2][1] + a[2]*abs_R[0][1];
    rb = b[0]*abs_R[1][2] + b[2]*abs_R[1][0];
    t  = (float)fabs(T[0]*R[2][1] – T[2]*R[0][1]);

    if(t > ra + rb)
        return FALSE;

    // L = pBox1->Normal[1] X pBox2->Normal[2]:
    ra = a[0]*abs_R[2][2] + a[2]*abs_R[0][2];
    rb = b[0]*abs_R[1][1] + b[1]*abs_R[1][0];
    t  = (float)fabs(T[0]*R[2][2] – T[2]*R[0][2]);

    if(t > ra + rb)
        return FALSE;

    // L = pBox1->Normal[2] X pBox2->Normal[0]:
    ra = a[0]*abs_R[1][0] + a[1]*abs_R[0][0];
    rb = b[1]*abs_R[2][2] + b[2]*abs_R[2][1];
    t  = (float)fabs(T[1]*R[0][0] – T[0]*R[1][0]);

    if(t > ra + rb)
        return FALSE;

    // L = pBox1->Normal[2] X pBox2->Normal[1]:
    ra = a[0]*abs_R[1][1] + a[1]*abs_R[0][1];
    rb = b[0]*abs_R[2][2] + b[2]*abs_R[2][0];
    t  = (float)fabs(T[1]*R[0][1] – T[0]*R[1][1]);

    if(t > ra + rb)
        return FALSE;

    // L = pBox1->Normal[2] X pBox2->Normal[2]:
    ra = a[0]*abs_R[1][2] + a[1]*abs_R[0][2];
    rb = b[0]*abs_R[2][1] + b[1]*abs_R[2][0];
    t  = (float)fabs(T[1]*R[0][2] – T[0]*R[1][2]);

    if(t > ra + rb)
        return FALSE;


    return TRUE;
}

Die Verwendung der Vektorprodukte der Normalenvektoren als separierende Achsen sieht für den Nicht-Mathematiker sehr kryptisch aus. Grund genug, um uns den Sachverhalt anhand zweier Spezialfälle zu verdeutlichen:

// L = pBox1->Normal[0] X pBox2->Normal[0]:
ra = a[1]*abs_R[2][0] + a[2]*abs_R[1][0];
rb = b[1]*abs_R[0][2] + b[2]*abs_R[0][1];
t  = (float)fabs(T[2]*R[1][0] – T[1]*R[2][0]);

Fall 1: Box1 und Box2 sind achsenausgerichtet. Beide Normalenvektoren zeigen in die gleiche Richtung und das Vektorprodukt aus pBox1->Normal[0] und pBox2->Normal[0] ist entsprechend null. In diesem Fall existiert die separierende Achse überhaupt nicht (R[1][0] = R[2][0] = 0).

Fall 2: pBox2->Normal[0] zeige in die z-Richtung, pBox2->Normal[1] in die y-Richtung und pBox2->Normal[2] in die negative x-Richtung (Drehung einer achsenausgerichteten Bounding Box um 90° um die y-Achse).

Box1 soll dagegen wieder eine AABB sein.

Berechnen wir nun das Vektorprodukt aus pBox1->Normal[0] und pBox2->Normal[0], dann erhalten wir als Ergebnis eine separierende Achse, die in die negative y-Richtung zeigt. Um die Länge dieser Achse zu berechnen, ersetzen wir nun die Matrixelemente R[i][k] durch die entsprechenden Skalarprodukte, welche wir bereits zuvor berechnet haben:

t = fabs(T[2]*D3DXVec3Dot(&pBox1->Normal[1], &pBox2->Normal[0]) -
         T[1]*D3DXVec3Dot(&pBox1->Normal[2], &pBox2->Normal[0]))

//t = fabs(-T[1]) , -y-Komponente des Mittelpunktdifferenzvektors
//wegen D3DXVec3Dot(&pBox1->Normal[2], &pBox2->Normal[0]) = 1

Auf die gleiche Weise können wir jetzt auch die Box-Ausdehnungen entlang der separierenden Achse berechnen:

ra = a[1]*fabs(D3DXVec3Dot(&pBox1->Normal[2], &pBox2->Normal[0])) +
     a[2]*fabs(D3DXVec3Dot(&pBox1->Normal[1], &pBox2->Normal[0])))

//ra = a[1] , y-Komponente der Box-Ausdehnung
//wegen fabs(D3DXVec3Dot(&pBox1->Normal[2], &pBox2->Normal[0]) = 1

rb = b[1]*fabs(D3DXVec3Dot(&pBox1->Normal[0], &pBox2->Normal[2])) +
     b[2]*fabs(D3DXVec3Dot(&pBox1->Normal[0], &pBox2->Normal[1])))

//rb = b[1] , y-Komponente der Box-Ausdehnung
//wegen fabs(D3DXVec3Dot(&pBox1->Normal[0], &pBox2->Normal[2]) = 1