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