Finding intersect of line segment and AABB
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?
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 axisbool 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;}
no problem.
In the link, they actually user a similar method, but a different logic, which can also work.
In the link, they actually user a similar method, but a different logic, which can also work.
// *untested code*// ray-aabb test along one axisbool 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;}
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement