Barnes-Hut N-Body Simulation
A C++ gravitational simulation that evolves from a brute-force O(N²) baseline into a Barnes-Hut algorithm with OpenMP parallelization and Morton ordering - real-time with up to ~150,000 bodies.
click to add · drag to move
The simulation above is just a neat little visualization of the same idea - please don't try running 150,000 particles in it, your browser will probably blow up.
I built this because I love emergent things, large amount of simple particles forming a larger whole due to pair wise attraction. N-Body simulations are kind of addictive and a great starting point in learning performance optimizations!
What it does
- Brute-force O(N²) baseline with Euler integration
- Barnes-Hut quad/oct-tree spatial partitioning for O(N log N) force approximation
- OpenMP-parallelized force calculation and tree construction
- Morton ordering for cache locality and predictable tree building
- Real-time rendering with OpenGL
Performance highlights
- Brute force becomes unusable past ~10,000 bodies
- Barnes-Hut drops compute time to O(N log N)
- Morton ordering improves cache efficiency and cuts tree build cost by ~202%
- Parallel tree construction achieves a 5.14x speedup over unsorted sequential builds
- Up to a 15x overall speedup - real-time simulation of ~150k bodies
Tech highlights
- C++17 core simulation
- OpenMP parallelization
- OpenGL 3.3+ real-time rendering
The full write-up is available as a PDF: Read the report.
I've also written up the whole journey as a blog series - the SIMD and multithreading story is covered in Part 2, with the related SIMD project.
The demo below is a small browser simulation inspired by the same idea.