Particles

Particles make up all the little floating effects in many video games. They can be sparks flying away from an explosion, or animated fire textures rising up from a flame and turning into smoke.

Usually a particle system is made up of two parts:

The emitter

The particle emitter usually has some sort of particle generation frequency set up (the lower it is, the faster particles are made) and a set behavior to assign to the particles. An emitter can be told to make particles to imitate a torch flame, bonfire, explosion, or water fountain. Its job is to give the particle everything it needs to complete its behavior on its own, and let something else handle the particle from then on.

Emitters must have a reference to the particle set they are tagged to add particles to.

The particles

Particles usually have the following data elements:

Using all this information, a particle can be entirely animated without any help from other objects. This is beneficial since particles could be moved from one particle set to another, depending on rendering or processing strategies.

Particles are usually rendered without any depth information to speed up rendering. This requires that they generally be drawn after everything else that is solid. As much as possible, they should be sorted and ordered so that other alpha surfaces (such as walls or or see-through objects) properly blend over the far ones, and the closer particles drawn last so that they properly blend over everything else.

It's a good idea to set up a rendering routine specifically designed to handle a single array of particles, minimizing texture state switching as much as possible.

A typical problem

In my portal engine, I want to be able to render groups of particles with each room. Since the rooms are properly sorted back to front, it stands to reason that particle sets tied to each room will also ultimately be rendered back to front. There are a couple of challenges with this, however:

Since in my portal algorithm, I'm using an octree to divide the map into sections for faster data parsing, I figured I could use it to my advantage, which I have yet to implement, but I will post my findings here. (update: so far it's looking very fast. A few hundred particles didn't phase the framerate at all)

The basic idea is this:

This sequence of steps, I believe, reduces the amount of calculations on particles to a minimum. Again, I'll try it and post my findings. (update: it works, seemingly very well).

Animation of particles

It's impractical to animate all emitters and particles in a map. Usually, only the emitters and particles in visible rooms are animated. The proper sequence of events should go as follows:

Since it is possible in a portal engine for emitters and particle sets to be parsed twice (because of mirrors), it's important to only animate them once. Even in the case of moving particles from one room to another, we don't want the moved particle to be animated again, either. So particle sets and emitters will have a lastTimeAnimated value, and moved or new particles will have an animated flag that will be cleared when they are parsed. Only the particles with a cleared animated flag will be animated. This should ensure that all rendered emitters and particles are only animated once.

It's still possible in some circumstances to get orphaned particles. Say a torch is flung near a door, and its particles are accumulating in the next room (the emitter in this room is expelling particles into the other room), but the room isn't visible. Something else causes the torch to disappear. After a few moments, the viewpoint moves in view of the other room, and for a few seconds, fire particles are seen rising up and disappearing where the torch was. The current setup above can't avoid this possibility, since the animated flags were set on the particles as they were moved into the other room. If we were to put a lastTimeAnimated value on each particle and animate them off currentTime, the torch particles would have been immediately consumed when they came into view. But I'm not sure I want to put that much data at the particle level. The less data that is there, the better.

Sorting particles

Even though you've managed to render particle sets in the correct order, you still need to make sure you are rendering the particles in each set in the correct order. To make them look right, they should be rendered back to front, although some strategies might allow additive blending to circumvent the need.

In any case, should you need to sort them, one possible method is a binary tree sort. I won't go into too much detail here, suffice it to say you submit each particle to the binary tree and add them on the left or right side based on sorting criteria, and after you're done, a quick parse of the tree allows you to render them back to front.

Bear in mind that it is highly likely that after a particle set is sorted in this fashion, it will remain properly sorted for a few frames of rendering. So if you were to put the particles back in the set sorted, you may reduce how often you need to sort them. This is also something I'll need to experiment with. I've heard that a bubble sort is very fast for nearly sorted particles. I'm not sure what sort is best for badly sorted items at this time - possibly a radix sort.

As a final note, you'll need to sort particles multiple times in a render if you have mirrors, so be warned.

Bugs

A remaining problem is that since I render my particles with rooms back to front, and I don't write any depth information with my particles, particles viewed along the borders of rooms will not render or be partially erased.

Other observations

After finally getting my particle system working the way I like, I have a few parting thoughts: