Coding Example: Blue Noise Sampling using Bridson method

Bridson method

If the vectorization of the previous method poses no real difficulty, the speed improvement is not so good and the quality remains low and dependent on the k parameter. The higher, the better since it basically governs how hard to try to insert a new sample. But, when there is already a large number of accepted samples, only chance allows us to find a position to insert a new sample. We could increase the k value but this would make the method even slower without any guarantee in quality. It’s time to think out-of-the-box and luckily enough, Robert Bridson did that for us and proposed a simple yet efficient method:

Step 0:

Initialize an n-dimensional background grid for storing samples and accelerating spatial searches. We pick the cell size to be bounded by $\frac{r}{\sqrt{n}}$, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple n-dimensional array of integers: the default −1 indicates no sample, a non-negative integer gives the index of the sample located in a cell.

Step 1:

Select the initial sample, x_0, randomly chosen uniformly from the domain. Insert it into the background grid, and initialize the “active list” (an array of sample indices) with this index (zero).

Step 2:

While the active list is not empty, choose a random index from it (say $i$). Generate up to k points chosen uniformly from the spherical annulus between radius $r$ and $2r$ around $x_i$. For each point in turn, check if it is within distance r of existing samples (using the background grid to only test nearby samples). If a point is adequately far from existing samples, emit it as the next sample and add it to the active list. If after $k$ attempts no such point is found, instead remove $i$ from the active list.

$$$$

Implementation

The implementation poses no real problem. Note that not only is this method fast, but it also offers a better quality (more samples) than the DART method even with a high $k$ parameter. Here’s the complete Bridson implementation: