The Mitchell’s best candidate algorithm is an algorithm with the following procedural:
- Start with N existing blue noise samples (N can be 0 initially)
- Generate M new candidate points using white noise (where M is scaled with N)
- Keep the candidate farthest away from any existing point
- Goto 1 and repeat until the desired number of samples is reached The algorithm works in any number of dimensions, including on a sphere.
Pseudo code below:
const SCALING_CONSTANT = 1;
var samples: Vec<Point> = [];
for i from 0 to sample_count {
// scale candidate count with the current sample count
let candidate_count = i * SCALING_CONSTANT + 1;
var best_distance_sq = -FLOAT_MAX;
var best_candidate = null;
for _ from 0 to candidate_count {
let candidate = random_point();
// Find minimum distance for this sample
var min_dist_sq = FLOAT_MAX;
for sample in samples {
let dist_sq = distance_square(sample, candidate);
if min_dist_sq > dist_sq { min_dist_sq = dist_sq; }
}
if min_dist_sq > best_distance {
best_distance_sq = min_dist_sq;
best_candidate = candidate;
}
}
samples.push_back(best_candidate);
}
Notice that we use square distance in the above code, as we only need to compare the distance so we can save a bit computation. Also note that scaling the number of candidate by existing sample point is important to guarantee samples of good quality. 1
This algorithm produces high-quality blue noise distributions, but its time complexity is O(n^2 * m)
, where n is the number of samples and m is the number of candidates per sample. For large sample counts or high dimensions, more efficient algorithms like fast poisson disk sampling might be preferred.