Particle systems have been used to model a variety of "fuzzy" objects such as water, fire, grass, fireworks, clouds, smoke, and others. In no work that I am aware of do the particles within the system interact with each other. Instead to simulate the realities which they model, the designers of the particle-system use specific starting configurations, groups of particle systems, and introduce torques, spirals, and other effects to the particle system(s). Sometimes to simulate waterfalls and other fuzzy objects where collisions are necessary, the particles are checked for collision against a small number of external objects and are bounced off of the objects with which they collide. Independent particle systems therefore, do not experience pressure gradients, do not collide with particles within their own system, and only approximate the reality which they represent. The results reported within this paper report on particle-systems that do interact with their neighboring particles. The motivation behind this research is an attempt to allow the interaction of two or more particle systems and to more produce a more realistic model of particle systems.
Section 2 reviews the principles of independent particle systems, section 3 presents the problems and methods used in this research, section 4 discusses the results, section 5 presents the conclusion and possible extensions, while section 6 presents the references.
The other characteristic of particle systems is that there are a large number of particles. Water is technically comprised of billions and billions of H2O molecules, and a particle system likewise represents what it models with many many particles, though not billions and billions. The typical particle system is comprised of thousands of particles where this could range from a few thousand to hundreds of thousands depending upon the resolution needed and the size of the desired image.
Particle systems are used to model "fuzzy" objects, such as fire, water, and other dynamic systems that are difficult to model with conventional methods, mainly due to the wide variations in color and shape even for just one moment in time. To provide a well known example of a particle system take a look at the "Genesis Effect" in Star Trek II: The Wrath of Kahn. A particle system is used to model first an explosion and then the spreading of a fire around a planet. The Genesis Effect used 25-750+ thousand particles throughout the course of the animation.
The obvious and most difficult problem when dealing with an interactive particle system is the large number of particles. To determine collision, engergy exchange, or other interactive effects on any particle X, the particle either must search or sum the effects of all its neihgboring N-1 particles. The problem as most simply and correctly formulated is N squared in complexity. With a hundred thousand particles, however, moving and changing N squared particles per frame of an animation will take too long. A simplification is needed to make the system develop more quickly and is easily justified and arrived at when examining real systems.
In all systems we are concerned with, a particle's dependency on its neighbors is usually proportional to or less than the inverse square of the distance between it and the neighbor. With thousands of particles within a system, it is likely that much less than a hundred particles will actually contribute significantly to the motion or energy level of any particle. Thus, there is but to determine what a "significant" contribution is, the distance where the average particle's contribution will be less than significant, and which particles are within that distance.
The problem is simplified, but to determine which particles are within the distance without any other information than given by the particles themselves would still be an N squared operation. Therefore, it is logical to introduce into the model, the concept of bins. Space is divided into regularly spaced equal volume bins. Each particle is put into the bin corresponding to its location in space. Thus, there are two large lists - one a list of all the particles, and the other an arranged set of bins containing pointers to the appropriate particle.
Ideally each bin would in any dimension be at least the size of the distance whereby a particle is judged to possibly have a significant contribution. To determine the contributions of the neighbors to particle X, the program would need to search only the other particles within the bin that particle X is in and all the particles within the immediately neighboring bins --to deal with particles located near the boundaries of a bin. Since all particles within the threshold distance are guaranteed to be within the space searched, particle X is guaranteed to be modified by all significant contributors.
Though this would work, it is impractical to implement due to memory limitations. The ideal bin size would generally be only three to four times the size of a particle. However to account for all the places a particle might move to during the progression of its life, there will be a large percentage of bins that most of the time are empty. Given this and the fact that there are 3 dimensions which must have bins allocated, result in very large numbers of bins. For instance, taking a hundred bins per each dimension, results in the need for a million bins- more bins than particles. A hundred bins, would also be inefficient for many parts of the particle system where there were large densities of particles-- again the lists to be searched would be in the hundreds per particle negating the effectiveness of using bins. Therefore, a larger number of bins is necessary, but using more bins would quickly exhaust the resources of almost any computer.
To solve this problem we must simplify the model even further losing much of the accuracy that could be obtained with the previous methods. Each bin is now allowed to hold only a number of particles, a temperature,or some other most important data element. Instead of containing a variable size list of particles within the bin, it contains a set small number of informational elements. This results in the loss of alot of useful information and will result in rough approximations that lose the accuracy of earlier models. However, interdependent reactions are still possible, because there is some information available about any particle's local region of space and its immediately neighboring areas of space.
The problem is transformed from one of searching through thousands of particles to one of communication and/or accuracy. By containing only such simple information, spatial relation is lost, as well as specific data, and most importantly identity. Simulation of collisions, movement, and temperature exchange is now possible only as probabilities and is no longer deterministic.
For example, to determine the collision of a particle X moving through space with another particle, we must bound the maximum number of particles in any given region of space. If particle X is attempting to move through a bin, then collision occurs with a probablility equal to the number of particles within the bin divided by the maximum number of particles allowed in the bin. For example, if the maximum number of particles per bin is 30, and there are 19 particles in the bin that particle X is attempting to move through, then there is a 2/3rds chance that particle X will collide.
The communication issue is also a problem that must be resolved. In the efforts to research fire and water combining to form steam, the appropriate physical model is each particle exchanges temperatures and sometimes steam is created and/or sometimes the fire is extinguished. Since the identity of any particle within a bin is lost, a particle that moves from a bin to another bin where it should change state and likewise decrement the opposing particles' states will not have any specific particle with which to interact. Therefore, some means of communicating the change of state is necessary. For example, consider a water particle moving into a bin full of fire-particles.With all the surrounding fire particles, the water particle(s) should transform to steam. But the fire particles should have their temperatures altered as well, or should have some proportion of fire particles die to account for the energy exchanged.
The bins therefore must be utilized to pass messages to particles that should die or undergo a loss in energy. One set of particles is choosen to perform the transition and issue the appropriate message, the other is choosen to listen for the message and take the appropriate action. In the fire and water example, the water is the one which performs the tansition to steam and passes the message, while the fire particles are the system that reacts to the passed messages.
One possible means of message passing and the one utilized in this research is to use the number of particles per bin as the means of message passing. Temperature of given particles and motion vectors can be calculated based on these figures. To differentiate water from fire, water is given a negative count. Where it is obvious that two types of particles are present in a certain bin, it is assumed that fire extinguishes water with a certain ratio of fire particles to water particles. If the water particles transform, they decrement the number of particle bins by the number of fire particles extinguished. Before the fire-particles move again they note the change and that percentage of particles will on average die.
For example, take particle X. It moves into a bin and after all other fire particles have moved it notes that there are 15 particles including itself in the bin. During the water movement portion of the frame, 3 water particles move into the same bin and are considered to exchange heat and vaporize with the fire particles. Say that it takes two fire particles to vaporize one water particle, then 6 fire particles are extinguished, while 3 new steam particles are created. The final bin count is 9-- steam is counted as a neutral particle. The final position of all particles in the frame is output and processing for the next frame begins. Each fire-particle is searched for those particles that should have died. When particle X is reached (or any of the fire particles in the bin) it notes that there are now 9 particles in the bin when their used to be 15. Thus, 6 out of the 15 particles must have died. The particle picks a random number between 0 and 1 and if it's number is less than 6/15ths, it's number is up and the particle "dies."
It can happen the opposite way as well, that a fire-particle moves into a bin populated by water particles and should extinguish itself as well. The water particles also need to know their state after all water particles have moved, so that they will also be killed off in the appropriate situtation.
A byproduct of the fact that probabilities are used to kill of particles, is that the bin counts are accurate only on the average. As time passes however, local error and changes in the system based on the error could accumulate. Therefore it is necessary to recount the number of particles of any type at the end of each movement phase. This in some ways doubles the time required to animate any interacting particle system, but is still linear in time and better than N squared. Thus, the steps required to interact 2 particle systems with message passing can be generalized as follows:
This problem encountered during the research can either be side-stepped by ignoring interim bins completely (as is done in this research) or perhaps can have a damping factor applied proportionate to the number of collisions that might have occurred. Another difficulty is that there are even more parameters that must be tweaked into place to produce an image that approximates the reality and doesn't approximate some alterante reality-- where flames progress upwards in very defined bands for instance.
An implementation of an interdependent fire system was investigated and can be seen by the results below. The fire particle system image was originally created with a 200,000 particle-system. attempted to use 150,000 particles in the provided MPEG. The particles are created during frames 1-30 and after that are created from the particles that have already died. The image was rendered using DX with a color map and an opacity map. The animation took approximately 11 minutes to create running on a RISC 6000 processor with 128 MB of memory. However, it has been noticed that due to the bin limitations many of the particles go unused and essentially only slightly more than 50,000 particles are being used. Using only 50,000 particles (due to the current initialization sequence of the program) a slightly less full animation is produced, but is comparable to the original and only takes 5.4 minutes to create.
In the provided animation, a particle's temperature is based on the number of particles within the same region of space, while it's motion vector is determined based upon the density of particles immediately within its own space as well as those bins that immediately neighbor the space. A damping factor is applied to the motion in the plane that produces a circular cross-section when no particles are collided, whereas in the vertical direction changes in motion are based on temperature. Overall, there are 21 parameters including bin sizes that may be modified. It is also important to note, that if the bin size is selected to be too large, visible artifacts will be generated.
The animation is also present as an MPEG.
There are some artifacts present in the animation of the flame that I am not quite yet sure why they are there. In the first frame of the animation provided, a top view is provided. It is possible to see from this top view a criss-cross pattern that is an obvious artifact from using the bins and/or some combination of the motion mechanism, although I am unsure as to why this is the case. Also, the flame tends to pulse from one frame to the next which is something that would preferably not occur- I am unsure what is causing the oscillatory motion.
There is another benefit to using bins with an interdependent particle systems, parallelization. As opposed to passing particles and all their associated information across bin boundaries, only the information contained by the bins need be passed. This can save (given the amount of information each particle must pass as well as the fact that there can be a good number of particles per bin) up to more than 100 times the amount of message passing that needs to be done. Thus, it should be possible to parallelize the application.
One other effect should be noted. In independent particle systems, groups of particle systems can be lessened or local processing abandoned altogether once sufficient information for a given area of the output area has been determined (e.g. there is no reason to use a thousand particles to represent a section of the screen only 10 pixels by 10 pixels wide). In an interdependent particle systems, this is not the case. The entire process of the particle system is dependent upon the presence and number of its nearest neighbors-- stopping part of the particle system will eventually translate its effects to neighboring parts of the particle system that are still moving, with unknown consequences. Thus, some of the optimizations that are possible for independent systems, are not necessarily possible with interdependent particle systems.
There are many aspects of interdependent particle systems where research could still be done. For instance, investigating the interactions used on independent systems to achieve the flickering of a flame by adding spirals or clustering particles. Or trying to simulate these effects by adding an air particle system to the field to simulate the convection of air. Starting configurations that change over time and are not based on some random distribution of some preset starting configuration, but perhaps based on preset data volumes. It would also be interesting to see the results of a wall of fire, or some other configuration of flames modeled on a parallel processor.
"Particle Systems-- A Technique for Modeling a Class of Fuzzy Objects", William T. Reeves, ACM Transactions on Graphics, Vol 2, No 2, pp 91-108
"Particle Animation and Rendering Using Data Parallel Computation", Karl Sims, Computer Graphics, Vol 24, No 4, pp 405-413