Barnes–Hut force layout — for idiots
The problem, in one breath
The graph picture froze at ~30 000 dots. Not because 30 000 dots is a lot to draw (the GPU laughs at that) — but because of how the dots find their places.
How the dots find their places
A "force layout" pretends every dot is a little magnet:
- dots push each other apart (so they don't pile up),
- lines pull connected dots together (so friends sit close).
Let it wiggle for a while and it settles into a nice shape. Good.
Why it hung
The pushing was done the dumb way: every dot pushed against every other dot. With 30 000 dots that's 30 000 × 30 000 ≈ 900 million little pushes — every single wiggle, and it re-wiggled every single frame. The computer drowned.
The fix, part 1: squint at far-away crowds
Here's the trick (it's how astronomers simulate galaxies). If a big clump of dots is far away, you don't work out each dot's push separately — you treat the whole clump as one blob sitting at its average spot. Close things: still exact. Far things: one blob. Way fewer sums.
We chop space into boxes (a quadtree in 2-D, an octree in 3-D), each box knows its blob. Now it's ~30 000 × 15 sums instead of 900 million. Same picture, ~fifty thousand times less work. And we split the work across all 12 cores at once.
The fix, part 2: stop redoing finished homework
The shape only needs to be worked out once. After that, unless you add or remove dots, it's the same shape — so we remember it and just re-draw the same positions every frame instead of re-solving the puzzle 60 times a second. That's the "freeze".
The fix, part 3: adding dots without starting over
When new dots arrive, we don't throw the whole picture away and start again. We keep everyone where they are, drop the new dots next to the friends they're connected to, and let only the new ones jiggle into place. That's absorb — how korp streams new nodes in without a stutter.
One more thing we had to fix
One special layout ("MDS") needed a giant table with a row and a column for every dot — 30 000 × 30 000 numbers ≈ 3.6 gigabytes. That doesn't hang, it crashes (out of memory). So above a size limit we switch it to a cheap approximation that gives a good-enough 3-D shape without the giant table.
The result
30 000 dots now settle in about a second instead of never. Small graphs behave exactly as before — we only turn on the clever mode when it's big enough to matter.