<p>Another very simple, easy to implement, algorithm to generate a Poisson-disk/blue noise point distribution is the following one [ 1 ]: </p>

<ol>
<li>Decide a radius <strong><em>r</em></strong>, and therefore the expected number <em>N</em> of samples per area (use the formula for maximum packing density of <em>k</em> disks distributed on a toroidal domain see [ 2 ]) </li>
<li>Generate 10~20 x <em>N</em> samples in your area using a plain unbiased montecarlo sampling</li>
<li>Until all samples respect poisson disk condition:

<ul>
<li>randomly choose a sample <strong><em>p</em></strong> </li>
<li>remove all the samples at distance lower than <strong><em>r</em></strong> from <strong><em>p</em></strong></li>
</ul></li>
</ol>

<p>Eventually step 3 can be furtherly iterated a small number of times choosing the sample with minimal number of surviving samples within distance r.</p>

<p>You can find an implementation of this algorithm in MeshLab.</p>

<p><strong>References</strong></p>

<p>[ 1 ] <a href="http://vcg.isti.cnr.it/Publications/2012/CCS12/" rel="nofollow noreferrer"><strong>Efficient and Flexible Sampling with Blue Noise Properties of Triangular Meshes</strong><br>
<em>Massimiliano Corsini, Paolo Cignoni, Roberto Scopigno</em><br>
IEEE Transaction on Visualization and Computer Graphics, Volume 18, Number 6, page 914--924 - 2012</a></p>

<p>[ 2 ] <a href="https://lirias.kuleuven.be/handle/123456789/176251" rel="nofollow noreferrer"><strong>A comparison of methods for generating Poisson disk distributions</strong><br>
 <em>Ares Lagae, Philip Dutré,</em><br>
Computer Graphics Forum vol:27 issue:1 , 2008</a></p>

CC BY-SA 3.0
2017-10-05T07:19:55.487Z
2017-10-05T07:19:55.487Z
ALoopingIcon
<p>The problem turned out to be that you don't do the same number of candidates per point, but that if you have <span class="math-container">$n$</span> points already, you should generate <span class="math-container">$m*n$</span> candidates for the next point.</p>
<p><span class="math-container">$m$</span> is a tuneable parameter where in general higher values of <span class="math-container">$m$</span> will take longer to calculate, but will result in higher quality sampling.</p>
<p>The reason that the candidate count should scale with the existing sample count is that it keeps statistics about the points constant, so lets you reason about how higher sample counts will look / behave by looking at lower sample counts.</p>
<p>Values of <span class="math-container">$m$</span> that are too high will end up looking like the lower images of the question though, where the randomness is almost completely gone.</p>
<p>The problem with the high sample counts is that they more fully cover all possible pixel locations, and since the best candidate is chosen, much randomness will go away leaving you with something a lot more deterministic.</p>
<p>I personally choose to do <span class="math-container">$m*n+1$</span> samples to slightly simplify the logic and let it handle the first sample when <span class="math-container">$n=0$</span>.</p>
<p>This technique was described in this paper:</p>
<p>&quot;Spectrally optimal sampling for distribution ray tracing&quot; Mitchell 1991.
<a href="https://dl.acm.org/citation.cfm?id=122718.122736" rel="nofollow noreferrer">https://dl.acm.org/citation.cfm?id=122718.122736</a></p>
<p>Below is the same setup as in the question where 455 black pixels are placed in a 64x64 image, showing the result for some values of <span class="math-container">$m$</span>.  The quality is surprisingly good even for low values of <span class="math-container">$m$</span> and the execution time is much, much lower than the process described in the question.  I'm also limiting the candidate count to be at maximum 1/2 the number of pixels (an arbitrary limit I came up with) in the image to keep the candidate count from going too high for denser samplings in an effort to keep the quality and computation time decent.</p>
<p>I've heard that storing points in grids can help in accelerating the calculation time of &quot;how far is this candidate from the closest point&quot; and I believe it should, but I haven't tried it yet.</p>
<p>When <span class="math-container">$m=0$</span>, it's equivelant to white noise and just randomly placing the dots.</p>
<p>Note that when calculating the distance between two points I am treating the image as if it wraps around, so that dots on opposite edges are treated close  together.  If interested in details of how to calculate distance in wrap around (toroidal) space, check out this blog post:
<a href="https://blog.demofox.org/2017/10/01/calculating-the-distance-between-points-in-wrap-around-toroidal-space/" rel="nofollow noreferrer">https://blog.demofox.org/2017/10/01/calculating-the-distance-between-points-in-wrap-around-toroidal-space/</a></p>
<p>Here is a blog post on Mitchell's best candidate algorithm too I wrote up:
<a href="https://blog.demofox.org/2017/10/20/generating-blue-noise-sample-points-with-mitchells-best-candidate-algorithm/" rel="nofollow noreferrer">https://blog.demofox.org/2017/10/20/generating-blue-noise-sample-points-with-mitchells-best-candidate-algorithm/</a></p>
<p><a href="https://i.sstatic.net/blUaK.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/blUaK.png" alt="enter image description here" /></a></p>

CC BY-SA 3.0
2017-10-05T22:05:30.717Z
How does this technique compare to the very easy to generate [Halton sequence](https://en.wikipedia.org/wiki/Halton_sequence)?
Quinchilion
CC BY-SA 3.0
2017-10-05T22:52:08.610Z
It's a lot closer to ideal blue noise. Worth another question probably!
Alan Wolfe
CC BY-SA 4.0
2020-07-29T17:29:40.177Z
A better answer 3 years later... halton sequence is a low discrepancy sequence. It converges faster than white noise but can have aliasing problems before it converges.  Blue noise converges at the same speed as white noise but has lower starting error. The error it leaves behind is better perceptually than white noise or LDS. Blue noise is for low sample counts basically.
Alan Wolfe
CC BY-SA 4.0
2017-10-05T19:28:30.110Z
2020-07-29T17:30:36.030Z
2020-07-29T17:30:36.030Z
Alan Wolfe
<p>I'm trying to generate an image where black dots are arranged in a blue noise distribution on a white background.</p>

<p>I know that there are other ways to do this, one of the best being "Fast Capacity Constrained Voronoi Tessellation." [<a href="https://www.microsoft.com/en-us/research/publication/fast-capacity-constrained-voronoi-tessellation/" rel="noreferrer">Hongwei 09</a>], but I'm using Mitchell's best candidate algorithm.</p>

<p>This algorithm works by generating $N$ random pixel locations as candidates for where the next black pixel should go and chooses the candidate which has the farthest distance to the nearest black pixel.</p>

<p>I've implemented this and have used it to put 455 black pixels on a 64x64 image, using various candidate counts.  Looking at the DFT (frequency magnitude, not phase) of the results, I'm seeing some unexpected frequency data.</p>

<p><a href="https://i.sstatic.net/zCTZO.png" rel="noreferrer"><img src="https://i.sstatic.net/zCTZO.png" alt="enter image description here"></a></p>

<p>Strangely, I never get that "nice concentric rings" DFT frequency amplitude that i'd expect and see in papers regarding blue noise sample patterns.</p>

<p>Are these results expected?</p>

<p>Manually hunting between 100 and 1000 samples, it seems like 400 is pretty near optimal.</p>

<p><a href="https://i.sstatic.net/NytDe.png" rel="noreferrer"><img src="https://i.sstatic.net/NytDe.png" alt="enter image description here"></a> <a href="https://i.sstatic.net/mtrOr.png" rel="noreferrer"><img src="https://i.sstatic.net/mtrOr.png" alt="enter image description here"></a></p>

<p>Is there some "sweet spot" for the number of candidates to use based on image size and desired sample (black pixel) count to get the best result?</p>

<sampling>
Mitchell's Best Candidate Algorithm
Alan Wolfe
# Mitchell's Best Candidate Algorithm

(Asked by: username_0 on 2017-10-05)

I'm trying to generate an image where black dots are arranged in a blue noise distribution on a white background.

I know that there are other ways to do this, one of the best being "Fast Capacity Constrained Voronoi Tessellation." [[Hongwei 09](https://www.microsoft.com/en-us/research/publication/fast-capacity-constrained-voronoi-tessellation/)], but I'm using Mitchell's best candidate algorithm.

This algorithm works by generating $N$ random pixel locations as candidates for where the next black pixel should go and chooses the candidate which has the farthest distance to the nearest black pixel.

I've implemented this and have used it to put 455 black pixels on a 64x64 image, using various candidate counts. Looking at the DFT (frequency magnitude, not phase) of the results, I'm seeing some unexpected frequency data.

[![enter image description here](https://i.sstatic.net/zCTZO.png)](https://i.sstatic.net/zCTZO.png)

Strangely, I never get that "nice concentric rings" DFT frequency amplitude that i'd expect and see in papers regarding blue noise sample patterns.

Are these results expected?

Manually hunting between 100 and 1000 samples, it seems like 400 is pretty near optimal.

[![enter image description here](https://i.sstatic.net/NytDe.png)](https://i.sstatic.net/NytDe.png) [![enter image description here](https://i.sstatic.net/mtrOr.png)](https://i.sstatic.net/mtrOr.png)

Is there some "sweet spot" for the number of candidates to use based on image size and desired sample (black pixel) count to get the best result?

**Tags:** sampling


---

## 2 answers

### Answer by username_0 on 2017-10-05. Score: 6 | Accepted answer

The problem turned out to be that you don't do the same number of candidates per point, but that if you have $n$ points already, you should generate $m\*n$ candidates for the next point.

$m$ is a tuneable parameter where in general higher values of $m$ will take longer to calculate, but will result in higher quality sampling.

The reason that the candidate count should scale with the existing sample count is that it keeps statistics about the points constant, so lets you reason about how higher sample counts will look / behave by looking at lower sample counts.

Values of $m$ that are too high will end up looking like the lower images of the question though, where the randomness is almost completely gone.

The problem with the high sample counts is that they more fully cover all possible pixel locations, and since the best candidate is chosen, much randomness will go away leaving you with something a lot more deterministic.

I personally choose to do $m\*n+1$ samples to slightly simplify the logic and let it handle the first sample when $n=0$.

This technique was described in this paper:

"Spectrally optimal sampling for distribution ray tracing" Mitchell 1991.
<https://dl.acm.org/citation.cfm?id=122718.122736>

Below is the same setup as in the question where 455 black pixels are placed in a 64x64 image, showing the result for some values of $m$. The quality is surprisingly good even for low values of $m$ and the execution time is much, much lower than the process described in the question. I'm also limiting the candidate count to be at maximum 1/2 the number of pixels (an arbitrary limit I came up with) in the image to keep the candidate count from going too high for denser samplings in an effort to keep the quality and computation time decent.

I've heard that storing points in grids can help in accelerating the calculation time of "how far is this candidate from the closest point" and I believe it should, but I haven't tried it yet.

When $m=0$, it's equivelant to white noise and just randomly placing the dots.

Note that when calculating the distance between two points I am treating the image as if it wraps around, so that dots on opposite edges are treated close together. If interested in details of how to calculate distance in wrap around (toroidal) space, check out this blog post:
<https://blog.demofox.org/2017/10/01/calculating-the-distance-between-points-in-wrap-around-toroidal-space/>

Here is a blog post on Mitchell's best candidate algorithm too I wrote up:
<https://blog.demofox.org/2017/10/20/generating-blue-noise-sample-points-with-mitchells-best-candidate-algorithm/>

[![enter image description here](https://i.sstatic.net/blUaK.png)](https://i.sstatic.net/blUaK.png)

> **Comments:**
> **username_2**: How does this technique compare to the very easy to generate [Halton sequence](https://en.wikipedia.org/wiki/Halton_sequence)?  
> **username_0**: It's a lot closer to ideal blue noise. Worth another question probably!  
> **username_0**: A better answer 3 years later... halton sequence is a low discrepancy sequence. It converges faster than white noise but can have aliasing problems before it converges.  Blue noise converges at the same speed as white noise but has lower starting error. The error it leaves behind is better perceptually than white noise or LDS. Blue noise is for low sample counts basically.  

---

### Answer by username_1 on 2017-10-05. Score: 3

Another very simple, easy to implement, algorithm to generate a Poisson-disk/blue noise point distribution is the following one [ 1 ]:

1. Decide a radius ***r***, and therefore the expected number *N* of samples per area (use the formula for maximum packing density of *k* disks distributed on a toroidal domain see [ 2 ])
2. Generate 10~20 x *N* samples in your area using a plain unbiased montecarlo sampling
3. Until all samples respect poisson disk condition:
   * randomly choose a sample ***p***
   * remove all the samples at distance lower than ***r*** from ***p***

Eventually step 3 can be furtherly iterated a small number of times choosing the sample with minimal number of surviving samples within distance r.

You can find an implementation of this algorithm in MeshLab.

**References**

[ 1 ] [**Efficient and Flexible Sampling with Blue Noise Properties of Triangular Meshes**  
*Massimiliano Corsini, Paolo Cignoni, Roberto Scopigno*  
IEEE Transaction on Visualization and Computer Graphics, Volume 18, Number 6, page 914--924 - 2012](http://vcg.isti.cnr.it/Publications/2012/CCS12/)

[ 2 ] [**A comparison of methods for generating Poisson disk distributions**  
*Ares Lagae, Philip Dutré,*  
Computer Graphics Forum vol:27 issue:1 , 2008](https://lirias.kuleuven.be/handle/123456789/176251)


---

