Fast Poisson Disk Sampling in Arbitrary Dimensions
Paper（700 words）
Abstract
- 既存の手法は，2次元より大きい次元のサンプルを容易に生成することができない．
- 本論文では，O(N)でポアソンディスクサンプルを生成するダーツ投げのシンプルな修正と容易に任意の(arbitrary)次元で実行する方法を示す．
2. The Algorithm
Step 0.
- 点群データの格納，空間探索の高速化のためのn次元グリッドを初期化する．
- r/√nで囲まれるセルサイズを選択し，各グリッドセルが最大で一つのサンプルを含むようにすると，グリッドは単純なn次元int型配列として実装できる．
Step 1.
- 領域(domain)からランダムに一様に選択された，初期サンプルx0を選択する．
- 初期サンプルをグリッドに挿入し，このインデックス（0）でactive list（点群のインデックス配列）を初期化する．
Step 2.
- active listが空でない間，active listからランダムにインデックスを選択する（例えば，iとする）．
- x[i]の周りの半径rと半径2rの計数球内から一様に選択されたk点までを生成する．
- 各点について，既存のサンプルの半径r内の距離にあるかどうかを確認する．（グリッドを使用して，近傍点のみを参照する．）
- 注目点が既存のサンプル点から十分に遠い場合，注目点を次のサンプルとして排出し，active listに追加する．
- k回の試行後にそのような点がない場合，active listからiを削除する．
