# AABB - Line Segment intersection test

This topic is 2742 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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) < 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]

##### Share on other sites
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.

##### Share on other sites
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)

Distance: abs(segCenteri)

2. Cross products (axisi = segDirectionXboxAxisi)

Segment radius: 0 (cross product always perpendicular to segment direction)
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.

##### Share on other sites
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.)

##### Share on other sites
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?

##### Share on other sites
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.

##### Share on other sites
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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 13
• 9
• 15
• 14
• 46
• ### Forum Statistics

• Total Topics
634058
• Total Posts
3015288
×