Simple Intersection Tests For Games

**An
Axis-Aligned Bounding Box (AABB) Sweep Test****
**** **

Just like the name says, the faces of an axis-aligned bounding box are aligned with the coordinate axes of its parent frame (see Figure 3). In most cases AABBs can fit an object more tightly than a sphere, and their overlap test is extremely fast.

To see if A and B overlap, a separating axis test is used along the x, y, and z-axes. If the two boxes are disjoint, then at least one of these will form a separating axis. Figure 4 illustrates an overlap test in one dimension.

In this example the x-axis forms a separating axis because

Note that the separating axis test will return true even if one box fully contains the other. A more general separating axis test is given in the section below on oriented bounding boxes (OBB’s). Listing 3 defines an AABB class that implements this overlap test.

**Listing
3. An AABB class.**

#include "vector.h"

// An axis-aligned bounding box

class
AABB

{

public:

VECTOR P; //position

VECTOR E; //x,y,z extents

AABB( const VECTOR& p,

const VECTOR& e ): P(p), E(e){}

//returns
true if this is overlapping b

const bool
overlaps( const AABB& b ) const

{

const VECTOR T = b.P - P;//vector from A to B

return fabs(T.x) <= (E.x + b.E.x)

&&

fabs(T.y) <= (E.y + b.E.y)

&&

fabs(T.z) <= (E.z + b.E.z);

}

//NOTE:
since the vector indexing operator is not const,

//we must cast
away the const of the this pointer in the

//following
min() and max() functions

//min x,
y, or z

const SCALAR min( long i ) const

{

return ((AABB*)this)->P[i] - ((AABB*)this)->E[i];

}

//max
x, y, or z

const SCALAR
max( long i ) const

{

return ((AABB*)this)->P[i] + ((AABB*)this)->E[i];

}

};

For more information on AABBs and their applications, please see [8].

Just
like spheres, AABBs can be swept to find the first and last occurrence
of overlap. In Figure 5(a), A and B experienced displacements **v _{a}**
and

Figure 6 shows B's displacement as observed by A.

In this example, the normalized times it took for the x-extents and y-extents to overlap are given by

and
it can be seen that the x-extents will cross before the y-extents. The
two boxes cannot overlap until all the extents are overlapping, and
the boxes will cease to overlap when any one of these extents becomes
disjoint. If *u _{0,x}*,

Likewise,
if *u _{1,x}*,

In order for the two boxes to have overlapped during their displacement, the condition

must
have been met. Just like in the sphere sweep test, the positions of
first and last overlap can be linearly interpolated with *u*. Listing
4 gives an implementation of this AABB sweep algorithm.

**Listing
4. An AABB sweep algorithm.**

#include "aabb.h"

//Sweep
two AABB's to see if and when they first

//and last
were overlapping

const
bool AABBSweep

(

const VECTOR& Ea, //extents of AABB A

const VECTOR& A0, //its previous position

const VECTOR& A1, //its current position

const VECTOR& Eb, //extents of AABB B

const VECTOR& B0, //its previous position

const VECTOR& B1, //its current position

SCALAR& u0, //normalized time of first collision

SCALAR& u1 //normalized time of second collision

)

{

const AABB A( A0, Ea );//previous state of AABB A

const AABB B( B0, Eb );//previous state of AABB B

const VECTOR va = A1 - A0;//displacement of A

const VECTOR vb = B1 - B0;//displacement of B

//the problem is solved in A's frame of reference

VECTOR v = vb - va;

//relative velocity (in normalized time)VECTOR u_0(0,0,0);

//first times of overlap along each axisVECTOR u_1(1,1,1);

//last times of overlap along each axis//check if they were overlapping

// on the previous frame

if( A.overlaps(B) )

{

u0 = u1 = 0;

return true;}

//find the possible first and last times

//of overlap along each axis

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

{

if( A.max(i)<B.min(i) && v[i]<0 )

{

u_0[i] = (A.max(i) - B.min(i)) / v[i];}

else if( B.max(i)<A.min(i) && v[i]>0 )

{

u_0[i] = (A.min(i) - B.max(i)) / v[i];}

if( B.max(i)>A.min(i) && v[i]<0 )

{u_1[i] = (A.min(i) - B.max(i)) / v[i];}

else if( A.max(i)>B.min(i) && v[i]>0 )

{

u_1[i] = (A.max(i) - B.min(i)) / v[i];}

}

//possible first time of overlap

u0 = MAX( u_0.x, MAX(u_0.y, u_0.z) );//possible last time of overlap

u1 = MIN( u_1.x, MIN(u_1.y, u_1.z) );//they could have only collided if

//the first time of overlap occurred

//before the last time of overlap

return u0 <= u1;

}