Lessons Learned and Improvements when Building Screen-Space Samplers with Blue-Noise Error Distribution

Lessons Learned and Improvements
when Building Screen-Space Samplers
with Blue-Noise Error Distribution

Laurent Belcour

Eric Heitz

⚠️ What You See Is Maybe Not What You Should ⚠️

Two Years Ago ...

Blue-noise screen-space sampler

[Heitz et al. 2019]

LittlestTokyo - 4 spp

Random Scrambling

Heitz et al. [2019]

Random Scrambling

Heitz et al. [2019]

3D model by Glen Fox

Inset

Power Spectrum

Two Years Ago ...

Traditionnally, path tracers use sequences of (quasi)-random numbers per pixels for Monte-Carlo integration. To avoid aliasing, those sequences are uncorrelated to each other. Usualy using what we call random scrambling of a main sequence. *click*

As you can see on the right random scrambling produces an error that distributes like a white-noise in screen-space. The power spectrum contains energie in all frequencies. *click*

Inspired by Iliyan Georgiev and Marcos Fajardo's 2016 Siggraph talk, we introduced a sampler that correlates sequences of (quasi)-random number across pixels to distributes the error closer to a blue-noise. *click*

This sampler produces images that look more converged than random scrambling ones. Though in fact, the error with respect to the ground truth is the same. *click*

Two Years Ago ...

Blue-noise screen-space sampler
Please refer to our 2019 talk
- https://belcour.github.io/blog

Two Years Ago ...

Blue-noise screen-space sampler
Please refer to our 2019 talk
- https://belcour.github.io/blog
Many people seems to like it
- Already in Unity's HDRP and Lightmapper
- A lot of feedbacks and misunderstandings

Unity's Lightmapper

Viking - 32 spp

Heitz et al. [2019]

Ours

Heitz et al. [2019]

Ours

3D model by nigelgoh

Inset

Power Spectrum

First A Quick Recap

Scrambling mask

Sorting mask

Sobol samples

function screen_space_sampler(i, j, index, dimension)
{
// Fetch keys associated with pixel (i,j)
scramble = scrambling_keys(i,j)
sort = sorting_keys(i,j)

// XOR the index
index  = index ^ sort
sample = sobol_owen(index, dimension)

// XOR the sample
sample = sample ^ scramble

return sample
}

2 texture fetches + 2 XORs

QMC Integration

Optimized on test integrands

See [Heitz et al. 2019] for more details

To do so, I will need to give you a glance of our 2019 talk. *click*

This sampler use as input the sobol sequence ... *click*

and two textures that we call the scrambling and the sorting masks. *click*

Every pixel of the scrambling and sorting masks (in blue and red) scramble the sobol sequence. In practice, we XOR the Sobol sequence with the value in the scrambling mask and shuffle the indexing with the value in sorting mask. *click*

So, different pixels correspond to different sequences. *click*

*click*

When we use this sampler in a path tracer, we obtain renderings where the correlation of the pixels depends on the correlation between the sequences. *click*

This sampler is quite straighforward to include in a path tracer and the code is two texture fetches and two XORs. *click*

Now, the key point of improving the quality of rendering, is to optimize the masks. But to make them scene agnostic, we optimize them with respect to a database of test integrands. *click*

First A Quick Recap

Test integrand

First A Quick Recap

Test integrand

Scrambling mask

Sorting mask

Test 'rendering'

Misunderstanding #1

👨‍💻

I bet the blue-noise won't work on smooth integrands since it is optimized for discontinuities.

@pedanticMathematician - very late in the night.

Insight #1: Optimizing Vectors

Test 'rendering'

Insight #1: Optimizing Vectors

Test 'rendering'

$$\begin{bmatrix} \\ \vdots \\ \vdots \\ \\ \end{bmatrix}$$

Vector of realization

Insight #1: Optimizing Vectors

We are swapping 2¹⁶D vectors!
- Requires a specific loss
Equivalent to swapping PCA coordinates
Eigen-test integrands from PCA
- They are quite smooth!

$$\begin{bmatrix} \\ \vdots \\ \vdots \\ \\ \end{bmatrix} = R_\theta \begin{bmatrix} \\ \vdots \\ \vdots \\ \\ \end{bmatrix}$$

$$ f_3(x)$$

$$ f_{49}(x)$$

Sobol + XOR

$$ f_0 $$

$$ f_1 $$

$$ f_2 $$

$$ f_3 $$

$$ f_4 $$

The insight we got from this point of view is that *click*

the optimization process is simply swapping vectors of very large dimensions (in fact 2^16 D!!). Looking at this vector space, we can extract its principal directions using an eigen decomposition. *click*

When we optimize the masks, we equivalently optimize the spatial distribution of another set of vectors in the space of the PCA. And this space is given by a rotation matrix in this high dimensional space. *click*

So the optimizer is optimizing the realization of a different set of functions that are defined by the eigenvectors. We call them eigen-test-functions. Each eigen-test-function is the weighted sum of all the test functions weighted by the values in the eigenvector.

And because there is so many discontinuous function, we end up with eigen-test-functions that are pretty smooths. ! *click*

The Limits of Owen's Scrambled Sobol

But not that smooth ...

Sobol + XOR

$$ f_0 $$

$$ f_1 $$

$$ f_2 $$

$$ f_3 $$

$$ f_4 $$

independent

$$ f_0 $$

$$ f_1 $$

$$ f_2 $$

$$ f_3 $$

$$ f_4 $$

The Limits of Owen's Scrambled Sobol

But not that smooth ...
- Impacts the quality of the blue-noise

Sobol+XOR

Independent

The Limits of Owen's Scrambled Sobol

But not that smooth ...
- Impacts the quality of the blue-noise
Difference seems due to scrambling
- Sobol+XOR produces few variations
- Independent produces an infinite set sequences
Works with a different scrambling
- Wait! Cranley-Patterson Rotations???

Sobol+XOR

✔ convergence
✘ blue-noise

Independent

✘ convergence
✔ blue-noise

Sobol+CPR

✘ convergence
✔ blue-noise

Question #1

Can I use my own sequence?

@QMC_Master - mod(noon * k, 1).

Changing The Sequence

Rank-1 Lattices [Keller 2019]

Changing The Sequence

Rank-1 Lattices [Keller 2019]
- Wrapped 1D points
- Empirically do no alter convergence
But provides better results
- Large space of variations

Rendering of Teapot at 16 spp

Request #1

👩‍💻

Plz share the optimizer code!

@SpeedyCoder - 2s after publishing the talk.

Old Optimizer

A Genetic Algorithm
- Swap random scrambles according to loss
- Extremely slow to converge!

GPU-friendly Optimizer

Start with almost perfect mask
- Only one pixel to move
- We only need to randomly find it ...
Can we try all possible swap?
- We need a collisions-free scheme
- We need to preserve neighbourhoods

Dither tile

So we decided to build a parallel version of the optimizer. *click*

But this isn't so easy. Let say that what we have here is an almost converged dither mask. *click*

And let's assume that there is only one pixel to be swapped to reach the global optimum for the optimization. *click*

The iterative algorithm would randomly pick two pixels and test whether they need to be swapped. *click*

Since they should not, it will test another pair. *click*

And another pair until finaly it randomly select the one pixel to change. *click*

I hope you see with me that this scheme is unoptimal. In this his context, if we could test all possible combinaisons, we would find the last mutation needed and ends the algorithm.

But testing all possible mutations has two issues: first it creates data races. So we need to find a collision free swapping scheme. Second, we need to preserve neighbourhoods. If many close pixels are swapped at the same time they might not reduce the loss globally. *click*

Collision Free Scheme

Dither tile

scramble pairs

Linearized and permuted dither tile

{

Preserving Neighbourhoods

Still not optimal w.r.t the loss
- Permutation might break neighboors
Not a big deal
- Solution: only permute a half of the pairs
- We even got simulated annealing for free
Allows quick iteration
- ~9 times faster than our CPU-sequential version
Available for all!
- Check our projet webpage
- Implementation by Sylvain Durand

Dither tile

Question #F

👩‍🎨

How can I know if my tile is of good quality?

@QA - too often.

Quality Criterion

Assessing blue-noise quality is perceptual
- Depends on the medium (screen, printed paper, ...)
- Depends on the conditions (resolution, ...)
- We need a numerical criterion

Quality Criterion

Assessing blue-noise quality is perceptual
- Depends on the medium (screen, printed paper, ...)
- Depends on the conditions (resolution, ...)
- We need a numerical criterion
The idea is to look at denoising [Chizhov et al. 2020]
- Blue-noise improves L2 after denoising
- But how can we make it scene agnostic?

Blur Criterion on Test Integrands

integrated test function at 8 spp

error after blurring

Blur Criterion on Test Integrands

Is Stratification the Ultimate Goal?

Dyadicity is a hot topic
Its only about per pixel convergence
- Misses convergence after denoising
- Maybe not so important?

Request #2

🧑‍🎓

It tried it using BDPT, it doesn't work! Can you debug my code?

@GeekyStudent - 5min before sending his homework.

Use Your Sampler Wisely

BDPT: Dimensions must match
- Sub-paths must share random numbers
- Not vanilla!

The first point I would like to make here is that you should use a screen-space sampler wisely. There is no point in optimizing with such a care the arangement of sequences if in the end this correlation is wasted by how you use them. *click*

One example of such misuse is to use a screen-space sampler in a bidirectionnal path tracer. A fundemental concept that you must remember is that with a screen-space sampler, random values must be consumed at the same time and for the same dimensions across pixels. If we take the example of this eye and light paths. *click*

There is two ways to create length 5 paths. *click*

It means that we must ensure that both end point vertices share the same dimensions in our sampler. If not, we will mix together two dimensions that are spatially uncorrelated. And this will be detrimental to the blue-noise distribution.

More Please!

More dimensions
- Not best quality for direct illumination
- Takes time to optimize
We advise to pad dimensions
- We only optimize 2D tiles
- Pad with random tile shifts
More samples
- Tune your sampler to you SPPs!

People often requested to have blue-noise sampler with very high dimensions. *click*

For our 2019 sampler, we provided 8 dimensions in our sampler. But we did not directly optimize for 8D. This would reduce the quality we can achieve for low dimensions (for example direct illumination). And it would take ages to optimize. *click*

Instead of looking for more and more dimensions, we advise to padd 2D sequences with random offsets. This has the benefit of preserving a little more the correlation in higher dimension (if it is really needed). *click*

Another request was to get higher sample count sequences. If doing so, please remind that the best quality is obtained at the target sample count. Intermediate sample counts are only partially good thanks to the sorting.

Summary

We improved our 2019 screen-space sampler
- Better blue-noise of rendered frames
- Better quality after denoising
- Still efficient and compatible with real-time
Our contributions
- New insights on the optimization process
- Changed the sequence and scrambling
- Accelerated optimization using GPU
Thanks to you
- Interaction with a lot of interested folks

Project available at belcour.github.io/blog