Particle System Code Architecture

This document will describe the core architecture of the new particle system I've worked on in the last couple of weeks. The particle system itself is work-in-progress, but the general architecture is becoming quite clear already.

Goal

The goal for this specific particle system is to give artists a lot of control over the behavior of particles, while still allowing high level abstractions for common tasks. A possible user interface for the system has been proposed in this document. The system should be easily extensible and have high performance by design.

In order to be able to design such a system, the scope has to be reduced. There are just too many different kinds of possible particle systems that need very different solvers. Trying to put everything into the same system would probably force me to do many compromises that result in a slow and less usable system. For example, simulating sand or other granular materials is not a use case for this system. It should still be possible to have interactions with other physics systems of course.

To achieve high extensibility I define a couple of interfaces. High performance is achieved by following data oriented design patterns and ensuring good threadability.

High Level Overview

The core of the system is the void simulate_step(ParticlesState &, StepDescription &) function. It takes two parameters:

1. A ParticlesState object that contains all particle data at the beginning of the time step. Furthermore, it also stores the current simulation time. This parameter will be modified during the simulation. When the function ends, it will contain the new state of all alive particles.
2. A StepDescription object that describes how to get from the old particle state to the new state. It also knows the duration of the time step.

The simulate_step function does not care about where the particle data or the step description comes from. Currently, the particle state is always the result of the last simulation step and the step description has been created based on a node tree.

Particle Storage

The way particles are stored is essential for high performance and extensibility. This section explains how particle data is stored in memory.

Considerations

Among others, the following aspects have to be considered:

• Dynamic vs. static storage: When using static storage the amount of required memory is fixed during the simulation. When using dynamic storage, more memory management is necessary. It has the benefit that the maximum number of particles does not need to be known in advance. I consider that to be an important feature, so the system uses dynamic storage.
• Array of Structs (AOS) vs. Struct of Arrays (SOA): When using AOS there usually is a Particle struct that contains all attributes like location, velocity and size. When using SOA, there will be separate arrays for all attributes. I decided to use the SOA approach for two main reasons. First, it allows dynamically adding and removing entire attributes more easily which is essential for a flexible system. And second, it is more cache efficient since most loops don't need to access all attributes. By having them in separate arrays, it is more likely that all bytes in a loaded CPU cache line will be used.
• Single vs. multiple arrays: Using a single array for every attribute makes sense when the amount of particles is relatively small and not varying too much. Reallocating this array would involve copying the attributes of all particles. A better solution is to split up the attribute arrays into multiple equally sized chunks that can be allocated and freed individually. This approach also simplifies the threading, because the blocks can be distributed to threads easily.

Particle Storage Hierarchy

Currently, the particle data is stored in a hierarchy. The individual levels are explained below.

At the top there is the Particles State. It contains an arbitrary amount of Particle Containers. Each container in the state is identified by a name. All particles in the same container belong to the same particle type and have the same attributes. Particles in different containers can have different attributes.

A Particle Container contains information about the attributes of particles in this container. Furthermore, it contains an arbitrary amount of Particle Blocks. Every block in the same container has the same size. EVery block belongs to exactly one container.

A Particle Block contains an array for every attribute. The number of particles in a block is at most the size of the block. By definition, all active particles are grouped at the beginning of the block. Every block knows how many active particles it has.

Attributes

There is a fixed set of attribute types (currently byte, float and float3). Attributes are identified by their name. Additionally, attributes can also be identified by an index when the set of attributes does not change. Depending on what a function is doing, one or the other identification method is more appropriate.

Step Description

The step description contains emitters and particle types. A particle type contains information about the required attributes for that type, an integrator, an arbitrary amount of events and an arbitrary amount of offset handlers.

Emitter

An emitter allocates and initializes attributes for new particles. It can create particles of different types. It also specifies the exact birth times of every particle it creates, because they might be simulated partially within the current time step.

Integrator

The task of the integrator is to determine how every particle in a block would move in a certain time span, if there were no events. It does so by computing offsets for a subset of all attributes. For example, a simple integrator would just compute how the velocity and positions will change. It does not actually adjust the particles itself.

Event

An event has two functions: filter and execute. The filter function gets a set of particles and checks which of those trigger the event. It also specifies the exact trigger-time. The execute function gets a set of previously triggered particles and modifies them. It can also kill the particle or create new ones.

It is possible to pass information from the filter to the execute method (e.g. the normal of the collision point with a mesh).

Offset Handler

An offset handler just observes the movement of particles. It might modify attributes that are not integrated or create new particles. This can be used to create e.g. particle trails.

Simulation Step

A simulation step starts by ensuring that all necessary particle containers and attributes exist. Then all emitters are evaluated and all particles are simulated. In the end, the containers are compressed to save memory.

Ensure Containers and Attributes Exist

Sometimes the existing attributes in the particle state do not match the attributes required by the step description. Also the step description might emit particles of types that do not have containers yet. As first step, all missing attributes and containers are created. That allows later steps to assume that e.g. all expected attributes really exist.

Emit and Simulate

The simulation happens in a loop. In the first step, all existing particles are simulated till the end of the time step and emitters are evaluated. While doing that, new particles might have been created that need to be simulated for partial time steps. Those might create new particles and so on. This repeats until no new particles have been created.

Simulate Block

All particles in a block are simulated in the same way. To simplify the explanation, I'll explain it based on a single particle.

At first, the integrator computes the offsets of some attributes for the current time step. For example, it computes that the particle should move along the x axis for one unit.

Then, all events are checked to see if the any of it is triggered. If multiple are triggered, the first one (with regard to simulation time) is used. Then the particle is forwarded to the time at which the event happens. Once forwarded, the event is executed which might change the attributes and integrated offsets of the particle.

Afterwards, all events are checked again. A particle can be modified by multiple events in the same time step. However, there is an upper limit (10 currently).

In the end, particles marked as dead, are removed by reordering the attribute arrays.

Emit

Particles can be created by emitters, events and offset handlers. It is important that multiple threads can emit at the same time with very little synchronization overhead.

This is achieved by using "particle allocators". Every thread has its own particle allocator. When new particles are created for the first time, the allocator will request a new block from the particles container. This requires some locking. However, once it has the block, it can allocate particles in it until it is full, without any locking.

Compress

During the compression, particle data is copied between different blocks to fill up all blocks except one per particle type. Empty blocks will be deallocated or cached for further use.