Lucas Sifoni

Fastfish, Elixir + Rust 2D poisson disc sampling

elixir rust explorations 2d

Source at

Random but natural disk placement

I recently had the occasion to implement two algorithms aiming to place disks on a surface. My constraints were perceptual, as the placement should look homogeneous to the eye while not too deterministic. An hexagonal grid is the opposite feel of what I was looking for.

I stumbled on this elegant visualisation by Jason Davies (, based on the paper “Fast Poisson Disk Sampling in Arbitrary Dimensions” by Robert Bridson, University of British Columbia.

A first implementation in Elixir & Rust, based on the paper, quickly gave me a similar result to Jason’s visualisation.

The algorithm

Letting aside the performance optimizations in Roberd Bridson’s paper, here are the general steps :

This works but lifts the need to check for collisions at every step. Bridson’s paper solves this with a data structure that represents a background grid, sampling the domain to ensure there’s at most one disk in every cell. As every disk has the same radius, you just have to check nearby cells for collisions.

Multi-radius sampling

My task needed to have a compact cluster of disks, unbounded, with a defined number of disks having defined radii. The picture below is a visualisation of the expected result :

I replaced the background grid by a subsetting of the total disk list, based on existing radii and next-disk radius. We check the circles in a circular shell for collisions. It is less efficient than the background grid but works well with a diverse disk list.

What is interesting is the variety of clusters you get by varying the value of K, the number of allowed attempts :

K = 2

K = 5

K = 10

K = 30


My use-case has those parameters :

Benchmarking Elixir, 100 samples, k=30 ...
Benchmarking Rust  , 100 samples, k=30 ...

Name                                ips        average  deviation         median         99th %
Rust  , 100 samples, k=30        6.90 K       0.145 ms    ±67.27%       0.186 ms        0.31 ms
Elixir, 100 samples, k=30        0.71 K        1.42 ms     ±8.98%        1.40 ms        1.69 ms

Benchmarking Elixir, 500 samples, k=30 ...
Benchmarking Rust  , 500 samples, k=30 ...

Name                                ips        average  deviation         median         99th %
Rust  , 500 samples, k=30        1.16 K        0.86 ms    ±93.65%        1.01 ms        1.96 ms
Elixir, 500 samples, k=30      0.0477 K       20.96 ms     ±2.88%       20.92 ms       22.45 ms

So, for my use-case, fair enough. I’ll have to start investigating how did I get this variability on the Rust side though. My Rust isn’t yet that idiomatic, and rewriting it in a few months should shed light on that matter.

Previous post : [Video, 2h30] Fabrication d'un miroir primaire amateur
Next post : [Video, 35mn] f(x) = 📖, vers un système généraliste d'automatisation du design ?