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).
struct COBB
{
D3DXVECTOR3 Mittelpunkt;
D3DXVECTOR3 Ausdehnung;
D3DXVECTOR3 Normal[3];
};
{
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;
}
{
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]);
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
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
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