• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Grain

AABB - Line Segment intersection test

9 posts in this topic

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

Share this post


Link to post
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.
0

Share this post


Link to post
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.
0

Share this post


Link to post
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[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]
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
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)

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

Share this post


Link to post
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.)
0

Share this post


Link to post
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?
0

Share this post


Link to post
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.
0

Share this post


Link to post
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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0