# collision detection with BSP trees

I am experimenting with collision detection and BSP trees. Tell me if this is correct:

I traverse the tree in front to back order. This gives be a list of all polygons which are closest to the camera. The camera has a ‘bounding sphere’ which is really just the distance from the cameras position to the farthest point on the near plane. At each node I test to see if the plane is farther away than the radius of the bounding sphere. If it is then I can stop processing the tree because there are no more possible intersections (that is to say that since I am not intersecting with the polygon that is closest I am obviously not intersecting with any polygons that are farther away). This seems to make sense to me but I am not positive nor do I know how to prove it. Also if I am using a recursive function what is a good way to short cut out of processing the tree? Here is more or less what I have:

bool done = false;

void process_BSP_Node(BSP_Node cur)
{
if (done == false) //shortcut out of processing the entire tree
{
float distance = cur->A
camera.xPos + cur->Bcamera.yPos + cur->Ccamera.zPos - cur->D;

if (distance &gt; 0) //process front side
{
if (cur-&gt;front_pointer != NULL) process_BSP_Node(cur-&gt;front_pointer);
if (distance &gt; camera.radius) {done = true; return;}

//we have found there is a collision with the current plane
//check further to see if there is collision with the actual polygon

if (cur-&gt;back_pointer != NULL) process_BSP_Node(cur-&gt;back_pointer);
}
else //process back side
{
if (cur-&gt;back_pointer != NULL) process_BSP_Node(cur-&gt;back_pointer);
if (distance &gt; camera.radius) {done = true;return;}

//we have found there is a collision with the current plane
//check further to see if there is a collision with the actual polygon

if (cur-&gt;front_pointer != NULL) process_BSP_Node(cur-&gt;front_pointer);
}
}

}

Ok I have figured out that this method does not work but then what does? I think there must be a way to use BSP trees so you do not have to parse the entire tree right?

I guess I was not thinking clearly about what the BSP tree actually is. Here is my new synthesis (THESIS-ANTITHESIS-SYNTHESIS). You can use a BSP tree to cull away large areas of geometry that can not possibly be colided with. For instance, say you have a bounding sphere around an object. At each node you ask a question: Is this sphere completely on one side of the plane or the other. If the sphere is entirely on the front half-space of the plane then the back half-space does not need to be checked because it is farther away by definition. If the sphere is entirely on the back half-space of the plane then the front half-space does not need to be checked because it is farther away by definition. This should cull down the tree to only a few possible collisions (and fairly quickly if the tree is somewhat balanced).

This leads me to another problem. Objects are moving. If an object were static then it would obviously never colide with anything else that is not moving. So how do I reconcile this with an efficient bounding sphere algorithm to cull large areas of the BSP tree? My first idea is to create a new bounding sphere that encompases the entire movement of the object. In other words I start with a vector that represents the movement. I then calculate a point halfway along the line that is the new center of the bounding sphere. Then I compute the radius of the new bounding sphere which is the length of the movement vector plus two times the objects radius. What this new bounding sphere represents is a space that the object does not leave in the entire time interval. The negative part is that the farther you move in each time interval the bigger the bounding sphere will be. This means the smaller the distance traveled the more geometry will be culled from the BSP tree. But this technique should give me somewhat consistant returns the larger the scene gets I think.

I should mention that this will be only a preliminary filter and of course I will have to go further to determine actual intersections. Does this seem like a some what feasible idea?

I implemented collision detection as well as a general ray/polygon intersection test using BSP trees. Performance was very good. The algorithm proved very difficult to perfect when BSP error tolerance was taken into account. (The BSP planes did not perfectly separate the geometry!)

geoman: Yes your culling concept is correct. You can get exact per/poly collision info, but you’ll have to start splitting polygons to be very efficient. You could slightly generalize the concept to reduce splitting by having a separate inside and outside planes for each node (similar extension as loose octrees for octrees).

Most physics systems assume that the time step is small enough to not make objects go through things. If you really want to worry about it, you can do the super sphere thing you mentioned (or a capsule method…). But yeah, generally you only worry about finding the extact intersections if you have a general collision.

macarter: What was the problem with error tolerance? I’ve implemented ray BSP collision for a ray tracer, and never had any issues with error checking.

Adruab, maybe he means a little floating point bias that helps with “sliding”. You know, so friction can be simulated, rather than just hard stops. I’ve found that 1/32 makes a good bias for that case. Just a subtle nudge off the plane in the direction of the normal. Otherwise, you could end up with an intersection point right on, or slightly behind the plane, in which case subsequent traces could end up starting inside a solid. For brute force line traces, this can help quite a bit.

Geohoffman49431, your plan sound good to me as well. Take care that you include your trace object size in the sphere, AABB, OBB, or whatever you choose to bound things, else you might inadvertently skip relevant nodes. Not that this ever happened to me, mind you

Thanks for all the replies.

Adruab - that will make the calculations simpler if I only need to test the second point that the player is moving into. Thanks.

SG and macarter- I think I know what you mean. Since floats are not exact the plane equation is not going to be exact. So the player can possible find themselves inside an object without the posibilty of getting out? I think my solution would be to slightly increase the size of the bounding sphere to take into account that inaccuracy. But what do you mean it can help with simulating friction? That is the next thing I need to consider, how my players will react when they hit the wall. Will they stop, slide, or bounce. Of course I want them to slide. So i think I will need to detect the colision and then move them in the direction of the plane. Any suggetions on where to start in figuring this out?

Geohoffman, first an obligatory mention of ODE (Open Dynamics Engine), a free physics SDK that will handle all this stuff for you, and then some! It works very well, and it’s getting better all the time. I’m sure you are aware that there are packages that will handle this stuff for you, so I mention this in passing for the interested reader

To me, the most difficult aspect of player movement in a BSP world is sliding; that is, we want to allow the player to slide along multiple planes, simultaneously, and as smoothly as possible. Toward this end, we can use a loop to handle the basic movement. For each iteration, we first create a line segment from the current player position, P, to the destination position P’

P’ = P + V dt

where V is the current player velocity, and dt is the current time step.

Next, we trace the line P->P’ through our BSP. Many game engines will use a box or cylinder as the sweep primitive here, since these can be easily accounted for in the tree by using simple plane shifts, and they more closely resemble the player’s actual shape in most cases (tall and skinny). They both work well, so let’s use a box for simplicity.

To perform the trace, place the player’s bounding box at P, place the same box at P’, then create a new box to bound the whole thing; this is the bounds of the trace, and as you guessed, a little expansion can help with floating point issues (the amount of expansion will depend on how you scale things). We can now “filter” this box down the tree using a box-plane test. How you proceed with the actual trace here depends on how you have organized your tree.

As I mentioned in a previous post, I like to keep my original convex geometry on the boundary of my leaf hulls. In this way, I can simply filter the trace box into the empty leaves of the tree, then proceed to trace the individual convex polyhedrons (brushes), one at a time. This is a very fast and easy operation (brushes have nice properties that make them especially easy to trace). As a bonus, this approach also affords the opportunity to trace other things in the leaf as well, such as other players, patch meshes, and so on. In essence, you can let your empty leaves be repositories for all your stuff. Yet another boon is the ability to easily expand and rotate each brush/actor on a case-by-case basis, making this method very robust for dynamic objects. Furthermore, attaining collision surface information (texture/material) is a cinch. Anyway, it’s up to you.

Now that we have the line trace end point, we can move the current position, P, to the new trace end position, E. If there was no intersection (didn’t hit anything), then we’re done: we set the player’s position to E and bail. Otherwise, we set P = E, then clip the velocity with the intersection plane (force the velocity along the plane). As we’re dealing with multiple planes here, we need to add this plane to a list, and clip the current velocity against each plane in the list.

Here’s the basic idea in pseudo code:

// For each unique intersection plane encountered so far
for all planes i

// Clip velocity to current plane
clip V against plane[i]

// Now clip to all other planes
for all planes j != i

clip V against planes[j]

// If this clip pushes us back into
// an earlier plane
if dot(V,planes[i]) < 0

// Slide along both
crease = cross(planes[i],planes[j])
V = crease * dot(V,crease)

// See if this pushes us into
// a 3rd plane
for all planes k != i, k != j

// If into a corner, stop
if dot(V,planes[k]) < 0
V = 0
return

Care must be taken to avoid moving the player in the opposite direction that he started in; when V dot originalV is less than 0, some very annoying behavior can result (player developes an irritating shimmy when walking into a wall or sloping combos). This is not a situation that is easily rectified.

A function to clip the velocity against a plane might look like this:

Vector3 clipVelocity( Vector3 v, Vector3 n, float clip = 1.001 )
{
float d = dot(v,n);

// Clip helps fix some floating point issues
// by either nudging the velocity away or
// into the plane, depending on the sign
// of the dot product.
if( d < 0.0 ) d *= clip;
else          d /= clip;

// Return a vector that now
// parallels the plane.
return v - n * d;
}

By the way, by “clip”, I mean to clip the component of velocity into the plane’s normal.

Having now clipped the current velocity, we are ready to repeat the entire process, or bail if the velocity is 0 or the maximum number of iterations has been reached.

I have omitted a few details, most involving floating point issues and actual physics. I’ve some code I could post, but it’s rather large and riddled with dependencies. Maybe I can chip it down to size. Or, maybe someone else has some code they could post.

Anyway, I hope this makes some sense.