demoCells.webm
This is a simple physics simulation program that shows particles moving. I implemented :
- Elastic collisions between particles
- Attractions between particles, (the greater the size of the particles, the greater the attraction)
- Friction in the air
- Different algorithms for handling the collision detection
For each particle, we check if it collides with any other particle.
Complexity: O(n^2)
We sort the particles by their x coordinate. Then we check if any of the particles collide with the particles that are on their left and right.
Complexity: O(nlogn)
We build a KD-Tree with the particles. Then we check if any of the particles collide with the particles that are in the same leaf.
Complexity: O(nlogn)
The naive approach is the simplest to implement, but it is also the slowest. The Sort and Sweep algorithm is faster and easy to implement. The KD-Tree is surprisingly slower than the Sweep and Prune algorithm and seems to do mistakes in the collision detection with very small particles.