Poisson Disk Sampling: A Simple Algorithm with Surprising Depth
Poisson disk sampling places points randomly but not too close together, a key tool in procedural generation and simulation. Bridson's 2007 one-page algorithm is efficient, but this post explores two improvements: a parental optimization that skips sampling angles too close to a point's parent, and tuning the distance distribution exponent to balance density and randomness. It also covers dynamic radius for stippling effects and introduces Mitchell's 2022 deterministic, maximal, and uniform sampling method.
In 2024, a team of nine mathematicians released a monstrous, nearly 1,000 page proof of the geometric Langlands conjecture, and I have accepted that I will never understand even the statements that they proved, much less the proof itself.
- akkartik
Still one of the most satisfying debug UIs I ever came up with.
- jacobolus
Folks may find https://observablehq.com/@fil/poisson-distribution-generator... useful
- Terr_
> Consider when the algorithm places a point p and then samples its annulus to get a new point q.
I was confused for a while thinking p and q were swapped here, relative to the visualization below. [0] However I now think what I missed is that that the visualization is showing two points that are already firmly-established, and the question is where a potential third (unseen, unnamed) point could be placed.
So metaphorically speaking, it's about picking a new direction of travel that isn't guaranteed to be into your own recent footsteps.
[0] You might say I have problems minding my p's and q's.