Mod:Coding Challenge #33: Poisson-disc Sampling

Poisson-disk Samplingは，ランダムに分布する点の集合をサンプルする方法．普通にランダムを使うと，偏りが生まれる．それに対してPoisson-disk Samplingは，ルールとして一定間隔に分布するように距離を測って置いていく．そのアルゴリズムが幾つかあるようだ．

アクティブな点を用意してその点を移動させながらその近くにランダムな点を生成し，その上下左右の位置にある点との距離を確認して，グリッド内の領域から溢れていない場合に点としてプロットしてる．口で説明するよりコードを読むほうが早いかもしれない．

以下のページを参照しながら，p5.jsからProcessingに移植した．JavaScriptの配列をJavaのArrayListに読み替えたり，undefinedの挙動と揃えるような処理の書き方で少し躓いた．null使って処理した．

Poisson-Disc Sampling

daiki-yamanaka.hatenablog.com

qiita.com

こういうアルゴリズムで動くプログラム，書き溜めておくと何かあったときにすぐ使えて便利だなと最近思う．

コード

float r = 8;
float k = 30;
float w = r / sqrt(2);
int cols, rows;
ArrayList<PVector> grid;
ArrayList<PVector> active;
ArrayList<PVector> ordered;

void setup() {
  fullScreen();
  colorMode(HSB, 360, 100, 100, 100);
  strokeWeight(r);

  init();
}

void init() {
  grid = new ArrayList<PVector>();
  active = new ArrayList<PVector>();
  ordered = new ArrayList<PVector>();

  // step 0
  cols = floor(width / w);
  rows = floor(height / w);
  for (int i = 0; i < cols * rows; i++) {
    PVector p = null;
    grid.add(i, p);
  }

  // step 1
  float x = width / 2;
  float y = height / 2;
  int i = floor(x / w);
  int j = floor(y / w);
  PVector pos = new PVector(x, y);
  grid.set(i + j * cols, pos);
  active.add(pos);
}

void draw() {
  background(0, 0, 0);
  for (int total = 0; total < 25; total++) {
    if (active.size() > 0) {
      int randIndex = floor(random(active.size()));
      PVector pos = active.get(randIndex);
      boolean found = false;
      for (int n = 0; n < k; n++) {
        PVector sample = PVector.random2D();
        float m = random(r, 2 * r);
        sample.setMag(m);
        sample.add(pos);

        int col = floor(sample.x / w);
        int row = floor(sample.y / w);

        if (col > -1 && row > -1 && col < cols && row < rows) {
          boolean ok = true;
          for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
              int index = (col + i) + (row + j) * cols;
              if (index > 0 && index < grid.size()) {
                PVector neighbor = grid.get(index);
                if (neighbor != null) {
                  float dist = PVector.dist(sample, neighbor);
                  if (dist < r) {
                    ok = false;
                  }
                }
              }
            }
          }
          if (ok) {
            found = true;
            grid.set(col + row * cols, sample);
            active.add(sample);
            ordered.add(sample);
            break;
          }
        }
      }

      if (!found) {
        active.remove(randIndex);
      }
    }
  }
  for (int i = 0; i < ordered.size(); i++) {
    PVector order = ordered.get(i);
    if (order != null) {
      stroke(i%360, 80, 100);
      strokeWeight(r / 2);
      point(order.x, order.y);
    }
  }
}

void mousePressed() {
  init();
}

リファレンス