Moving to the GPU

Spatial hashing, parallel passes, and scaling from dozens to thousands of particles.

The Neighbor Problem

In Part 1 we built a fluid simulation that computes density, pressure, and viscosity for each particle by looking at its neighbors. The physics was the interesting part. But the expensive part is something much simpler: finding who those neighbors are.

For each particle, we scan every other particle and check whether it falls within the smoothing radius. With n particles, that means n × (n − 1) distance checks per frame. Double the particle count, quadruple the work.

Brute force neighbor search

adjust particle count

        // For each particle i:

        for each particle j ≠ i:

          if distance(pos[i], pos[j]) < H:

            // j is a neighbor of i

Particles: 6

Figure 1. Each line is a distance check. With 6 particles, we need 30 checks. The count grows as n × (n − 1).

At 100 particles, that's 9,900 checks. At 1,000, it's 999,000. The physics formulas from Part 1 are cheap per pair. It's the sheer number of pairs that bogs things down. We need a way to skip the particles that are obviously too far away.

Spatial Hashing

The idea is straightforward: divide the simulation space into a grid of cells, each sized to match the smoothing radius H. Each particle drops into the cell that contains its position. When we need a particle's neighbors, we only check the 9 cells surrounding it (a 3×3 block in 2D) instead of every particle in the simulation.

Spatial hash cell lookup

click a particle

        // Insert: O(n)

        cell_x = floor(pos.x / H)

        cell_y = floor(pos.y / H)

        grid[cell_x, cell_y].push(particle)

        // Query neighbors: check 3×3 block

        for dx in [-1, 0, 1]:

          for dy in [-1, 0, 1]:

            for p in grid[cell_x+dx, cell_y+dy]:

              if distance < H: // true neighbor

Particles: 40

Figure 2. Click a particle to select it. Its cell is highlighted in teal and the 9-cell search region in light blue. Particles within H are true neighbors (green circles). Drag particles to see cells update. Brute force: 0 checks. Spatial hash: 0 checks.

With uniformly distributed particles, the spatial hash reduces neighbor search from O(n²) to roughly O(n). Each particle only checks a handful of candidates instead of the entire population.

From Sequential to Parallel

On the CPU, we loop through particles one at a time. On the GPU, every particle runs the same computation simultaneously. The inner loop (checking neighbors) is the same. The outer loop disappears.

Particles: 8

CPU: Sequential

Waiting

GPU: Parallel

Waiting

Figure 3. Both sides simulate 8 particles over 20 timesteps. The CPU updates one particle at a time (200ms each, 1.6s per timestep). The GPU updates all 8 simultaneously (200ms per timestep). Try increasing to 20 particles to see the CPU fall hopelessly behind.

GPU Parallelism

Once we have an efficient neighbor search, the next observation is that each particle's computation within a single pass is independent. Particle 42's density doesn't depend on what particle 17 computed for its density in the same step. This makes SPH a natural fit for GPU parallelism: launch one thread per particle, all running the same code simultaneously.

The simulation loop from Part 1 becomes a sequence of GPU dispatches. Each pass reads from buffers written by the previous pass and writes its own results. The diagram below shows how data flows through the four passes.

Pass 1 of 4: Density

Figure 4. Each column is one particle. All columns compute simultaneously within a pass. Passes run sequentially top to bottom: density feeds pressure, forces feed integration. Outputs from each pass become inputs to the next. Step through to see the example equation for one particle on the right.

Scaling Up

This simulation runs on your GPU using WebGPU compute shaders. The same four passes from the pipeline diagram above, each dispatching one thread per particle.

Gravity: 200 Viscosity: 100

Initializing... Particles: 0 FPS: 0

Figure 5. SPH with spatial hashing. Same physics as Part 1's final figure, running the four compute passes on GPU (or CPU fallback). Click and drag to push particles. Particles are colored by speed: dark blue is settled, lighter blue is moving fast.

The GPU runs thousands of particles in parallel, each thread executing the same density/force/integration code. The spatial hash keeps the neighbor search cheap, and the parallelism handles the rest. In Part 3 we explore what we can do with that headroom: springs, friction, temperature, and collisions with solid objects.