Low-discrepancy sequence (準亂數列)

• 前言

在上一章介紹了如何使用一個2維變數 (ξ1,ξ2)來得到一個 GGX 分布的法線向量，

在這裡衍生了一個問題，

要如何找到一個合適的2維變數陣列作為積分用的採樣點的法線向量。

本章節就是介紹使用 Low-discrepancy sequence (準亂數列) 

作為 Quasi Monte Carlo Method 取樣點的優點與實作方法。

• Monte Carlo Method

Monte Carlo Method 是使用亂數取樣點作為積分計算的數列，

若使用 N 個樣本數，則他的積分誤差的收斂速度為 O(N^−0.5)[1]。

這代表著如果我要提升2倍的精度，我需要提供4倍的樣本數。

• Quasi Monte Carlo Method

不同於 Monte Carlo Method 使用亂數列作為採樣點，

 Quasi Monte Carlo Method 使用了 Low-discrepancy sequence 作為採樣點，

使得其積分誤差的收斂速度為 O(log(N)^dim/N)， 其中 dim 為 dimension(次元數)。

這代表著如果在 2 維空間使用 Quasi Monte Carlo Method 做積分，

要提升2倍的精度，只需要提供2倍的樣本數。

因此可以得知若在低次元空間下做積分，

Quasi Monte Carlo Method 比 Monte Carlo Method 有著更高的收斂速度。

• Hammersley Sequence

回到了一開始的問題，如何找到一個合適的2維變數陣列作為積分用的採樣點的法線向量。

在這裡就是使用 Quasi Monte Carlo Method，

利用 Low-discrepancy sequence 找出採樣點陣列做積分計算。

本章節接下來會說明並實作一個常用的 Low-discrepancy sequence，

也就是 Hammersley Sequence。

基本理論很簡單

圖片來源 : Physically Based Rendering - 7.4 The Halton Sampler

我給定一個索引值 α，先將其轉為2進制，

再依序將2進制的每個位數由後往前依序放入小數點後，在由前往後乘以2的倒數，

就是回傳結果。

ex.

0.1     = 1 * 2⁻¹ = 0.5
0.01   = 0 * 2⁻¹ + 1 * 2⁻² = 0.25
0.11   = 1 * 2⁻¹ + 1 * 2⁻² = 0.75
0.001 = 0 * 2⁻¹ + 0 * 2⁻² + 1 * 2⁻³= 0.125
...

如此可以得到一個在 [0,1] 數列。

下圖為  Hammersley Sequence 的2維採樣結果

圖片來源 : Physically Based Rendering - 7.4 The Halton Sampler

從上圖可知，這是一個非隨機的數列，

但是它的結果分布卻是有著微小差異(不知情的人可能會認為他是一個隨機採樣結果)。

這種數列就叫做 Low-discrepancy sequence。

2維 Hammersley Sequence 的實作方式如下

float RadicalInverse_VdC(uint bits) 
{
    bits = (bits << 16u) | (bits >> 16u);
    bits = ((bits & 0x55555555u) << 1u) | ((bits & 0xAAAAAAAAu) >> 1u);
    bits = ((bits & 0x33333333u) << 2u) | ((bits & 0xCCCCCCCCu) >> 2u);
    bits = ((bits & 0x0F0F0F0Fu) << 4u) | ((bits & 0xF0F0F0F0u) >> 4u);
    bits = ((bits & 0x00FF00FFu) << 8u) | ((bits & 0xFF00FF00u) >> 8u);
    return float(bits) * 2.3283064365386963e-10; // / 0x100000000
}

float2 Hammersley(uint i, uint N)
{
    return float2(float(i)/float(N), RadicalInverse_VdC(i));
}  

• References

1. Søren Asmussen and Peter W. Glynn, Stochastic Simulation: Algorithms and Analysis, Springer, 2007, 476 pages

2. Physically Based Rendering - 7.4 The Halton Sampler