AABB - Line Segment intersection test
Author
How would I test for this. All I need is a simple Boolean test.
I figure I can test if one or both points are inside the box. and I can test if both points of the line are completely on one side of the box in any one dimension. But I don’t know how to handle the third case where points are on either side or across corners?
I am defining my AABB using two vectors min and max.
For segment/AABB boolean only, it's hard to beat the separating axis test. If you can't find code or references for it, I can post some code for you.
ta-da!!!
as found here.
static bool RaySlabIntersect(float slabmin, float slabmax, float raystart, float rayend, float& tbenter, float& tbexit){ float raydir = rayend - raystart; // ray parallel to the slab if (fabs(raydir) < 1.0E-9f) { // ray parallel to the slab, but ray not inside the slab planes if(raystart < slabmin || raystart > slabmax) { return false; } // ray parallel to the slab, but ray inside the slab planes else { return true; } } // slab's enter and exit parameters float tsenter = (slabmin - raystart) / raydir; float tsexit = (slabmax - raystart) / raydir; // order the enter / exit values. if(tsenter > tsexit) { swapf(tsenter, tsexit); } // make sure the slab interval and the current box intersection interval overlap if (tbenter > tsexit || tsenter > tbexit) { // nope. Ray missed the box. return false; } // yep, the slab and current intersection interval overlap else { // update the intersection interval tbenter = max(tbenter, tsenter); tbexit = min(tbexit, tsexit); return true; }}static bool SegmentAABBoxIntersect(const CAABBox1& Box, const CSegment1& Seg, float &tinter){ // initialise to the segment's boundaries. float tenter = 0.0f, texit = 1.0f; // test X slab if (!RaySlabIntersect(Box.Min.x, Box.Max.x, Seg.Start.x, Seg.End.x, tenter, texit)) { return false; } // test Y slab if (!RaySlabIntersect(Box.Min.y, Box.Max.y, Seg.Start.y, Seg.End.y, tenter, texit)) { return false; } // test Z slab if (!RaySlabIntersect(Box.Min.z, Box.Max.z, Seg.Start.z, Seg.End.z, tenter, texit)) { return false; } // all intersections in the green. Return the first time of intersection, tenter. tinter = tenter; return true;}as found here.
Here's the boolean version:
And a version that returns points of intersection (just reject t's outside [0,1] for a segment):
[Edit: Fixed a couple of things.]
[Edited by - jyk on August 14, 2005 9:23:01 PM]
bool Intersection::Intersect(const Vector3& p1, const Vector3& p2, const Vector3& min, const Vector3& max){ Vector3 d = (p2 - p1) * 0.5f; Vector3 e = (max - min) * 0.5f; Vector3 c = p1 + d - (min + max) * 0.5f; Vector3 ad = d.Absolute(); // Returns same vector with all components positive if (fabsf(c[0]) > e[0] + ad[0]) return false; if (fabsf(c[1]) > e[1] + ad[1]) return false; if (fabsf(c[2]) > e[2] + ad[2]) return false; if (fabsf(d[1] * c[2] - d[2] * c[1]) > e[1] * ad[2] + e[2] * ad[1] + EPSILON) return false; if (fabsf(d[2] * c[0] - d[0] * c[2]) > e[2] * ad[0] + e[0] * ad[2] + EPSILON) return false; if (fabsf(d[0] * c[1] - d[1] * c[0]) > e[0] * ad[1] + e[1] * ad[0] + EPSILON) return false; return true;}And a version that returns points of intersection (just reject t's outside [0,1] for a segment):
template <class T> bool IntersectLineAABB( const Vector3<T>& O, const Vector3<T>& D, const Vector3<T>& min, const Vector3<T>& max, T t[], T epsilon){ Vector3<T> C = (min + max) * (T)0.5; Vector3<T> e = (max - min) * (T)0.5; 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;}[Edit: Fixed a couple of things.]
[Edited by - jyk on August 14, 2005 9:23:01 PM]
Author
Quote:Original post by jyk
Here's the boolean version:
Thanks. But could you explain what your doing in that Boolean test. I don’t just want a code solution that works; I want to understand the concept as well.
Quote:Thanks. But could you explain what your doing in that Boolean test. I don’t just want a code solution that works; I want to understand the concept as well.Sure.
The algorithm is an application of the separating axis theorem. I won't bother explaining the SAT, as it's well documented elsewhere. To learn about SAT, I would start here. Also try this (free membership required), and maybe this and this.
Once you understand the SAT, the following will make sense. The first step is to translate the problem so that the AABB is centered at the origin. The SAT tells us that for a line segment and a box there are six potential separating axes:
1. The box axes
2. The cross products of the segment direction vector and the box axes
For an AABB, the box axes are the cardinal axes, x, y and z.
For each axis, we test to see if the projected distance from the box center to the segment center is greater than the sum of the objects' projected radii. If so, the axis is a separating axis and we're done. Here's an overview of the tests.
1. Box axis i (0 <= i < 3)
Segment radius: abs(segDirectioni)
Box radius: boxExtentsi
Distance: abs(segCenteri)
2. Cross products (axisi = segDirectionXboxAxisi)
Segment radius: 0 (cross product always perpendicular to segment direction)
Box radius: boxExtents.Dot(abs(axisi))
Distance: abs(segCenter.Dot(axisi))
Since the box axis components are all 1's and 0's, a lot of the operations drop out and we're left with the code I posted. The epsilon is to deal with degenerate cross products, which can occur if the segment is nearly parallel to a box axis.
Well, now that I try to explain it, I guess it's not that intuitive. But once you become familiar with the SAT (if you're not already), it will make sense.
Just to add further confusion, the problem can also be thought of in terms of testing the origin for inclusion in the CSO of the AABB and segment. The CSO has six faces whose normals are the box axes, and six faces whose normals are the cross products of the segment direction vector and the box axes. Culling the origin against the planes of these faces is equivalent to the six separating axis tests, and if you work through it you come up with exactly the same code.
(Disclaimer: I'm pretty sure about the above, but I haven't worked through it formally.)
(Disclaimer: I'm pretty sure about the above, but I haven't worked through it formally.)
Author
I'm not seeing where you do the cross product? Has that been factored out some how? And what is the significance of this point? Vector3 c = p1 + d - (min + max) * 0.5f;
Also could this be easily adapted to an OBB if you transform the Segment into the OBB's local coordinate space then treat it as an AABB?
Also could this be easily adapted to an OBB if you transform the Segment into the OBB's local coordinate space then treat it as an AABB?
Quote:I'm not seeing where you do the cross product? Has that been factored out some how?Yeah. Quoting from my earlier post:
Quote:Since the box axis components are all 1's and 0's, a lot of the operations drop out and we're left with the code I posted.You could write the function using actual cross and dot products. But once you remove all the redundant multiplications by 1 and 0, you end up with the posted code.
Quote:And what is the significance of this point? Vector3 c = p1 + d - (min + max) * 0.5f;d is half of the segment direction vector, so p1 + d is the segment center. (min + max) * 0.5 is the AABB center. So this expression is basically c = segCenter-boxCenter, which effectively translates the problem so that the box is centered at the origin.
Quote:Also could this be easily adapted to an OBB if you transform the Segment into the OBB's local coordinate space then treat it as an AABB?Yes, you can transform the segment into local OBB space and do an AABB test, or you can just do the SAT test in place using the OBB axes. Either way it comes down to the same thing, but with the former method you can make use of the segment/AABB function you already have.
'Hope that helps.
I stumbled upon this ancient thread the other day looking for a solution to the same problem, and I've been reading through it and all the related materials that jyk had posted. It's been a great amount of help to me so far, but I'm having trouble understanding a few things.
Looking on Wikipedia's page for the Seperating Axis Theorem, it mentions that this is an intersection test for convex polygons, but doesn't that imply that the two shapes must contain at least 3 vertices each? A line segment would only contain two vertices; is the line segment being treated like a collapsed triangle?
Second, for the cross products I noticed you posted:
boxExtents.Dot(abs(axis[sub]i[/sub]))
I understand that (for the purposes of finding the box "radius") you are making the axis vector's components all positive, but wouldn't this result in an axis pointed in a different direction in some cases? I figured that you would have to change the sign of the x/y/z/ values of the box extents vector depending on what octant the axis vector was located in to get the "radius", but by making the axis vector all positive, and keeping the box extents vector constant, you're acheiving the same result with less work?
Third, if this test was being performed in 2D (i.e. a 2D AABB and a 2D line segment) wouldn't you have to test the axis perpendicular to the line segment? Why does this not have to be done in 3D? Do the cross-products take the place of this test (since they're all perpendicular to the line segment)?
Fourth, can you give an example of a line segment and AABB that only the cross product tests could detect a non-collision on?
Thanks,
theJ89
PS: jyk, if you're still around, you might want to change the metanet tutorial link: http://www.metanetsoftware.com/technique/tutorialA.html
Looking on Wikipedia's page for the Seperating Axis Theorem, it mentions that this is an intersection test for convex polygons, but doesn't that imply that the two shapes must contain at least 3 vertices each? A line segment would only contain two vertices; is the line segment being treated like a collapsed triangle?
Second, for the cross products I noticed you posted:
boxExtents.Dot(abs(axis[sub]i[/sub]))
I understand that (for the purposes of finding the box "radius") you are making the axis vector's components all positive, but wouldn't this result in an axis pointed in a different direction in some cases? I figured that you would have to change the sign of the x/y/z/ values of the box extents vector depending on what octant the axis vector was located in to get the "radius", but by making the axis vector all positive, and keeping the box extents vector constant, you're acheiving the same result with less work?
Third, if this test was being performed in 2D (i.e. a 2D AABB and a 2D line segment) wouldn't you have to test the axis perpendicular to the line segment? Why does this not have to be done in 3D? Do the cross-products take the place of this test (since they're all perpendicular to the line segment)?
Fourth, can you give an example of a line segment and AABB that only the cross product tests could detect a non-collision on?
Thanks,
theJ89
PS: jyk, if you're still around, you might want to change the metanet tutorial link: http://www.metanetsoftware.com/technique/tutorialA.html
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
