Basic concepts in this post, but worth refreshing.
Very often in Computer Graphics (in Monte Carlo integration in particular) you need to sample
N points uniformly over the surface of a square, a disk, or a sphere.
Depending on many (many!) factors such as how critical the quality of the random distribution needs to be, performance or code simplicity considerations, availability of a high-quality randomization seed, etc… one may choose one method or another. There are plenty of options, and each comes with their own strengths and weaknesses.
In this post I will talk about:
- The Equal-Area transform to turn a pair of uniformly distributed random numbers in the unit square into uniformly distributed points over the surface of the the unit disk/sphere.
- A super-simple Fibonacci-based method to generate
Npoints that uniformly cover the unit square (and hence the unit disk/sphere).
u a uniform distribution of 2D points in the surface of the unit square, the transforms to produce uniform distributions of 2D points in the unit disk, or 3D points in the unit sphere are:
There are very clean-cut explanations for these on the always fantastic wolfram.com website.
These are based on the area (disk) and solid angle (sphere) differential elements.
The algorithm to generate the first
N points in the Fibonacci lattice goes like this:
This produces a stratified distribution of points in the unit square.
The beauty of this method is that it’s a strikingly simple couple of divs and a mod. Unlike most series generators, however, it requires that you know
N beforehand. Other usual methods like the ones depicted later in this post are incremental, so each new sample is spawned next to the previous ones. The Fibonacci lattice, on the other hand, “squeezes” previous samples as new ones come in, as illustrated by the videos below.
Fibonacci lattice (square/disk/sphere)
This videos simply plug the Fibonacci lattice formula to the Equal-Area transforms above.
As a bonus, the next videos are generated like the ones above, but using a uniformly distributed QRN generator (the popular and very strong Mersenne Twister) and the van Der Corput stratified series (in particular, the Halton sequence using primes