Cube on Cube collision detection algorithm?

Question

I'm trying to find the most efficient way to check if 2 arbitrarily sized cubes collide with each other. The sides of the cubes are not necessarily all equal in length (a box is possible). Given these constraints, how could I efficiently check if they collide? (each box has 24 verticies) Thanks

They are axis alligned

Answer 1

Since both boxes are axis-aligned you can just compare their extents:

  return (a.max_x() >= b.min_x() and a.min_x() <= b.max_x())
     and (a.max_y() >= b.min_y() and a.min_y() <= b.max_y())
     and (a.max_z() >= b.min_z() and a.min_z() <= b.max_z())

Answer 2

For a boolean query, use Laurence's answer. It can also be made to work with moving boxes, but then you have to use a binary search to find the intersection point, or the time interval.

Solving the parametric time for intersection on an axis

Another solution if you want movable boxes is to find the parametric time where the intersection happens on each axis separately, with respect to the traveling direction. Let's call the boxes A and B, their extreme points for Min and Max. You only need one direction, because you can subtract A's direction from B's direction and be left with one vector. So you can consider B to be moving and A to be stationary. Let's call the direction D. Solving for t gives:

(for the start of the intersection along D)
Bmax + tEnter*D = Amin
tEnter*D = Amin - Bmax
tEnter = (Amin - Bmax) / D

(for the end of the intersection along D; the back side of A)
Bmin + tLeave*D = Amax
tLeave*D = Amax - Bmin
tLeave = (Amax - Bmin) / D

Do this check on each axis, and if they all overlap, you have an intersection. If the denominator is zero, you have an infinite overlap or no overlap on that axis. If tEnter is greater than 1 or tLeave is less than zero, then the overlap is further away than the direction lengths, or in the wrong direction.

bool IntersectAxis(float min1, float max1, float min2, float max2,
    float diraxis, float& tEnter, float& tLeave)
{
    const float intrEps = 1e-9;

    /* Carefully check for diraxis==0 using an epsilon. */
    if( std::fabs(diraxis) < intrEps ){
        if((min1 >= max2) || (max1 <= min2)){
            /* No movement in the axis, and they don't overlap,
                hence no intersection. */
            return false;
        } else {
            /* Stationary in the axis, with overlap at t=0 to t=1 */
            return true;
        }
    } else {
        float start = (min1 - max2) / diraxis;
        float leave = (max1 - min2) / diraxis;

        /* Swap to make sure our intervals are correct */
        if(start > leave)
            std::swap(start,leave);

        if(start > tEnter)
            tEnter = start;
        if(leave < tLeave)
            tLeave = leave; 
        if(tEnter > tLeave)
            return false;
    }
    return true;
}

bool Intersect(const AABB& b1, const AABB& b2, Vector3 dir, float& tEnter, float&         tLeave)
{
    tEnter = 0.0f;
    tLeave = 1.0f;

    if(IntersectAxis(b1.bmin.x, b1.bmax.x, b2.bmin.x, b2.bmax.x, dir.x, tEnter, tLeave) == false)
        return false;
    else if(IntersectAxis(b1.bmin.y, b1.bmax.y, b2.bmin.y, b2.bmax.y, dir.y, tEnter, tLeave) == false)
        return false;
    else if(IntersectAxis(b1.bmin.z, b1.bmax.z, b2.bmin.z, b2.bmax.z, dir.z, tEnter, tLeave) == false)
        return false;
    else
    return true;
}