Sign in to follow this  
helix

Ray / AABounding Box Collision

Recommended Posts

I don't know why I'm having trouble figuring this out. I've written this collision routine in the past (lost it in a hard drive crash :( ). What's the algorithm for this? Source code, pseudocode, or a description will be fine. Thanks!

Share this post


Link to post
Share on other sites
easy peasy


void AxisIntersect(float min, float max, float p, float d, float& tfirst, float& tlast)
{
if (fabs(d) > 1.0E-8f)
{
float t0 = (min - p) / d;
float t1 = (max - p) / d;
if (t0 > t1) swap(t0, t1);
if (t0 > tfirst) tfirst = t0;
if (t1 < tlast) tlast = t1;
if (tmast < tfirst) return false;
retrun true;
}
else
{
return (p > min) && (p < max);
}
}

bool BoxRayIntersect(Vector Min, Vector Max, Vector P, Vector D, float maxt)
{
float mint = 0;

if (!AxisIntersect(Min.x, Max.x, P.x, D.x, mint, maxt))
return false;
if (!AxisIntersect(Min.y, Max.y, P.y, D.y, mint, maxt))
return false;
if (!AxisIntersect(Min.z, Max.z, P.z, D.z, mint, maxt))
return false;

return true;
}



this is code from the top of my head. I believe it is correct, but I've been drinking a bit...

you can also add extra info, like the normal if intersection at point of intersection, ect...

Share this post


Link to post
Share on other sites
The point of intersection would be nice but only for completeness. The bare minimum is to just return a boolean.

oliii, that function doesn't appear to work for me. I don't really understand what you are doing so could you explain it a little bit?

Share this post


Link to post
Share on other sites
picture worth a 1000 words


/*

missed intersection.
--------------------
intervals [tymin, tymax] and [txmin, txmax] do not overlap (here, txmin > tymax)


| |
| |
*P0 | |
\ | |
\tymin | |
--------*-----+-----+-----------------
\ | |
\ | |
-----------*--+-----+-----------------
tymax \ | |
\| |
*txmin|
|\ |
| \ |
| \ |
| \ |
| \|
| *txmax
| |\
| | \
| | *P1


we have intersection.
----------------------
intervals [tymin, tymax] and [txmin, txmax] overlap (tymin < txmax and tymax > txmin)

*P0 | |
\ | |
\ | |
\|txmin |
* |
|\ tymin
--------------+-*----+-----------------
| \ |
| \ tymax
--------------+----*-+-----------------
| \|
| *txmax
| |\
| | \
| | \
| | *P1
| |


in code, you start off with a ray where tfirst = 0.0f, and tlast = |P1 - P0|
- first, you test intersection with the two X planes
=> will give you [txmin, txmax]
=> also, you notice that txmin > tfirst, and txmax < tlast, so then
tfirst = txmin, tlast = txmax
- second, you test with the Y planes
=> will give you [tymin, tymax]
=> here also, (tymin > tfirst), so tfirst = tymin
=> (tymax < tlast), so tlast = tymax

- finally, (tlast > tfirst). this is consistent. so we have an intersection.


in case of no intersection
-------------------------
- first, you test intersection with the two X planes
=> will give you [txmin, txmax]
=> also, you notice that txmin > tfirst, and txmax < tlast, so then
tfirst = txmin, tlast = txmax
- second, you test with the Y planes
=> will give you [tymin, tymax]
=> but here, tymin is not > tfirst
=> (tymax < tlast), so tlast = tymax
- finally, now that we have tfirst = txmin, tlast = tymax
but, (tfirst > tlast). discrepency, the interseciton is invalid.


- bottom line
-------------
you keep testing intersections with pairs of planes along axes.
-> you keep reducing the initial interval [tfirst, tlast] with the small values
for both.
-> As soon as the interval becomes invalidated, it means that the ray missed the box and there
is no intersection.
/**/










this is the code I have which works



bool CRasteriser::ClipSegment(float min, float max, float a, float b, float d, float& t0, float& t1)
{
const float threshold = 1.0e-6f;

if (Abs(d) < threshold)
{
if (d > 0.0f)
{
return !(b < min || a > max);
}
else
{
return !(a < min || b > max);
}
}

float u0, u1;

u0 = (min - a) / (d);
u1 = (max - a) / (d);

if (u0 > u1)
{
Swap(u0, u1);
}

if (u1 < t0 || u0 > t1)
{
return false;
}

t0 = Max(u0, t0);
t1 = Min(u1, t1);

if (t1 < t0)
{
return false;
}

return true;
}

bool CRasteriser::ClipSegment(Vector& A, Vector& B, const Vector& Min, const Vector& Max)
{
Vector S = A;
Vector D = (B - A);

float t0 = 0.0f, t1 = 1.0f;

if (!ClipSegment(Min.x, Max.x, A.x, B.x, D.x, t0, t1))
{
return false;
}

if (!ClipSegment(Min.y, Max.y, A.y, B.y, D.y, t0, t1))
{
return false;
}

if (!ClipSegment(Min.z, Max.z, A.z, B.z, D.z, t0, t1))
{
return false;
}

A = S + D * t0;
B = S + D * t1;

return true;
}






you can find the full featured code here

you need to run demo 3 to run the code (press '3').

it is a ray rasteriser. But the first stage is clipping the ray to the voxel map area (a cube). The clipping basically clip the ray to the cube, so it calculates the points of intersection of the ray with the cube.

to get the normals at points of collision, simply store the normals at tfirst and tlast (call them Nfirst, Nlast) everytime tfirst and tlast are changed.

Share this post


Link to post
Share on other sites
Thanks for the detailed description. I've got my collision working now.

I ...uh... had a bug with the coordinates I was using that was screwing it up... :)

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