Ray / AABounding Box Collision

Started by
4 comments, last by helix 19 years, 2 months ago
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!
Advertisement
Do you need the point of intersection, or just a boolean result?
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...

Everything is better with Metal.

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?
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 = tymaxbut, (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.

Everything is better with Metal.

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

This topic is closed to new replies.

Advertisement