Module

Hylograph.Forces.ManyBody

Package
purescript-hylograph-forces
Repository
afcondon/purescript-hylograph-forces

The many-body force: every node attracts or repels every other, with the far field approximated by Barnes-Hut over a quadtree.

Ported from d3-force 3.0.0, manyBody.js (ISC, Copyright 2010-2021 Mike Bostock); see LICENSE. The arithmetic, its order and the draws from the random source follow d3 line for line, so the velocities agree with d3-force to the bit.

Each application has three steps, and the first two are pure:

  1. build the quadtree of the nodes' positions (Quadtree.build);
  2. turn it into a chain of Clusters: d3's accumulate, which gives every square its total strength and centre, done together with the threading that lets the walk run without a stack;
  3. for each node in turn, walk the chain to get the node's new velocity, and write it.

The chain is the tree in d3's visiting order. Each cluster knows the cluster to go to when its square has to be opened (inside) and the one to go to when the square is finished with (after), so "visit, and skip the children if the callback says so" becomes a loop that follows one pointer or the other.

#Config Source

type Config :: Row Type -> Typetype Config row = { distanceMax :: Number, distanceMin :: Number, group :: Node row -> Membership, scope :: Scope, strength :: Node row -> Number, theta :: Number }

d3's forceManyBody settings. strength is asked once per node when the force is initialized; negative repels.

#defaultConfig Source

defaultConfig :: forall row. Config row

d3's defaults: strength -30, theta 0.9, distances from 1 to infinity, between every pair of nodes.

#Scope Source

data Scope

Which pairs of nodes the force acts between. Only EveryPair is d3's; the other two are the Rust kernel's scoped many-body (apply_many_body in force-kernel/src/forces.rs), which test/differential.mjs holds this to bit for bit.

  • WithinGroups: for each group in ascending order of its number, d3's many-body is applied to that group's nodes alone: its own quadtree, its nodes in node order. A node in no group neither exerts nor feels anything.
  • BetweenGroups: d3's many-body over all the nodes, followed by WithinGroups with every strength negated. With theta 0 that is the sum over pairs in different groups; with theta above 0 it is the difference of two Barnes-Hut approximations. A node in no group interacts with every node.

The random source is drawn from in that order too.

#everyPair Source

#withinGroups Source

#betweenGroups Source

#ManyBody Source

newtype ManyBody :: Row Type -> Typenewtype ManyBody row

An initialized many-body force: every node, and the nodes of each group as the scope wants them (with their strengths negated for BetweenGroups).

#initialize Source

initialize :: forall row. Config row -> Source -> Array (Node row) -> ManyBody row

d3's force.initialize(nodes, random). A node's index is its place in the array, which is what d3's simulation sets node.index to.

#apply Source

apply :: forall row. ManyBody row -> Number -> Effect Unit

d3's force(alpha): add the many-body acceleration to every node's velocity.