Poisson-Disc V

This animation shows the branching process of Bridson’s Poisson-disc sampling algorithm. Each time a new sample is added, a line is drawn between the new sample and the neighboring sample that spawned it.

forked from mbostock's block: Poisson-Disc V

forked from enoex's block: Poisson-Disc V

<!DOCTYPE html>
<meta charset="utf-8">
<style>

line {
  stroke: #000;
  stroke-width: 1.5px;
  stroke-linecap: round;
}

</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>

var width = 960,
    height = 780,
    delay = 1000,
    duration = 150;

var sample = poissonDiscSampler(width, height, 10);

var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);

var s;

while (s = sample()) {
  if (!s[1]) continue;
  svg.append("line")
      .attr("x1", s[1][0])
      .attr("y1", s[1][1])
      .attr("x2", s[1][0])
      .attr("y2", s[1][1])
      .style("stroke-opacity", 0)
    .transition()
      .delay(s[0].depth * duration + delay)
      .duration(duration)
      .ease("linear")
      .style("stroke-opacity", 1)
      .attr("x2", s[0][0])
      .attr("y2", s[0][1]);
}

// Based on https://www.jasondavies.com/poisson-disc/
function poissonDiscSampler(width, height, radius) {
  var k = 30, // maximum number of samples before rejection
      radius2 = radius * radius,
      R = 3 * radius2,
      cellSize = radius * Math.SQRT1_2,
      gridWidth = Math.ceil(width / cellSize),
      gridHeight = Math.ceil(height / cellSize),
      grid = new Array(gridWidth * gridHeight),
      queue = [],
      queueSize = 0,
      sampleSize = 0;

return function() {
    if (!sampleSize) {
      var s1 = [Math.random() * width, Math.random() * height];
      s1.depth = 0;
      return sample(s1, null);
    }

// Pick a random existing sample and remove it from the queue.
    while (queueSize) {
      var i = Math.random() * queueSize | 0,
          s = queue[i];

// Make a new candidate between [radius, 2 * radius] from the existing sample.
      for (var j = 0; j < k; ++j) {
        var a = 2 * Math.PI * Math.random(),
            r = Math.sqrt(Math.random() * R + radius2),
            x = s[0] + r * Math.cos(a),
            y = s[1] + r * Math.sin(a);

// Reject candidates that are outside the allowed extent,
        // or closer than 2 * radius to any existing sample.
        if (0 <= x && x < width && 0 <= y && y < height && far(x, y)) return sample([x, y], s);
      }

queue[i] = queue[--queueSize];
      queue.length = queueSize;
    }
  };

function far(x, y) {
    var i = x / cellSize | 0,
        j = y / cellSize | 0,
        i0 = Math.max(i - 2, 0),
        j0 = Math.max(j - 2, 0),
        i1 = Math.min(i + 3, gridWidth),
        j1 = Math.min(j + 3, gridHeight);

for (j = j0; j < j1; ++j) {
      var o = j * gridWidth;
      for (i = i0; i < i1; ++i) {
        if (s = grid[o + i]) {
          var s,
              dx = s[0] - x,
              dy = s[1] - y;
          if (dx * dx + dy * dy < radius2) return false;
        }
      }
    }

return true;
  }

function sample(s1, s0) {
    if (s0) s1.depth = s0.depth + 1;
    queue.push(s1);
    grid[gridWidth * (s1[1] / cellSize | 0) + (s1[0] / cellSize | 0)] = s1;
    ++sampleSize;
    ++queueSize;
    return [s1, s0];
  }
}

</script>

https://d3js.org/d3.v3.min.js