層化サンプリング

ひとことで

標本を取る範囲を小さな区画に分け、各区画に 1 つずつランダムに点を置く方法です。ジッター（ゆらぎ）サンプリングとも呼びます。ただの乱数では、たまたま点が片側に寄って、見積もりが大きく外れることがあります。区画ごとに 1 点と決めておけば、点は必ず範囲全体に広がり、それでいて区画の中ではランダムなので、規則正しい格子のような縞模様も出ません。とても簡単な工夫で、誤差をはっきり減らせます。

ゲームでの使いどころ

• アンチエイリアス：1 画素の中に複数の標本を置いて、図形が画素をどれだけ覆っているかを求める。MSAA の標本位置も、偏りを避けるよう工夫された配置になっている。
• ソフトシャドウ・AO：光源の面や半球の方向を区画に分けて光線を飛ばす。
• ランダムな配置：マップを大きな区画に分け、各区画に敵やアイテムを 1 つずつランダムに置くと、1 か所に固まらない。ローグライクの部屋の配置にも使える。
• スポーン時間の散らし：時間を区間に分け、各区間のどこかで 1 回だけ出現させると、出現がまとまったり、長い空白ができたりしない。

しくみ

範囲 $[0, 1)^2$ を $n \times n$ の区画に分け、区画 $(i, j)$ には

の点を置きます（$\xi$ は一様乱数）。$\xi = 0.5$ に固定すれば規則正しい格子、区画を分けなければただの乱数です。層化はその中間です。

ただの乱数で平均を見積もると、誤差は標本数 $N$ に対して $1/\sqrt{N}$ でしか小さくなりません。層化すると、各区画の中のばらつきしか残らないので、なめらかな関数では誤差が大きく減ります（2 次元の図形の境目のような場合、およそ $N^{-3/4}$）。一方、規則正しい格子は誤差が小さく見えても、誤差が隣の画素とそろって同じ向きに出るので、縞（エイリアシング）として目につきます。

実装のポイント

• 順番をばらす：区画の順に使うと、先頭の数個だけ使ったときに片側に寄ります。点の一部だけを使う場合は並べ替えておきます。
• 次元が高いとき：$d$ 次元を $n^d$ 区画に分けると、数が爆発します。各次元を別々に層化して並べ替える方法（ラテン方格、N ルークス）や、低食い違い列を使います。
• 円盤や半球へ：正方形で層化した点を円盤や半球へ写すときは、区画の形をなるべく保つ写像（同心写像など）を使うと、層化の効果が残ります。

つまずきやすい点

• 標本数が平方数でない：$n \times n$ 区画にするには、標本数を 4、9、16…にそろえる必要があります。そろわない場合は、縦と横の分割数を変えるか、ほかの方法を使います。
• 毎フレーム同じ点を使う：乱数を固定したままだと、誤差の模様が画面に貼り付きます。フレームごとに変えて、時間方向に平均します。
• 格子で十分と思い込む：止まった画面では格子の方がきれいに見えることがありますが、物体が動くと縞がちらつきます。

デモで試すこと

1. 左は回転する三角形を、各画素の標本で塗った結果です。右は 1 画素の拡大で、黄色い点が図形の内側に入った標本です。
2. 「でたらめ」にすると、境目がざらざらし、右下のグラフの赤い線（誤差）が大きくなります。拡大図で、点が片側に寄る画素があることを確かめてください。
3. 「層化」では、拡大図の各区画に 1 点ずつ入り、誤差（緑）が下がります。
4. 「規則正しい格子」は誤差（青）がさらに小さく見えますが、回転させると境目に階段状の縞が動いて見えます。「1 画素の標本数」を増やして、誤差の減り方も比べてください。