QUAKE 3 BSP

RAY-BSP Collision Detection

Frank Puig Placeres (fpuig)

Fpuig2003@yahoo.com

Overview:

The basic idea of this tutorial is to show us how to detect collision between a ray and the BSP. This code is very basic and very important that be fully understood because the collision detection between a sphere/box use the same principle and almost the same code that this one.

Quake 3 use Brushes to handle collision. Each of the Leaf stored in the BSP data, has a number of associated brushes. Each brush is a set of planes that form a convex volume and has a property. That property functions as a flag that tell us when the brush is a solid area, water, slime, lava, among others. To handle collision, we will start from a point and traverse the BSP like in the previous tutorial (BSP 4).

OutPut:

When we trace to detect collision we need that by some way that collision gets reported. For that we introduce the next structure

struct sMoveData{

float Fraction;

CVector3 EndPoint;

CVector3 CollisionNormal;

bool StartOut;

bool AllSolid;

};.

All collision functions, and currently the one of this tutorial that handle collision between a Ray and the BSP, will return a sMoveData structure to inform us what happens with the trace. The members of that structure, means the next:

Fraction: How long has the trace move?

Fraction = 0 means not move at all.

Fraction = 1 means complete move by not collision. Any value in between tells how much it move.

EndPoint: Indicate the point where we end the move just because a collision or because we get to the target.

CollisionNormal: Store the normal of the plane we collide with.

StartOut: True if the line segment starts outside of a solid volume.

AllSolid: True if the line segment is completely enclosed in a solid volume.

Ray-BSP collision detection

The first we are going to do when we need to check collision is store the initial information in the variables we have, in order to get access to they on the traversal check. Don’t worry about that yet, we get into next.

// Global variables used to store needed information. This will be used on the CheckBrush

CVector3 MStart; // Where The ray Start

CVector MEnd; // The ray target (where it will end)

sMoveData CQuake3BSP::CheckRayMove( CVector3 Start, CVector3 End)

{

// Initializations, This will change if the traversal detect it was wrong

MoveData.StartOut = true;

MoveData.AllSolid = false;

MoveData.Fraction = 1.0f;

// Necessary info to collide with brushes

MStart = Start;

MEnd = End;

// traverse the BSP tree checking collision.

// start from node 0 (root) and began on Start Point, Width a fraction of 0

// End in the End Point with a fraction of 1.

// Result on MoveData.Fraction will be returned in the 0..1 range because that’s what we tell it to do

CheckMoveByNode ( 0, 0.0f, 1.0f, Start, End );

Once we setup the necessary info we call CheckMoveByNode who is responsible to check collision against the tree. The first parameter is the starting node.

We want to collide with the complete BSP so we put 0, which means the root. The Ray is traced from Start to End which are the last parameters. But talking about fractions, if we say that start is point labeled by 0 and End is the point labeled by 1 the any in-between fraction (0<= t <= 1) will give me a point of the ray according to the line formula:

Point = Point0 + (Point1 – Point2)*t

Check some math book or any other tutorial if you don’t get fully into that!

So that’s why the second and third parameter are 0 and 1 respectively: We traverse from the start to the end of the ray.

CheckMoveByNode change the MoveData structure. So we see the information that is there after we call the function.

Remember that MoveData.Fraction tells us how much we can move on the ray with out collision. So if in return it has the value 1, then we reach the End Point with out a collision. So we assign MoveData.EndPoint to the Target Point.

If Fraction wasn’t equal to 1, then is any value between 0 and 1. So we linearly interpolate with the line equation and compute the ending point.

if (MoveData.Fraction == 1.0f)

{ // nothing blocked the trace

MoveData.EndPoint = End;

}

else

{ // collided with something

MoveData.EndPoint = Start + (End-Start)*MoveData.Fraction;

}

return MoveData;

}

CheckMoveByNode actually traverse the tree like we did it on last tutorial when rendering. It start from the node was enter (initially the root) and call children until found a leaf. When we found the leaf, we check all the solid brushes of that leaf. Remember that a brush represent some place that has a property, for example is solid or is slime, or water, etc. Brushes are stored as a set of planes that form a convex volume. Take a look to the 2D example

Lets began with the code:

But first of all: If you collide with and brush, MoveData.Fraction will be updated accordingly. So if you are tracing on a startfraction that is greater than MoveData.Fraction then you are tracing by nothing because any brush you can collide from that point on, will be farther than the current brush you collide. That’s an optimization that allow not checking all the BSP

void CQuake3BSP::CheckMoveByNode( int nodeIndex, float startFraction, float endFraction, CVector3 Start, CVector3 End )

{

// If the path was blocked by a nearer obstacle, don't bother checking

if (startFraction > MoveData.Fraction)

return ;

if (nodeIndex < 0)

{ // this is a leaf

tBSPLeaf *leaf = &m_pLeafs[~nodeIndex]; // Get a pointer from the m_pLeafs Array.

// Remember that NodeIndex is negative so the corresponding leafs is

// ~nodeIndex which is same of saying -(NodeIndex+1) but faster!

// Loop by all the brushes

for ( int i = 0; i < leaf->numOfLeafBrushes; i++)

{

Take a point to the i-th brush in the leaf

tBSPBrush *brush = &m_pBrushes[m_pLeafBrushes[leaf->leafBrush + i]];

// If the brush has sides (is a convex volume) and is SOLID then check it out!

if ( brush->numOfBrushSides > 0 && (m_pTextures[brush->textureID].contents & 1))

{

CheckTouchBrush ( brush );

}

}

// don't have to do anything else for leaves

return ;

}

No hard till the moment! But things became a gradually complex.

Now, we know we are a Node, so we have an splitter plane who divide the world in two pieces. We need to continue with the children till find leafs, because we just can collide with the brushes that are in the leaf. So this is what we do for traversing: If the ray is complete in one of the sides of plane, then that’s not our job, is a job of the children we have on that side. (Did that make sense?) If the ray is complete on one side, then we pass it to the child of that side so he can check collision.

// this is a node.

// Get pointer to the Node it self and to the splitter plane

tBSPNode *node = &m_pNodes[nodeIndex];

tBSPPlane *plane = &m_pPlanes[node->plane];

// Get the distance from the start and end point to the plane. This is done with the Plane formula:

float startDistance = plane->vNormal.x * Start.x +

plane->vNormal.y * Start.y +

plane->vNormal.z * Start.z -

plane->d;

float endDistance = plane->vNormal.x * End.x +

plane->vNormal.y * End.y +

plane->vNormal.z * End.z -

plane->d;

// If both points are in front of the plane (the positive side) pass the ray to the front

// child as the ray comes.

if (startDistance >= 0 && endDistance >= 0)

{

CheckMoveByNode ( node->front, startFraction, endFraction, Start, End );

}

// If both points are in behind the plane (the negative side) pass the ray to the back

// child as the ray comes.

else if (startDistance < 0 && endDistance < 0)

{

CheckMoveByNode ( node->back, startFraction, endFraction, Start, End );

}

If the Start and End point are in different sides of the plane, then the ray is intersecting that plane. We need to split the ray in two pieces. One that falls complete on the front side and one that is complete on the back side of the plane. But because of computer floating operation range errors, if we split exactly in the middle then the plane can say that the middle is fully in one side and not in the plane. I make my self clear: Computers has a limited accuracy. So when we compute the distance from a point to a plane the computer make some accuracy errors. And the equation could result in 0.0001 that is truly 0.0 but with the errors the machine tell us that number. Of course he will know that 0.0001 is not 0.0 so the point is not in the plane but in one side, when truly the point is on the plane. To avoid that we introduce an epsilon and we split epsilon units from the plane. See the picture.

Epsilon is a ridicule small value. Quake use 0.03125f which is 1/32.

Now we have the ray divided in two pieces: One for the front side and one for the back side. So we pass those new ray segments to the front and back children. But one important thing is to know which side to traverse first, the front or the back? We want to collide with the first brush not the last one. So is chosen the nearest side (the side that contains the start point).

One more thing that can bring into confusions who to determine the Smiddle (Start-middle), and Emiddle Points:

The ray Fraction that represent Smiddle from to start to end is:

Fraction = (start-epsilon) / (start - end)

And the Middle point is interpolated with the line equation we see above.

else

{ // the line spans the splitting plane

int side1, side2; // Variables to hold which side to traverse first and which second

float fraction1, fraction2 // Used to know compute the Smiddle and Emiddle.

CVector3 middle; // middle point (Smiddle and Emiddle)

// split the segment into two

// If we know that one is positive and the other is negative, and startDistance < endDistance, so

// startDistance is negative and endDistance is positive (front and back correspondingly)

if (startDistance < endDistance)

{

side1 = node->back; // the back side contains the start point so the back will be the first

side2 = node->front;

float inverseDistance = 1.0f / (startDistance - endDistance); // optimization

fraction1 = (startDistance - EPSILON) * inverseDistance; // compute fraction for the start-middle

fraction2 = (startDistance + EPSILON) * inverseDistance; // compute fraction for the middle-end

}

// On the other hand if endDistance is negative and startDistance is positive

else if (endDistance < startDistance)

{

side1 = node->front; // the front side contains the start point so the front will be the first

side2 = node->back;

float inverseDistance = 1.0f / (startDistance - endDistance);

fraction1 = (startDistance + EPSILON) * inverseDistance;

fraction2 = (startDistance - EPSILON) * inverseDistance;

}

else

{

side1 = node->front;

side2 = node->back;

fraction1 = 1.0f;

fraction2 = 0.0f;

}

// make sure the numbers are valid

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

middle = Start + (End - Start)*fraction1;

// get the Smiddle fraction (not just the point)

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

// check the first side

CheckMoveByNode ( side1, startFraction, middleFraction, Start, middle );

// calculate the middle point for the second side

middle = Start + (End - Start)*fraction2;

// get the Emiddle fraction (not just the point)

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

// check the second side

CheckMoveByNode ( side2, middleFraction, endFraction, middle, End );

}

}

Wow! We know how to traverse the tree. But when we get to a leaf we test collision against all solid brushes. As we see above a brush is a convex volume made by planes (brush sides). Here is the algorithm to test a ray against a convex volume:

In 2D, we have a brush and a ray. Two float variables will be set to an small value S=-1 , and to the end point E=1.

Take each side and intersect it with the ray. Assuming that a brush plane is negative to the interior volume, then we know when Start is positive and when is negative (in the pictures when Start is positive then the side is colored red and when end is positive black).

Made this for all sides:

If the side is red and the intersection fraction is greater than S then move S to the intersection.

If the side is black and the intersection fraction is smaller than E then move E to the intersection.

Let’s see what’s happen with a line that collide and with one that is don’t.

	Ray not collide with the brush	Ray collide with the brush
Side 0
Side 1
Side 2
Side 3
Final Result

Can any one tell me the difference? Of course the E < S when no collision took place. And S < E when a Collision took place.

An advice: take a pencil, draw a brush and check the algorithm for several lines. If doesn’t work then go to quake and there HAS to be a place where you MUST not collide! J

We also can know the collision normal. Because is the plane that change the S the last time! That’s why in the code I has a variable named CandidateToHitNormal and every time I change S, the variable took the plane’s normal. By that way if at the end I found collision, CandidateToHitNormal is the normal.! Did that make sense to you?

void CQuake3BSP::CheckTouchBrush( tBSPBrush *brush)

{

float startFraction = -1.0f; // The S in the pictures

float endFraction = 1.0f; // The E in the pictures

bool startsOut = false; // If not plane change this value then the ray start IN

bool endsOut = false; // If not plane change this value then the ray end IN

CVector3 CandidateToHitNormal;

// Go for every brush side

for ( int i = 0; i < brush->numOfBrushSides; i++)

{

// take a pointer to the brush side and the plane it represent

tBSPBrushSide *brushSide = &m_pBrushSides[brush->brushSide + i];

tBSPPlane *plane = &m_pPlanes[brushSide->plane];

// Compute distances from the plane to the MStart and MEnd (the values enter at the begging of the trace

float startDistance = plane->vNormal.x * MStart.x +

plane->vNormal.y * MStart.y +

plane->vNormal.z * MStart.z -

plane->d;

float endDistance = plane->vNormal.x * MEnd.x +

plane->vNormal.y * MEnd.y +

plane->vNormal.z * MEnd.z -

plane->d;

// if the start point is in front this plane, then it can be IN the brush so it’s OUT

if (startDistance > 0) startsOut = true;

// if the end point is in front this plane, then it can be IN the brush so it’s OUT

if (endDistance > 0) endsOut = true;

// 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 ;

}

// The line is Red so is entering the brush.

// Compute the new S (fraction)

// if (the new S) > S move S and update CandidateToHitNormal

if (startDistance > endDistance)

{

float fraction = (startDistance - EPSILON) / (startDistance - endDistance);

if (fraction > startFraction){

startFraction = fraction;

CandidateToHitNormal = plane->vNormal;

}

}

else

// The line is Black so is leaving the brush.

// Compute the new E (fraction)

// if (the new E) < E move E

{

float fraction = (startDistance + EPSILON) / (startDistance - endDistance);

if (fraction < endFraction)

endFraction = fraction;

}

}

// After checking all sides if startOut remain false, then the Start Point is complete in the brush

if (startsOut == false)

{

MoveData.StartOut = false;

// if also the EndPoint is in this brush, then the ray is complete in this brush

if (endsOut == false)

MoveData.AllSolid = true;

return ;

}

// if there was collision against the brush (S < E)

if (startFraction < endFraction)

{

// And of course if we move S (if we don’t then we don’t enter the brush

// and we don’t collide with some nearest brush

if (startFraction > -1 && startFraction < MoveData.Fraction)

{

// UpDate OutPut values

if (startFraction < 0) startFraction = 0;

MoveData.Fraction = startFraction;

MoveData.CollisionNormal = CandidateToHitNormal; // The candidate gets postulate!

}

}

}

Till here you have all you need to detect BSP-Ray collision. Check the code the see it in practice and if you don’t understand anything, email me and I will try to be more clear.

If you understand all that stuff, then you can understand very easily the BSP-Sphere and BSP-Box, just because they use the same algorithm. I will post other tutorial covering them.

Usefull Links:

Really nice collision page: http://www.nathanostgard.com/tutorials/quake3/collision/

Box-BSP code: http://www.gametutorials.com/forum/topic.asp?TOPIC_ID=3810&whichpage=1

Quake 2 source code: ftp://ftp.idsoftware.com/idstuff/source/q2source-3.21.zip

Quake Fusion Proyect: http://hkitchen.quakesrc.org/

Frank Puig Placeres ( fpuig2003@yahoo.com )

Last Revised May 18, 2003