Thread by @nbonneel

Super happy to share our @siggraph paper with @nvidia "MatBuilder: Mastering Sampling Uniformity Over Projections" (@LoisResearch, @nbonneel, @dcoeurjo, JC.Iehl, A.Keller, V.Ostromoukhov) projet.liris.cnrs.fr/matbuilder/. The motivation is that to estimate the value of an integral [1/16]

we can randomly sample the integrand and sum values -- this is Monte Carlo integration. With "well spread" samples instead of naive random values, we can improve the accuracy of the integral estimate a lot -- this is the quasi-Monte Carlo method. [2/16]

For instance, we can use stratified samples: for example, if we want 16 samples to estimates a 2-d integral defined in the domain [0,1]x[0,1], we decompose the domain into 4x4 square cells, and we put one sample in each cell. [3/16]

We can also use a (0, m, 2) net: it's like stratification, but we ensure there is one sample within non-necessarily square cells (e.g., with 16 2-d samples, each rectangle of size 1/16 x 1 will contain one point ; same thing for rectangles of size 1/8 x 1/2 etc.). [4/16]

It's much more difficult to build such point sets, but it has the advantage of guaranteeing a good quasi-Monte Carlo convergence rate. An even harder problem is to find *sequences* of samples intead of *sets* of samples: if we already have 16 samples and we want a 17th one,[5/16]

we want to keep the first 16 samples and add just one (not throwing away everything and finding an entirely new point set of 17 samples). There are methods based on primitive polynomials in Galois fields to build such sequences. [6/16]

Our method is conceptually much simpler, works better, and allows to satisfy arbitrary constraints on these sequences. E.g., we can ask for a sequence of samples in 5 dimensions, such that the first 3 represent a (0, 3)-sequence [7/16]

(i.e., like a (0, m, 2)-net but in 3-d and for sequences instead of sets), that the next 2 dimensions are stratified, and the full 5-d sequence is a (0, 5)-sequence. In short, guaranteeing that points are very well uniformly spread in n-dimensions and in given projections. [8/16]

Why? Because when we render 3d scenes, we integrate fonctions by propagating light paths within the scene and these fonctions have different dimensions: for the same set of points we integrate fonctions in 2-d, 4-d, 6-d etc. and we want good uniformity in these projections [9/16]

How? We realize that stratification and (0, m, s) constraints can be formulated by constraints on matrix determinants. To generate coordinates for sample number "i" -- e.g., in 2-d -- we decompose "i" in base 2 (in binary) to form a vector of digits, [10/16]

we find 2 triangular matrices (one for the X coordinates, one for Y) with values in {0, 1}, multiply modulo 2 each matrix with the vector of digits to obtain 2 new vectors V and W. The 2-d coordinates of that point are given by X=sum(V_i * 2^-i) and Y=sum(W_i * 2^-i). [11/16]

The difficulty is to find these 2 matrices in such a way that the final pair of coorinates (X, Y) respects the desired constraints. [12/16]

So, it turns out that stratification and (0, m, 2) constraints can be written as the constraint that the determinant (mod 2) of a matrix formed by the concatenation of the first few rows of each of these 2 matrices should be different from 0. [13/16]

And trying to progressively find the elements of these 2 matrices column by column, these constraints on determinant can be put in the form of a integer linear program (ILP). [14/16]

In short satisfying complex sets of contraints on points can be done by solving an ILP. It turns out that finding solutions in base 2 is not a good choice as it leaves too little flexibility for the solver to satisfy constraints and we obtain much better results in base 3 [15/16]

This is the short version..go check the paper, it is excellent! For more experts we can actually replace Sobol sequence: it works better, the discrepancy is lower, and we control projections! And since Sobol is used everywhere, MatBuilder will undoubtely find its place :) [16/16]

@INS2I_CNRS @LIRISLyon @cnrs @UniversiteLyon @UnivLyon1 @Asso_AFIG @nvidia @ParisSIGGRAPH #Siggraph #SIGGRAPH2022 @siggraph