Sign in to follow this  
OrangyTang

Finding intersect of line segment and AABB

Recommended Posts

OrangyTang    1298
I have a line segment and an axis-aligned rectangle and I'd like to find whether they intersect and if they do the exact intersection point. Can anyone suggest a general method for doing this? The most obvious method would be to convert each edge into another line segment and test for intersections between all of these and the original segment, but I'm sure there's a better way (perhaps one that takes advantage of the rectangle being axis-aligned) that I can't think of right now. Anyone any pointers?

Share this post


Link to post
Share on other sites
oliii    2196
Yes there are better ways. I like the dimension reduction one. Combining it and the SAT, you can do swept SAT.



// *untested code*
// ray-aabb test along one axis
bool rayAABBIntersect1D(float start, float dir, float min, float max, float& enter, float& exit)
{
// ray parallel to direction
if(fabs(dir) < 1.0E-8)
return (start >= min && start <= max);

// intersection params
float t0, t1;
t0 = (min - start) / dir;
t1 = (max - start) / dir;

// sort intersections
if(t0 > t1) swap(t0, t1);

// check if intervals are disjoint
if(t0 > exit || t1 < enter)
return false;

// reduce interval
if(t0 > enter) enter = t0;
if(t1 < exit) exit = t1;
return true;
}

bool rayAABBIntersect(Vector start, Vector dir, Vector min, Vector max, Vector& penter, Vector& pexit)
{
float enter = 0.0f, exit = 1.0f;

if(!rayAABBIntersect1D(start.x, dir.x, min.x, max.x, enter, exit))
return false;

if(!rayAABBIntersect1D(start.y, dir.y, min.y, max.y, enter, exit))
return false;

if(!rayAABBIntersect1D(start.z, dir.z, min.z, max.z, enter, exit))
return false;

penter = start + dir * enter;
pexit = start + dir * exit;
return true;
}


Share this post


Link to post
Share on other sites
oliii    2196
no problem.

In the link, they actually user a similar method, but a different logic, which can also work.



// *untested code*
// ray-aabb test along one axis
bool rayAABBIntersect1D(float start, float dir, float length, float min, float max, float& enter, float& exit)
{
// ray parallel to direction
if(fabs(dir) < 1.0E-8)
return (start >= min && start <= max);

// intersection params
float t0, t1;
t0 = (min - start) / dir;
t1 = (max - start) / dir;

// sort intersections
if(t0 > t1) swap(t0, t1);

// reduce interval
if(t0 > enter) enter = t0;
if(t1 < exit) exit = t1;

// ray misses the box
if(exit < enter)
return false;

// intersections outside ray boundaries
if(exit < 0.0f || enter > length)
return false;

return true;
}

bool rayAABBIntersect(Vector start, Vector dir, float length, Vector min, Vector max, Vector& penter, Vector& pexit)
{
float enter = -INFINITY, exit = INFINITY;

if(!rayAABBIntersect1D(start.x, dir.x, length, min.x, max.x, enter, exit))
return false;

if(!rayAABBIntersect1D(start.y, dir.y, length, min.y, max.y, enter, exit))
return false;

if(!rayAABBIntersect1D(start.z, dir.z, length, min.z, max.z, enter, exit))
return false;

penter = start + dir * enter;
pexit = start + dir * exit;
return true;
}

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