Collision Detection between non-axis aligned rectangular prisms

Collision detection can be generalized for any convex shape (convex meaning it has not indents.)
If there exist at least a single flat plane that can go between both objects without touching either of them then the objects don't collide. Or put in simpler terms two objects aren't touching if I can pass a flat piece of paper between them. This is known as the Hyperplane Separation Theorem (AKA Separating Axis Theorem)

The trick now is finding position and orientation of this plane. When dealing with objects that have only flat surfaces, like boxes, you can guarantee that if the objects don't touch, there will be a plane that separates them that is parallel to one of the flat surfaces of the two objects. Or in other words, the flat piece of paper that fits between the two non-touching objects can pass between the two objects and lie flat on one of the surfaces of one of the two objects.

What this means for our boxes is that we only have to check for 12 different planes to see if the two boxes collide because each cube has 6 faces and there are two cubes, but because a cube consists of 3 sets of parallel faces we can reduce the number of planes to test by half. This is because the plane separation theorem depends on the normal of the plane being tested. The same normal can be used to test two faces at the same time. So the algorithm works something like this.

some 'pseudo' pseudo code

// I am assuming normal is a unit vector
// although the overlap algorithm will still
// work even if normal is not a unit vector
double scalarProjection(point, normal)
{
// http://en.wikipedia.org/wiki/Vector_projection
return point.dot(normal) / normal.dot(normal);
}
Range projectBox(box, normal)
{
Range result;

// iterate over each corner in the box
foreach (vertex in box.vertices)
{
double scalar = scalarProjection(vertex, normal);

if first vertex
{
result.max = scalar;
result.min = scalar;
}
else if (scalar > result.max)
result.max = scalar;
else if (scalar < result.min)
result.min = scalar;
}
}
bool doesCollide(boxa, boxb)
{
// create an array of vectors the represent the combined axis of the two boxes
Array<Vector> boxaxislist;

boxaxislist.append(boxa.axisList);
boxaxislist.append(boxb.axisList);

foreach (axis in boxaxislist)
{
Range boxaRange = projectBox(boxa, axis);
Range boxbRange = projectBox(boxb, axis);

if (!boxaRange.intersects(boxbRange))
{
// there was no overlap, we found a plane that separates the two boxes.
return false;
}
}

// no plane was found, the boxes must be overlapping
return true;
}


The axis list is simply an array of size 3 with the vectors in it.
Each vector is perpendicular to two of the faces of the box. You can think of this as
the x,y,z direction of the box. To know how to calculate the axis first think of a single
corner on a box. That corner will have the lines connecting it to three adjacent points.
Those three lines can be used as the three axis and can be calculated by simply subtracting
one endpoint from the other. You don't have to normalize the axis for this algorithm but keep
in mind if you later wish to use the axis in another algorithm it may require them to be normalized.
Just be aware of that

Here is a paper that describes what I just did but has some pictures.
Separating Axis Theorem for Oriented Bounding Boxes
If you need help understanding, google around some more about the seperating axis theorem and how to use it on boxes. If you still need help just ask what needs clearing up and if you do have anther question could post the way you are representing a box in 3 space?

I don't know if I remember correctly but with 2 OBB don't you have to check 15 axis? 3 normals of the first box, 3 normals of the second box and all possibly cross products between the normals of the the two boxes? 3 + 3 + 3 * 3.
Maybe I'm overlooking something. You seem to have a good grasp of that stuff, maybe you can explain?

I don't know if I remember correctly but with 2 OBB don't you have to check 15 axis? 3 normals of the first box, 3 normals of the second box and all possibly cross products between the normals of the the two boxes? 3 + 3 + 3 * 3.
Maybe I'm overlooking something. You seem to have a good grasp of that stuff, maybe you can explain?

You are right, I overlooked that. Thank you for catching that.

So the other axis of seperation you need to check are the edges. The paper I linked to illistrates it well. The new axes would consist of crossing every every axis in box a with every axis in box b.


bool doesCollide(boxa, boxb){
// create an array of vectors the represent the combined axis of the two boxes
Array<Vector> boxaxislist;

foreach (axisa in boxa.axisList)
{
foreach (axisb in boxb.axisList)
{
boxaxislist.append(axisa.cross(axisb));
}
}

boxaxislist.append(boxa.axisList);
boxaxislist.append(boxb.axisList);
// rest of the doesCollide code....