3D Programming - Weekly : Line Box Intersection

In many 3D programs, objects have bounding boxes. A bounding box is a box of sufficient size that the entire object is inside it. Here I'll just assume the object is a static mesh, but it could be anything. A bounding box can be used to speed up tests, mainly collision detection related. Here I'll cover determining if a line intersects with the bounding box. Only if the line does interesect will you need to perform the more expensive test against the mesh inside the box. I use lines in collision dectection to represent shot particles, and also for line of sight tests.

The box in this article is Axis-Aligned and so can be defined by only two 3D points:
B1 - the smallest values of X, Y, Z
B2 - the largest values of X, Y, Z

There's a possible issue here. Let's say your mesh has been rotated in world-space. The bounding box you've computed will now be invalid. If you try to fix this by rotating the bounding box along with the mesh, it will no longer be axis-aligned. What I do is just compute and store the object-space bounding box for each object when it's created. I also store the object's current transformation( rotation & translation. ) Now instead of rotating the mesh when checking the line against mesh, we do the inverse transformation on the line, transforming the line into object-space.

We're ready to check the line against the box now. The line is defined by two points, L1 and L2. The first thing to do is to see if the line is completely on one side of the box to see if we can return false quickly. If it isn't we'll have to do something more complicated. Here I check it against each face of the box by finding the intersection point with the plane the face defines, then check to see if that point is within the edges of the face itself. This is a good place for some actual code. The 2 inline functions are helpers for the CheckLineBox function.
(Note: This isn't the most sophisticated way to do it. If we don't need the intersection point, and want code that is often faster, the separating axis test is a good alternative, see the code of IsLineInBox in the Bounding Boxes article.)

C++ Code

int inline GetIntersection( float fDst1, float fDst2, CVec3 P1, CVec3 P2, CVec3 &Hit) {
if ( (fDst1 * fDst2) >= 0.0f) return 0;
if ( fDst1 == fDst2) return 0; 
Hit = P1 + (P2-P1) * ( -fDst1/(fDst2-fDst1) );
return 1;
}

int inline InBox( CVec3 Hit, CVec3 B1, CVec3 B2, const int Axis) {
if ( Axis==1 && Hit.z > B1.z && Hit.z < B2.z && Hit.y > B1.y && Hit.y < B2.y) return 1;
if ( Axis==2 && Hit.z > B1.z && Hit.z < B2.z && Hit.x > B1.x && Hit.x < B2.x) return 1;
if ( Axis==3 && Hit.x > B1.x && Hit.x < B2.x && Hit.y > B1.y && Hit.y < B2.y) return 1;
return 0;
}

// returns true if line (L1, L2) intersects with the box (B1, B2)
// returns intersection point in Hit
int CheckLineBox( CVec3 B1, CVec3 B2, CVec3 L1, CVec3 L2, CVec3 &Hit)
{
if (L2.x < B1.x && L1.x < B1.x) return false;
if (L2.x > B2.x && L1.x > B2.x) return false;
if (L2.y < B1.y && L1.y < B1.y) return false;
if (L2.y > B2.y && L1.y > B2.y) return false;
if (L2.z < B1.z && L1.z < B1.z) return false;
if (L2.z > B2.z && L1.z > B2.z) return false;
if (L1.x > B1.x && L1.x < B2.x &&
    L1.y > B1.y && L1.y < B2.y &&
    L1.z > B1.z && L1.z < B2.z) 
    {Hit = L1; 
    return true;}
if ( (GetIntersection( L1.x-B1.x, L2.x-B1.x, L1, L2, Hit) && InBox( Hit, B1, B2, 1 ))
  || (GetIntersection( L1.y-B1.y, L2.y-B1.y, L1, L2, Hit) && InBox( Hit, B1, B2, 2 )) 
  || (GetIntersection( L1.z-B1.z, L2.z-B1.z, L1, L2, Hit) && InBox( Hit, B1, B2, 3 )) 
  || (GetIntersection( L1.x-B2.x, L2.x-B2.x, L1, L2, Hit) && InBox( Hit, B1, B2, 1 )) 
  || (GetIntersection( L1.y-B2.y, L2.y-B2.y, L1, L2, Hit) && InBox( Hit, B1, B2, 2 )) 
  || (GetIntersection( L1.z-B2.z, L2.z-B2.z, L1, L2, Hit) && InBox( Hit, B1, B2, 3 )))
	return true;

return false;
}