BSP Collision Detection As Used In MDK2 and NeverWinter Nights

Player Control and Navigation

This paper first discusses player control and navigation in an action oriented 3D game. The collision requirements mentioned help motivate the following sections on collision detection. The final sections discuss application and construction issues, as well as ideas for future work.

In a video game there are many small projectiles, such as rocks or bullets, that travel along a given trajectory. You would expect one of these to hit a character only if it impacts a polygon on that character. This makes sense because it simulates how things work in real life.

So how should we handle the separate problem of collision and navigating of a character in a 3D environment? In the real world this is achieved by "left foot forward", "right foot forward", and so on. In a video game the user has an avatar which is often a biped, so why not implement something analogous to how things work in the real world? The big problem here is that our interface is restricted to a 2DOF mouse and a few extra bits from the available mouse buttons and keys. There have been various attempts, but its very hard to make an effective interface that perfectly mirrors how we do things in the real world - such as picking up objects, walking with our feet, and so on. Olympic Decathlon on the Apple 2 is one of the few successful examples. Rather than trying to physically simulate all the limbs of the body, most of the popular shooters today seem to navigate the character as if it was a simple shape - such as a sphere or cube.

In MDK2 we used a cylinder model for the character-to-environment collision detection. This cylinder is always upright. Note that the cylinder has bilateral symmetry, so the user is never ever restricted from turning. In real life you have to turn sideways to squeeze through a narrow passage. This is not something you would ever want to force on the user - especially if it is a first person game.

If the game is 3rd person, or if you are looking at another player, you still expect to see the model move its feet when walking, or play a jump-animation when the player jumps into the air. The animation of the character is a function of what's going on in our simple navigation model - not the other way around. In MDK2 each character had a set of animations for running and walking forward, backward, sideways, jumping, climbing and so on. These were invoked at the appropriate times. We didn't do any IK, but that would be a great improvement over just playing "canned" animations. IK is consistent with the system presented here

Resolving Collisions
Based on user input the engine applies accelerations to the cylinder object. As the player moves around it is important to check to see if he collides with the environment. If a collision occurs you must deal with it by changing the location where you had planned to relocate the player. This may require a few iterations to get right.

Sliding
Its best to solve a collision by deflecting the players motion rather than stopping at the impact point. Imagine running down a hallway and brushing up against the wall would cause you to "stick". This is easily solved using something in your code like:

Where:

In English, this just means: move the target-position above the impact plane in the direction perpendicular to that plane.

There is one thing to watch out for with this simple collision resolution algorithm: when you have two planes of impact that face each other you do not want an endless cycle deflecting the motion vector back and forth. It is best if the code can handle multiple planes simultaneously.

Stepping
When was the last time you were crossing the street and tripped on the curb?

Stepping up onto the sidewalk is a function processed by some subconscious part of the brain. In a video game, the users do not want to have to worry about small steps and stairs. He mouselooks where he wants to go while holding the forward arrow key. It is up to the game developer to implement all the lower level brain functions.

I solved this by lifting up the path of the player when it collided with something. If the raised path was clear I'd move the player along it and then drop it back down. I thought this was just a temporary fix when I first implemented it during our prototype stage, but it worked beautifully and ended up in the final code that was shipped.

In MDK2, implementing climbing turned out to be a basic extension to the step up ability. Climbing was used if the height transition was large enough. In this case, the player's climbing animation was also invoked. For the user, it became easy to move his character up onto a ledge. No keypresses required. No special skills to learn.

Standard Player Control Interface
In the mature world of Windows there is an evolved interface with scrollbars, menus, and buttons, which has become our standard means of 2D interaction at the desktop. Change this and you will make the user very angry. Some people are actively looking for the standard 3D interface. Well, I believe that it is already here right under our noses. Look at the games we play.

VRML browsers are fine for grabbing and rotating an object. But they are not as well suited for navigating around a world. There is little sense of "presence". Whether 1st or 3rd person, it is nice to have an avatar that has some volume to it and will collide with the environment. Furthermore, the movement shouldn't be cumbersome. People expect to be able to move sideways, to slide along walls, and to automatically ascend stairs or ladders. To appease the user you want to provide an intuitive interface that feels right. So even if you are building some 3D internet shopping mall application, grab the key bindings from the user's Quake config file, and let him rocket-jump from the bank to the clothing store. It would be nice to see more successful applications, other than games, that are based on 3D immersive technology.

Offset Surfaces and BSP Usage

Simulating an object as a point is a popular technique to reduce the complexity of various math and physics problems. Fast collision detection is important for interactive 3D applications that wish to maintain a high frame rate. Not surprisingly, one popular method of doing collision detection of an object with an arbitrary polygonal environment is to approximate the object as a point. The reason the object does not intersect the environment's geometry is because the object does its collision detection with an approximate offset surface - an "expanded" or "scaled" copy of the geometry where the interior walls have been moved inward, exterior walls shifted outward, the floors raised, and the ceiling lowered. The modifications to the environment correspond to the size of the object that collision tests will be performed. Note that by environment we are referring to a large, detailed, 3D model that is rigid (static).

As the object moves from one position, v0, to another, v1, the motion line segment, (v0,v1), is checked against the offset surface to determine if it has collided. Character collisions are resolved as discussed in the previous section. Physically based objects typically have their velocity reflected off of the plane of impact.

Note that just treating an object as a point is not a sufficient method for fast collision detection. An arbitrary polygonal environment can contain thousands of polygons. Therefore this geometry should be represented in an efficient spatial structure such as a binary space partitioning (BSP) tree.

A disadvantage of this offset surface technique is that it requires an additional copy of the environment's geometry for each object shape/size. If an object is allowed to change orientation, then there are further symmetry restrictions on the object's collision envelope.

In an effort to make MDK2 a content-rich game, we have many different sized characters. The memory requirement for having multiple copies of the environment's geometry was a problem. In addition to characters, our game also creates many small artifacts to make special effects such as explosions and debris. These small artifacts require fast collision detection as well. Creating another BSP tree for every particle size is just not feasible. This problem was overcome by using the dynamic plane shifting BSP traversal discussed in the next sections.

Dynamic Plane Shifting BSP Algorithm

Instead of using expensive collision test or having to store extra offset surfaces, MDK2 used a variation of the line-segment to BSP collision algorithm referred to as "dynamic plane shifting BSP traversal". Collision detection for a non-zero volume object is still done using a fast line segment check. The environment is represented with only one standard BSP tree that was constructed without any regard for what shapes it would be doing collision detection with. We modify the plane equations of a BSP tree during the collision detection traversal, which gives us a reasonable approximation for collision detection of an arbitrary convex shaped object moving along a linear path.

The standard algorithm for colliding a ray with a BSP tree is a recursive function that starts at the root. If the segment lies on one side of the node's plane then the segment is passed down to the corresponding subtree. Otherwise, the segment crosses the plane so it is split. The first piece of the segment is checked. If it fails to collide then the second piece of the segment is checked against the other subtree. If a solid leaf node is reached then the algorithm returns a collision with impact equal to the start of the subsegment that reached the leaf.

Here, in more detail, is our revised algorithm that dynamically alters the plane equations:

HitCheckBSP (node n,vector v0,vector v1)
int hit = 0
vector w0,w1
if n is an empty leaf
return 0
if n is a solid leaf
Impact = v0
return 1
if dot_product(n.normal,v1-v0) > 0
if rayunder(n shift up,v0,v1,&w0,&w1)
hit = HitCheckBSP(n.under,w0,w1)
if hit==1
v1 = Impact
if rayover(n shift down,v0,v1,&w0,&w1)
hit |= HitCheckBSP(n.over,w0,w1)
return hit
else
same thing, but in the other direction
End

The function rayunder returns true if part of (v0,v1) lies under the supplied plane. The portion of the line segment under the plane (cropped if necessary) is returned in (w0,w1). The function rayover has similar functionality. Unlike the standard algorithm, the segment is not divided into two disjoint pieces - the subsegments passed down into the subtrees will overlap. Even if a collision occurs in the first subtree, it may still be necessary to check the other subtree (after adjusting the segment endpoint) since an impact may occur sooner. The amount the planes are shifted (offsets) correspond to the dimensions of object being checked for collision.

A thorough description of Dynamic Plane Shifting BSP Traversal can be found in the proceedings to Graphics Interface 2000, which is available online at www.graphicsinterface.org, or you can try my web page at www.cs.ualberta.ca/~melax.

Potential Inaccuracy and Beveling

As mentioned previously, our technique (and similar techniques that simulate the object as a point) are subject to a certain degree of inaccuracy. This is illustrated in the adjacent figure. Two spheres, A and B, collide with the geometry below them. Using the center of each sphere is its reference point, the environment's geometry is offset outward as represented by the dotted lines. The center of each sphere rebounds off these offset planes. As sphere A moves along its trajectory, the collision occurs before its perimeter contacts the surface. For comparison, sphere B will rebound with an appropriate impact point and direction of deflection.

Most of the time, the protrusion of solid cells is tolerable, but the error starts to increase dramatically as the angle between adjacent planes approaches 180 degrees. We reduce this problem by beveling the solid cells of the BSP tree. This is achieved simply by inserting additional nodes at the bottom of the tree. When the planes are offset during a collision query, the solid cell no longer protrudes as far as it did without the extra nodes.

Although it may not always seem necessary, this beveling step is very important. Even if the initial boundary representation contains no acutely convex angles, the BSP compilation process slices space and may still produce cells with sharp ridges. There is a cost of adding nodes to the tree: in practice we found that we would typically double the number of nodes in the tree. This is still better than having multiple trees. Since the collision algorithms are O(lg(n)), the impact on performance (due to tree size) is minor.

Performance Overhead

There is a performance cost for object collision queries that use the dynamic plane shifting technique. Additional nodes will be visited due to the bi-directional shifting of the node's plane equations. Testing an object as large as the environment will end up searching every node in the tree. Clearly dynamic plane shifting works best for colliding objects that are small relative to the size of the environment. For some "real world" performance results we look at execution times from MDK2.

When we replaced our multiple tree collision detection with our dynamic plane shifting solution, we did not detect a noticeable difference in the overall performance of the program. Most of the computing resources go into other areas such as animation, AI, physics, and rendering - collision detection is a small fraction of the work. Furthermore, many of the BSP queries are for particle, bullet, line-of-sight, lens flare, and shadow checks. These require little or no geometry expansion. To see the cost of the algorithm, we measured a player character's collision times in isolation.

We compare 3 methods of collision detection: regular BSP collision (labeled Ray), spherical offset, and cylindrical offset. Each method received the same input parameters, including the player's current position and desired new position for that frame. Nothing but BSP traversal code contributed to the times. Testing was done on a Pentium 3, 400MHz. Our results show that plane shifting collision detection can be 2.5 to 3.5 times more expensive. Putting these results in context, at 30 FPS, each frame allows 33000 microseconds. We felt an additional 20 to 50 microseconds for a character's collision detection was worth the flexibility of allowing different sized characters and objects in our game. We also noticed that the performance did not vary that much from one frame to the next. In a 3D interactive application, a good frame rate must be maintained at all times - not just in the "average" case.

BSP Construction and Challenges

In MDK2 everything (and I mean everything) was already being built in 3DS Max. We even had dummy nodes that we used to place lights, particle emitters, and bad guys in the level. We used the mesh modifier facility to add the BSP compiler to the art production pipeline. When the modifier was added to a node it would create a BSP tree out of its polygons.

The BSP compiler required non-self-intersecting borderless 2-manifold geometry as input. 3DS Max doesn't automatically place modeling constraints on the content. Therefore, extra work was required for the artists to get the models to comply with our requirements.
Another disadvantage of not having modeling constraints is that surfaces that should be flat often aren't. In many situations there were 2 triangles that made up a quad but the 4 vertices weren't coplanar within a large epsilon. This ended up making the BSP trees larger than should have been necessary. In contrast, a Quake editor will insist that the sides of a brush are flat even if it has to have an extra vertex and make a couple of skinny triangles. Considering how fast 3D rendering hardware is now and how slow random memory accesses can be (such as tree searches), it is probably better to have geometry with a minimal half-space representation than a minimal mesh representation.

Neverwinter Nights

Neverwinter Nights (NWN) is a very exciting and ambitious project. However, it isn't an action/physics oriented game where characters are jumping and shooting in a 3D environment. The NWN RPG is based on the D&D rule system. Consequently the needs for collision detection are different than for MDK2. Most of the collision tests will only be line segment tests required for user selections, determining the path-searching node under the character, and line-of-sight between 2 characters. Furthermore, NWN is a very large game production, so there is no time for dealing with problems such as fixing broken meshes. The game engine has to be able to deal with non-solid or "polygon soup" geometry. Therefore we chose to use a hierarchical overlapping bounding box approach for NWN's collision detection such as AABB or OBB-Tree. We are currently leaning toward just using AABB due to the smaller memory requirements, and the AABB performance seems to be just as good [JGT reference]. AABB requires less work per node since no rotation is required, but the boxes can be larger and overlap more. Given a large percentage of the polygons are already axis-aligned (floors and walls on the NWN tiles) the oriented bounding boxes will not be much tighter than the aligned bounding boxes. Please note that we need to confirm these hunches with more experiments.

NWN uses a similar art production pipeline to MDK2. Similar to the BSP modifier, there is a modifier that computes bounding box hierarchy information.

Future

There is nothing concrete planned for the future of the action oriented player control and the BSP collision algorithm. However, there are some directions that would be interesting.

Games in general could start doing more with being able to manipulate physical objects in the environment. I'd like the ability to rearrange some of the objects while playing a game so I can make myself a better camping spot to get more kills with my AWP.

As I confessed, our BSP production wasn't perfect. I'd like to improve this while still allowing the artists to model as they do now. They appreciated being able to use 3DS Max. I would want to continue to let them make non-convex geometry, but have some better tools to find and possibly fix the problems that can occur. The single big mesh approach from MDK2 was more work and was very unforgiving when errors did occur. It would be better to allow for multiple objects or meshes and let them interpenetrate with each other.

I've already started testing an extension to the BSP collision algorithm with general motion. It works, but more testing is required to measure performance gains over more accurate techniques. Although there can be some inaccuracy, the algorithm may be appropriate when there are many objects, they are fast moving, or when they are of lower priority.

For any references and follow up to this presentation, please see the web page:
http://www.cs.ualberta.ca/~melax