This project was inspired by the fantastic pen plotter visualizations created by Michael Fogleman.
Poisson Disk Sampling is a technique for drawing batches of blue noise distributed samples from an n-dimensional domain. The method works by selecting an initial, seed, point and proposing
k (the branching factor) random points within 1 to 2 radii
r of the initial point. For each of these proposal points we test whether they are closer than the threshold radius
r from any of the accepted points (initially just the seed point). If the point is far enough away from any of the accepted points, it becomes accepted, and we sample
k new points around it for later processing. If the point is too close to another accepted point it is immediately discarded.
By continuing the process for a given number of accepted points, until the n-dimensional space can no longer be filled without points being closer than the threshold
r, or some other criteria is met we end up with a set of well distributed points that have nice mathematical properties when used in stochastic approximation methods.
An interesting observation is that the set of sample points is "grown" outwards from the seed point, and that each accepted point can trace its origin to a single parent point which spawned it. If we connect the sampled points as a tree hierarchy we can visualize the growth pattern of sample set as a tree.
The implementation I used to generate the above image used the sampling algorithm described in Fast Poisson Disk Sampling in Arbitrary Dimension, Robert Bridson 2007 which can produce batches of well distributed samples in
O(n) computation time.
I have released the code for this project open source as a jupyter notebook. The main bottleneck in this code is actually the line plotting of the sample tree due to limitations of Matplotlib. With a better method of drawing the generated trees larger and deeper growth patterns could easily be visualized.