重要度サンプリング・逆CDF

ひとことで

合計や平均を少ない標本で見積もるとき、結果に大きく効く所から多めに標本を取り、その分だけ重みを下げて足す方法です。空の明るさを合計するなら、ほんの一部の太陽が大部分を占めます。空をまんべんなく調べると、太陽に当たる標本はまれで、当たったかどうかで結果が大きくぶれます。太陽の付近を多く調べて、そのぶん 1 本の寄与を小さく数えれば、ぶれが大きく減ります。狙った分布から値を作る方法として、逆 CDF 法（累積分布関数の逆関数）がよく使われます。

ゲームでの使いどころ

• 環境マップの光：イメージベースドライティングやパストレーシングで、HDR の空の画像から、明るい画素（太陽や窓）を優先して光線を飛ばす。
• 反射の方向：光沢のある面では、GGX の分布に合わせて反射方向を選ぶ。拡散面では余弦重み。
• 多数の光源から選ぶ：何千もの光源の中から、明るくて近いものほど高い確率で選んで影を計算する（ReSTIR などの土台）。
• 地図から出現位置を選ぶ：「敵が出やすい所」を表した密度マップから、その密度に比例して出現位置を選ぶ。2 次元の逆 CDF で作れる。

しくみ

$\int f(x)\,dx$ を、確率密度 $p(x)$ で選んだ標本 $x_k$ で見積もるときは

とします。$p$ が $f$ と同じ形（$p \propto f$）なら、$f/p$ はどの標本でも同じ値になり、ばらつきは 0 になります。形が近いほどばらつきが減り、逆に $f$ が大きい所で $p$ が小さいと、まれに $f/p$ がとても大きくなって、かえって悪化します。

逆 CDF 法：累積分布関数 $P(x) = \int_0^x p(t)\,dt$ は 0 から 1 へ増える関数です。一様乱数 $u$ を縦軸に取り、$P(x) = u$ となる $x$ を横軸から読み取ると、$x$ は密度 $p$ に従います。$p$ が大きい所では $P$ が急に立ち上がるので、多くの $u$ がそこへ集まります。

画像のような表で決まる分布では、各区間の重みを足し合わせた表（区分定数の CDF）を作り、$u$ が入る区間を二分探索で見つけます。2 次元の画像では、行ごとの合計で行を選び、その行の中で列を選びます。

実装のポイント

• 確率密度も一緒に返す：見積もりには $f/p$ が必要です。選んだ値と一緒に、その値の確率密度を返す作りにします。
• ゼロの重みに注意：$p = 0$ の所で $f \ne 0$ だと、その部分は決して見積もりに入りません。重みに小さな下限を付けるか、一様な分布と混ぜます（MIS：複数の分布の組み合わせ）。
• 抽選を何度もするなら：同じ表から大量に選ぶ場合は、二分探索の代わりにエイリアス法を使うと、1 回あたりの手間が一定になります。
• 解析的に逆関数が求まる場合：指数分布 $x = -\ln(1 - u)/\lambda$（次のイベントまでの待ち時間）や、円盤の半径の平方根などは、式で直接求められます。

つまずきやすい点

• 重みで割り忘れる：多く選んだ所を割り引かないと、明るい所が何倍にも数えられ、結果が明るくなりすぎます。
• 分布が合っていない：思い込みで作った分布が実際の $f$ とずれていると、まれに巨大な値（ホタルのような明るい点）が出ます。
• CDF の端：最後の値が浮動小数点の誤差で 1 にならないと、$u$ が 1 に近いとき区間が見つからないことがあります。最後を 1 に固定します。

デモで試すこと

1. 上のグラフの黄色が空の明るさ $f$ で、右の細い山が太陽です。下は選んだ分布の CDF（紫）で、縦軸の $u$ から横へ読んだ点線が、そのまま上の標本（青い点）になります。
2. 「一様」では CDF が斜めの直線になり、標本は均等に散らばります。右下のグラフの赤い線（16 標本での見積もり）が、太陽に当たるかどうかで大きく上下します。
3. 「明るさと同じ形」では、CDF が太陽の所で急に立ち上がり、標本が太陽の付近に集まります。見積もり（緑）はほとんどぶれません。
4. 「形が合わない分布」では、太陽から外れた所を重視するため、緑の線が一様よりも大きく跳ねることがあります。ヒストグラムが確率密度（点線）に近づいていく様子も確かめてください。