Dynamic Plane Shifting BSP Traversal

Stan Melax - 2001

The downloadable zip file: BSPdemos2001.zip contains two technical demos (melaxbsp.exe and melaxcsg.exe) that show interaction and geomod using bsp trees. See the readme, help, and cfg files in the zip file for more information about the demos. Try hitting the 'b' key when running the CSG demo to have some fun.

The collision detection of swept volumes is done using bsp plane shifting and the csg boolean operations is done by tree merging. The academic paper Dynamic Plane Shifting BSP Traversal, from GI2000, explains the collision technique for moving objects. A 2001 gamastra article elaborates on the collision detection in video game settings. Apparently, there's a gdc presentation (but the slides aren't visible).

  • GI Abstract: Interactive 3D applications require fast detection of objects colliding with the environment. One popular method for fast collision detection is to offset the geometry of the environment according to the dimensions of the object, and then represent the object as a point (and the object's movement as a line segment). Previously, this geometry offset has been done in a preprocessing step and therefore requires knowledge of the object's dimensions before runtime. Furthermore, an extra copy of the environment's geometry is required for each shape used in the application. This paper presents a variation of the BSP tree collision algorithm that shifts the planes in order to offset the geometry of the environment at runtime. To prevent unwanted cases where offset geometry protrudes too much, extra plane equations, which bevel solid cells of space during expansion, are added by simply inserting extra nodes at the bottom of the tree. A simple line segment check can be used for collision detection of a moving object of any size against the environment. Only one BSP tree is needed by the application. Successful usage within commercial entertainment software is also discussed.