Gamasutra - Features - "BSP Collision Detection As Used In MDK2 and NeverWinter Nights" [03.22.01]

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.


				\|\|\|\|

________________________________________________________