Ray-AABB intersection

This topic is 4836 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Okay, so far, I've got that the ray is = o + td, where o is the origin point of the ray and d is a direction vector, and I'm assuming that t is a scaling factor of some sort. With the AABB box, it has two points amax and amin and that aimin <= aimax where i is x,y and z in a 3d point. Am I right so far? I've got the book "Real-Time Rendering", but I'm not understanding a whole lot from this specific part of the book. Can anyone help me with understanding how to implement finding an intersection between an AABB and a ray?

Share on other sites
first i'm sorry for my lang but i gess u'll understand me.

In ordere to do the intersection between the ray an dthe ABB box you can do the following:
in the box you have 6 face( quad ofcourse ) and the faces are as the following:
the face with the min on x;
the face with the max on x;
the face with the min on y;
the face with the max on y;
the face with the min on z;
the face with the max on z;

first : test if the origin is in the box;
second: for each of the faces above test if the ray may intersect with and you can do that as the folowing:
//for the face of min on x:
if( (origin.x < amin.x) && dir.x > 0 ) //there are probability of intersection.
{
//now the intersection become between ray and quad it's easy ha.
}
else
if()//test the second face
.........
when u have an intersection with any face u 'll not need to continue and test the remaining faces.

Share on other sites
Here is a paper that explains how to do a fast ray-aabb box intersction test.

Lizard

Share on other sites
plucker coordinates might not help his understanding though.

this is what I use,

/*  missed intersection.  --------------------  intervals [tymin, tymax] and [txmin, txmax] do not overlap (here, txmin > tymax)                  |     |                 |     |        *P0      |     |         \       |     |          \tymin |     |   --------*-----+-----+-----------------            \    |     |             \   |     |   -----------*--+-----+-----------------         tymax \ |     |                 \|     |                  *txmin|                  |\    |                  | \   |                  |  \  |                  |   \ |                  |    \|                  |     *txmax                  |     |\                  |     | \                  |     |  *P1   we have  intersection.  ----------------------  intervals [tymin, tymax] and [txmin, txmax] overlap (tymin < txmax and tymax > txmin)           *P0 |      |            \  |      |             \ |      |              \|txmin |               *      |               |\ tymin --------------+-*----+-----------------               |  \   |               |   \ tymax --------------+----*-+-----------------               |     \|               |      *txmax                |      |\                |      | \                |      |  \                 |      |   *P1                |      | in code, you start off with a ray where tfirst = 0.0f, and tlast = |P1 - P0|- first, you test intersection with the two X planes=> will give you [txmin, txmax]=> also, you notice that txmin > tfirst, and txmax < tlast, so then    tfirst = txmin, tlast = txmax- second, you test with the Y planes=> will give you [tymin, tymax]=> here also, (tymin > tfirst), so tfirst = tymin=>            (tymax < tlast),  so tlast  = tymax- finally, (tlast > tfirst). this is consistent. so we have an intersection.in case of no intersection-------------------------- first, you test intersection with the two X planes=> will give you [txmin, txmax]=> also, you notice that txmin > tfirst, and txmax < tlast, so then    tfirst = txmin, tlast = txmax- second, you test with the Y planes=> will give you [tymin, tymax]=> but here, tymin is not > tfirst=>            (tymax < tlast),  so tlast  = tymax- finally, now that we have tfirst = txmin, tlast = tymaxbut, (tfirst > tlast). discrepency, the interseciton is invalid.- bottom line-------------you keep testing intersections with pairs of planes along axes. -> you keep reducing the initial interval [tfirst, tlast] with the small values   for both. -> As soon as the interval becomes invalidated, it means that the ray missed the box and there   is no intersection./**/bool ClipSegment(float min, float max, float a, float b, float d, float& t0, float& t1){	const float threshold = 1.0e-6f;	if (Abs(d) < threshold)	{		if (d > 0.0f)		{			return !(b < min || a > max);		}		else		{			return !(a < min || b > max);		}	}	float u0, u1;	u0 = (min - a) / (d);	u1 = (max - a) / (d);	if (u0 > u1) 	{		Swap(u0, u1);	}	if (u1 < t0 || u0 > t1)	{		return false;	}	t0 = Max(u0, t0);	t1 = Min(u1, t1);	if (t1 < t0)	{		return false;	}	return true; }bool ClipSegment(Vector& A, Vector& B, const Vector& Min, const Vector& Max){	Vector S = A;	Vector D = (B - A);	float t0 = 0.0f, t1 = 1.0f;	if (!ClipSegment(Min.x, Max.x, A.x, B.x, D.x, t0, t1)) 	{		return false;	}		if (!ClipSegment(Min.y, Max.y, A.y, B.y, D.y, t0, t1)) 	{		return false;	}	if (!ClipSegment(Min.z, Max.z, A.z, B.z, D.z, t0, t1)) 	{		return false;	}	A = S + D * t0;	B = S + D * t1;	return true;}

that clips a segment to inside a cube. returns false if ray misses.

Share on other sites
Quote:
 Original post by EndarOkay, so far, I've got that the ray is = o + td, where o is the origin point of the ray and d is a direction vector, and I'm assuming that t is a scaling factor of some sort. With the AABB box, it has two points amax and amin and that aimin <= aimax where i is x,y and z in a 3d point. Am I right so far?

Mostly right. The ray is written in what is known as parameterized form. So you can think of the ray as being the set of points obtained by setting t to all possible values t >= 0.

The important realization, I think, to grokking how the algorithm works is this.

An AABB can be described as the intersection volume of three perpendicular slabs, where a slab is the (infinite) volume between two parallel planes. Thus, a ray intersects an AABB if and only if a point of the ray simultaneously lies inside all three slabs.

What the algorithm does is intersecting the ray against each slab in turn, finding the t values at which the ray enters and exits the slab. The largest t value for entering and the smallest t value for exiting then describes the part of the ray inside the AABB.

If the largest entering value is larger than the smallest exiting value, the ray does not intersect the AABB (as the interval described by the two t values is empty).

I hope that helps you understand the algorithm description better.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 12
• 9
• 12
• 37
• Forum Statistics

• Total Topics
631435
• Total Posts
3000056
×