Particle collision with voxel world in compute shader

Question

I've added a particle system to a voxel game I'm working on. At the moment, all the physics are done on the CPU, and it's pretty slow (my CPU struggles with 2000 particles).

For each particle, I determine the range of voxels that it could theoretically collide with (based on the particle's position and velocity, and the elapsed time), and then check for collisions with all the voxels in that range and use the nearest collision.

To increase performance, I'm exploring whether I can use a compute shader to perform the physics.

If I convert my voxel world into a bit array and toss that in an SSBO, then the compute shader has all the geometry information required to do the collision detection. However...

The collision detection code that I wrote for CPU is not going to be efficient at all on the GPU; there's just wayyy to much branching/looping. Is there an efficient way to have particles collide with a voxel grid, on a compute shader?

Answer 1

For simplification, consider your particles as point-shaped objects with only position P and velocity V units/tick. Instead of computing exactly which voxels your particles will touch, a first approximation for particle motion could just be to check if P + V is occupied by a solid voxel (using a 3D sampler), and set V to zero (or to a fraction of itself) if this is the case, otherwise increment P by V. These conditional operations can be efficiently done with integer arithmetic, no branching is required.

If this approximation is too rough, because V is often multiple voxel units long, and because your voxel geometry is fine enough that this could cause particles to clip through solid walls, you could simply repeat the above operation N times inside the shader, using V/N instead of V, where N should be the smallest constant integer that makes the clipping stop most of the time. For-loops of constant length will be unrolled by the shader compiler, so you will still require no true branching.

Now with this algorithm, the behavior of your particles will be to cease all (or most) motion once they reach an obstacle. If they are affected by gravity (best done inside the shader as well), they will fall straight down, but only after losing their vertical velocity. If they reach a floor, they will stay where they are.

If you want your particles to skid across horizontal surfaces instead of stopping where they land, and retain their vertical momentum when hitting walls, you can separate V into a horizontal and a vertical component, and do the above steps separately for the two components.

You also have the option to separate all three coordinates of V, so particles hitting walls with diagonal horizontal motion will follow the wall instead of dropping straight down, but the performance penalty may outweigh the benefits compared to two components.