Jump to content
  • Advertisement

Archived

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

Screndib

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.

If you intended to correct an error in the post then please contact us.

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


Link to post
Share on other sites
Advertisement


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


Link to post
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.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!