该动画演示了Bridson的Poisson-disc采样算法的工作原理。
红点表示“活动”样本。在每次迭代中，从所有活动样本的集合中随机选择一个。然后，在所选样本周围的环形区域内随机生成多达k个候选样本（显示为空心黑点）。
环面从半径r延伸到2r，其中r是任意两个样本之间的最小允许距离。半径r范围内的现有样本的候选样本将被拒绝；该“排除区”显示为灰色，并用黑线将被拒绝的候选对象与太接近的现有样本连接起来。如果可以接受，则将其添加为新的有效样本。
大小为r /√2的背景网格用于加速每个候选者的距离检查。由于每个单元最多只能包含一个样本，因此仅需要检查固定数量的相邻单元。
如果k个候选者都不可接受，则所选的活动样本将标记为非活动，并且将不再用于生成候选者。不活动的样品以黑色显示。
当没有样本保持活动状态时，算法结束。
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.grid {
stroke: #000;
stroke-opacity: .15;
shape-rendering: crispEdges;
}
.exclusion {
fill: #ccc;
}
.candidate-connection,
.candidate {
fill: #fff;
stroke: #000;
stroke-width: 1.5px;
}
.candidate-annulus {
fill: #000;
fill-opacity: .25;
stroke: #000;
stroke-width: 1.5px;
}
.sample--active {
fill: #f00;
stroke: #f00;
stroke-width: 2px;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script>
var width = 960,
height = 500;
var k = 30, // maximum number of samples before rejection
radius = 50,
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;
var arcEmptyAnnulus = d3.svg.arc()
.innerRadius(radius)
.outerRadius(radius)
.startAngle(0)
.endAngle(2 * Math.PI)();
var arcAnnulus = d3.svg.arc()
.innerRadius(radius)
.outerRadius(radius * 2)
.startAngle(0)
.endAngle(2 * Math.PI)();
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var gExclusion = svg.append("g")
.attr("class", "exclusion");
svg.append("path")
.attr("class", "grid")
.attr("d", d3.range(cellSize, width, cellSize)
.map(function(x) { return "M" + Math.round(x) + ",0V" + height; })
.join("")
+ d3.range(cellSize, height, cellSize)
.map(function(y) { return "M0," + Math.round(y) + "H" + width; })
.join(""));
var searchAnnulus = svg.append("path")
.attr("class", "candidate-annulus");
var gConnection = svg.append("g")
.attr("class", "candidate-connection");
var gSample = svg.append("g")
.attr("class", "sample");
var gCandidate = svg.append("g")
.attr("class", "candidate");
sample(Math.random() * width, Math.random() * height);
setTimeout(function selectActive() {
var i = Math.random() * queueSize | 0,
s = queue[i],
j = 0;
gCandidate
.style("opacity", null);
gConnection
.style("opacity", null);
searchAnnulus
.style("opacity", null)
.style("stroke-opacity", 0)
.attr("transform", "translate(" + s + ")")
.attr("d", arcEmptyAnnulus)
.transition()
.attr("d", arcAnnulus)
.style("stroke-opacity", 1)
.each("end", generateCandidate);
var sampleActive = gSample.selectAll("circle")
.filter(function(d) { return d === s; });
function generateCandidate() {
if (++j > k) return rejectActive();
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.
if (0 > x || x >= width || 0 > y || y >= height) return generateCandidate();
// If this is an acceptable candidate, create a new sample;
// otherwise, generate a new candidate.
gCandidate.append("circle")
.attr("r", 1e-6)
.attr("cx", x)
.attr("cy", y)
.transition()
.attr("r", 3.75)
.each("end", far(x, y) ? acceptCandidate : generateCandidate);
function acceptCandidate() {
removeCandidates()
.each("end", queueSize ? selectActive : null);
sample(x, y);
}
}
function rejectActive() {
queue[i] = queue[--queueSize];
queue.length = queueSize;
removeCandidates()
.each("end", queueSize ? selectActive : null);
sampleActive
.classed("sample--active", false);
}
function removeCandidates() {
gCandidate.transition()
.style("opacity", 0)
.selectAll("circle")
.remove();
gConnection.transition()
.style("opacity", 0)
.selectAll("line")
.remove();
return searchAnnulus.transition()
.style("opacity", 0);
}
}, 250);
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) {
gConnection.append("line")
.attr("x1", x)
.attr("y1", y)
.attr("x2", x)
.attr("y2", y)
.transition()
.attr("x2", s[0])
.attr("y2", s[1]);
return false;
}
}
}
}
return true;
}
function sample(x, y) {
var s = [x, y];
gExclusion.append("circle")
.attr("r", 1e-6)
.attr("cx", x)
.attr("cy", y)
.transition()
.attr("r", radius);
gSample.append("circle")
.datum(s)
.attr("class", "sample--active")
.attr("r", 1e-6)
.attr("cx", x)
.attr("cy", y)
.transition()
.attr("r", 3);
queue.push(s);
grid[gridWidth * (y / cellSize | 0) + (x / cellSize | 0)] = s;
++queueSize;
return s;
}
</script>
public class PoissonDiscSampler {
private Point[][] mPoints;
private int mWidth;
private int mHeight;
private int mNumCandidates = 10;
private QuadTree mQuadTree;
public PoissonDiscSampler(QuadTree quadTree) {
mPoints = new Point[mWidth][mHeight];
mQuadTree = quadTree;
mWidth = mQuadTree.getWidth();
mHeight = mQuadTree.getHeight();
}
public void setNumCandidates(int numCandidates) {
mNumCandidates = numCandidates;
}
public void addNumPoints(int numPointsToAdd) {
// add a point to the quadtree if it's empty
if (mQuadTree.getCount() == 0) {
mQuadTree.set(generateRandomPoint());
numPointsToAdd--;
}
Point candidatePoints[] = new Point[mNumCandidates];
double furthestDistance;
double distance;
int furthestDistanceIndex;
// this loop iterates once for each point to be added to the quadtree
for (; numPointsToAdd > 0; numPointsToAdd--) {
// generate random candidate points that aren't already in the quadtree
for (int i = 0; i < mNumCandidates; i++) {
candidatePoints[i] = generateRandomPoint();
while (mQuadTree.find(candidatePoints[i]) != null) { // while point already exists in quadtree
candidatePoints[i] = generateRandomPoint(); // generate a new point to replace it
}
}
// if any of the candidate points we've created share
// the same coordinates of another candidate point,
// overwrite one of the duplicate points until all
// candidate points are unique. -- TODO: TOO SLOW? FIX...?
for (int j = 0; j < mNumCandidates; j++) {
for (int k = 0; k < mNumCandidates; k++) {
if (j != k) {
while (candidatePoints[j].hasCoordinatesOf(candidatePoints[k])) {
candidatePoints[j] = generateRandomPoint();
}
}
}
}
furthestDistance = 0;
furthestDistanceIndex = 0;
// for each candidate point:
// 1. find distance between candidate point and
// nearest point in the quadtree
// 2. if the distance is larger than the distances
// for the previous points, save the index of
// the candidate point to furthestDistanceIndex
for (int i = 0; i < mNumCandidates; i++) {
distance = findDistance(findNearestPointInQuadTree(candidatePoints[i]),
candidatePoints[i]);
if (distance > furthestDistance) {
furthestDistance = distance;
furthestDistanceIndex = i;
}
}
// add the candidate point that is furthest from the
// other points in the quadtree to the quadtree
mQuadTree.set(candidatePoints[furthestDistanceIndex]);
}
}
public QuadTree getQuadTree() {
return mQuadTree;
}
// This grabs one or more points that are near
// referencePoint in the quadtree.
// There is no guarantee that the point(s)
// will be the closest point(s) to referencePoint,
// but they/it will tend to be in the vicinity.
public Point[] findPointsUnderParentNodeOf(Point referencePoint) {
boolean refPointAlreadyInQuadTree = false;
// if reference point is already in the quadtree,
// adding it to the quadtree in order to facilitate our search would be redundant.
// instead, we'll just use the already existing point.
if (mQuadTree.find(referencePoint) != null)
refPointAlreadyInQuadTree = true;
else
mQuadTree.set(referencePoint);
Node node = mQuadTree.find(referencePoint); // find the node containing our reference point.
// go up a node in the tree until the current
// node has 2+ points beneath it.
while (mQuadTree.searchWithin(node).length < 2) {
node = node.getParent();
}
// remove the reference point from quadtree
// if it wasn't part of the quadtree
// before this search.
if (!refPointAlreadyInQuadTree) {
mQuadTree.remove(referencePoint);
}
return mQuadTree.searchWithin(node); // find all points within the node (and its children) and return them
}
public Point findNearestPoint(Point referencePoint, Point[] candidatePoints) {
// set var with a large enough value that any valid
// distance we calculate is guaranteed to be smaller
double nearestCandidateDistance = mWidth * mHeight;
Point nearestCandidatePoint = null;
for (Point curPoint : candidatePoints) {
double curCandidateDistance = findDistance(referencePoint, curPoint);
if (curCandidateDistance < nearestCandidateDistance
&& !(curPoint.hasCoordinatesOf(referencePoint))) {
nearestCandidateDistance = curCandidateDistance;
nearestCandidatePoint = curPoint;
}
}
// in the unlikely event that all of the randomly
// generated candidate points share the same x,y coords
// with referencePoint, generate random points until
// we find one that doesn't.
if (nearestCandidatePoint == null) {
nearestCandidatePoint = generateRandomPoint();
while (nearestCandidatePoint.hasCoordinatesOf(referencePoint)) {
nearestCandidatePoint = generateRandomPoint();
}
}
return nearestCandidatePoint;
}
public Point findNearestPointInQuadTree(Point referencePoint) {
// grab some points in the vicinity of referencePoint
Point points[] = findPointsUnderParentNodeOf(referencePoint);
// pick the one that is closest to referencePoint and find distance
// between this point and reference point (and multiply distance by 2)
Point closePoint = findNearestPoint(referencePoint, points);
double dist = (findDistance(referencePoint, closePoint)) * 2;
// create a search area around referencePoint using above calculated distance
double minX = referencePoint.getX() - dist;
double minY = referencePoint.getY() - dist;
double maxX = referencePoint.getX() + dist;
double maxY = referencePoint.getY() + dist;
// find the nearest points to referencePoint using the above search area
Point nearestPoints[] = mQuadTree.searchWithin(minX, minY, maxX, maxY);
return findNearestPoint(referencePoint, nearestPoints);
}
// use pythagorean theorum to find the distance between two points
public double findDistance(Point point1, Point point2) {
double xDiff = point1.getX() - point2.getX();
double yDiff = point1.getY() - point2.getY();
return Math.sqrt((xDiff * xDiff) + (yDiff * yDiff));
}
public Point generateRandomPoint() {
int randX = (int) (Math.random() * mWidth);
int randY = (int) (Math.random() * mHeight);
while (randX > mWidth) {
randX--;
}
while (randY > mHeight) {
randY--;
}
Point point = new Point(randX, randY, null);
return point;
}
public Point[] toArray() {
return mQuadTree.searchWithin(-1, -1, mWidth, mHeight);
}
}
