Physics Simulations with BSP Trees

Efficiently detecting collisions in a 3D environment.

Purpose

I programmed this as a final project for my computer graphics class. I learned a great deal of 3D math (affine transforms and the like), as well as a great deal about simulation with discrete steps and frame rate management (which I have seen others, even retail games, do very poorly). In fact, I have been using it to develop a scheduler which can manage frame rates, network communication, and other tasks on my curveball project.

Methods

This simulation uses Binary Space Partitioning (BSP) trees to simulate a 3D environment which moving objects can collide with. Collision detection using BSP trees is very efficient.

One interesting problem I encountered while creating this program is that the ball would not stop bouncing, even after applying a dampening effect of 10% or so. Although reducing the velocity by 10% after every bounce is not exactly a realistic physical model, I figured eventually the velocity would get so low it would be effectively zero. However, this was not the case. Because the physics simulation is stepped a discrete amount over each frame, even if the ball starts at 0 velocity gravity will impart to it a constant amount of velocity on the next frame. For example, if the step time is t the ball will get a downward velocity of t * 9.8m/s. This velocity would then cause a collision with the plane below the ball, and it would be bounced up by some amount at a velocity roughly (t * 9.8) / 2 * .90 The ball would thus appear to continuously jiggle. To solve this problem, I introduced a self-regulating equation formulated with the use of a 3D graphing program. Given the values of t (the time per physics frame) and the acceleration of gravity (-9.8m/s, or an arbitrary value) this equation determines what dampening factor to use, and what the threshold velocity is below which the velocity should be explicitly set to zero. In a more sophisticated application, once an object reaches the threshold of movement amount, it can be frozen and removed from physics processing until another object interacts with it.

Another interesting problem that the use of offsets for collision detections using geometric shapes (described in the PDFs below) is that of beveling. If you use the number keys to see the presets, you may notice that the sphere sometimes appears to float in midair on top of an invisible object. This is a side effect of plane offsets or "dynamic plane shifting", and can be remedied by automatically beveling acute angles of plane intersection. Unfortunately, I haven't gotten around to implementing that kind of functionality.

See also:

Dynamic Plane Shifting BSP Traversal by Stan Melax from BioWare
Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering by Samuel Ranta-Eskola (Master's Thesis)

Files

Keyboard Shortcuts