Particle Systems

John Lynch

Computer Science Seminar CS 480-60

2001

Abstract

Particle systems provide a way to create effects of natural phenomena such as fire, clouds, and plants. A particle system is defined as a collection of particles that evolve over time. Particle systems are also used to model scenes that would be too time intensive for an animator. This can include a flock of birds, or a crowd of people.

In traditional computer graphics, objects are defined mainly as points, lines, and polygons¹. The boundary of an object is represented by these primitive surface elements. A particle system is an object whose volume consists of a cloud of primitive particles.

Particle systems are not static their particles change form and move as time passes. Also, new particles are generated into the system and old particles are removed from the system. This represents what are called "birth and "death" events. An object represented by a particle system is not deterministic. That is, its shape and form are not completely specified. Stochastic processes rather than deterministic are used to create and change an object's shape and appearance [5].

Introduction

In the last ten years, special effects in the motion picture industry have relied more and more on computer graphics. This is because computer graphics has evolved to the point where the imagery is "real" to the viewer. In the early days of computer graphics, images, although realistic, had a "computer feel" about them. The world we see around us is too complex to describe mathematically. To give images a natural look, it became necessary to emulate to randomness and unpredictability of the real world. Consider for example a cloud. Even if we knew all the physical principles that govern how a cloud looks and behaves, it would still be impossible to model in a computer all the variables that actually make a cloud look the way it does. If we are interested only in creating an image of a cloud, we can "fake it", since our purpose here is only to fool the eye, and not create a meteorological model.

The need to create imagery of natural objects such as clouds led to the development of particle systems. In this paper we will discuss particle systems and how they create imagery of natural phenomena such as clouds, fire, and explosions. We will also look at other applications of particle systems. We will discuss the basic model of a particle system. Since particles have to behave as individual entities, they have individual attributes that distinguish one particle from another. We will discuss these attributes and how they are arrived at. We will discuss particle dynamics and how it is handled. The principles that describe a basic particle system can be used to model other types of objects. We will discuss an example of this. We will also talk about how particle systems use random numbers.

Basic particle system model

In animation, the illusion of motion is created by rapidly flashing a series of images in front of the eye. To generate each image (known as a frame) the following sequence is performed. First, new particles are generated into the system. Second, each new particle is assigned its individual attributes. Third, particles that have existed past their lifetimes are killed (removed from the system). Fourth, the particles that remain are moved and transformed according to their dynamic attributes. After the previous steps are done, an image (frame) can be created (rendered) [4,5].

At any step of this process, the particle system can be programmed to execute instructions that modify the system. This programming can incorporate any computational model that describes the appearance or dynamics of the object. For example, the transformations and motions of particles could be determined by the solution of a system of partial differential equations, or attributes of each particle could be assigned on the basis of statistical mechanics. This allows us to use models that have been developed in other scientific or engineering fields [5].

For this example of a basic particle system, we will keep to simple stochastic processes as the procedural elements of each step in the generation of a frame of animation. A set of parameters that the model designer has access to, controls the appearance, dynamics, and shape of the particles in the system. These parameters are used to constrain the stochastic processes that randomly select each particle's appearance and movement. Each parameter specifies a range in which a particle's value must lie. This range is defined by its mean value and its maximum variance [5].

Particle Generation

Speed is the change in position divided by time. For example, if I am at point A, and move toward point B, which is 50 miles from point A, and arrive there one hour later, my speed can be described as 50 miles per hour. When dealing with animation, the interval for time is usually defined in frames. When particles are generated into the system, we need to know the number of particles entering the system during a given interval of time. As stated before, this is achieved by using a controlled stochastic process. The number of particles generated is important because it determines the density of the object [5].

Controlling the number of new particles generated can be done one of two ways. The first method involves controlling the mean number of particles generated at a frame and its variance. The actual number of particles generated at specific frame (frame f) is

NParts_f = MeanParts_f + Rand( ) x VarParts_f

where NParts_f is the number of particles to be generated at this frame (frame f) ⁵. Rand( ) is a procedure returning a uniformly distributed random number between 0 and 1. MeanParts_f is the mean number of particles generated at each frame, and VarParts_f its variance [5].

In the second method, the number of new particles depends on the screen size of the object. The mean number of particles is not the mean for each frame, but is generated per unit of screen area. The system can determine the view parameters at a particular frame, calculate the approximate screen area that the system covers, and set the number of new particles accordingly [5].

The corresponding equation is

NParts_f = (MeanParts_saf + Rand( ) x VarParts_saf) x ScreenArea

NParts_f is the number of particles to be generated at this frame (frame f). MeanParts_saf is the mean per screen area. VarParts_saf is its variance, and ScreenArea the particle system's screen area [5].

A frame that has a large number of particles takes longer to render than one that has fewer particles. This method controls the level of detail of the particle system, which minimizes the time required to render an image.

This makes sense when one considers that there is no need to generate 200,000 particles in an object that covers 8 pixels on the screen [5].

The number of particles generated in each frame needs to change over time in order to convincingly model natural phenomena. This is done by varying the mean number of particles generated for each frame. In order to do this MeanParts_f and MeanParts_saf have to become functions of the frame number. This is done with the functions below

MeanParts_f = InitialMeanParts + DeltaMeanParts x (f - f_o) or MeanParts_saf = InitialMeanParts_sa + DeltaMeanParts_sa x (f - f_o)

Here f is the current frame, f₀ the first frame during which the particle system is alive, InitialMeanParts is the mean number of particles at this first frame, and DeltaMeanParts its rate of change. The mean number of particles is specified for the first frame only. The variance controls, VarParts_f and VarParts_saf, are currently constant over all frames. The particle system is controlled by specifying f₀ and either the parameters InitialMeanParts, DeltaMeanParts, and VarParts, or the parameters InitialMeanParts_sa, DeltaMeanParts_sa, and VarParts_sa [5].

Particle Attributes

Each particle that is generated into the system has certain attributes that define its characteristics. The particle system can determine values for the following attributes:

(1) initial position,

(2) initial velocity (both speed and direction),

(3) initial size,

(4) initial color,

(5) initial transparency,

(6) shape,

(7) lifetime.

Initial position

The particles that are in the particle system have to start off at some point. This is known as the initial position. This position is relative to the particle system itself, not to the outside environment that the system exists in. The position of the particle system itself is determined by its origin point. A particle’s position within the system is determined by two angles of rotation about a coordinate system that is centered on this origin point [5].

Another factor that describes a particle’s position is the generation shape of the particle system. Three shapes in the basic system are spherical, rectangular, and circular. The generation shape defines a region about its origin into which newly born particles are randomly
placed [5].

Initial velocity

The generation shape also describes the initial direction in which new particles move. In the spherical system, particles move outward from the origin of the system. For circular, and rectangular systems the particles move upward from the x-y plane, but are allowed to vary from vertical by means of an "ejection angle". The ejection angle is another parameter that may be specified [5].

The initial speed of a particle is determined by

InitialSpeed = MeanSpeed + Rand() x VarSpeed,

where MeanSpeed and VarSpeed are two other parameters of the particle system, the mean speed and its variance [5].

Initial Color

To determine a particle's initial, a particle system is given an average value for (color, transparency, or size), and the maximum deviation from that value. The equations follow the same format as the one given above for initial speed [5].

Particle shape

The shape of the particles in the system can be set by a parameter. In the first particle systems like the basic one in this example used three different shapes - spherical, rectangular, and streaked spherical [5].
In later, more sophisticated systems any type of modeled shape could be used. These shapes themselves could have their own animation. For example the particles emitted could be a flock of birds, where each bird is a particle. The wings on the bird model could be animated to flap.

The attributes described here are for a basic particle system. The actual number of possible attribute control parameters and their variants is dependent on the purpose of the particle system.

Particle Dynamics

A particle in a particle system must be able to move in three-dimensional space and change its color over time. By using a particle’s previous position, speed and direction, the position of the particle in the next frame can be calculated. In more complex systems, an acceleration factor can be used to modify a particle’s velocity. This can be used to simulate the effect of gravity and cause the particles to move in parabolic arcs [5].

Color change of individual particles is controlled by the rate-of-color-change parameter. The transparency and size of particles are controlled in exactly the same way. In our implementation, these rates of change are global for all particles in a particle system, but one can easily imagine making this parameter stochastic too [5].

Particle Extinction

In many applications of particle systems it is preferable to have particles removed from the system. Consider for example, the sparks from a welding torch, as the spark cools it disappears. This would be considered a "death event". In order to model this type of behavior, a particle is given a lifetime. The lifetime of a particle is measured in frames. As each frame is processed, the particle’s lifetime is decremented. A particle is removed from the system (killed) when its lifetime reaches zero. There are other reasons to remove a particle from the system; if the particle is no longer in the frame, if its luminance becomes too low, or transparency to high for to contribute to the image. Also if it strays too far from the origin point of the particle system, it may be killed [5].

Variations of the basic particle system:

Structured particle systems

The basic model for a particle system can be expanded to produce types of models that are nothing like an what we think of as a particle system i.e. smoke, fire, sparks etc. In some particle systems the particles are static. Take for instance a particle system that generates a tree. An algorithm first generates the main trunk, then constructs the rest of the tree by recursively generating sub-branches. This builds up a tree data structure for the model, where each node describes a branch segment [6].

Natural objects such as trees and grass are more structured than say, an explosion. In an explosion, the particles are independent from one another. A tree is a cohesive three-dimensional object. The branches are created as particles systems, and have sub-branches that are themselves child particle systems [6].

Before the recursive branch generation procedure is run, the algorithm stochastically assigns a set of initial characteristics and dimensions. This is analogous to setting the attributes in the basic particle system.
Some of these dimensions are: branching angle, mean branch length, tree height, and first branch height [6].

The values for these parameters are randomly drawn from distributions associated with the tree's type [6]. This is similar to the procedures used to generate the number of particles created for a frame of animation. The following equation determines the height of a tree:

Height = MeanHeight + Rand() X DeltaHeight

where Rand() is a procedure returning a pseudo-random

number uniformly distributed between -1.0 and +1.0.

MeanHeight and DeltaHeight are specified according to the tree type. One parameter may determine the value of another. For example, the global width controls the breadth of the primary branches; this parameter is stochastically set to a fraction of the tree's height according to the equation:

Width = Height X (MeanWidth + Rand() X DeltaWidth )

Non-linear relationships between parameters may be used.

For example, branches taper as the distance from the branch base increases. This can be accomplished with the equation:

thickness = thickness_b X squaroot of(length-d)/length

where length is the total length of the branch and thickness_b is the thickness at its base [6].

Distance between two sub-branches is maintained by a distribution that depends on the tree type and the thickness of the parent branch. The height of the lowest branch is determined by stochastically setting it to a fraction of the tree's height [6].

The parameters of the branch length distribution depend on the dimensions of the species of tree. The height and width define the space the tree takes up, known as a bounding volume. Different tree types have different shapes; conical for evergreens and elliptical for deciduous trees. The angles of branches are determined from a distribution associated with the tree type. The length of the branch is also determined by a function that operates on a mean length value [6].

Sub-branches are generated by a recursive algorithm.

The ratio between the diameters of the parent branch and each sub-branch are found by taking sample from nature. The recursive algorithm stops when a branch becomes too thin, or at some specified stop value for the depth of
recursion [6].

In nature different species of trees have branches that fork in different ways. A probability is assigned to control whether a branch will fork [6].

Particle Rendering

After the position and appearance of all the living particles have been determined, a rendering algorithm handles the task of creating an image. The issues involved with rendering a particle system are as complicated as the rendering of common graphical objects.

These include the following:

Particles can partially, or totally obscure other particles that are behind them. They can also be transparent, so particles that appear behind them can be seen. Whether or not they are transparent, they can cast shadows on other particles. Particle systems may exist and even intersect with objects modeled by surface-based primitives [5].

In the most basic system, particles do not intersect with surface based-modeling primitives. Also in the basic system, each particle is displayed as a point light source. So determining hidden surfaces is no longer a problem. Each particle adds a bit of light to the pixels that it covers. When a particle is behind another particle it is not obscured, but rather adds more light to the pixels
covered [5].

When Objects modeled using other techniques are in the same scene as a particle system, separate images are created for different types of objects, then composited together in a post rendering stage. If the particle system is to intersect or appear behind other objects, the rendering system will create subimages based on the clipping planes of each of the objects in the scene. Then the subimages are combined in the compositing stage [5].

For a more complex system such as a forest, where each tree is a particle system it is not feasible to generate particles for all trees in an image and then perform a traditional visible surface algorithm on them [6].

To render a frame in this situation a painter's algorithm approach is used. The painter algorithm works in this way:

First, all trees in the scene are sorted into a back-to-front order with respect to screen depth. This sorted list of trees is then processed. A stochastic model is generated for each tree in the list. The tree is then shaded and rendered into the image, on top of any trees that have been previously rendered. After the image of the tree is rendered, the data that describes it is discarded. In order to for this process to be accurate, none of the trees intersect. While this is not true for nature, the images generated are good enough to fool the eye. The painter's algorithm that is used to sort the forest of trees is also used on each individual tree to render images of branches that obscure one another [1,6].

The particle system that describes a tree is contained with a space that known as a bounding volume. The bounding volume of the tree is used to define a set of smaller units called buckets that are indexed in relation to the distance (z distance) from the viewpoint of the scene. As a particle is generated, it is transformed into two dimensional screen space and inserted into the bucket list corresponding to its average distance to the viewpoint. Once all the particles have been generated, they are then drawn in back-to-front bucket order (farthest to nearest) on top of any particles that have already been rendered into the image. Any imperfections are very difficult to detect, since the images are so complex to start with [1,6].

Shading Models for Particle Systems

Since the basic particle system is designed to simulate pyrotechnic effects such as fire, sparks, explosions, it requires only simple shading calculations. This is because each particle is modeled as an independent light source [5].

When using a particle system to model things that reflect rather than emit light a more sophisticated shading model is required. This model has to account for ambient, diffuse, and specular shading components. To attain more realistic realistic renderings, the shading algorithm also provides self-shadowing, external shadows, and colored light sources [6].

A single tree may consist of over one million particles. It is not possible to shade each particle exactly, since you would have to calculate whether it is in shadow and determine if it should be highlighted. It is almost impossible to tell whether or not any one leaf should be in shadow. In this case a probabilistic shading model is used. To determine if a particle is in shadow, the particle's position and orientation are analyzed. The probability that it is in shadow is calculated and then a random number is used to decide whether or not to render the particle as if it were in shadow [6].

The branches and leaves of a tree can shadow other parts of the same tree (self-shadowing). A tree can also be shadowed externally by neighboring trees. Where the tree's branches or leaves are exposed directly to sunlight, highlights will occur. This is more likely to occur close to the outer edge of the tree, in the direction of the sun. Shading functions provide ambient, diffuse, and specular components and also approximate both forms of shadowing. The diffuse shading component for a particle changes according to the particle’s distance into the tree from the light source. The diffuse component drops off exponentially as distance increases according to the following equation:

D = c^{-a dd}

The parameter a controls the rate of the exponential dropoff. Random highlights are added by stochastically turning on a specular component whenever d_d is small and the cosine of the angle between the light direction and the branch direction is close to zero [6].

Self-shadowing simulates the ambient controlling shading component. As a particle’s depth (d_a) inside the tree increase, the ambient component drops off exponentially. This depth is independent of the position of the light source. It represents the shortest distance from the particle to a point on the tree's bounding volume in a direction parallel to the ground. To guarantee that there will be some light, even in the deepest interior of the tree, another parameter, A_min, sets a minimum for the ambient. The ambient component equation is:

A = max(e^{-b a da}, A_min)

External shadows are shadows cast by other trees. An approximation technique is used here too, because exact computation of the shadows would be very intensive [6].

The trees that are between the tree being shaded and the light source define a plane that skims the tops of neighboring trees and passes through the light source. If a particle is above this plane, then it is in full sunlight. If this is the case, then the specular, diffuse, and ambient shading components all contribute to the shading calculation. For particles located below the plane, the probability that sunlight reaches them decreases with distance. When a particle is more than a specified distance below the plane, only the ambient shading component is used. A random number is used when particles lie in between, the plane and the specified distance to decide if the diffuse and specular components contribute to the shading [6].

Particle Hierarchy

The particles generated by a particle system may themselves be particle systems. The particle system that generates other particle systems is considered the parent system. Its children are the systems that it generates. When a transformation is applied to the parent system, the child systems inherit the transformation.

The child system also inherits the parent particle system's mean color and its variance. The number of new systems generated in each frame is based on the parent’s generation rate. This parent-child system is represented by a tree data structure [5].

The hierarchy can provide global control on a complicated (parent-child) particle system. A cloud, for example could be produced by many particle systems. Each system would represent a billowing volume of water particles. The parent particle system would group all children (and possibly grandchildren) to control the entire clouds movement [5].

How random numbers are used in a particle system

When modeling an object using a surface based model, aspects that describe the model have to be stored in some way. For example, if we wanted to model a cube, we would have to store information about the cube, its vertices, color, and movement (if animated). Databases have been used to store information about objects. Although when one uses software to model objects, they often don’t "see" a database, but they are in fact using one.

We have seen how by using random numbers, we can generate a large number of particles, with each particle being a unique entity, with its own attributes. If we were to explicitly store the information on each particle in a database, as we do with surface based models, the storage and retrieval requirements would be enormous. In his paper (Particle System — A Technique for modeling a Class of Fuzzy Objects) William Reeves states:

This is possible because the random numbers used are actually psuedorandom numbers. Psuedorandom numbers use a recursive algorithm; the output of an iteration is used in the calculation of the next iteration. This produces a sequence of numbers that have the properties of randomly chosen numbers. To start the generation of random numbers a seed value is used. The data that is needed to describe a particle system is a table of seed values [5,7].

If one wanted to know how many particles are to be generated at frame 175 in a sequence, we need to run through 175 iterations of the function that generates the mean number of particles at frame n, and use that number in the 175^th iteration of the function that calculates the actual number of particles.

This concept can also be applied to the structured particle system. In his paper (Approximate and Probabilistic Algorithms for Shading and Rendering Structured Particle Systems) William Reeves states:

Although these processes generate a great deal of data from a small set of source data (data amplification), we don’t need to store the data. Once we have an image then it has served its purpose [6,7].

Conclusion

We have looked at what a particle system is and how it differs from surface-based models. We’ve discussed the basic particle system model, and how particles are generated and destroyed. We have discussed the various particle attributes in the basic model. Particle dynamics was discussed. We also talked about how particle systems are rendered, and how shading is handled. We looked at particle hierarchy, and finished up with how random numbers allow particle systems to work efficiently.

This paper only scratches the surface on this topic. In my research I found papers that dealt with similar topics such as the creation and rendering of fur and animation of clouds [3]. While these papers did not explicitly deal with particle systems, the ideas in them build on the information presented here. There is no fine line that distinguishes particle systems from non-particle systems. The principles here have been adapted to create animation of machines crashing, crowd movement, and are not limited to what they may be adapted to do.

References

1. Foley, J., van Dam, A., Fiener, S., Hughes, J., (1997). Computer Graphics Principles and Practice. New York: Addison Wesley

2. Fournier, A., D. Fussell, and L. Carpenter, Computer Rendering of Stochastic Models, CACM, 25(6), June 1982, 371-384

3. Kajiya, James T., and Kay, Timothy L., Rendering Fur with Three-Dimensional Textures, Computer Graphics, Volume 23, Number 3, July 1989

4. Laybourne, Kit (1979). The Animation Book. New York: Crown Publishers, Inc

5. Reeves, W.T., Particle Systems-A Technique for Modeling a Class of Fuzzy Objects, SIGGRAPH 83, 359-376

6. Reeves, W.T., and Blau, R., Approximate and Probabilistic Algorithms for Shading and Rendering Particle Systems, SIGGRAPH 85, 359-376

7. Rosen, Kenneth H, (1988). Discrete Mathematics and Its Applications. McGraw-Hill, Inc. New York