Expand description
Barnes-Hut 2D force simulation.
Port of the d3-force semantics onto a quadtree-accelerated n-body repulsion kernel, plus link springs and a center-of-mass gravity. The result is deterministic given a seed so the WASM and native call sites (Wave 2+) produce identical layouts for the same graph.
§Single-threaded for Wave 1
The naive per-tick traversal on 50k nodes is well under 5 ms on
a modern laptop core so we leave it single-threaded here. A
rayon-parallel variant would live behind #[cfg(feature = "native")]
once we have profile data to justify it. Wave 1’s priority is
correctness + WASM-compatibility of the algorithm, not raw peak
throughput on a dense 100k-node graph.
§SIMD choice
Positions are 2-float vectors, so per-element SIMD (f32x2)
buys nothing — the dot product over two floats is one FMA already.
We use glam::Vec2 scalar math everywhere in this file and keep
graph_core::util::dot_simd for the wide-float kernels (cosine,
BM25, bloom) that need it. A future revision that batches the
center-gravity force over all positions at once and runs it as a
fused reduction could reach for dot_simd; the per-node force
loop wouldn’t benefit.
Structs§
- Simulation
- Public force simulation handle. Owns positions, velocities, edges, and a scratch quadtree that gets rebuilt every tick.
- Simulation
Config - Force simulation configuration. The defaults match d3-force’s defaults so graphs that used to render there look the same here.