Steven J. Barnett

In the past few weeks, I learned about the Barnes-Hut algorithm for approximating long-range forces between many 2d particles from this video, and decided to try my own hand at a 3d implementation. My goal: to see how many stars I can fit into a single galaxy in real time, on my M1 Macbook Air. The video below was captured on that computer, with 262k stars. The code I wrote is here.

The Barnes-Hut algorithm reduces the naïve O(n²) force calculation to O(n log n) by organizing particles into an octree. Each internal node stores the center of mass of everything beneath it. When computing the force on a particle, you walk the tree and substitute an entire cluster for a single point mass whenever it’s far enough away — specifically, when the node’s width divided by the distance to the particle falls below a threshold θ. The closer θ is to zero, the faster but less accurate the approximation.

The implementation is written in C++20 with Vulkan compute shaders handling the heavy lifting on the GPU. Tree construction happens on the CPU using a flat, index-based node array (no pointers, so it’s cache-friendly and easy to upload). Two compute shaders then run per frame: one traverses the tree to accumulate gravitational accelerations, and one integrates positions and velocities using symplectic Euler.