Coding Example: Blue Noise Sampling using Bridson method

In this lesson, we will try to do the blue noise sampling using the Bridson method. First we will discuss the step-by-step approach and then implement it in code.

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 rn\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 ii). Generate up to k points chosen uniformly from the spherical annulus between radius rr and 2r2r around xix_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 kk attempts no such point is found, instead remove ii 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 kk parameter. Here’s the complete Bridson implementation:

Get hands-on with 1200+ tech skills courses.