An experimental verlet particle system entirely on the GPU (GLSL) using Flow Fields/Distance Fields. Next to verlet integration, this includes some very efficient collision detection as well as other features like cohesion.

It enables realtime particle simulation for up to millions of particles on common graphics cards.

 

 

 

Algorithm

The whole algorithm is executed on the GPU using OpenGL/GLSL.

All the particles data is stored and updated in textures. Each physics step the particles position is updated using verlet integration. Particles are moved/accelerated by one flowfield which is the result of combined collision detection among particles-particles and particles-obstacles, cohesion and external forces (gravity, user interaction).

To solve collisions, particles are rendered as pointsprites into a distance field using additive blending. The resulting flow field, derived from the distance field, is then used for acceleration. The same process is used for cohesion.

 

Flow Field Particle Simulaltion, 50K Particles

Particle Trails

 

Data Structures

The required core-parts are a couple of 2D textures used for storing particle-data, like position, and for rendering particles as point-sprites.

2D OpenGL Textures

Particles Position ......... GL_RGBA32F, RG=current px/py, BA=previous px/py

Collision Distance Field ... GL_R32F, distance
Cohesion Distance Field .... GL_R32F, distance
Obstacle Distance Field .... GL_R32F, distance

Collision Flow Field ....... GL_RG16F, velocity
Cohesion Flow Field ........ GL_RG16F, velocity
Obstacle Flow Field ........ GL_RG16F, velocity
Accumulated Flow Field ..... GL_RG16F, velocity

Distance Field (DF)

A Distance Field is a scalar field (single-channel texture). It contains the (shortest) distance to … “anything” – but usually some kind of defined obstacle, the nearest foreground. Optionally this information could also be stored in a 2 channel-texture as either the position (px, py) of that obstacle or as the direction-vector(dx,dy) to that position of that obstacle.

Note, that it is up to the desired usage wheter this distance is the distance to the nearest local obstacle or to something else, like in the case of pathfinding, where the distance is shortest path-length, … even just a common heightmap, or basically anything that can be described via gradually changing values.

A distance field can be gained from a distance-transform applied onto an image which has been separated in a foreground (FG) and a background (BG).

github.com/diwi/PixelFlow/…/distancetransform.frag

Particles Simulation – Distance Field

Flow Field (FF)

A Flow Field is a vector field (two-or-three-channel texture). It contains a vector/velocity/direction/etc. One of many ways to create a flowfield is by computing the gradients of a distance field (scalar field) using for example a sobel filter. The result is then the 2D/3D-direction-vector following the local change in distance.

github.com/diwi/PixelFlow/…/flowfield_create.frag

Particles Simulation – Flow Field

 

 

 

Physics Update

The particles position is stored and updated in a simple texture-ping-pong manner using verlet integration. The current particle position is stored in the XY-channel and the previous position in the ZW-channel.

Verlet Integration

  v = c - p
  p = c
  c += v + a * 0.5 * dt * dt
  a = 0

v  ... velocity
c  ... current position
p  ... previous position
a  ... acceleration
dt ... timestep

further readings:
- www.gotoandplay.it/_articles/2005/08/advCharPhysics.php
- www.gamedev.net/articles/programming/math-and-physics/a-verlet-based-approach-for-2d-game-physics-r2714

My GLSL code follows the little notation from above, but the Acceleration and the Velocity are integrated in 2 separate passes (therefore the #define).
The multiplicator for the acceleration (acc_mult) includes the timestep while the multiplicator for the velocity (vel_mult) is just used for damping.

The acceleration data comes from a texture which can contain any kind of flowfield (velocity) information, like gravity, or other velocity fields. In case there is no need for collision detection and other mechanics this would actually be enough to do a proper particle simulation.

In my version, the acceleration is the combined result of all solved collisions (particles and obstacles), cohesion, … and external forces, like gravity, user interaction and other possible acceleration fields (e.g. flowfield pathfinding).

In the end the number of update-calls is minimized to one in the best case, two or three in case of refining the accelleration/position update.

Update (GLSL): github.com/diwi/PixelFlow/…/particles_update.frag

// GLSL uniforms, defines and other stuff

void main(){

  // particle index, based on the current fragment position
  ivec2 tex_loc  = ivec2(gl_FragCoord.xy);
  int   particle_idx = tex_loc.y * wh_position.x + tex_loc.x;
  vec4  particle_pos = texelFetch(tex_position, tex_loc, 0);
  
  vec2 pos_cur = particle_pos.xy;
  vec2 pos_old = particle_pos.zw;

  if(particle_idx < spawn_hi){
  
#if UPDATE_VEL
    // velocity
    vec2 vel = (pos_cur - pos_old) / wh_velocity_rcp;
    // fix length
    limitLength(vel, vel_minmax);
    // update position, verlet integration
    pos_old = pos_cur;
    pos_cur += (vel * vel_mult) * wh_velocity_rcp;
#endif
  

#if UPDATE_ACC
    // acceleration
    vec2 acc = texture(tex_velocity, pos_cur).xy;
    // fix length
    limitLength(acc, acc_minmax);
    // update position
    pos_cur += (acc * acc_mult) * wh_velocity_rcp;
#endif

  }

  out_frag = vec4(pos_cur, pos_old);
}

 

Particle Simulation – Rendering

 

 

 

Particle Collisions

Solving particle to particle collisions can be quite expensive and usually requires some kind of acceleration structure to quickly find nearby particles that need to be checked and updated for possible collisions.

My GPU-approach here is a bit quicker:

  1. Render the particles into a texture to get a distance field.
  2. Create a flow field from the distance field.
  3. Update particles acceleration via the flow field in the update step.

Collision Detail: 1) Render, 2) Distance Field, 3) Flow Field

ad 1) Particle Distance Field

This is the tricky part, but after lots of testing the simplest and fastest method turned out to work the best.

A distance field is a scalar field, so only one channel gets written (GL_R32F) and additive blending needs to be enabled to get the information of overlapping particles. The particles are simply rendered as point sprites with twice the size of the collision-size (which probably is equal to the display size).

Most important is the fragments shading where the fragments intensity is linear proportional to the distance of the particles center.

distance field (GLSL): github.com/diwi/PixelFlow/…/particles_dist.glsl

out float out_frag;

void main(){
 out_frag = max(0, 1.0 - length(gl_PointCoord * 2.0 - 1.0));
}

particle distance – linear

particle distance – blured (gaussian)

I experimented with several different distance-to-center functions. Ideally it must be some kind of bell-curve, that flattens at the particle-center and the particle-border. However, I encountered numerous precission issues, especially for small particles where only a couple of fragments are covered and overall more serious issues since the distance field is a discrete grid-space for particles that are updated in a continues space. A negative sideffect in such a case is the rather unpredictable motion of particles that either get stuck at either one position or one velocity direction.

In the end I got quite stable results using a simple linear distance function (code-snipped above) and a blur-pass over the flow field the next step. This turned out to work very well for solving cohesion and obstacle collisions as well.

Particles – Distance Field

Note that in the screenshot above the obstacles (big circles) have the same linear distance shading falloff as the particles; altough the distance-field-process for obstacles is sightly different. More on that later.

ad 2) Particle Flow Field

The flowfield is then simply obtained by computing the gradients in X and Y of the distance field using a sobel filter.

As mentioned before an additional blur pass (gaussian blur filter) needs to be applied to take into account for the particle distance-to-center function (bell curve).

Particles – Flow Field

ad 3) ParTicle Update, Acceleration

At this point the flowfield is ready to be used in the update step. The particle-particle collision flow field is just one of many flowfields in use. To minimize the number of update-steps all those flowfields are combined (merged) into a single one.

Particles – Rendering

 

 

 

Particle Cohesion

I am using the “exact” same process as for solving particle collisions.

The only difference is the much larger particle radius during the distance field pass and reverse direction for the flow field, … particles attract each other instead of repelling each other.

Cohesion – Rendering

Cohesion – Distance Field

 

 

 

Obstacle Collision

The idea is the same as for the particle collisions.

  1. Apply a distance transform onto the scene to get a distance field.
  2. Create a flow field from the distance field.
  3. Update particles acceleration via the flow field in the update step.

Obstacle Detail: 1) Render, 2) Distance Field, 3) Flow Field

Obstacle Border

The scene obstacles need to be prepared before the distance transform. To do so the obstacles boundary pixels are extracted (4 neighborhood) and used as the FG-mask for the distance transform shader. This is necessary to get a distance field of the complete scene (inside and outside of obstacles).

Obstacles FG (GLSL): github.com/diwi/PixelFlow/…/obstacles_FG.frag

Obstacle Distance Field Offset

At this point all pixels contain a positive distance to the nearest obstacle border (inside and outside of obstacles). The obstacle mask is then used to invert distances outside of obstacles and the particle collision radius as a global constant is added to the complete distance field. Negative values are clamped to 0 before writing the new “shifted” distance to the fragment.

Obstacles Dist (GLSL): github.com/diwi/PixelFlow/…/obstacles_dist.frag

Obstacles – Distance Field

Obstacle FlowField

Finally, based on this distance field a flowfield is created and a gaussian blur filter is applied, same as for the particle collision.

Obstacles – Flow Field

 

 

 

Stresstest – 4 Million Particles

As mentioned in the beginning, this method allows to simulate millions of particles in realtime, including collision detection. However, more precission issues emerge since the particles are very small and therefore the covered fragments in the collision buffer are not enough to get a 100% stable simulation. The only solution to this is to increase the resolution of the collision buffer, which costs performance.

4 Million Particles – Rendering

4 Million Particles – Distance Field

4 Million Particles – Flow Field

 

 

 

Particles Attraction and Obstacles Gravity

This is an experimental demo to run do run an N-body simulation. This is in general a challenging problem since each particle is influenced by all other particles the system.

In my simulation demo the cohesion-pass does the job of simulating N^N gravitational attraction reasonably well, at basically zero performance overhead.

The attractors in this demo are the two blue circle-obstacles. There are numerous ways to create the gravity flow field for them. I’m using a separate shader that builds the flowfield directly, … rather than running a distance transform.

 

NBody Bloom

NBody Distance Field

NBody Particles

 

 

 

Particle Trails

This is just a rendering effect where particlestrails as lines and frames are blured each iteration.

 

Particle Trails

Particle Trails