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:

Position of the particle, in the world, be it 2D or 3D.
Velocity of the particle, to determine its movement along the timeline.
Lifespan of the particle, to determine how long a particle is visible, or dies out.
Size of the particle (optional), to determine how big the particle is.
Color of the particle (optional), to determine the color of a particle. 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 class ParticleGroup { public : InitializePolicy d_InitializePolicy; ActionPolicy d_ActionPolicy; explicit ParticleGroup() throw()_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 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 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()_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 GravityAction { public : Vector3D d_vGravity; public : explicit GravityAction() throw()_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 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