Hi HN,
Inspired by a YouTube video that popped up on my feed (The Fastest Gravity Algorithm You've Never Heard Of: Fast Multipole Method by Keyframe Codes) I decided to write a library implemeting a N-body solver with an O(N) time complexity.
Most real-time physics engines rely on the Barnes-Hut algorithm, which gets the time complexity down to O(N log N). The Fast Multipole Method (FMM) achieves true O(N) scaling, and I decided to write it entirely in C99 as an stb-style single-header library.
I ended up with a implementation, that running a 200,000 particles simulation grants a ~150x better performance than a naive O(N^2) approach, scaling linearly.
One of the downsides with the FFM approach is the cost of generating the octree, but i managed to yield better performance (compared to the naive approach) at as low as 1,000 particles.
Hi HN, Inspired by a YouTube video that popped up on my feed (The Fastest Gravity Algorithm You've Never Heard Of: Fast Multipole Method by Keyframe Codes) I decided to write a library implemeting a N-body solver with an O(N) time complexity.
Most real-time physics engines rely on the Barnes-Hut algorithm, which gets the time complexity down to O(N log N). The Fast Multipole Method (FMM) achieves true O(N) scaling, and I decided to write it entirely in C99 as an stb-style single-header library.
I ended up with a implementation, that running a 200,000 particles simulation grants a ~150x better performance than a naive O(N^2) approach, scaling linearly.
One of the downsides with the FFM approach is the cost of generating the octree, but i managed to yield better performance (compared to the naive approach) at as low as 1,000 particles.