Particle Simulation

I created a particle simulator in python using OpenGL for the visualization. I included some physics like viscosity and gravity which made it possible to see some cool behaviour. As a way to interact with the whole system I could "accelerate" the box with the arrow keys. Also I could launch a particle into the box of any size using the virtual catapult. 

I was heavily inspired to do try this out after watching the video: Building Collision Simulations by Reducible on YouTube.

Collision Detection

The crux of the whole thing that makes or breaks the simulation speed is the collision detection algorithm. There are a few algorithms that I tried with some better than the others. The gist would be that lesser the collision checks an algorithm makes, the faster it will be. But some algorithms apply a computationally cheaper collision check to prune the number of candidate collision pairs the more computationally expensive check needs to do.

1. Brute Force: Check if a given particle collides with every other particle in the simulation. These collision checks for one particle of course grows linearly with the number of total particles, but what makes this method infeasible is that this check must be for every particle too. That makes this algorithm's computational complexity grow quadratically [O(n²)] with the number of particles. I couldn't get this to work at all for more than 10 particles at 60 FPS.

2. Sweep and Prune: This method significantly reduces the number of collision checks that need to be made by checking overlaps along an axis of the box. If along the one axis two particles have overlap, they could potentially be in collision, but they could also be far away from each other due to a large distance in the other coordinate. When I implemented this I arbitrarily took the horizontal axis as the axis along which I would do the pruning of the collision checks. What might make this method a bit better would be to compute the 2 eigenvectors of the particle distribution and prune along the direction of the largest variance (basically PCA).

3. Axis Aligned Bounding Boxes: This is very similar to the sweep and prune approach except you could imagine that it happens along both axes of the box. 

4. KD Trees: This method creates a tree structure (yeah it is in the name) for the space of particles. The box is divided repeatedly along alternating axes using the median of the distribution of the particles. This method also significantly reduces the number of collision checks. It would of course be quite cool to write up my own KD Tree implementation but I didn't feel like it, so I just used scipy.spatial.KDTree

5. Bounding Volume Hierarchy: This method is quite cool and I don't feel like typing up an explanation for it now so I will save you the clicks and put in a few sentences from the first paragraph Wikipedia here,

"A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, that form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree."

Gravity

I just had to add integrate the position considering gravity as the only force causing an acceleration on a particle (excluding collisions of course). Now the unfortunate thing is that unlike collision which don't happen between every particle, gravity is not so forgiving. It acts between each and every particle and the complexity grows quadratically just as the brute force collision check case. Of course one optimization would be to neglect gravity between particles that are more than a certain distance away - exploiting the inverse square law.

As Newton famously said,

To which Einstein famously said,