Sign in to follow this  
Endar

Ray-AABB intersection

Recommended Posts

Endar    668
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 this post


Link to post
Share on other sites
DoomAngel    132
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 this post


Link to post
Share on other sites
oliii    2196
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 = tymax
but, (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 this post


Link to post
Share on other sites
Quote:
Original post by Endar
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?


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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this