Gamasutra: The Art & Business of Making Gamesspacer
Simple Intersection Tests For Games
View All     RSS
September 1, 2014
arrowPress Releases
September 1, 2014
PR Newswire
View All





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Simple Intersection Tests For Games
by miguel gomez []

October 18, 1999 Article Start Previous Page 5 of 7 Next
 

An Oriented Bounding Box (OBB) Intersection Test

A drawback of using an axis-aligned bounding box is that it can’t fit rotating geometry very tightly.

On the other hand, an oriented bounding box can be rotated with the objects, fitting the geometry with less volume than an AABB. This requires that the orientation of the box must also be specified. Figure 8 shows a 2D example, where A1, A2, B1 and B2 are the local axes of boxes A and B.

 

 

 

For OBBs, the separating axis test must be generalized to three dimensions. A box's scalar projection onto a unit vector L creates an interval along the axis defined by L.

The radius of the projection of box A onto L is

The same is true for B, and L forms a separating axis if

Note that L does not have to be a unit vector for this test to work. The boxes A and B are disjoint if none of the 6 principal axes and their 9 cross products form a separating axis. These tests are greatly simplified if T and B’s basis vectors (B1, B2, B3) are transformed into A’s coordinate frame.

An OBB class and an implementation of the OBB overlap test is given in Listing 6 below.

Listing 6. An OBB class.

#include "coordinate_frame.h"

class OBB : public COORD_FRAME
{

public:

 

VeCTOR E; //extents
OBB( const VECTOR& e ): E(e)

{}

};

//check if two oriented bounding boxes overlap
const bool OBBOverlap
(

 

//A
VECTOR& a, //extents
VECTOR& Pa, //position
VECTOR* A, //orthonormal basis

//B
VECTOR& b, //extents
VECTOR& Pb, //position
VECTOR* B //orthonormal basis

)

{

 

//translation, in parent frame
VECTOR v = Pb - Pa;

//translation, in A's frame
VECTOR T( v.dot(A[0]), v.dot(A[1]), v.dot(A[2]) );

//B's basis with respect to A's local frame
SCALAR R[3][3];
float ra, rb, t;
long i, k;

//calculate rotation matrix
for( i=0 ; i<3 ; i++ )

 

for( k=0 ; k<3 ; k++ )

 

R[i][k] = A[i].dot(B[k]);

/*ALGORITHM: Use the separating axis test for all 15 potential
separating axes. If a separating axis could not be found, the two
boxes overlap. */

//A's basis vectors
for( i=0 ; i<3 ; i++ )
{

 

ra = a[i];

rb =
b[0]*fabs(R[i][0]) + b[1]*fabs(R[i][1]) + b[2]*fabs(R[i][2]);

t = fabs( T[i] );

if( t > ra + rb )
return false;

}

//B's basis vectors
for( k=0 ; k<3 ; k++ )
{

 

ra =
a[0]*fabs(R[0][k]) + a[1]*fabs(R[1][k]) + a[2]*fabs(R[2][k]);

rb = b[k];

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

if( t > ra + rb )
return false;

}

//9 cross products

//L = A0 x B0
ra =
a[1]*fabs(R[2][0]) + a[2]*fabs(R[1][0]);

rb =
b[1]*fabs(R[0][2]) + b[2]*fabs(R[0][1]);

t =
fabs( T[2]*R[1][0] -
T[1]*R[2][0] );

if( t > ra + rb )
return false;

//L = A0 x B1
ra =
a[1]*fabs(R[2][1]) + a[2]*fabs(R[1][1]);

rb =
b[0]*fabs(R[0][2]) + b[2]*fabs(R[0][0]);

t =
fabs( T[2]*R[1][1] -
T[1]*R[2][1] );

if( t > ra + rb )
return false;

//L = A0 x B2
ra =
a[1]*fabs(R[2][2]) + a[2]*fabs(R[1][2]);

rb =
b[0]*fabs(R[0][1]) + b[1]*fabs(R[0][0]);

t =
fabs( T[2]*R[1][2] -
T[1]*R[2][2] );

if( t > ra + rb )
return false;

//L = A1 x B0
ra =
a[0]*fabs(R[2][0]) + a[2]*fabs(R[0][0]);

rb =
b[1]*fabs(R[1][2]) + b[2]*fabs(R[1][1]);

t =
fabs( T[0]*R[2][0] -
T[2]*R[0][0] );

if( t > ra + rb )
return false;

//L = A1 x B1
ra =
a[0]*fabs(R[2][1]) + a[2]*fabs(R[0][1]);

rb =
b[0]*fabs(R[1][2]) + b[2]*fabs(R[1][0]);

t =
fabs( T[0]*R[2][1] -
T[2]*R[0][1] );

if( t > ra + rb )
return false;

//L = A1 x B2
ra =
a[0]*fabs(R[2][2]) + a[2]*fabs(R[0][2]);

rb =
b[0]*fabs(R[1][1]) + b[1]*fabs(R[1][0]);

t =
fabs( T[0]*R[2][2] -
T[2]*R[0][2] );

if( t > ra + rb )
return false;

//L = A2 x B0
ra =
a[0]*fabs(R[1][0]) + a[1]*fabs(R[0][0]);

rb =
b[1]*fabs(R[2][2]) + b[2]*fabs(R[2][1]);

t =
fabs( T[1]*R[0][0] -
T[0]*R[1][0] );

if( t > ra + rb )
return false;

//L = A2 x B1
ra =
a[0]*fabs(R[1][1]) + a[1]*fabs(R[0][1]);

rb =
b[0] *fabs(R[2][2]) + b[2]*fabs(R[2][0]);

t =
fabs( T[1]*R[0][1] -
T[0]*R[1][1] );

if( t > ra + rb )
return false;

//L = A2 x B2
ra =
a[0]*fabs(R[1][2]) + a[1]*fabs(R[0][2]);

rb =
b[0]*fabs(R[2][1]) + b[1]*fabs(R[2][0]);

t =
fabs( T[1]*R[0][2] -
T[0]*R[1][2] );

if( t > ra + rb )
return false;

/*no separating axis found,
the two boxes overlap */

return true;

}

 

For a more complete discussion of OBBs and the separating axis test, please see [3]. Some other applications of the separating axis test are given next.


Article Start Previous Page 5 of 7 Next

Related Jobs

Cloud Imperium Games
Cloud Imperium Games — Santa Monica, California, United States
[09.01.14]

Technical Animator
Blizzard Entertainment
Blizzard Entertainment — Irvine, California, United States
[09.01.14]

Heroes of the Storm - User Interface Artist
Playtika Santa Monica
Playtika Santa Monica — Santa Monica, California, United States
[09.01.14]

BI Analyst
Playtika Santa Monica
Playtika Santa Monica — Santa Monica, California, United States
[09.01.14]

Sr. BI Developer






Comments


Dave Moss
profile image
The scaler u0 and u1 represent the time the objects will collide...

Petter Oberg
profile image
Shouldn't SphereSphereSweep() return true only if 0 <= u0 <= 1, since else the collision does not occur within this frame?


none
 
Comment: