Andrew Woo, who along with John Amanatides developed the raymarching algorithm (DDA) used ubiquitously in raytracers, wrote “Fast Ray-Box Intersection” (alternative source here) which was published in Graphics Gems, 1990, pp. 395-396. Rather than being built specifically for integration through a grid (eg. a voxel volume) as DDA is (see zacharmarz’ answer), this algorithm is specifically suited to worlds that are not evenly subdivided, such as your typical polyhedra world found in most 3D games.
The approach provides support for 3D, and optionally does backface culling. The algorithm is derived from the same principles of integration used in DDAs, so it is very quick. More detail can be found in the original Graphics Gems volume (1990).
Many other approaches specifically for Ray-AABB to be found at realtimerendering.com.
EDIT: An alternative, branchless approach — which would be desirable on both GPU & CPU — may be found here. The actual code, including the max() on the return test, is available here.
What I have been using earlier in my raytracer:
// r.dir is unit direction vector of ray
dirfrac.x = 1.0f / r.dir.x;
dirfrac.y = 1.0f / r.dir.y;
dirfrac.z = 1.0f / r.dir.z;
// lb is the corner of AABB with minimal coordinates - left bottom, rt is maximal corner
// r.org is origin of ray
float t1 = (lb.x - r.org.x)*dirfrac.x;
float t2 = (rt.x - r.org.x)*dirfrac.x;
float t3 = (lb.y - r.org.y)*dirfrac.y;
float t4 = (rt.y - r.org.y)*dirfrac.y;
float t5 = (lb.z - r.org.z)*dirfrac.z;
float t6 = (rt.z - r.org.z)*dirfrac.z;
float tmin = max(max(min(t1, t2), min(t3, t4)), min(t5, t6));
float tmax = min(min(max(t1, t2), max(t3, t4)), max(t5, t6));
// if tmax < 0, ray (line) is intersecting AABB, but the whole AABB is behind us
if (tmax < 0)
{
t = tmax;
return false;
}
// if tmin > tmax, ray doesn't intersect AABB
if (tmin > tmax)
{
t = tmax;
return false;
}
t = tmin;
return true;
If this returns true, it’s intersecting, if it returns false, it’s not intersecting.
If you use the same ray many times, you can precompute dirfrac (only division in whole intersection test). And then it’s really fast. And you have also length of ray until intersection (stored in t).
Nobody described the algorithm here, but the Graphics Gems algorithm is simply:
-
Using your ray’s direction vector, determine which 3 of the 6 candidate planes would be hit first. If your (unnormalized) ray direction vector is (-1, 1, -1), then the 3 planes that are possible to be hit are +x, -y, and +z.
-
Of the 3 candidate planes, do find the t-value for the intersection for each. Accept the plane that gets the largest t value as being the plane that got hit, and check that the hit is within the box. The diagram in the text makes this clear:
My implementation:
bool AABB::intersects( const Ray& ray )
{
// EZ cases: if the ray starts inside the box, or ends inside
// the box, then it definitely hits the box.
// I'm using this code for ray tracing with an octree,
// so I needed rays that start and end within an
// octree node to COUNT as hits.
// You could modify this test to (ray starts inside and ends outside)
// to qualify as a hit if you wanted to NOT count totally internal rays
if( containsIn( ray.startPos ) || containsIn( ray.getEndPoint() ) )
return true ;
// the algorithm says, find 3 t's,
Vector t ;
// LARGEST t is the only one we need to test if it's on the face.
for( int i = 0 ; i < 3 ; i++ )
{
if( ray.direction.e[i] > 0 ) // CULL BACK FACE
t.e[i] = ( min.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
else
t.e[i] = ( max.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
}
int mi = t.maxIndex() ;
if( BetweenIn( t.e[mi], 0, ray.length ) )
{
Vector pt = ray.at( t.e[mi] ) ;
// check it's in the box in other 2 dimensions
int o1 = ( mi + 1 ) % 3 ; // i=0: o1=1, o2=2, i=1: o1=2,o2=0 etc.
int o2 = ( mi + 2 ) % 3 ;
return BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) &&
BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) ;
}
return false ; // the ray did not hit the box.
}