Animating Family Trees, a la Pachinko

In musing on how a family tree is kind of like Pachinko, I wondered if this could be animated somewhat like a Pachinko machine in the family tree visualization I have been playing with (available at https://learnforeverlearn.com/ancestors).

I took some first steps towards this by pulling out the Bezier curve parameters d3 is generating for the links between nodes, coupled with Particle in Cell's notes on computing the intersection between Bezier curves and a line , to make some first steps towards a Pachinko-like animation effect. Some details on this implementation are at the bottom of this note.

A few youtube videos demonstrating this are below. You can also go directly to the interactive visualization with the tree for Charles II of Spain automatically loaded via this link, and clicking the "Do Pachinko" button.

An animation in time of my family tree

An animation of pedigree collapse in the family tree of the British Monarchy
(direct link to this tree is at
https://learnforeverlearn.com/ancestors/?file=royal92.txt

While I still need to play with the timing and smoothness, it is nevertheless interesting to watch the animations play over and over, reflecting on the huge number of things that had to happen (or not happen) through the centuries to result in me being here today.

Equations to be Solved to Find the Coordinates of the Animated Circles

Shown below is an example of a curve displayed on the screen and the svg path generated by d3:

${\bf P_0}$ is the center of the circle for the parent, and ${\bf P_3}$ is the center of the circle for the child. The C stuff in there for the "d" attribute contains the cubic Bézier commands. The equation for the thicker blue curve is given by
$${\bf{r}}(t) = {(1-t)}^3 {\bf P_0} + 3{(1-t)}^2 t {\bf P_1} + 3{(1-t)} t^2 {\bf P_2} + t^3 {\bf P_3}, \ t \in [0,1]$$ Placing a circle on this curve at a given year $\hat{y}$ (i.e., height) requires finding the $\hat{t}$ so that $$\begin{eqnarray} \hat{y} & = & \text{y-coordinate of } {\bf{r}}(\hat{t}) \\ & = & \text{y-coordinate of } {(1-\hat{t})}^3 {\bf P_0} + 3{(1- \hat{t})}^2 \hat{t} {\bf P_1} + 3{(1-\hat{t})} \hat{t}^2 {\bf P_2} + \hat{t}^3 {\bf P_3} \end{eqnarray} $$

and then using that $\hat{t}$ to find the $x$ coordinate $\hat{x}$ of the intersection. The center of the animated circle is then $(\hat{x},\hat{y})$. The cubic equation can be solved exactly (some preprocessing is done using the parent and child birth years to ensure that the line at year $y$ passes through the curve) - but there's some potential tedium dealing with multiple roots. The root-finding implementation in this visualization, from Particle in Cell, is originally from Stephen Schmitt (this was apparently on a Verizon personal web space site that no longer exists).

There are optimizations I need to address with respect to quickly finding the paths intersecting a given point in time, but it seems to work ok on small to moderately-sized trees.