Skip to main content
GameDev.net gamedev.net
🔒 Locked

ray-aabb-intersection (2D)

Started by ehmdjii Jan 23, 2007 at 12:12 PM 6 replies 7.5k views
Original Post
ehmdjii
ehmdjii
hello, i am looking for an algorithm that does exact ray box intersection. all the algorithms i found through google only return true or false, but i need the exact intersection point on the edge of the box. thanks!
Dunge
Dunge
http://www.realtimerendering.com/int/

Should be at least one in there doing that?
xissburg
xissburg
do ray-plane intersection test for each side of the box. Ray-plane intersection algorithm at SoftSurfer.

Hope this helps
.
Zakwayda
Zakwayda
Here's some code:

template <class T> bool IntersectLineAABB(    const Vector3<T>& O, // Line origin    const Vector3<T>& D, // Line direction (unit length)    const Vector3<T>& C, // AABB center    const Vector3<T>& e, // AABB extents    T t[],               // Parametric points of intersection on output    T epsilon)           // Threshold for epsilon test{    int parallel = 0;    bool found = false;    Vector3<T> d = C - O;    for (int i = 0; i < 3; ++i)    {        if (Math<T>::Fabs(D) < epsilon)            parallel |= 1 << i;        else        {            T es = (D > (T)0.0) ? e : -e;            T invDi = (T)1.0 / D;            if (!found)            {                t[0] = (d - es) * invDi;                t[1] = (d + es) * invDi;                found = true;            }            else            {                T s = (d - es) * invDi;                if (s > t[0])                    t[0] = s;                s = (d + es) * invDi;                if (s < t[1])                    t[1] = s;                if (t[0] > t[1])                    return false;            }        }    }        if (parallel)        for (int i = 0; i < 3; ++i)            if (parallel & (1 << i))                if (Math<T>::Fabs(d - t[0] * D) > e || Math<T>::Fabs(d - t[1] * D) > e)                    return false;    return true;}

This is old code (I'd do it differently now) but it should work. The algorithm is standard and should be clear from reading the source. Basically, you clip the line to each of the three 'slabs' formed by pairs of planes coincident with the box faces. If the line is clipped completely away there's no intersection, else the parametric points of intersection are returned.
ehmdjii
ehmdjii
dunge, thanks but i couldnt find one there.

xissburg, thanks but a plane is not limited, so the ray will probably always intersect with the planes, except if they are paralell.

jyk, thanks that should work, but unfortunately i am bad with math. in what format are those parametric points? or what are these values parameters for?
Zakwayda
Zakwayda
Quote:
Original post by ehmdjii
jyk, thanks that should work, but unfortunately i am bad with math. in what format are those parametric points? or what are these values parameters for?
Any point on the line can be represented as:
P = O + t * D;
On output, t[] holds the parametric values corresponding to the points where the line intersects the AABB.

Here's how you might use the function:
// Assume that the ray and box already exist...float t[2];if (IntersectLineAABB(    ray.origin,    ray.direction,    box.center,    box.extents,    t,    0.001f)){    Vector3f intersection_point_1 = ray.origin + t[0] * ray.direction;    Vector3f intersection_point_2 = ray.origin + t[1] * ray.direction;    // ...}
If you're working with rays rather than lines, you'll want to reject intersections for which t < 0.

Let me know if you have any other questions.
xissburg
xissburg
Quote:
xissburg, thanks but a plane is not limited, so the ray will probably always intersect with the planes, except if they are paralell.


But I'm talking about non-infinite planes(rectangles) ;). after get the intersection point(if it exists) check if it is inside the rectangle. You can use barycentric coordinates for this.
.
Zakwayda
Zakwayda
Quote:
Original post by xissburg
Quote:
xissburg, thanks but a plane is not limited, so the ray will probably always intersect with the planes, except if they are paralell.


But I'm talking about non-infinite planes(rectangles) ;). after get the intersection point(if it exists) check if it is inside the rectangle. You can use barycentric coordinates for this.
As far as I know there's no such thing as a 'non-infinite plane', so I can see how the OP might have been confused :)

However, as it turns out, intersecting the ray with the box planes is actually the (or at least 'a') solution to the problem. Checking for point containment isn't necessary (and in any case there's no need for barycentric coordinates, as the faces are axis-aligned rectangles); as described earlier, by clipping the line to the planes whose intersecting halfspaces form the AABB, you effectively find the intersection points without any containment tests.

Just to reiterate, the code I posted is not the best, most elegant, or most efficient implementation possible (I would do it differently were I to rewrite the function now), but it does illustrate the algorithm in question.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.