ブリッドソンのポアソンディスクサンプリング：より速く、より密に、それでもランダムに

ポアソンディスクサンプリングは、プロシージャルな森、ステイプル、ブルーノイズテクスチャの背後にある主力技術だ。ブリッドソンの2007年の1ページアルゴリズムは今も定番だが、最適とは言えない。2つの調整—無駄な角度サンプルをスキップするものと、サンプリング半径にバイアスをかけるもの—によって、反復回数を劇的に減らし、出力を自然に見せるランダム性を犠牲にせずに点をより密に詰められる。

ブリッドソンのアルゴリズムの要点

目標は、任意の2点が最小距離rより近づかないように、空間にランダムに点を配置することだ。単純な拒否サンプリングは、空間が埋まるにつれて急速に劣化する。ブリッドソンの工夫は、新しい隣接点を受け入れられる可能性のある点のactiveリストを維持することだ。各アクティブ点について、rから2rの間の環状領域を最大k回サンプリングし、背景グリッドを使って定数時間で衝突をチェックする。有効な点が見つかればアクティブリストに追加し、見つからなければ現在の点を引退させる。推奨されるk=30は、成功率と無駄な試行のバランスを取る。

最適化1：親の影をスキップする

新しい点qがpから生成されるとき、qの周りの環状領域のうちpに面する部分は部分的に無効だ—そこにある点はpに近すぎるからだ。各点の親を保存することで、無効な方向の角度円錐を計算し、有効な範囲だけをサンプリングできる。円錐の半角は、内側の円か外側の円のどちらが境界になるかに応じて、2つのarccos項の最小値で与えられる。この単純な簿記により、領域を埋めるのに必要な反復回数が減る。著者の実験が示す通りだ。

最適化2：半径にバイアスをかける

環状領域を一様にサンプリングする代わりに、距離分布を外側の端に偏らせることができる。距離のCDFはd次元でx^dに比例するが、指数dを調整可能な定数cに置き換えられる。cの負の値は点を親から遠ざけ、空間により多くの点を詰め込む。著者は経験的に、kが15から40の間でc = -1.4 - 17/sqrt(k)がうまく機能し、ランダム逐次吸着の理論的最大値に近い密度を生み出すことを発見した。ただし注意：負にしすぎると、出力が目に見えてパターン化し、ランダム性を台無しにする文字列やギャップが生じる。

ステイプルと並列変種

ポアソンディスクサンプリングは一定のrに限定されない。rを位置の関数にすることで、画像をステイプルできる—暗い領域にはより密な点が得られる。著者はまた、リアルタイムのステイプルを可能にするGPU並列アルゴリズムであるPixelPieを紹介し、スコット・ミッチェルによる2022年の決定論的手法がもっと注目されるべきだと述べている。

重要なポイント

• ブリッドソンのアルゴリズムは効率的だが、最適化の余地を残している。
• 親の点を保存することで、無効な角度範囲をスキップでき、反復回数が減る。
• 負の指数でサンプリング半径にバイアスをかけると、点密度が高まる。
• 極端なバイアスはランダム性を破壊するので、慎重に調整する必要がある。
• PixelPieのようなGPU並列変種は、リアルタイムアプリケーションを可能にする。