10,000 poisson-disc samples of Van Gogh’s The Starry Night. Compare to uniform random samples.
Forked from Poisson-Disc III
10,000 poisson-disc samples of Van Gogh’s The Starry Night. Compare to uniform random samples.
Forked from Poisson-Disc III
<!DOCTYPE html> | |
<meta charset="utf-8"> | |
<body> | |
<script src="http://d3js.org/d3.v3.min.js"></script> | |
<script> | |
var width = 960, | |
height = 500; | |
var sample = poissonDiscSampler(width, height, 5.45), | |
samples = [], | |
s; | |
while (s = sample()) samples.push(s); | |
var voronoi = d3.geom.voronoi() | |
.clipExtent([[0, 0], [width, height]]); | |
var canvas = d3.select("body").append("canvas") | |
.attr("width", width) | |
.attr("height", height); | |
var context = canvas.node().getContext("2d"); | |
var image = new Image; | |
image.src = "starry-night.jpg"; | |
image.onload = start; | |
function pointSampleImage(image, x, y) { | |
var i = (y * width + x) << 2; | |
return d3.rgb(image.data[i + 0], image.data[i + 1], image.data[i + 2]); | |
} | |
function squareSampleImage(image, x, y, r) { | |
var samples = []; | |
for (var col = x - r; col < x + r + 1; col++) { | |
for (var row = y - r; row < y + r + 1; row++) { | |
var i = (row * width + col) << 2; | |
samples.push([image.data[i], image.data[i+1], image.data[i+2]]); | |
} | |
} | |
return d3.rgb( | |
d3.mean(samples, function (sample) { | |
return sample[0]; | |
}), | |
d3.mean(samples, function (sample) { | |
return sample[1]; | |
}), | |
d3.mean(samples, function (sample) { | |
return sample[2]; | |
}) | |
); | |
} | |
function start() { | |
context.drawImage(image, 0, 0); | |
image = context.getImageData(0, 0, width, height); | |
voronoi(samples).forEach(function(cell) { | |
var x = Math.floor(cell.point[0]), | |
y = Math.floor(cell.point[1]); | |
// context.fillStyle = pointSampleImage(image, x, y) + ""; | |
context.fillStyle = squareSampleImage(image, x, y, 3) + ""; | |
context.beginPath(); | |
context.moveTo(cell[0][0], cell[0][1]); | |
for (var i = 1, n = cell.length; i < n; ++i) context.lineTo(cell[i][0], cell[i][1]); | |
context.closePath(); | |
context.fill(); | |
}); | |
} | |
// 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) 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(), | |
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); | |
} | |
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> |