O(n) particle inter-collision solver

In my last year at the University of Victoria (2006), I had the privilege to complete a Directed Study. I absolutely love working with particle animations, but find waiting for complex particle solves to be a bit of a bore ;) The basic old idea was each particle needed to check the position of every other particle in the scene. This is slow. I ended up taking this O(n²) algorithm and turned it into linear time, resulting in a very fast way to solve inter-colliding particle systems. To put theory into practice, I wrote a C++ plugin for Maya. It worked awesome.

 

This shows the particles being created at different sizes, affected by gravity and then interacting with a simple ground collision event.

 

I wrote this expanding feature to move the inter-colliding particles to a certain region where no inter-collisions are present before being affected by outside forces.

 

Here we have the particles filling a volume. There's a subtle compression effect which can be seen.