Designing an Extensible Particle System using C++ and Templates
by Kent "_dot_" Lai

Introduction

Fire, fountains, explosions, even stars. All these special effects can be implemented as particle systems. Yet they operate differently, and at times make you even wonder if they can even be the same code. This difference is the result of an extensible particle system, with which a simple change of parameters can just bring you an entire new visual. This article will bring to your attention some decisions you have to make while designing your own particle system, as well as introduce to you an extensible, possibly robust design.

This article requires some basic knowledge of C++ Templates, as well as knowledge of the Policy/Containment/Aggregation pattern.

Particle Properties

Before we delve into the actual particle system design, let's begin with the building block of all particle systems. The particle itself. A particle implementation could have the following properties:

Other optional properties would be acceleration of each individual particle, color step of each particle (changes in color along each step of time line), size step (same as color step), and possibility some angles for rotation as well.

For the purpose of this article, we will design a particle structure with the basic properties,

struct Particle {
  Point3D d_ptPos;
  Vector3D d_vVelocity;
  Color d_cColor;
  Size3D d_szSize;
  int d_nLife;
};

where Point3D, Vector3D, Color and Size3D can be substituted with your favorite 3D Geometry library structures, as well as int for life to float.

Inheritance or Parameterization?

Now that we have the basic particle defined, we have to make decisions to allow for an extensible system. The system should be able to operate on the default particle structure, yet allowing you at the same time to support additional properties. There are a few approaches.

One approach would be via inheritance of the particle structure (providing virtual functions like Init and Process for each particle. This approach, however, is costly, as each process and initialize of particle is via a virtual table lookup, and would amount to a huge, unnecessary overhead with the many particles.

Another approach would be to subclass the particle system, or provide composition/aggregation. This approach is slightly better, except there still is a function call involved (for composition at least. You could argue you inline the function calls for the parent particle system's Init and Process, and always work with the derived class)

Another approach would be via templates

My preferred approach, though, is via templates, with particle as a template parameter.

Most of the time, you already know what behavior each particle system need to exhibit before run-time. However, templates would run into issues like additional features/actions to act on each particle, which can be easily solved with the above two approach, with the extra overhead cost.

This article will, however, teach you how to use a template approach, yet able to resolve those two issues, using the Policy concept [Modern C++ Design, Chapter 1]. A policy, as its name suggests, describes a set of rules and workings pertaining to a specific issue. It's a design pattern, and as such, could be used as a composition pattern, but its true power shine in templates usage. For more on policy pattern, I would recommend getting Modern C++ Design, by Andrei Alexandrescu.

So let's start building the template particle system!

Particle System, a Brief Design

Let's decide on the few essentials of a particle system. Should we copulate the rendering to the particle system? We could, but they would actually 'kill off' the extensibility, as the particles have to be rendered “That way”. We could provide a Renderer object to the system, and pass the particles and the number of active particles to the Renderer's Render function. However, doing so might involve more function calls, and kill off the chance to optimize the rendering (For example, you might have a bunch of particle system which you could actually batch together, and use a shared vertex buffer and texture)

Next would be the data storage of the particles. There are again, two approaches. The first one would be dynamic memory allocation, where you allocate upon demand. You can either use a link list, or a vector. However, being dynamic, the cost of each allocation calls are high, but this approach scales, limited only by the memory resource of the running machine. But you wouldn't want to be able to scale to this extend, because the CPU would not be able to perform the processing of so many particles, and yet be able to render them at real-time. Thus you would have set a limit cap. Again, this can be determined before run-time. So to speed things up, we simply set aside the memory needed for the maximum number of particles before run-time, on the local heap.

Next we would need to have a way to add particles to the system, as well as process them. Thus we introduce two functions, Emit, which emits N number of particles at a given position, and Update, which process all particles in the system, killing off those which have lived to their max life.

Additional helper functions would be ParticlesCount which gets the current number of particles in used, MaxParticles which is the limit of the system, Clear which clears all particles used, as well as GetParticles, which returns the particles. With GetParticles, you can then perform additional processing (if you wished, though I see no reason why), as well as render the particles.

Handling the Initialization and Processing in an Extensible way

Now we come to the crucial part. How can we design the particle system, so that it can have initialization code as well as processing code plugged in before run-time, yet doesn't require us to recode the particle system every time? The answer, apparently, lies in Policy Pattern. We can narrow down this into two Policy, InitializePolicy, as well as ActionPolicy.

The InitializePolicy interface merely requires the definition of one interface, a function that takes in a particle object and initializes it. In this case, we chose the operator(). The same is required for the ActionPolicy, but they require an additional PrepareAction function. PrepareAction is a one time call during each Update of the particle system, as opposed to the operator(), which gets called for each particle.

Does that mean you need to write a Policy for the different particle system you might have? And function call for each particle seems as expensive as aggregation/composition? Well, the answer will be revealed later on how we can work around it. But for now, here's the listing of the particle system class.

template <size_t size, class InitializePolicy, class ActionPolicy, class ParticleType>
class ParticleGroup {
public : 
InitializePolicy d_InitializePolicy;
  ActionPolicy d_ActionPolicy;

  explicit ParticleGroup() throw():d_nCurrentCount(0) {}
  ~ParticleGroup() throw() {}

  inline void Clear() throw() {
    d_nCurrentCount = 0;
  }
  inline const ParticleType* GetParticles() const throw() {
    if ( ParticlesCount() == 0 ) {
      return 0;
    }
    return d_arrParticles;
  }
  inline const size_t MaxParticles() const throw() {
    return size;
  }
  inline const size_t ParticlesCount() const throw() {
    return d_nCurrentCount;
  }
  void Emit(const size_t& i_nAmount, const Point3D& i_ptPosition) {
    size_t nAmount = i_nAmount;
    //  exceed limit?
    if ( ( ParticlesCount() + nAmount ) > MaxParticles() ) {
      nAmount = MaxParticles() - ParticlesCount();
    }
    if ( nAmount > 0 ) {
      //  create the particles
      size_t nCnt = d_nCurrentCount;
      d_nCurrentCount += nAmount;
      for(; nCnt < d_nCurrentCount; ++nCnt) {
        d_arrParticles[nCnt].d_ptPos = i_ptPosition;
        d_InitializePolicy(d_arrParticles[nCnt]);
      }
    }
}
  void Update() throw() {
    d_ActionPolicy.PrepareAction();
    //  kill off all dead particles
    for(size_t nCnt = 0; nCnt < d_nCurrentCount; ) {
      d_ActionPolicy(d_arrParticles[nCnt]);
      if ( d_arrParticles[nCnt].d_nLife <= 0 ) {
        //  dead, move last particle to this particle
        d_arrParticles[nCnt] = d_arrParticles[d_nCurrentCount - 1];
        //  decrease particle count.
        --d_nCurrentCount;
      } else {
        //  move to next particle
        ++nCnt;
      }
    }
  }
private : 
  ParticleType d_arrParticles[size];
  size_t d_nCurrentCount;
};  //  end of class ParticleGroup

Defining the Initialization Policy and Action Policy

So how can we go about designing the Policy objects? We could start by building a complete Policy object, which defines policies for color, size, velocity, position, and life.

Again, we choose to allow for extensibility and go with templates, thus allowing different policies to be plugged in for different cases. Let's say you decided to do an explosion which requires spherical velocity movement. You simply specify a SphericalVelocityInitializationPolicy as the template parameter for VelocityPolicy, and it can initializes the particle's velocity to move in spherical motion. And what if you wanted to add a gravitational pull? You can simply plug in a GravitationalPolicy as a VelocityPolicy as well, and it gets processed. Color fading? Wind? Your effects are only limited by the number of policies you have at the moment. If you need another effect, you can simply code another one, which can be reused and plugged in for future uses.

template <class ParticleType, class ColorPolicy, class SizePolicy,
          class VelocityPolicy, class LifePolicy, class PositionPolicy>
class CompletePolicy {
public : 
  PositionPolicy d_PositionPolicy;
  ColorPolicy d_ColorPolicy;
  SizePolicy d_SizePolicy;
  VelocityPolicy d_VelocityPolicy;
  LifePolicy d_LifePolicy;

inline void PrepareAction() throw() {
    d_PositionPolicy.PrepareAction();
    d_VelocityPolicy.PrepareAction();
    d_SizePolicy.PrepareAction();
    d_ColorPolicy.PrepareAction();
    d_LifePolicy.PrepareAction();
  }
  inline void operator()(ParticleType& m_Particle) const throw() {
    d_PositionPolicy(m_Particle);
    d_ColorPolicy(m_Particle);
    d_SizePolicy(m_Particle);
    d_VelocityPolicy(m_Particle);
    d_LifePolicy(m_Particle);
  }
};  //  end of class CompletePolicy

Note that the calls are hinted to be inline, so they can replace those function calls in particle system, thus reducing the possible function call overhead.

Individual Policy

Individual policy will follow the similar design of CompletePolicy, though you can omit the PrepareAction function call for InitializePolicy. Below are three sample policies, one for Life, one for Gravity, and one essential Move, which moves the particle to their new position(as a PositionPolicy).

template <class ParticleType>
class LifeInitializer {
public : 
  int d_nLifeMin;
private : 
  int d_nLifeRange;
public : 
  // Sets the maximum life range.
  inline void SetLifeRange(const int& i_nLifeMin, const int& i_nLifeMax) throw() {
    d_nLifeMin = i_nLifeMin;
    d_nLifeRange = i_nLifeMax + 1 - d_nLifeMin;
  }
  explicit LifeInitializer() throw():d_nLifeMin(0), d_nLifeRange(0) {}
  inline void operator()(ParticleType& m_Particle) const throw() {
    m_Particle.d_nLife = d_nLifeMin + rand() % d_nLifeRange;
  }
};  //  end of class LifeInitializer

template <class ParticleType>
class GravityAction {
public : 
  Vector3D d_vGravity;
public : 
  explicit GravityAction() throw():d_vGravity(0.0f, 0.0f, 0.0f) {}
  inline void PrepareAction() throw() {}
  inline void operator()(ParticleType& m_Particle) const throw() {
    m_Particle.d_vVelocity += d_vGravity;
  }
};  //  end of class GravityAction

template <class ParticleType>
class MoveAction {
public : 
  inline void PrepareAction() throw() {}
  inline void operator()(ParticleType& m_Particle) const throw() {
    m_Particle.d_ptPos += m_Particle.d_vVelocity;
  }
};  //  end of class MoveAction

Note, however, the drawback of this template design is that the particle structure you come up with must provide the necessary properties and naming that you use in each of your policies.

Also take note of the use of the keyword inline here, which once again hints to the compiler to include those code simply in the callee function. With these inline keywords, the Process function can eliminate any further function calls and execute them there and then!

Sample Usage of a Particle System

Ok, so let's define a particle system to use! A declaration would look like the following,

ParticleGroup<1000, 
  CompletePolicy<Particle, ColorInitializer<Particle>, SizeInitializer<Particle>,
                 VelocityInitializer<Particle>, LifeInitializer<Particle>, NullPolicy<Particle> >,
  CompletePolicy<Particle, ColorAction<Particle>, SizeAction<Particle>,
                 GravityAction<Particle>, LifeAction<Particle>,
                 MoveAction<Particle> >, Particle > d_ParticleGroup;

Notice the NullPolicy, which is simply an empty policy which does nothing. Remember once again that we hinted to the compiler to have those function calls inlined, thus a NullPolicy would generate no extra overhead. So to initialize the system, for example, we simply do the following.

d_ParticleGroup.d_InitializePolicy.d_LifePolicy.SetLifeRange(10, 100);
d_ParticleGroup.d_InitializePolicy.d_SizePolicy.d_szSize = Size3D (0.025f, 0.025f, 0.025f);
…
d_ParticleGroup.d_ActionPolicy.d_LifePolicy.d_nLife = 1;
d_ParticleGroup.d_ActionPolicy.d_VelocityPolicy.d_vGravity = Vector3D (0.0f, -0.0005f, 0.0f);

And so on for the others. And to emit particles,

d_ParticleGroup.Emit(100, Point3D(0.0f, 0.0f, 0.0f));

Processing them,

d_ParticleGroup.Update();

Combining Policies

The original policy design work well, until the point where you might have too many action effects you require, and too little template parameters to work with. For example, you want a gravitational pull as well as a wind action, and you are unable to 'free up' the other policies, as all are essential. The solution here is to use a CompositePolicy. A composite policy is simply a policy itself, and it merges two policies into one. It follows the same rules and workings of a policy.

template <class ParticleType, class Policy1, class Policy2>
class CompositePolicy : public Policy1, public Policy2 {
public : 
  inline void PrepareAction() throw() {
    Policy1::PrepareAction();
    Policy2::PrepareAction();
  }
  inline void operator()(ParticleType& m_Particle) const throw() {
    Policy1::operator()(m_Particle);
    Policy2::operator()(m_Particle);
  }
};  //  end of class CompositePolicy

With a composite policy, you can actually nest them and merge endless possible policies as one. The only drawback here is the possible name collision of any data members in each policy.

Now with the new additional policy, let's add Wind, Gravity, as well as a retracting action to the particle system!

ParticleGroup<1000, 
  CompletePolicy<Particle, ColorInitializer<Particle>, SizeInitializer<Particle>,
                 VelocityInitializer<Particle>, LifeInitializer<Particle>, NullPolicy<Particle> >,
  CompletePolicy<Particle, ColorAction<Particle>, SizeAction<Particle>, 
CompositePolicy<Particle, RetractAction<Particle>, 
      CompositePolicy<Particle, 
        GravityAction<Particle>, WindAction<Particle> > >,
  LifeAction<Particle>, MoveAction<Particle> >,
Particle > d_ParticleGroup;

We can access the gravitational pull factors, retracting, as well as wind force all under the same VelocityPolicy.

d_ParticleGroup.d_ActionPolicy.d_VelocityPolicy.d_vGravity = Vector3D (0.0f, -0.0005f, 0.0f);
d_ParticleGroup.d_ActionPolicy.d_VelocityPolicy.d_vWind = Vector3D(-0.005f, 0.0f, 0.0f);
d_ParticleGroup.d_ActionPolicy.d_VelocityPolicy.d_dwRetractCounter = 50;

One could declare Policy1 and Policy2 as data members of CompositePolicy, but it doesn't scale well for multiple nested policies. Imagine having to write

d_ParticleGroup.d_ActionPolicy.d_Policy1.d_Policy2.d_VelocityPolicy.d_vWind =
    Vector3D(-0.005f, 0.0f, 0.0f);

Now isn't that ugly?

Conclusion

With policies, you can mix and match different effects into a particle system, customizing it for each individual scenario, and yet have the best performance. The only drawback would be the following a fixed naming of data members of a particle, as well as watching out for possible name collision when using CompositePolicy to merge multiple policies.

Feel free to contact me via email(onedotonly@hotmail.com), or look for _dot_ on #gamedev. I'll be happy to answer questions, discuss problems, and merely hear about how you're using the technique and how it's working for you.

Acknowledgements

My many thanks to those on #gamedev who helped reviewed my article, as well as muer for introducing me to the Modern C++ Design book.

Additional Resources

Modern C++ Design, by Andrei Alexandrescu

Advanced Particle Systems by John van der Burg

Particle System API by David McAllister

Trent Polack's: Game Tutorial #03

NeHe Productions: OpenGL Article #06

Discuss this article in the forums

Date this article was posted to GameDev.net: 8/19/2003
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Featured Articles
Particle Systems