BSP Collision Detection As Used In MDK2 and NeverWinter Nights

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.

	Comparison of three methods of collision detection: regular BSP collision (labeled Ray), spherical offset, and cylindrical offset.

 

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

________________________________________________________

Discussion