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}}$ ...