Related Work

Dynamic Simulation:

Certainly work in the area of dynamic simulation is not new. In fact several people are working on various simulation systems throughout the world.

References for work in the area of dynamic simulation can be found in the references sections of the two papers, Impulse-based Simulation of Rigid Bodies and Impulse-based Dynamic Simulation by Brian Mirtich. A more complete listing can be found from the link below:

Current Research in Simulation and Virtual Environments

Ongoing Research in Dynamic Simulation here at Berkeley includes the following individuals.

Parallel Simulation Approaches:

There is also work into the Parallelization of impulse-based algorithms by Dinesh Manocha.

Karl Sims of Thinking Machines Corporation developed a parallel simulation system for use in his research into "Evolving Virtual Creatures". A movie featuring the evolved creatures in the simulator can also be viewed. Sims uses a similar impulse based simulation approach with a simplified collision impulse model. However, he does handle multiple articulated connected bodies in the simulation, which is only now in development for Impulse.

A general discussion of parallelism and locality in simulations is discussed both here and here. Work by Wen and Yelick into parallelizing a digital circuit simulation appears here.

Other approaches to simulating particle systems fall into two main algorithms. These two algorithms are the Barnes-Hut algorithm and the fast multipole method. They both use a similar divide-and-conquer division of space with a quad-tree (in 2D) or oct-tree (in 3D). The basic idea is that the gravitational or other forces of a large cluster of particles, provided it is far enough away, can be approximated by a point mass at the center of mass of the particles. Our simulation does not involve such gravitation systems but instead only local events. That is, local state of our dynamic simulation system is not affected by remote events. This is to our advantage and will be expolited in future developments of the system.

We also examined a paper entitled "Parallelism and Locality in Priority Queues" by Ranade, et al. In this paper a O(log N) time heap removal and insertion algorithm was presented with N the size of the heap. However, our system must update elements deep in the heap which is more difficult to do in such a parallel implementation.

Discussion of fast hierarchical methods for the N-body problem including a discussion of the Barnes-Hut Algorithm and the Fast Multipole Method can be found here and here. These systems essentially group portions of the simulation space as near or distant and can quickly answer queries about relationships between groups of areas in the simulation. More papers on the subject can be found here.

[ Home ]

Eric Paulos / / 10 May 1995