Particle Systems

by Allen Martin

Introduction

The term particle system is loosely defined in computer graphics. It has been used to describe modeling techniques, rendering techniques, and even types of animation. In fact, the definition of a particle system seems to depend on the application that it is being used for. The criteria that hold true for all particle systems are the following:

This summary will present three different particle systems, two of which were created by Reeves [REE83] [REE85] and one created by Reynolds [REY87]. In addition, images from some example particle systems based on Reeves initial model [REE83] will be presented.

Using Particle Systems to Model Fire and Explosions

Reeves initially used the term "particle system" to describe a method he used to create a sequence of images for the move Star Trek II: The Wrath of Khan. The effect he was trying to create was that of a bomb exploding on the surface of a planet and fire spreading out from the point of impact to eventually engulf the planet. Each particle in this system was a single point in space. The fire was represented by thousands of these individual points. Typical polygonal rendering methods create objects with straight edges, but representing the fire by thousands of points gives the fire a "fuzzy" shape. Reeves calls an object made up of particles a fuzzy object.

Each object in Reeves particle system had the following attributes:

Particle Life Cycle

Each particle goes through three distinct phases in the particle system: generation, dynamics, and death. These phases are described in more detail here:

Rendering

When rendering this system of thousands of particles, some assumptions have to be made to simplify the process. First, each particle is rendered to a small graphical primitive (blob). Particles that map to the same pixels in the image are additive - the color of a pixel is simply the sum of the color values of all the particles that map to it. Because of this assumption, no hidden surface algorithms are needed to render the image, the particles are simply rendered in order. Effects like temporal ant-aliasing (motion blur) are made simple by the particle system process. The position and velocity are known for each particle. By rendering a particle as a streak, motion blur can be achieved.

Using Particle Systems to Model Trees

Reeves used the particle system approach to model trees in the animated short movie The Adventures of Andre and Wally B. [REE85] Each tree was created by using a particle system, and the position of the trees within the forest was also controlled by a particle system. The major enhancement over the previously mentioned particle system is the rendering algorithm used. In The Adventures of Andre and Wally B. a more traditional rendering method is used, and the previous simplification of rendering the particles in order and making them additive is not used. In addition, the generation shape of the particle system is not fixed, but is dependent on the current state. For example, leaves may only be created near the ends of branches.

Tree Particle System Rendering Technique

The particles of the trees are small circles used to represent leaves and lines used to represent branches. A more traditional rendering technique is used that is based on the painter's algorithm. Because of the large number of particles, standard lighting and shadow calculations are computationally prohibitive, so more reasonable solutions must be made. For the same reasons that shadows could not be perfectly generated for particles within the trees, the shadows that the trees cast on the ground must also be approximated. The way this was done was by rendering an image of the trees from a viewpoint on the ground. This image was then texture mapped to the ground as a "shadow map." Points in the image that correspond to trees were rendered as though they were in shadow.

The actual rendering algorithm used to draw the trees was a modified painter's algorithm. The first assumption used by this algorithm is that the bounding volumes of no two trees intersect, so each tree could be rendered independently. This cuts down on the number of particles that have to be loaded simultaneously. In addition, instead of simply depth sorting the particles, they are placed in a number of depth sorted bins. Inside each bin the particles are simply rendered in order. This saves time because an exhaustive sort of all particles does not have to be made. Errors caused by rendering particles in order inside the bin are masked by the large number of particles.

Using Particle Systems to Model Flocking Birds

The third example of using particle systems was used by Reynolds to model the behavior of birds moving in a flock [REY87]. In this particle system the particles are used to represent "boids" (short for bird-object). This use of a particle system has a few differences from what was used by Reeves:

Boid Behavior Model

Reynolds used observation of real flocks and research of flock behavior to come up with three primary needs of a boid. The boid's movement is made by combining the impulses that are generated from these three needs. If each need produces a vector that represents the direction and speed it thinks the boid should move in, it may not be adequate to simply average these vectors. In the worst case, these three vectors may be pointing in completely divergent directions, and the net movement would be zero.

=====================================================================

Examples

Here are a few particle system examples that I put together to demonstrate the process. These examples demonstrate the algorithm presented by Reeves in [REE83]. Each of the particles maps to a single pixel in the output image. The particles are translucent, with the color of multiple particles that map to the same pixel being additive. In each example the particles are given an initial upwards trajectory and are acted upon by gravity to give an overall parabolic path. Except for the example where there are multiple generation points each of these sequences was created using 20,000 particles and is rendered to a 256x256 MPEG animation. The number of frames in each animation varies from 20 to 50.

=====================================================================

References

[REE83]
W. T. Reeves, "Particle Systems - A Technique for Modeling a Class of Fuzzy Objects", Computer Graphics, vol. 17, no. 3, pp 359-376, 1983.
[REE85]
W. T. Reeves, "Approximate and Probabilistic Algorithms for Shading and Rendering Structured Particle Systems", Computer Graphics, vol. 19, no. 3, pp 313-322, 1985.
[REY87]
C. W. Reynolds, "Flocks, Herds, and Schools: A Distributed Behavioral Model", Computer Graphics, vol. 21, no. 4, pp 25-34, 1987.
=====================================================================

[Return to CS563 '95 talks list] =====================================================================

Allen Martin / amartin@cs.wpi.edu