Suppose we want to generate uniformly distributed points on a sphere. We might start off by picking spherical coordinates (λ, φ) from two uniform distributions, λ ∈ [-180°, 180°) and φ ∈ [-90°, 90°).
However, we can quickly see that this will result in an uneven distribution, with the density increasing as we get closer to the poles.
One way to explain this is to look at the how the area of a given “square” of width Δλ and height Δφ varies with φ.
Try picking any square on the graticule (the spherical grid). See how the squares get smaller towards the poles?
If we want any area on the sphere to contain approximately the same density of points, there are a number of solutions.
One solution is to pick λ ∈ [-180°, 180°) as before and then set φ = cos-1(2x - 1), where x is uniformly distributed and x ∈ [0, 1).
Although we’ve successfully generated uniformly distributed points on a sphere, it feels messy. Some points seem too close together, and some seem too far apart.
Perhaps we can drop our requirement for points to be uniformly distributed, but keep them well-distributed.
A more æsthetically pleasing pattern can be generated using Poisson-disc sampling, where no points are less than a minimum distance apart.
This produces spectral characteristics similar to blue noise, i.e. less clusters of high and low density.
Note that the points are no longer independent of each other, hence they are no longer uniformly distributed.
Mitchell’s best-candidate algorithm is a straightforward approximation. Generate a number of candidate samples and pick the furthest from all previous samples.
Poisson-disc sampling can of course be applied to other surfaces too e.g. it is often used on 2D planes.
Oh, and don’t forget to drag the spheres!