Module

Hylograph.Forces.RectCollide

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

Rectangle collision: push overlapping axis-aligned rectangles apart along the axis on which they overlap least.

Not in d3. The rule is the Rust kernel's (apply_rect_collide in force-kernel/src/forces.rs), and the two are held to each other bit for bit by test/differential.mjs.

Node i is a rectangle of half-width w_i and half-height h_i centred on its anticipated position a_i = position + velocity. A node is HELD on an axis if it cannot be moved along it: it is pinned there (fx for x, fy for y; here, whatever the config's heldX and heldY say). One iteration:

  1. Take a_i for every node that takes part, all at once, before anything moves.

  2. For every node i that takes part, and every other node j that takes part and may collide with it (see "Who collides"), both a finite, taking j in ascending order:

    dx = a_i.x - a_j.x          dy = a_i.y - a_j.y
    ox = (w_i + w_j) - |dx|     oy = (h_i + h_j) - |dy|
    

    The pair overlaps when ox > 0 and oy > 0. If it does, the push is along x if ox <= oy and along y otherwise. If i is held on that axis, nothing more happens for this pair. Otherwise

    share = 1                      if j is held on that axis
          = A_j / (A_i + A_j)      otherwise, with A = w * h
                                   (1/2 if A_i + A_j is not above 0)
    push  = s * overlap * strength * share
    v_i[axis] += push
    

    where s is the sign of dx (or dy): +1 if positive, -1 if negative, and if exactly zero, -1 when i < j and +1 when i > j.

So a held rectangle is never moved, and what overlaps it takes the whole correction; two free rectangles share it, the smaller moving more.

THE SQUEEZE. A wide rectangle nearly always overlaps another least vertically, so it is only ever pushed up or down; caught between two things that do not give way (two pinned dots, a dot and a packed row of other labels) the pushes cancel and it sits on both for ever. With squeezed: goesThrough, after the last iteration of one application of the force, for each node i and each axis it is not held on: let up be the sum of the positive pushes step 2 gave it on that axis over all the iterations, and down the sum of the negative ones, as a magnitude. If both are above 0 the node is squeezed, and it goes with one side and ignores the other:

v_i[axis] += down     if it goes up     (the downward pushes are undone)
v_i[axis] -= up       if it goes down

It goes the way it was already moving, if it was moving: with w its velocity on that axis as it was when the force was applied, if |w| > 0.001 * (up + down) it goes up when w > 0 and down when w < 0. Otherwise (a velocity that small is what is left of a movement long over, or the last of a pull dying away) it goes with the stronger side: up if up > down, down if up < down, and if they are equal, up when i is odd and down when it is even.

Going the way it is moving is what makes this resolve: the rectangle keeps on through whatever was squeezing it, a dot or another rectangle, until it is clear, where a rule that only compared the two sides would turn round as soon as it went deeper into the weaker one. It suits rectangles that nothing else is pressing together. Under a force that keeps pressing (a pull to a point that a pinned body is standing on) a squeeze is permanent and the rectangle will be walked through its neighbour, so let such a pull die away before expecting rest. With squeezed: staysPut, the default, step 2 is all there is.

Who collides. A node left out by include collides with nothing and nothing collides with it. With groups, pairs restricts the pairs: only two nodes of the same group (withinGroups), or only two nodes not of the same group (betweenGroups; a node in no group is in a different group from everyone).

Every correction in an iteration comes from the same anticipated positions, so no node is favoured by its index. Not scaled by alpha, as d3's collide is not.

The quadtree only finds the rectangles that overlap a given one. They are then put in index order before their corrections are added, which makes the result the same, bit for bit, as the loop over all pairs.

#Config Source

type Config :: Row Type -> Typetype Config row = { group :: Node row -> Membership, halfHeight :: Node row -> Number, halfWidth :: Node row -> Number, heldX :: Node row -> Boolean, heldY :: Node row -> Boolean, include :: Node row -> Boolean, iterations :: Int, pairs :: Pairs, squeezed :: Squeezed, strength :: Number }

halfWidth, halfHeight, include and group are asked once per node when the force is initialized; a half-extent of NaN counts as zero. heldX and heldY say whether a node cannot be moved along an axis, and are asked every time the force is applied, since pins come and go: Node.pinnedX and Node.pinnedY are the ones to give for nodes with fx and fy.

#defaultConfig Source

defaultConfig :: forall row. Config row

Unit squares, full strength, one iteration, every node, every pair, nothing held, a squeezed rectangle stays put.

#Pairs Source

data Pairs

Which pairs of rectangles collide.

#everyPair Source

#withinGroups Source

#betweenGroups Source

#Squeezed Source

data Squeezed

What a rectangle pushed from both sides does.

#RectCollide Source

newtype RectCollide :: Row Type -> Typenewtype RectCollide row

An initialized rectangle collision: the nodes that take part.

#initialize Source

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

#apply Source

apply :: forall row. RectCollide row -> Effect Unit

A node's velocity is only ever written by its own turn, so its anticipated position, read at its turn, is the one the tree was built from.