Sign in to follow this  
riksweeney

BSP collision detection

Recommended Posts

Hi, I've implemented my BSP collision detection OK but have encountered a problem. If I create a "ladder" slope (so that I can walk under it), I can walk up it, down it and underneath it, but if I try and walk underneath it towards the end where it meets the floor, I'm either pushed through the floor or I walk through the base of the ladder. I think this is being caused by my collision detection code moving me so close to the end of my movement that I end up on the edge of the vertex, so the next time I try and move it thinks I can move OK. Here's the code
void traceBox(Vector3 inputStart, Vector3 inputEnd, Vector3 inputMins, Vector3 inputMaxs)
{
	if (inputMins.x == 0 && inputMins.y == 0 && inputMins.z == 0 && inputMaxs.x == 0 && inputMaxs.y == 0 && inputMaxs.z == 0)
	{
		traceRay(inputStart, inputEnd);
	}

	else
	{
		tracer.traceType      = BOX;
		tracer.traceMins      = inputMins;
		tracer.traceMaxs      = inputMaxs;
		tracer.traceExtents.x = -tracer.traceMins.x > tracer.traceMaxs.x ? -tracer.traceMins.x : tracer.traceMaxs.x;
		tracer.traceExtents.y = -tracer.traceMins.y > tracer.traceMaxs.y ? -tracer.traceMins.y : tracer.traceMaxs.y;
		tracer.traceExtents.z = -tracer.traceMins.z > tracer.traceMaxs.z ? -tracer.traceMins.z : tracer.traceMaxs.z;

		trace(inputStart, inputEnd);
	}
}

void trace(Vector3 inputStart, Vector3 inputEnd)
{
	tracer.outputStartsOut = 1;
	tracer.outputAllSolid  = 0;
	tracer.outputFraction  = 1.0f;

	/* Walk the tree */

	checkNode(0, 0.0f, 1.0f, inputStart, inputEnd);

	tracer.outputEnd.x = inputStart.x + tracer.outputFraction * (inputEnd.x - inputStart.x);
	tracer.outputEnd.y = inputStart.y + tracer.outputFraction * (inputEnd.y - inputStart.y);
	tracer.outputEnd.z = inputStart.z + tracer.outputFraction * (inputEnd.z - inputStart.z);
}

void checkNode(int nodeIndex, float startFraction, float endFraction, Vector3 start, Vector3 end)
{
	int i, side;
	float fraction1, fraction2, middleFraction, inverseDistance;
	float startDistance, endDistance, offset;
	Vector3 middle;
	BSPLeaf *leaf;
	BSPBrush *brush;
	BSPNode *node;
	Plane *plane;

	if (nodeIndex < 0) /* Leaf */
	{
		leaf = &bsp.leafs[-(nodeIndex + 1)];

		for (i=0;i<leaf->numOfLeafBrushes;i++)
		{
			brush = &bsp.brushes[bsp.leafBrushes[leaf->leafBrush + i]];

			if (brush->numOfBrushSides > 0 && (bsp.textures[brush->textureID].contents & 1))
			{
				checkBrush(brush, start, end);
			}
		}

		return;
	}

	/* Node */

	node  = &bsp.nodes[nodeIndex];
	plane = &bsp.planes[node->plane];

	startDistance = (DOT(start, plane->normal)) - plane->d;
	endDistance   = (DOT(end, plane->normal))   - plane->d;

	if (tracer.traceType == RAY)
	{
		offset = 0;
	}

	else if (tracer.traceType == SPHERE)
	{
		offset = tracer.traceRadius;
	}

	else if (tracer.traceType == BOX)
	{
		offset = (float)(fabs(tracer.traceExtents.x * plane->normal.x) + fabs(tracer.traceExtents.y * plane->normal.y) + fabs(tracer.traceExtents.z * plane->normal.z));
	}

	if (startDistance >= offset && endDistance >= offset) /* Check front node as both points are in front of plane */
	{
		checkNode(node->children[0], startFraction, endFraction, start, end);
	}

	else if (startDistance < -offset && endDistance < -offset) /* Check behind node as both points are in back of plane */
	{
		checkNode(node->children[1], startFraction, endFraction, start, end);
	}

	else
	{
		if (startDistance < endDistance) /* Back */
		{
			side = 1;
			inverseDistance = 1.0f / (startDistance - endDistance);
			fraction1 = (startDistance - offset + EPSILON) * inverseDistance;
			fraction2 = (startDistance + offset + EPSILON) * inverseDistance;
		}

		else if (endDistance < startDistance) /* Front */
		{
			side = 0;
			inverseDistance = 1.0f / (startDistance - endDistance);
			fraction1 = (startDistance + offset + EPSILON) * inverseDistance;
			fraction2 = (startDistance - offset - EPSILON) * inverseDistance;
		}

		else /* Just set to Front */
		{
			side = 0;
			fraction1 = 1.0f;
			fraction2 = 0.0f;
		}

		if (fraction1 < 0.0f)
		{
			fraction1 = 0.0f;
		}

		else if (fraction1 > 1.0f)
		{
			fraction1 = 1.0f;
		}

		if (fraction2 < 0.0f)
		{
			fraction2 = 0.0f;
		}

		else if (fraction2 > 1.0f)
		{
			fraction2 = 1.0f;
		}

		/* Calculate the middle point for the first side */

		middleFraction = startFraction + (endFraction - startFraction) * fraction1;

		middle.x = start.x + fraction1 * (end.x - start.x);
		middle.y = start.y + fraction1 * (end.y - start.y);
		middle.z = start.z + fraction1 * (end.z - start.z);

		/* Check the first side */

		checkNode(node->children[side], startFraction, middleFraction, start, middle);

		/* Calculate the middle point for the second side */

		middleFraction = startFraction + (endFraction - startFraction) * fraction2;

		middle.x = start.x + fraction2 * (end.x - start.x);
		middle.y = start.y + fraction2 * (end.y - start.y);
		middle.z = start.z + fraction2 * (end.z - start.z);

		/* Check the second side */

		checkNode(node->children[1 - side], middleFraction, endFraction, middle, end);
	}
}

void checkBrush(BSPBrush *brush, Vector3 inputStart, Vector3 inputEnd)
{
	int i, startsOut, endsOut, planeIndex;
	float startFraction, endFraction, startDistance, endDistance, fraction;
	BSPBrushSide *brushSide;
	Plane *plane;
	Vector3 offset;

	startFraction = -1.0f;
	endFraction   = 1.0f;
	startsOut     = 0;
	endsOut       = 0;

	for (i=0;i<brush->numOfBrushSides;i++)
	{
		brushSide  = &bsp.brushSides[brush->brushSide + i];
		plane      = &bsp.planes[brushSide->plane];

		if (tracer.traceType == RAY)
		{
			startDistance = (DOT(inputStart, plane->normal)) - plane->d;
			endDistance   = (DOT(inputEnd, plane->normal))   - plane->d;
		}

		else if (tracer.traceType == BOX)
		{
			offset.x = plane->normal.x < 0 ? tracer.traceMaxs.x : tracer.traceMins.x;
			offset.y = plane->normal.y < 0 ? tracer.traceMaxs.y : tracer.traceMins.y;
			offset.z = plane->normal.z < 0 ? tracer.traceMaxs.z : tracer.traceMins.z;

			startDistance = (inputStart.x + offset.x) * plane->normal.x + (inputStart.y + offset.y) * plane->normal.y + (inputStart.z + offset.z) * plane->normal.z - plane->d;
			endDistance   = (inputEnd.x   + offset.x) * plane->normal.x + (inputEnd.y   + offset.y) * plane->normal.y + (inputEnd.z   + offset.z) * plane->normal.z - plane->d;
		}

		if (startDistance > 0)
		{
			startsOut = 1;
		}

		if (endDistance > 0)
		{
			endsOut = 1;
		}

		/* Make sure the trace isn't completely on one side of the brush */

		if (startDistance > 0 && endDistance > 0) /* Both are in front of the plane, its outside of this brush */
		{
			return;
		}

		if (startDistance <= 0 && endDistance <= 0) /* Both are behind this plane, it will get clipped by another one */
		{
			continue;
		}

		if (startDistance > endDistance) /* Line is entering into the brush */
		{
			fraction = (startDistance - EPSILON) / (startDistance - endDistance);

			if (fraction > startFraction)
			{
				planeIndex    = brushSide->plane;
				startFraction = fraction;
			}
		}

		else /* Line is leaving the brush */
		{
			fraction = (startDistance + EPSILON) / (startDistance - endDistance);

			if (fraction < endFraction)
			{
				endFraction = fraction;
			}
		}
	}

	if (startsOut == 0)
	{
		if (endsOut == 0)
		{
			tracer.outputAllSolid = 1;
		}

		return;
	}

	if (startFraction < endFraction)
	{
		if (startFraction > -1 && startFraction < tracer.outputFraction)
		{
			if (startFraction < 0)
			{
				startFraction = 0;
			}

			tracer.outputFraction = startFraction;
			tracer.outputNormal   = &bsp.planes[planeIndex].normal;
		}
	}
}

I've tried reducing the outputFraction so that it never moves the entire way but this doesn't make a difference and I still move through the floor / ladder base. Has anyone encountered this problem when performing collision detection on BSPs?

Share this post


Link to post
Share on other sites
I had this problem when i was writing the collision detection system in my Undead Engine, however it wasn't due to BSP... it can happen with ANY method.

This hapenned to me because i was just "pushing" the camera's bounding volume towards the colliding face's normal, just enough to "touch" but not penetrate the face - and i was doing that for every colliding face. This worked in most cases, but not all. And it had jerky movement.

Then i found [url=http://www.fluidstudios.com/pub/FluidStudios/CollisionDetection/Fluid_Studios_Generic_Collision_Detection_for_Games_Using_Ellipsoids.pdf]this document[/url], which describes how to create a "sliding plane" for sphere or ellipsoid-based collision detection. This sliding plane is used to project your velocity vector to it and then moving the object using the projected velocity vector. Personally i decided to not implement the whole algorithm, but only take the sliding plane idea and figure out the rest myself (it helped that i already had other stuff in the engine already working and i would have to rewrite them if i was going to implement the whole thing...).

This document is very easy to read, btw. And while says nothing about BSP, you'll be able to use BSP with it.

Share this post


Link to post
Share on other sites
If this is anything like the problem I encountered when implementing BSP based collision detection, it has nothing to do with the algorithm...the algorithm works perfectly. I copied ostgard's tutorials code verbatim, quake2 collision detection verbatim, and I even e-mailed john carmack about the problem. The problem I was having was that when the framerate would get very high the movement from frame-to-frame would get very small. These tiny movements would often come within the floating point error of a single precision floating point unit (the format for all of the collision hull information stored in the quake3 format).

The solution that worked for me: always make sure that the movement used for doing collision detection never falls below a certain size. This typically meant extrapolating the move, and if it collided, just don't get any closer.

Share this post


Link to post
Share on other sites
hey i just wrote up my code using the same article i think
can you please tell me how to make the inputstart and inputend vectors
i am not even sure what they are suposed to be
i tried setting start as camera position xyz
and the end as camera view xyz
but its not working

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