Tom.notes();

Computer Scienceや読書のメモ

Fast Poisson Disk Sampling in Arbitrary Dimensions

Paper(700 words)

https://www.researchgate.net/publication/242093366_Fast_Poisson_disk_sampling_in_arbitrary_dimensions

 

 

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を削除する.