-
Notifications
You must be signed in to change notification settings - Fork 5
/
poisson-disc-sampler.js
90 lines (68 loc) · 2.08 KB
/
poisson-disc-sampler.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
'use strict';
module.exports = 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);
var grid = new Array(gridWidth * gridHeight);
var queue = [];
var queueSize = 0;
var sampleSize = 0;
function far(x, y) {
var i = x / cellSize | 0;
var j = y / cellSize | 0;
var i0 = Math.max(i - 2, 0);
var j0 = Math.max(j - 2, 0);
var i1 = Math.min(i + 3, gridWidth);
var j1 = Math.min(j + 3, gridHeight);
for (j = j0; j < j1; ++j) {
var o = j * gridWidth;
for (i = i0; i < i1; ++i) {
var s;
if ((s = grid[o + i])) {
var 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;
}
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;
var 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();
var r = Math.sqrt(Math.random() * R + radius2);
var x = s[0] + r * Math.cos(a);
var 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 (x >= 0 && x < width && y >= 0 && y < height && far(x, y)) {
return sample(x, y);
}
}
queue[i] = queue[--queueSize];
queue.length = queueSize;
}
};
};