MatBuilder: Mastering Sampling Uniformity Over Projections

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 number of mathematical constructions for such samplers. We propose a novel approach by showing that uniformity constraints can be expressed as an integer 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 versatility of our constraint approach with respect to low-dimensional problem structure for several applications.

Caption: Generator matrix structure: (𝑎) The first row of the generator matrix 𝐶𝑖 acts on the most significant digit of b_{m-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. (𝑏) When coupling the matrices to design a 2D sampler, the first rows of 𝐶_0 select intervals along the 𝑥-axis, while the first rows of the 𝐶_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.

@article{paulin2022,
      author = {Loïs Paulin and Nicolas Bonneel and David Coeurjolly and Jean-Claude Iehl and Alexander Keller and Victor Ostromoukhov},
      journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH)},
      month = {August},
      number = {4},
      title = {MatBuilder: Mastering Sampling Uniformity Over Projections},
      volume = {41},
      doi = {https://doi.org/10.1145/3528223.3530063},
      year = {2022}
}