ポアソンディスクサンプリング (poisson disk sampling)

ゲームで木をまんべんなく生やしたいと思いポアソンディスクサンプリング(poisson disk sampling)を利用しようとしたが技術がないのでアルゴリズムの短い論文を読んで実装するのに非常に時間がかかったので、ここに要約を書こうと思う。ポアソンディスクサンプリングとは点同士が一定以上の間隔を保って面を覆うために使われる技法で、間隔を調整することで濃淡から絵を描くこともできる。

論文の要旨

確定した点のリスト、将来性のある点のリスト、及び２次元のグリッドを用意する。確定した点のリストには最終的に出力される点、将来性のある点のリストにはその点を基準に更に点を配置できる点が入る。グリッドは点同士の距離を計算する際に計算を簡略するために用いられる。点同士の最低間隔をrとする。

１　まずランダムな点を１つ生成する。これは直ちに確定した点のリストに入る（１つ目の点だから）。同時にこの点は将来性のある点のリストにも入る（周りにはまだ１つの点もないのでこの点を基準に新しい点を生成できる可能性があるから）。　確定した点はグリッドに登録し点同士の距離の比較に備える。
２　この点を基準点とする。この点の周囲半径r～2rのリングに収まる範囲に新しい点を生成する。この点とすべての確定した点との距離を計測し、間隔が小さすぎれば（グリッドを利用し計算を簡略する）その点を破棄する。確定した点たちと十分な間隔がある点は確定した点リストおよび将来性のある点リストに入りグリッドにも登録される。こうしてリング内に均等に点を生成し続ける（１０～３０回程度）。この試みの後、もしリング内に生成した点がすべて確定した点たちとの間隔の不足から破棄されていれば基準になった点にはもう将来性がないということなので、この基準になった点は将来性のある点リストから除かれる。
３　次の基準点は将来性のある点のリストの最後尾にする。そうしてまた２の処理を行う。
４　将来性のある点リストがカラになるまでこの処理を繰り返す。

この方法で素早く点を生成しゲームで指定範囲内に木を生えさせた。

　この場合点は白黒のテクスチャ上で黒のエリアの部分に生成されている。黒の部分が複数あり互いに白で隔てられている場合、アルゴリズムの特性上一つの塊の黒の部分でしか点が生成できない。そこでまず大雑把に全体に点を生成し、その各々の点を基準に２度目の点を生成することですべての黒の塊に点を生成している。