Halton Sequence Demonstration and Resources

November 5, 2022

Introduction

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.

What is the Halton Sequence?

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.

The Halton sequence is an example of generating random values. To learn about other random number generation methods in Unity, check out our article on the Unity Random method.

How do I use the Halton Sequence in Unity?

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 here:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

// Note that the Halton bases must consist of coprime integers._
// 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_

public class HaltonSequencer : MonoBehaviour

{
  [Header("Texture Generator")]
  public bool generateHaltonTexture;

  [Header("Demo")]
  public bool generateHaltonSamples;
  public float rate = 0.2f;
  public GameObject haltonSample;
  private float t = 0;
  private int index = 1;
  public float boxDimension = 5f;

  private void OnValidate()
  {
    if (generateHaltonTexture)
    {
      GenerateHaltonTexture();
      generateHaltonTexture = false;
    }
    if (generateHaltonSamples)
    {
      t = Time.time;
    }
  }
  
  private void Update()
  {
    if (generateHaltonSamples)
    {
      if(Time.time - t > rate)
      {
        float x = (Halton(2, index) - 0.5f) * boxDimension;
        float y = (Halton(3, index) - 0.5f) * boxDimension;
        float z = (Halton(5, index) - 0.5f) * boxDimension;
        Instantiate(haltonSample, new Vector3(x, z, y), Quaternion.identity);
        index++;
        t = Time.time;
      }
    }
  }
  
  private float Halton(int b, int index)
  {
    float result = 0.0f;
    float f = 1.0f;
    while (index > 0)
    {
      f = f / (float)b;
      result += f * (float)(index % b);
      index = index / b;
    }
    return result;
  }
  
  private void GenerateHaltonTexture(int baseR = 2, int baseG = 3, int baseB = 5, int baseA = 7, int maxIndex = 256)
  {
    Texture2D t = new Texture2D(maxIndex, 1, TextureFormat.RGBA32, false);
    Color[] c = new Color[maxIndex];

    for (int x = 0; x < maxIndex; x++)
    {
      float r = Halton(baseR, x + 30);
      float g = Halton(baseG, x + 30);
      float b = Halton(baseB, x + 30);
      float a = Halton(baseA, x + 30);
      c[x] = new Color(r, g, b, a);
    }

    t.SetPixels(c);
    t.Apply();
    byte[] encodedTexture = t.EncodeToPNG();
    System.IO.File.WriteAllBytes(Application.dataPath + "/halton.png", encodedTexture);
  }
  
  private void OnGUI()
  {
    GUI.Label(new Rect(0, 0, 300, 100), "Index: " + index);
  }
  
  private void OnDrawGizmos()
  {
    Gizmos.DrawWireCube(Vector3.zero, Vector3.one * 5);
  }
}

Hope this is interesting and helpful!

What is randomization good for?

Randomization is perfect to help procedurally create maps or levels. It is also a great tool for brainstorming. For example, you can use randomization to help you brainstorm new game ideas like our random game generator.