GPU layout engine + collision avoidance
ripped out the entire hand-rolled ForceAtlas2 + Barnes-Hut implementation and replaced it with vibe-graph-layout-gpu. (OMG i do not like that name, you could have called it anything. LITERALLY ANYTHING else)
195 lines of quadtree code: deleted. RIP. the custom ForceAccumulator, NodeState, adaptive speed calculation: all gone. replaced by a wgpu-backed force-directed layout that runs on the GPU. (no it’s not that intensive, only if you have like a million notes, and then too, we be smart and only calculate the stuff for notes you can see (animation and gamedev tip #1) rather than everything!
the engine now wraps GpuLayout with lazy initialization. the GPU doesn’t spin up until the first step() call, so construction stays synchronous. if the graph changes (node added, removed, links updated), it sets a dirty flag and re-inits on the next step. pinned nodes get their positions restored after each GPU step since the GPU doesn’t know about pinning.
step_neighborhood() is now just step(). with GPU acceleration the full graph is always computed, so neighborhood-only updates don’t make sense anymore. the test got rewritten to match: step_moves_unpinned_nodes instead of the old neighborhood-specific assertions.
collision avoidance
the GPU handles forces and attraction but it doesn’t know about card sizes. nodes are points to it. so after the GPU step runs, there’s now a CPU-side collision resolution pass that pushes apart overlapping bounding boxes.
each node can have a Bounds (width, height) set by the UI. after forces are applied and pinned nodes are restored, resolve_collisions() runs up to 5 iterative passes. each pass checks every overlapping pair, computes a center-to-center separation vector, and pushes both nodes apart by half the overlap distance (clamped to 20px per pass). pinned nodes never move from collision push.
the fallback for coincident centers is fun: when two nodes land on the exact same pixel, there’s no center-to-center vector to push along. so it derives a deterministic angle from the node indices using big primes as hash seeds. deterministic because the same pair should always separate in the same direction. not random because randomness in layout makes things jitter.
three new tests: overlapping nodes get separated, nodes without bounds are skipped (no crash), pinned nodes stay put during collision resolution.
the Cargo.lock diff (image) is… yeah. wgpu pulls in the entire graphics stack. metal, vulkan (ash), naga (oooh fun fact! this is the Hindi name for a bunch of semi-divine half-snake beings!), glow, spirv (pov you try to type spin but absolutely FAIL). the dependency tree roughly tripled. but the layout runs on the GPU now so I’m not complaining.
also deleted the test_events.rs example from penumbra-markdown that I forgot to clean up last commit. oops.
and also made the LayoutEngine WASM-compatible by making it async. WHOOPS
Comments 0
No comments yet. Be the first!
Sign in to join the conversation.