Quadtrees and The Barnes-Hut Algorithm: The Making of a Gravity Simulation

Have you ever been entranced by the beauty of gravity simulations? In this video, I explain the Barnes-Hut algorithm for quickly computing solutions to the n-body problem.
Code: github.com/womogenes/GravitySim
Barnes-hut article: arborjs.org/docs/barnes-hut
Collisions explained: • How to Simulate a Coll...
00:00 Intro
00:27 The physics of gravity
03:38 A naive approach
05:16 Quadtrees
10:00 Barnes-Hut
12:46 Time complexity analysis
14:02 Collisions!
16:25 Outtro

[@sebasfavaron]

20fps for 1000 particles in Processing is actually not bad! Kudos to you. From here on the only optimization left would be to change languages I guess. This in C++ or Rust should be over 100fps for sure (considering I coded a worse implementation in Rust and it handles 4000 at 60fps)

[@idiot528]

On c++ i got like 110 frames

[@JacobNax]

You're still limited. The actual solution is cpu cache friendly structures, subdivide the grid into chunks, assign each chunk into a worker thread, consolidate all worker thread results at the end of the frame. Congrats, you can now do 1m+ body simulations at 60fps

[@bobjoe747]

@@JacobNaxdo you have any resources on this?

[@paulembleton1733]

In Unity, using low poly objects, the Unity job system and burst compiler, about 4,000 objects before noticeable jitter. I’ve a fairly powerful GPU but the CPU isn’t anything special. And that could be improved since the force for each pair is calculated twice: difficult to update the force for the other object in the job system since there’s no way of knowing if it’s being updated from another thread without seriously impacting performance.
Ps, code is in C#. And it’s all brute force. I know little else.

[@anondude6361]

You explain things in such a good way

[@oystercatcher943]

Thanks. This is fascinating as I'm building exactly this kind of simulation. I'm using Metal and the GPU (no collisions yet). Given the GPU I can do the brute force O(N^2) on 10,000 bodies at 60 fps and I'm amazed its this good, but I'd like to do 100K or 1M bodies if possible. I tried rendering to an texture, and then generating mip-map with the idea you then sample mass in regular sized grids (just using the centre of the cell) at appropriate resolutions based on distance away. I haven't yet got this working well. Thanks for sharing Barnes-Hut. But doing stuff like this purely on the GPU is very difficult, so I'll probably continue playing around possible doing all close gravity calculations and random sub-sampling those further away. I'll share some videos some time. Good video. Keep it up!

You can probably do something better using something like the FFT.
Basically, each particle has a gravitational potential. You can dissect that potential with a Fourier transform (which you actually only have to do once properly, because the 'frequencies' are all the same for all particles, only the phases are different).
You can get the total gravitational potential by adding up individual potentials. Then you evaluate that total gravitational potential function for each particle's position to figure out the forces on them. (Well, plus a bit of math to go from potential to its derivative, the force. But you can do that symbolically.)
As a refinement, you can stick to low frequency components only, and use a hashmap (or a tree) to look up the precise impact of nearby particles.
See also en.wikipedia.org/wiki/Multipole_expansion

[@shingo371]

helpful video!

[@0MVR_0]

this idea is coherent as a lagrange point

[@menaced.]

Would be interesting to simulate relativistic gravity instead using like a vector field to represent the combined curvature of all the bodies gravitational forces, could be pretty efficient on a gpu using an image

[@WilliamYFeng]

true, I'd love to learn about relativistic gravity. do you have any suggestions for resources?

[@UseQPixinDune]

@@WilliamYFeng If you want the mathematical background of general relativity, then any introductory level textbook would be a good place to start (assuming you have some mathematical background in tensors and such)
EinsteinPy is a python package which implements some GR principles quite well, and it is open source too

[@arkanon8661]

​@@WilliamYFeng you can calculate 1/gravitational time dilation as sqrt(1f-2f*G*mass/distance), or 1/sqrt(1-2Gm/r) for the less readable physics version
you can then just multiply the acceleration by that number, and you now have general relativity gravity so that's cool
(but don't take my word for it, i could be incorrect, this is just the most accurate seeming thing i could find)

[@szymonbaranowski8184]

Yes!

How was timings for tree building and traversing?

[@WilliamYFeng]

Tree building is O(N log N) and so is traversing.

[@exel001]

that is nice. but i would just make some constant grid, calculate mass in each cell, and then i will be able to use this cell masses for distant points. at least it would be much easier to implement )

[@generichuman_]

This won't work. You need to know where each particle is to make a grid that will only divide space as necessary, unless you divide space across the whole grid evenly so that there's only room for on particle and that would be horribly wasteful. If you're not convinced, try implementing this and you'll immediately see the issue.

[@tgey6874]

Hey william, what program is it you use to run the code?

[@WilliamYFeng]

I used processing: processing.org

[@dougsellner9353]

Cool - Q: Does this account gravity traveling at speed of light?

[@generichuman_]

without even looking at the code...no

[@BleachWizz]

getting a result better than that it's beyond improving order of complexity. you'll need to get into parallelizing the code.

[@jasonboyd782]

This is very coherent explanation. However, at 10:40 you say that clustering bodies "approximates" the effects of their individual gravitational pulls. Isn't it literally the exact same effect? That is, combining their total mass and calculating pull towards their center of gravity ought to be identical to calculating all the individual gravitational vectors and summing them. No?

[@WilliamYFeng]

That's certainly a very intuitive thought, but it turns out that it doesn't work out in practice. The reason you can't treat a cloud of mass as just a single point mass concentrated at the center is because of the inverse-square law: bodies that are closer to you tend to exert a much greater force than bodies that are far away.
For instance, consider how the gravitational force on the Moon from the Sun and the Earth. The center of mass between the Sun and Earth is very, very heavily biased towards the Sun. However, the Moon experiences a greater gravitational effect from the Earth because it's so much closer to us-that's why the Moon orbits the Earth, and not the Sun.
Thanks for asking this question! I imagine it's a thought many people have-certainly something I was confused with for a long time.

[@jasonboyd782]

@@WilliamYFeng That makes sense! Thanks for the explanation.

[@Komprimat1111]

nice - thanks!

[@robbie_]

I think perhaps a 2d spatial hash would be a lot faster than a quadtree for this kind of thing, especially as it's 2d. Bonus you can effectively multithread most of hash generation and query/update, believe it or not. This is a big win once you get over a certain number of particles. Anyway nice sim.

[@TarkTheConlanger]

I feel really stupid for still not understanding how this works