#### Archived

This topic is now archived and is closed to further replies.

# Looking for a quick line-AABB intersection test.

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

## Recommended Posts

I have the top, left, right, and bottom of an axis-aligned box and two points defining end points of a line. I''m looking for a quick way to tell whether or not the line crosses through that box. I don''t need to know where or on which side, etc. the two objects crossed, I just need a simple true/false answer. Thanks for any help

##### Share on other sites

in 2 D

x = minx x = maxx
| |
P1. | |
\ | |
\| |
*tminx |
----------------+*tminy -------+-------------- y = miny
| \ |
| \ |
| \ |
| \ |
| \ |
----------------+------*tmaxy--+-------------- y = maxy
| \ |
| \ |
| \ |
| \ |
| \ |
| \ |
| \|
| *tmaxx
| |\
| | .P2

if you look at intervals along the (P1, P2) line, you''ll see

tminx tmaxx
-------------+--------------------------------------+--------
---------------+--------------------------+------------------
tminy tmaxy

the two intervals intersect, so the line intersects, and the first intersection is at t = tminx

x = minx x = maxx
| |
| |
| |
.P1 | |
\ | |
---*tminy-------+--------------+-------------- y = miny
\ | |
\ | |
\ | |
\ | |
\ | |
---------*tmaxy-+--------------+-------------- y = maxy
\ | |
\ | |
\ | |
\ | |
\ | |
\| |
* tminx |
|\ |
| \ |
.P2

tminx tmaxx
--------------------+-------------------------//---+---

--------+----------------+-----------
tminy tmaxy

here the two intervals don;t overlap. no intersection.

in 3D, I''ve got this algo. it''s "as is".

const float threshold = 0.00001f;

//-----------------------------------------------------------------------------

// See if a ray intersect an axis in the ray range [0.0, 1.0],

// and in the axis range [pmin, pmax].

//-----------------------------------------------------------------------------

inline BOOL RayCubeAxisIntersect(float pos, float dir, float pmin, float pmax, float& tmin, float& tmax)
{
//-----------------------------------------------------------------------------

// Find the span on x axis.

//

// If the ray goes along x axis, it is an extreme case

//-----------------------------------------------------------------------------

if (FABS(dir) < threshold)
{
//-----------------------------------------------------------------------------

// test if ray start is actually in the box range.

//-----------------------------------------------------------------------------

return (pos > pmin && pos < pmax);
}

//-----------------------------------------------------------------------------

// Compute the span on the x axis. Make sure it is sorted.

//-----------------------------------------------------------------------------

float t1 = (pmin - pos) / dir;
float t2 = (pmax - pos) / dir;

//-----------------------------------------------------------------------------

// Make sure span is sorted.

//-----------------------------------------------------------------------------

if (t1 > t2)
SWAPF(t1, t2);

if (t1 > tmax || t2 < tmin)
return FALSE;

if (t1 > tmin)
tmin = t1;

if (t2 < tmax)
tmax = t2;

return TRUE;
}

//-----------------------------------------------------------------------------

// Test if a ray intersects a box.

//

// Pass the ray posiiton and direction.

//

// pass the minimum point and maximum point of the box.

//

// returns if it intersects.

//-----------------------------------------------------------------------------

BOOL RayCubeIntersect(const Vector& Pos, const Vector& Dir, float& Distance,
const Vector& CubePos, const Vector& CubeExtents)
{
float tmax = Distance, tmin = 0.0f;

//-----------------------------------------------------------------------------

// Test range of intersection in the X axis

//-----------------------------------------------------------------------------

if (!RayCubeAxisIntersect(Pos.x, Dir.x, (CubePos.x-CubeExtents.x), (CubePos.x+CubeExtents.x), tmin, tmax))
return FALSE;

//-----------------------------------------------------------------------------

// Test range of intersection in the Y axis

//-----------------------------------------------------------------------------

if (!RayCubeAxisIntersect(Pos.y, Dir.y, (CubePos.y-CubeExtents.y), (CubePos.y+CubeExtents.y), tmin, tmax))
return FALSE;

//-----------------------------------------------------------------------------

// Test range of intersection in the Z axis

//-----------------------------------------------------------------------------

if (!RayCubeAxisIntersect(Pos.z, Dir.z, (CubePos.z-CubeExtents.z), (CubePos.z+CubeExtents.z), tmin, tmax))
return FALSE;

if (tmax < tmin)
return FALSE;

return TRUE;
}

##### Share on other sites
the parameter float& Distance can be set to tmin when an intersection is found to clip the ray to the intersection point, and call further RayBoxIntersect() routines.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633703
• Total Posts
3013455
×