Low-Discrepancy Sequence / Sobol

This explanation is currently available in Japanese.

ひとことで

次の点を「まだすいている所」に置くように作られた、空間を均等に埋めていく数列です。乱数の代わりに使うと、点の数がいくつの時点でも、範囲全体がまんべんなく埋まっています。ハルトン列、ソボル列、R2 列（黄金比を使う列）などがあります。乱数ではないので「準乱数」とも呼ばれ、これを使った見積もりは準モンテカルロ法と呼ばれます。

ゲームでの使いどころ

• TAA のジッター：TAA では、毎フレーム画素の中の標本位置を少しずつずらします。ハルトン列（2, 3）の最初の 8〜16 点を使うのが定番。何フレーム目で区切っても、画素の中がまんべんなく埋まる。
• レイトレーシングの標本：ソフトシャドウ、AO、GI で、少ない光線でもノイズを減らす。
• 点の配置：R2 列やフィボナッチ格子で、ドームの形の配置、花の種のような並び、球面上の方向を作る。点の数を後から増やしても、すでに置いた点を動かさずに済む。
• パラメータの探索：多数の設定を調べるとき、格子より少ない数で空間を均等に試す。

しくみ

土台は 根基逆関数 です。整数 $i$ を $b$ 進数で書き、その桁を小数点の反対側へ裏返します。

2 進数なら、1 = 1 → 0.1（= 0.5）、2 = 10 → 0.01（= 0.25）、3 = 11 → 0.11（= 0.75）となり、0.5、0.25、0.75、0.125…と、すき間を半分ずつ埋めていきます（ファン・デル・コルプト列）。

• ハルトン列：次元ごとに違う素数の基数を使い、$(\phi_2(i), \phi_3(i))$ とします。
• ソボル列：どの次元も 2 進数で作り、次元ごとの「方向数」との排他的論理和で桁をかき混ぜます。ビット演算だけで速く、高い次元でも質が落ちにくいので、レンダリングで広く使われます。
• R2 列：$x^3 = x + 1$ の実数解 $g \approx 1.3247$（2 次元の黄金比）を使い、$\big(\{0.5 + i/g\},\ \{0.5 + i/g^2\}\big)$ とします（$\{\cdot\}$ は小数部分）。足し算だけで作れます。

点の偏りの大きさは「食い違い量（ディスクレパンシー）」で測ります。これが小さい列ほど、どの長方形の中にも面積に比例した数の点が入ります。

実装のポイント

• 画素ごとにずらす：全画素で同じ列を使うと、誤差が画面全体でそろい、縞として見えます。画素ごとにブルーノイズなどでずらす（クランリー＝パターソンの回転）か、ソボル列をかき混ぜ（スクランブル）ます。
• ハルトン列の高い次元：大きな素数の基数では、最初のうち点が斜めに並ぶ相関が出ます。高い次元にはソボル列が向いています。
• 0 番目の点：多くの列は 0 番目が原点 $(0, 0)$ です。偏りを避けるため、1 番目から使うことがよくあります。

つまずきやすい点

• 乱数の代わりに何でも置き換える：次元どうしの組み合わせが重要なので、同じ列の同じ次元を別の用途に使い回すと、相関が出て結果がゆがみます。
• 途中から使う：列の途中の一部だけを使うと、均等さの保証が弱くなります。
• 偏りのなさ＝ランダムさではない：規則的に埋めていくので、点の並びに模様が見えることがあります。配置の見た目が大事なら、ポアソンディスク分布の方が自然です。

デモで試すこと

1. 4 つの正方形に同時に点が増えていきます。でたらめ（赤）は固まりやすき間ができますが、ハルトン列・ソボル列・R2 列は、少ない点のうちから全体がまんべんなく埋まります。
2. 「8 × 8 の区画」を表示して、「空の区画」の数を比べてください。低食い違い列はすぐに 0 になります。
3. 右下のグラフは、4 分の 1 円の中に入った点の割合から円の面積を見積もったときの誤差です。低食い違い列の方がすばやく小さくなります。
4. 「1 秒に増やす点の数」を下げて、ハルトン列が「すき間を半分ずつ埋める」ように点を置いていく様子を観察してください。