flipCode - Tech File - Kurt Miller [an error occurred while processing this directive]
Kurt Miller
Click the name for some bio info

E-Mail: kurt@flipcode.com

   02/20/2000, Bits And Particles

Good morning, friends. So I was working on a side-project, and one of my tasks was to add the special effects. To me, this meant particle systems. Now I don't really know as such if I'm doing my particle systems "the right way", but I guess it doesn't matter. In this document I'll explain the basics of how I implemented my particle systems, as well as discuss a special effects editor that I was working on. The editor isn't finished as there are a few issues to consider (mentioned later in this document), but I believe it has potential, which is why I wanted to share. Maybe someone out there has time to implement a similar system. I plan to finish it "someday", but I haven't the time just yet. However, before we get into the editor, I'll briefly explain the basics of a particle system.

Put rather bluntly: Particle systems are cool. According to this source (by Jeff Lander), particle systems were introduced by William Reeves while working at Lucasfilm. You can "model" all sorts of things with such systems including explosions, fireworks, smoke, precipitation effects, etc. The list is endless. Particle systems make dealing with collections of "particles" that behave in some way, rather simple. Lets look at one way to do this.

Minimally, I think a basic particle system needs the following methods: create, update, and render. Assuming you have a class with an array of particles, psuedo-code for each method could look like this:

     particle_system :: create()
           for(int i=0; i<num_particles; i++)
               // initialize the properties for this particle,
               // most notably the direction vector;
     particle_system :: update()
           for(int i=0; i<num_particles; i++)
               // update the positions / properties of the particle;
               // for example move it along the direction vector;
     particle_system :: render()
           for(int i=0; i<num_particles; i++)
               // render the particle (for example a "sprite");
You can store as many values for each particle as you wish, such as a color to interpolate, various physical properties, or whatever fits your application. If you plug simple values into the create method listed above, for example a random direction in 3-space, and update along that direction by some constant. When you run this system, it will look like a very basic explosion. Each frame, when you call update, the particles will expand along the direction they were each assigned in create. That's really all a basic system requires. Of course it won't LOOK too great, nor will it be very flexible if you do it like this, so lets look a little deeper.

If you examine the fragments above, you'll notice that the primary controlling factor for each particle, each update, is the direction vector. Sure the amount to travel in this direction is important as well, but for the sake of simplicity, we'll ignore that for now and look largely at the direction. If you know what your particle effects are for, you can easily hardcode various types of explosions using different create methods by setting each particle's direction to be some appropriate vector, and that might serve your purposes very well. There's nothing fundamentally wrong with that. But, imagine for a moment if you wanted to be able to create "any" kind of effect that you could dream up. If you had a way to manipulate the direction vector (other than hardcoding it), this could quickly become a reality. I spent some time thinking about this and came up with an idea for a special effects tool which I soon after built. One that would allow me to define particle systems using functions for directions, so their behavior isn't pre-set. One that would allow me to change directions various times over the entire system's lifetime. One that would make life easy. But unfortunately, as it turns out, one that also has a few problems :). The idea is sound, the implementation is decent, but there are a few things that concern me, which is why I didn't finish it. Yet. Before I explain "what's wrong", take a look at this screenshot:

The original design of the editor looks like this (as you can see, its not completely finished) in that I have a hierarchy as follows:

      Special Effect -> Particle Emitter -> Particle

Each parent containing a list of children. The emitter editor that you see here would let me specify all of the options for the particles to be created. I made it so that you could test run all of the effects in the preview window (the window beneath the emitter window), which made for a nice way to create and test fairly diverse special effects. The two key elements are the direction spawn functions, and the direction changes. The spawn functions are specified, as shown, in infix notation (the notation most people are comfortable with), which are then converted (internally) to postfix strings and "executed" when a particle system is created. For example:

      Infix:   1 + (2 * 3) / (4 + 5)
      Postfix: 1 2 3 * 4 5 + / +

The postfix strings are easy to evaluate using stacks, but this is where the problems crept in. How do I handle these operations "in game"? Here are the options I came up with:
  • "Execute" the strings in the create function - This is the brute force approach. It would take those postfix strings, which explain how to evaluate the direction functions (complete with support for variables) and evaluate the direction for every particle in the create function. It would do that for each direction change as well (an array of direction vectors). When I implemented this version, it worked just fine for decent sized particle systems, where the direction functions were relatively simple/realistic and the direction changes were not too many. The places where it slowed down would be when I put in some incredibly nasty direction function with many nested operations, like sin[cos[sqt[cos[sin[cos[sqt[cos[sin[1.0f]]]]]]]]]], or other things that you generally wouldn't realistically specify. It caught the slowdown because for each nested call, my evaluator made a recursive function call. Further, however, the speed hit ONLY took place when the particle system was first created, and it wasn't very extreme. Each update would still be as fast as the barebones particle system described above, as its still just moving along a direction vector. But when you compare the speed of this create function to the barebones or hardcoded particle system's create function, there's obvious performance that's just begging to be had. I'm pretty picky, so I couldn't really settle for this approach. So next I considered...

  • Pre-calculate everything, to speed up the create function - The reason why the postfix strings need to be evaluated in-game is because they make use of variables. For example, random angles (that you can use more than once in an expression), an iterator from 0 through number of particles, and various other simple variables that are available. If they didn't use variables, precalculating all of the functions would be simple. But since they do, it makes things a little trickier. Storing arrays of these variables, including 'random' ones would let me pre-calculate the direction functions. It would somewhat limit (very subtly) the amount of flexibility gained by defining the functions in the first place, but would greatly speed up the create function. Unfortunately it would also take up quite a bit more memory depending on how many 'random' variables I wanted to store. This approach isn't bad, but I'm still not happy with it. Its pretty damn far from elegant. So what else can I do?

  • Export C++ source code from the editor - This was the last technique that I tried implementing, and it works beautifully from what I tested. The "problem", however, is that its still going back to "hardcoding" the effects. At least that was my initial thought. But then when you consider the reason for a special effects editor in the first place, this makes sense. The editor would allow me to toy around with and create cool effects that I can test immediately and interact with. This is much more productive than the code->compile->run->repeat approach of hard-coding effects. The code generated is pretty much as "fast as it can get", and can easily be tweaked by hand if obvious optimizations are missed. It would be the same speed as if I hand-coded the effects. Another advantage to doing the effects editor this way is that non-programmers would be able to use it to create effects as well. When they have something they think is cool, they could generate the source code and hand it off to the programmer to stick into the effects code base. If I (or you) were to extend on this idea a bit and take out explicitly defining the functions for directions (ie, make it more "interactive" rather than math-based), it would allow for pretty much anyone to play around and make very flexible special effects that could easily be incorporated into the engine. Take this idea one step further still and you have particle plugins. I'll simply write an api for special effect DLLs, which the code for can be generated via the editor. This way the special effects can be shifted around or changed at any time in any way.
  • I'll probably post more about what I decide on when I actually have time to finish the editor. I haven't played with many other particle effect generators, but I can say that the ones I've seen are pretty darn limited, which is why I wanted to write my own. If you have suggestions for making it better or simplifying things while still maintaining a high degree of flexibility, please e-mail me. I'm pretty much always interested in chatting about graphics and game development in general. Also feel free to check out my 3d engine, grain, sometime. I hope you learned even a small bit today or something sparked an idea of your own. I'll leave you now with some further reading on particle systems to explore.

    Further Reading On Particle Systems

    Particle Systems by Allen Martin
    This is a paper by Allen Martin which explains what particle systems are and how they can be used to model things like fire, flocking birds, and explosions. There are several screenshots and examples available as well.

    Particle Systems by Hugo Elias
    This is a short introduction to particle systems and some basic requirements.

    Particle Systems (GDMAG July 1998) by Jeff Lander
    This is an article on particle systems by Jeff Lander, originally published in Game Developer Magazine back in 1998. A PDF version of the article, the executables, and some source code are available from the web site.

  • 03/15/2000 - Miscellaneous Jargon
  • 02/20/2000 - Bits And Particles
  • 09/09/1999 - Interface Design Ramblings
  • 08/16/1999 - Lightmapping Revisited (And My (Re)Introduction)

  • This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

    [an error occurred while processing this directive]