Skip to content

Instantly share code, notes, and snippets.

@enjalot
Last active April 26, 2016 16:12
Show Gist options
  • Save enjalot/83a916e9e9de4b9df54a09b30411ed01 to your computer and use it in GitHub Desktop.
Save enjalot/83a916e9e9de4b9df54a09b30411ed01 to your computer and use it in GitHub Desktop.
Poisson-Disc Voronoi
license: gpl-3.0
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body: {
position:fixed;
top:0; bottom: 0;
left: 0; right: 0;
}
canvas {
width: 100%;
height: 100%;
position:absolute;
top:0;
left: 0;
}
path {
fill: #fff;
stroke: #de4459;
}
path:nth-child(2n+1) {
fill: #de4459;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<canvas></canvas>
<script>
var bbox = d3.select("body").node().getBoundingClientRect();
var width = bbox.width,
height = bbox.height;
var r = 8;
var sample = poissonDiscSampler(width, height, r);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var grid;
var points = [[width/2, height/2]];
var voronoi = d3.geom.voronoi();
d3.timer(function(elapsed) {
var mod = -2
+ 100 * Math.sin(elapsed * Math.PI*2)
- 5 * Math.cos(elapsed * Math.PI)
;
for (var i = 0; i < 10; ++i) {
var s = sample(r + mod);
if (!s) {
renderVoronoi();
svg.selectAll("circle")
.remove()
return true;
}
svg.append("circle")
.attr("cx", s[0])
.attr("cy", s[1])
.attr("r", 0)
.transition()
.attr("r", 2);
}
//console.log(elapsed)
});
function renderVoronoi() {
var canvas = d3.select("canvas").node();
canvas.width = width;
canvas.height = height;
var context = canvas.getContext('2d');
var noids = voronoi(points);
/*
for (var i = 1, n = noids.length; i < n; ++i) {
draw(noids[i]);
context.stroke();
}
*/
console.log("noids",noids)
var cells = svg.selectAll("path.cell").data(noids)
cells.enter().append("path")
.attr("d", function(d) {
if(!d) return;
return "M" + d.join("L") + "Z";
})
function draw(cell) {
if (cell) {
context.beginPath();
context.moveTo(cell[0][0], cell[0][1]);
for (var j = 1, m = cell.length; j < m; ++j) {
context.lineTo(cell[j][0], cell[j][1]);
}
context.closePath();
return true;
}
}
}
// Based on https://www.jasondavies.com/poisson-disc/
function poissonDiscSampler(width, height, radius) {
var k = 30; // maximum number of samples before rejection
var radius2 = radius * radius;
var R = 3 * radius2
var cellSize = radius * Math.SQRT1_2
var gridWidth = Math.ceil(width / cellSize)
var gridHeight = Math.ceil(height / cellSize)
grid = new Array(gridWidth * gridHeight)
var queue = []
var queueSize = 0
var sampleSize = 0
return function(newRadius) {
radius2 = newRadius * newRadius;
R = 3 * radius2
cellSize = radius * Math.SQRT1_2;
if (!sampleSize) return sample(Math.random()*width,Math.random()*height);
// 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(),
rad = Math.sqrt(Math.random() * R + radius2),
x = s[0] + rad * Math.cos(a) * Math.random(),
y = s[1] + rad * Math.sin(a) * Math.random();
// 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)) {
points.push([x,y])
return sample(x, y);
}
}
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(x, y) {
var s = [x, y];
queue.push(s);
grid[gridWidth * (y / cellSize | 0) + (x / cellSize | 0)] = s;
++sampleSize;
++queueSize;
return s;
}
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment