Halton Sequence Demonstration and Resources

April 26, 2023

On this page

    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

    Michael Sacco
    Founder & CEO

    Michael Sacco is the Founder and CEO of OccaSoftware where he specializes in developing game assets for Unity game developers. With a background ranging from startups to American Express, he's been building great products for more than 10 years.


    Recommended Articles