Discrete Event Simulation

This is a snapshot from a real-time discrete event physical simulation of a room filled with 400 bouncing spheres and three fixed spheres (the large ones in the middle). The simulator can easily handle up to a few thousand spheres, though the rendering, especially with reflections and shadows enabled, tends to get bogged down. The snapshot below was taken on a GeForce3 with AGP disabled.

This program uses a simulator similar to the one described by Brian Mirtich in his PhD thesis. In this case, the balls all follow a simple ballistic path, subject only to the force of gravity, which makes it easy to compute their position at an arbitrary time from a closed-form function -- namely, a parabola. I compute collision times with the walls and floor by intersecting their respective planes with these parabolas. Since the balls, other than the three fixed ones, are all subject to the same force, gravity, they are really only moving linearly with respect to one another so it is nearly trivial to compute their potential collision times, if any. When two balls have different accelerations, such as between a fixed and a ballistic ball, I make a series of conservative potential collision tests based on when the ballistic ball first hits a plane separating the two. This event prediction is similar to what Mirtich describes in his thesis.

At the start of the simulation, each dynamic object is tested for potential collisions against every other object and only the found collisions are entered into an event queue. As the simulation proceeds, an event is popped off the queue, the physics of the collision is resolved, any other events in the queue involving the prior motion of those two balls is removed from the queue, and then those two balls are each tested against all other objects to insert new collision events into the queue.

This simulator is a part of Infinite Fun Space, my thesis work on on-the-fly procedural landscape generation.

Infinite Fun Space

My home page

Steven C. Dollins

Last modified: Mon Feb 18 19:52:04 EST 2002