Halton Sequence Demonstration and Resources
January 24, 2023
I recently learned about the Halton sequence, a quasirandom, low discrepancy number sequence, and thought it might be useful to other game devs looking for alternative random noise generation algorithms.
Halton sequence is a low discrepancy deterministic sequence based on coprime numbers. It quickly covers the range [0,1], and you can extend it to n dimensions (i.e., 3D). This is great for randomly and quickly distributing procedural objects on terrain. For my use case, it's a good algorithm to use for subpixel jitter when conducting temporal anti-aliasing (e.g., for volumetric cloud or fog rendering).
The only drawback is that it requires a while() loop, which can run over 20 times per sample depending on your index. Presumably, sampling a texture within a given domain would be faster than computing this value for every screen pixel by requiring just one texture sample as compared to 40+ division operators, 20+ addition operators, 20+ multiplication operators, and 20+ mod operators, plus casting.
Therefore, I've drafted a tiny script that can compute and encode the sequence into an RGBA texture2D across a given domain, though 256 should be sufficient for most use cases.
I put together a brief video demonstrating the results of the Halton sequence in 1D, 2D, and 3D: Visualizing the Halton Sequence (+ Script Download) - YouTube
You can directly pull the script used for the demo from a gist on Github: A demonstration of Halton Sequencing Quasirandom Noise (github.com)
Hope this is interesting and helpful!
I copied this post to my website
- Learn more about the Halton sequence: https://en.wikipedia.org/wiki/Halton_sequence
- Learn more about low discrepancy sequences: https://en.wikipedia.org/wiki/Low-discrepancy_sequence
- Learn more about coprime numbers: https://en.wikipedia.org/wiki/Coprime_integers
- View an implementation on Shadertoy from piyushslayer: Halton(2, 3) Sequence (shadertoy.com)
- A detailed review of the Halton sequence by Jacob Rus on Observable: Halton Sequence / Jacob Rus / Observable (observablehq.com)