• An emitter that generates new particles and adds them to a particle set
• Particle sets that contain a large group of particles that can be submitted to the renderer. These are organized in a way relevent to the rendering and processing strategy - by room, volume cell, or however they are to be organized. They usually contain a large array with safeguards to make sure that no more than the maximum number of particles is added to that set, and whenever a particle is removed, the last entry is copied into its slot and the current quantity reduced to keep all active data together. New particles are always added at the end.

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:

• Position - its position
• Old position - its previous position. So far, for me, this is only needed to detect passing through a portal, which isn't absolutely necessary.
• Velocity - how fast is the particle travelling and in which direction?
• Gravity - how does the particle accelerate on each axis?
• Size - how large is the particle?
• Alpha - how much is the particle "there"? Used to fade it in or out.
• Size and Alpha adjustments - to guide how size and alpha change
• Texture or Texture loop - some way to define the texture the particle is to be rendered with, or a loop with time values to animate it
• emitter - this is a flag stating that the particle gives off light and is not affected by light sources (fire and sparks would be emitters, but not smoke or water)
• Animated flag - flag telling the animation to skip this particle, it's either new or has already been animated (see below)

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:

• Emitters can move to a different room - this isn't such a big deal, it just means that when the emitter makes more particles, they will be added to that room's particle set instead.
• Particles can move to a different room - this is a biggy. We don't want to calculate too much on each particle and slow down the algorithm

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:

• When a particle moves, I need to figure out if it's still in the same room
• I can submit the position of the particle to the octree and get the cell the point resides in
• Each cell has a list of rooms that touch it
• If the cell only has one data element, and it's the room the particle is currently in, then I'm done. Otherwise, I assign the particle to the single room in the list. Once again, done.
• There are multiple rooms in the list, so the particle could be in any of them.
• If the point has passed through a portal in the current assigned room, then I can assign the particle to the room on the other side of the portal, and I'm done. This may result in the occasional inaccuracy (it could pass through multiple portals and be in a different room entirely), but not often enough to be a problem.
• I will then check to see if the point is still in the room it was assigned to. If so, I am done. I save this step for near the end since I will be calculating off multiple surfaces. I am gambling on the chance that one of the above conditions was met first.
• I will then check to see if it's in any of the other rooms in the cell's list. When I find one, I assign the particle to that room, and I'm done. If no rooms fit the criteria, I get rid of the particle.

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:

• The list of rooms to be rendered is assembled by the portal engine
• For each room to be rendered:
  • Emitters are animated, creating new particles.
  • Particle sets are animated (new particles from emitters are skipped)
  • All particles are evaluated to determine the correct room to be placed in.
• Each room is rendered along with its particles in sequence, back to front (particles in a room still need to be sorted, see below)

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:

• As I already stated, rendering groups of particles with each visible room back to front can create small problems, notably the partial erasure of particles that lie exactly on a room border. Closer room walls will erase the particles, since they have no depth information written. It may be more accurate to render all non-alpha walls, then submit the particles and alpha walls together into some sort of scene graph, and render them back to front.
• Emitters can interpolate the position of new particles by carefully tracking elapsed time and using that along with the emitter frequency, current position and old position to calculate where new particles should be placed. This way, if you have a slow frame rate with a fast producing emitter, your particles will still be placed uniformly. However, be very aware of when you alter the old position of the emitter. I do it ONLY in the emitter animation routine, after the emitter itself is done creating new particles. When I create a new emitter (whether by allocating a brand new one, or retrieving one from a deleted list), I'll initialize the old position to some arbitrary value, and that is the only other place I set it.
• Put in safeguards to make sure the emitter and particles are only animated once in a render. Especially in a map with mirrors, it's very likely you'll parse the emitters and particles multiple times for rendering, but should only animate them once. A last time animated value serves this purpose well.
• Particles could be animated based on current time and last time animated. That way, for particles you haven't animated for a long time, when you finally aniamte them again, they will consume their time they way they would have had they been animated the whole time. The emitters should only be animated on elapsed time in the last game tick - otherwise, if an emitter isn't animated for a long time and you suddenly are about to render it again, it will produce and animate all the particles it would have in all that time.
• Even though particles are only animated in visible rooms, the emitters should be tagged to move with any objects they are attached to, even in rooms that aren't visible. This is because an object in a room that isn't visible could move to a visible one, and the emitter's room has to be evaluated every time its position changes to make sure it moves with the object into the visible room.