Jump to content

  • Log In with Google      Sign In   
  • Create Account

AABB - Line Segment intersection test


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 Grain   Members   -  Reputation: 467

Like
0Likes
Like

Posted 14 August 2005 - 10:04 AM

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.

Sponsor:

#2 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 14 August 2005 - 10:09 AM

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.

#3 0BZEN   Crossbones+   -  Reputation: 2025

Like
0Likes
Like

Posted 14 August 2005 - 12:54 PM

ta-da!!!


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.


#4 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 14 August 2005 - 01:23 PM

Here's the boolean version:


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[i]) < epsilon)
parallel |= 1 << i;
else
{
T es = (D[i] > (T)0.0) ? e[i] : -e[i];
T invDi = (T)1.0 / D[i];

if (!found)
{
t[0] = (d[i] - es) * invDi;
t[1] = (d[i] + es) * invDi;
found = true;
}
else
{
T s = (d[i] - es) * invDi;
if (s > t[0])
t[0] = s;
s = (d[i] + 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[i] - t[0] * D[i]) > e[i] || Math<T>::Fabs(d[i] - t[1] * D[i]) > e[i])
return false;

return true;
}



[Edit: Fixed a couple of things.]

[Edited by - jyk on August 14, 2005 9:23:01 PM]

#5 Grain   Members   -  Reputation: 467

Like
0Likes
Like

Posted 14 August 2005 - 05:34 PM

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.

#6 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 14 August 2005 - 05:58 PM

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.

#7 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 14 August 2005 - 06:27 PM

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.)

#8 Grain   Members   -  Reputation: 467

Like
0Likes
Like

Posted 14 August 2005 - 09:54 PM

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?


#9 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 15 August 2005 - 01:37 AM

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.

#10 theJ89   Members   -  Reputation: 122

Like
0Likes
Like

Posted 15 July 2011 - 09:55 AM

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(axisi))

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




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS