自然なランダム配置の決定版！ポアソンディスクサンプリングを徹底解説

ポアソンディスクサンプリング（Poisson Disk Sampling）は、空間内に点をランダムに配置しつつも、近すぎる点が発生しないように制御する非常に強力なアルゴリズムです。ゲーム開発における草木の配置や、生成アート、テクスチャ生成など、均等でありながら自然なバラつきを持たせたいシーンで重宝されます。単純なランダム配置とは異なり、各点に最小距離（半径）を設けることで、過密やスカスカな領域を防ぐことが可能です。実装の肝は、近傍点探索を効率化するためにグリッド構造を利用することにあります。

これ参考になるかもよ https://observablehq.com/@fil/poisson-distribution-generators

こういう問題って最高だよね。だって、純粋なランダムじゃなくて、人間が「ランダムだ」と感じるものを作ろうとしてるんだから。ブルーノイズもその良い例だね。

Casey Muratoriのブログ記事が面白いかも。ゲーム内で草をランダムに配置する話で、ブルーノイズを使ってるよ：https://caseymuratori.com/blog_0013

これって低不一致数列（low-discrepancy sequence）として使えるのかな？

生成されたポイントが線状に並ぶことが多くて、コンピュータグラフィックスだとエイリアシングの原因になりそうなんだけど、なんで低不一致数列を使わないんだろう？

今まで作った中で一番満足度が高いデバッグUIの一つ。 https://akkartik.name/post/2023-11-04-devlog

おっ、自分が想像してたディスクサンプリングとはちょっと種類が違うな。

アルゴリズムがポイントpを配置し、そのアニュラス（環状領域）をサンプリングして新しいポイントqを得る場合を考えてみて。

下の図と見比べて、しばらくpとqが逆だと思い込んで混乱してたよ。[0] でも今考えると、見落としてたのは、図がすでに確定済みの2つのポイントを示していて、3つ目の（まだ見ぬ）ポイントをどこに置けるかという話だったってことだね。

例えるなら、自分のついさっきの足跡を踏まないような新しい進行方向を選ぶ、みたいな感じか。

[0] pとqを取り違える（p's and q's）ってね。

シェーダーでピクセルごとにやる方法がどうしても見つからなかったな。Bridsonのアルゴリズムにはアクティブリストが必要だし。結局、セルをハッシュ化してその中でジッターをかける方法に落ち着いたよ。