AABB Ray Intersection

visualizing the classic Ray AABB intersection

AABBs intro

AABBs (Axis Aligned Bounding Box) are extremely useful and common in games because of the restriction that they are, as the name implies axis aligned, meaning they will not rotate.

Because of this restriction overlap calculations between AABBs and rays are extremely fast.

Usually an AABB surrounds more complex geometry, and/or are comprised of multiple sub AABBs.

AABB Ray Intersection

Why? There are already tons of explanations of this online

Yes, this is a very covered topic all over the internet that explains HOW to check for such an intersection (linked below in additional resources) but not really WHY.

And I found that this was because a lot of resources online combine either X & Y in their explanations, or all axes at once which muddied up my understanding.

Clarity through 1D

It wasn't until I started looking at the problem solely in 1D and dealing only with a single axis that everything finally clicked, so maybe it helps you too.

Projection on a single dimension

The objective is to find the point on the line where we intersect with this dimension while staying locked to the AABB's dimention

Here if we only take (for ex) the X axis for the given AABB you can see there the line intersects with that dimension at the box's min X and max X

Here is an example in UE that helps visualize it.

The red dots represent the min and max intersection points for the X axis (only handling 1 dimension).

Notice they stay within the AABBs X dimension bounds even if the line isn't intersection with the actual AABB (which is fine, we need all 3 dimension tests to determine actual intersection, for now just worry about this 1 dimension).

Finding t

We will have two values of t, one for the min and one for the max.

Those points are determined by scaling the ray by some fraction (t) based on the min or max bounds. We want to know how much of the ray is needed to reach the min and max of the bounds

Remember we're only in a single dimension right now, so we are dealing with scalars only.

We can find this fraction (t) of the ray by projecting the AABB's min and max onto the ray

Ray scaled by tMin
Ray scaled by tMax
X dimension (the red dots will stay clipped to the bounds of the AABBs X min and max on the ray)

Account for direction

Additionally we need to account for the direction of the ray since depending on which direction along the dimension it's travelling (from start to end) will determine which of the two intersections is our first and actual intersection

FBox box = AABB->GetComponentsBoundingBox();
FVector rayStart = RayStart->GetActorLocation();
FVector rayEnd = RayEnd->GetActorLocation();

float txMin = (box.Min.X - rayStart.X) / (rayEnd.X - rayStart.X);
float txMax = (box.Max.X - rayStart.X) / (rayEnd.X - rayStart.X);

if (txMin > txMax)
{
	float tTemp = txMin;
	txMin = txMax;
	txMax = tTemp;
}
Green dot indicates the CLOSEST intersection based off the rays direction (red arrow)

Repeat 1D projection for all dimensions

Now we just do the exact same projection for each dimension (x, y, z)

// ... X Axis

// Y Axis
float tyMin = (box.Min.Y - RayStart->GetActorLocation().Y) / (RayEnd->GetActorLocation().Y - RayStart->GetActorLocation().Y);
float tyMax = (box.Max.Y - RayStart->GetActorLocation().Y) / (RayEnd->GetActorLocation().Y - RayStart->GetActorLocation().Y);
if (tyMin > tyMax)
{
	float tTemp = tyMin;
	tyMin = tyMax;
	tyMax = tTemp;
}

FVector tyMinPos = rayStart + (Ray * tyMin);
FVector tyMaxPos = rayStart + (Ray * tyMax);

// Z Axis
float tzMin = (box.Min.Z - RayStart->GetActorLocation().Z) / (RayEnd->GetActorLocation().Z - RayStart->GetActorLocation().Z);
float tzMax = (box.Max.Z - RayStart->GetActorLocation().Z) / (RayEnd->GetActorLocation().Z - RayStart->GetActorLocation().Z);
if (tzMin > tzMax)
{
	float tTemp = tzMin;
	tzMin = tzMax;
	tzMax = tTemp;
}

FVector tzMinPos = rayStart + (Ray * tzMin);
FVector tzMaxPos = rayStart + (Ray * tzMax);
intersection points colour coded (red = x, green = y, blue = z)
Y dimension (the green dots will stay clipped to the bounds of the AABBs Y min and max on the ray)
Z dimension (the blue dots will stay clipped to the bounds of the AABBs Z min and max on the ray)

Great, now we have the intersections along the min and max for all 3 dimensions, but as you have seen they extend infinitely along that dimension...which means not all intersections really intersect with out AABB.

We need to figure out which of these intersections are actually within valid ranges of the AABB

Filter intersections by only those within valid AABB bounds

We've found each dimensions' min and max intersections by finding a min and max fraction to scale the ray by (txMin txMax, tyMin tyMax, tzMin txMax) but only 2 of these will be the actual intersection points depending on which plane the ray intersects with on the AABB

Largest Min & Smallest Max

Therefor, to find the final tMin and tMax we need to find the LARGEST min and the SMALLEST max

here y0 is the largest min, and t1x is the largest max
(left) we can see the LARGEST min is x. (right) we can see the SMALLEST max is z
therefor our final tMin is txMin and our final tMax is tzMax

Check for missing intersections

Additionally we can early out if we detect a failed invariant of "min < max" and "max > min".

If we find that a min is ever exceeding another dimensions max then there is no intersection on that plane

xMin > yMax: means the ray is too far to the right

yMin > xMax: means the ray is too far to the left

if either of these are true then the ray is not colliding with the AABB on the XY plane

Likewise we need to check the Z dimension which we save for checking after we find our largest min and smallest max 

// check missing intersection on XY plane
if (txMin > tyMax || tyMin > txMax) return;

// now find the largest min and the smallest max. 
// LARGEST min is the fraction furthest from ray start. The SMALLEST min would actually not be colliding with the plane otherwise
// SMALLEST max is the fraction closes to ray start. The LARGEST max would actually not be colliding with the plane otherwise
float tMin = FMath::Max3(txMin, tyMin, tzMin);
float tMax = FMath::Min3(txMax, tyMax, tzMax);

// check missing intersection on the Z dimension
if (tMin > tzMax || tzMin > tMax) return;

FVector tMinPos = rayStart + (Ray * tMin); // tMinPos is the closest intersection
FVector tMaxPos = rayStart + (Ray * tMax);

Here is a visualization of the X and Y dimensions

X dimension (ray too far right) the red xMIN will be above the green yMAX (ray too far left) the green yMIN will be above the red xMAX
Y dimension another visualization

Example combined

bool ASomeClass::TryGetAABBRayIntersection(FBox box, FVector rayStart, FVector rayEnd, FVector outIntersectionPoint)
{
	// X Axis
	float txMin = (box.Min.X - rayStart.X) / (rayEnd.X - rayStart.X);
	float txMax = (box.Max.X - rayStart.X) / (rayEnd.X - rayStart.X);
	if (txMin > txMax)
	{
		float tTemp = txMin;
		txMin = txMax;
		txMax = tTemp;
	}

	FVector txMinPos = rayStart + (Ray * txMin);
	FVector txMaxPos = rayStart + (Ray * txMax);

	// Y Axis
	float tyMin = (box.Min.Y - rayStart.Y) / (rayEnd.Y - rayStart.Y);
	float tyMax = (box.Max.Y - rayStart.Y) / (rayEnd.Y - rayStart.Y);
	if (tyMin > tyMax)
	{
		float tTemp = tyMin;
		tyMin = tyMax;
		tyMax = tTemp;
	}

	FVector tyMinPos = rayStart + (Ray * tyMin);
	FVector tyMaxPos = rayStart + (Ray * tyMax);

	// Z Axis
	float tzMin = (box.Min.Z - rayStart.Z) / (rayEnd.Z - rayStart.Z);
	float tzMax = (box.Max.Z - rayStart.Z) / (rayEnd.Z - rayStart.Z);
	if (tzMin > tzMax)
	{
		float tTemp = tzMin;
		tzMin = tzMax;
		tzMax = tTemp;
	}

	FVector tzMinPos = rayStart + (Ray * tzMin);
	FVector tzMaxPos = rayStart + (Ray * tzMax);

	// Bounds checks
	if (txMin > tyMax || tyMin > txMax) return;

	float tMin = FMath::Max3(txMin, tyMin, tzMin);
	float tMax = FMath::Min3(txMax, tyMax, tzMax);
	
	if (tMin > tzMax || tzMin > tMax) return;

	FVector tMinPos = rayStart + (Ray * tMin);
	// only if desired
	//FVector tMaxPos = rayStart + (Ray * tMax);

	outIntersectionPoint = tMinPos;
	return true;
green intersection is the FIRST intersection from the ray direction

Optimization

You probably noticed there are a lot of divisions, and similar code which isn't great for performance.

There are a number of ways to optimize this which i'll briefly mention, otherwise the minimal ray tracer doc below has them in greater detail.

  • test for a miss on XY plane early before doing Z

  • instead of dividing by the ray length each time, instead multiply by the ray length inverse

    • cache the ray length inverse outside of AABB checks so each doesn't have to do it

  • instead of swapping the max and min each time we can use the ray length direction to tell which direction the ray is going

    • removing the need for a swap operation

Supplemental Resources

Some do a better job of explaining certain parts than others. Honestly I consumed these all and more before I fully understood it so just posting here in case any of these help more

LogoA Minimal Ray-Tracer: Rendering Simple Shapes (Sphere, Cube, Disk, Plane, etc.)
good at explaining the code side, but light on math visualization
excellent at explaining the math, but light on the code representation
someone's interpretation of AABB ray intersection based off the above two resources which I found helpful
PreviousMathNextVector Reflection

Last updated