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

9 replies to this topic

### #1Grain  Members

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

### #2scgames  Members

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

### #30BZEN  Members

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

### #4scgames  Members

2082
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]

### #5Grain  Members

500
Like
0Likes
Like

Posted 14 August 2005 - 05:34 PM

Quote:
 Original post by jykHere'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.

### #6scgames  Members

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

### #7scgames  Members

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

### #8Grain  Members

500
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?

### #9scgames  Members

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

### #10theJ89  Members

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.