Halton Sequence Demonstration and Resources

November 15, 2022

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

Additional Resources

Read more