GPU boids (Unity)
A GPU driven boid simulation and rendering made in Unity. With the aim to learn and extract the most out of GPU Driven Rendering, I have used Unity’s compute shader capabilities and indirect rendering commands to simulate and draw up to one million boids.
Boids
Developed by Craig Reynolds in 1986, Boids is an algorith that tries to simulate the flocking behaviour of birds. Each boid represents an individual inside the flock, with their movements being determined by three simple rules:
Alignment
Alignement forces push nearby boids into movint at the same direction.
Cohesion
Cohesion forces push the boids towards the central position of the nearby boids, causing agglomeration.
Separation
Separation forces avoid collision between the boids inside the agglomerate
The simplicity of the algorithm makes it very simple to implement, even in parallel. However, the catch is that we must check for nearest neighbors, making it scale in complexity as O(N^2)
Space Partitioning
In order to solve the O(N^2) scaling and inspired by Rama C. Hoetzlein presentation on Fast Fixed-Radius Nearest Neighbors approach, I have used a uniform spatial grid as an acceleration data structure:
With this space partitioning scheme, each boid is firstly assigned into a grid cell. Then, based on Rama’s presentation and using nvidia’s GPU gems Work Efficient Parallel Prefix Sum (Scan) We improve the memory access pattern on the GPU by sorting the boid array with counting sort. After sorting, we search for nearby boids by iterating over contiguous slices of the array.