ACM Siggraph, 2022, Proceedings

MatBuilder: Mastering Sampling Uniformity Over Projections

LoΓ―s Paulin1       Nicolas Bonneel1       David Coeurjolly1
Jean-Claude Iehl1       Alexander Keller2       Victor Ostromoukhov1



1Université de Lyon, CNRS/LIRIS, France
2NVIDIA



Generator Matrix Structure. (a) The first row of the generator matrix 𝐢𝑖 acts on the most significant digit of π‘π‘šβˆ’1 selecting one two intervals of size 2π‘šβˆ’1 in base 2, the first two rows of 𝐢𝑖 determine one intervals of size 2π‘šβˆ’2 and so on. (b) When coupling the matrices to design a 2D sampler, the first rows of 𝐢0 select intervals along the π‘₯-axis, while the first rows of 𝐢1 select intervals along the 𝑦-dimension. If 𝑀𝐾 is of full rank, samples generated by 𝐢0 and 𝐢1 will be stratified in the cells induced by selected rows of the two matrices.

Abstract

Many applications ranging from quasi-Monte Carlo integration over optimal control to neural networks benefit from high-dimensional, highly uniform samples. In the case of computer graphics, and more particularly in rendering, despite the need for uniformity, several sub-problems expose a low-dimensional structure. In this context, mastering sampling uniformity over projections while preserving high-dimensional uniformity has been intrinsically challenging. This difficulty may explain the relatively small num- ber of mathematical constructions for such samplers. We propose a novel approach by showing that uniformity constraints can be expressed as an inte- ger linear program that results in a sampler with the desired properties. As it turns out, complex constraints are easy to describe by means of stratification and sequence properties of digital nets. Formalized using generator matrix determinants, our new MatBuilder software solves the set of constraints by iterating the linear integer program solver in a greedy fashion to compute a problem-specific set of generator matrices that can be used as a drop-in replacement in the popular digital net samplers. The samplers created by MatBuilder achieve the uniformity of classic low discrepancy sequences. More importantly, we demonstrate the benefit of the unprecedented versa- tility of our constraint approach with respect to low-dimensional problem structure for several applications.

Bibtex

           @Article{matbuilder2022,
                    title =        {MatBuilder: Mastering Sampling Uniformity over Projections},
                    author =       {Paulin, LoΓ―s and Bonneel, Nicolas and Coeurjolly, David and Iehl, Jean-Claude and Keller, Alexander and Ostromoukhov, Victor},
                    journal =      {ACM Transactions on Graphics (Proceedings of SIGGRAPH)},
                    year =         {2022},
                    month =        aug,
                    volume =       {41},
                    number =       {4},
                    doi =          {https://doi.org/10.1145/3528223.3530063},
                    url =          {https://github.com/loispaulin/matbuilder},
            }

Downloads

Paper
PDF
  		Supplementary material
PDF
  		Source Code
Github