“MatBuilder: mastering sampling uniformity over projections” by Paulin, Bonneel, Coeurjolly, Iehl, Keller, et al. …

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.

1. Abdalla G. M. Ahmed, Hélène Perrier, David Coeurjolly, Victor Ostromoukhov, Jianwei Guo, Dong-Ming Yan, Hui Huang, and Oliver Deussen. 2016. Low-Discrepancy Blue Noise Sampling. ACM Trans. on Graphics (SIGGRAPH Asia) 35, 6 (2016), 13 pages. Google ScholarCross Ref
2. Abdalla G. M. Ahmed and Peter Wonka. 2020. Screen-space blue-noise diffusion of Monte Carlo sampling error via hierarchical ordering of pixels. ACM Trans. on Graphics (SIGGRAPH Asia) 39, 6 (2020), 1–15. Google ScholarCross Ref
3. Abdalla G. M. Ahmed and Peter Wonka. 2021. Optimizing Dyadic Nets. ACM Trans. on Graphics (SIGGRAPH) 40, 4, Article 141 (2021), 17 pages. Google ScholarCross Ref
4. Pietro Belotti, Christian Kirches, Sven Leyffer, Jeff Linderoth, James Luedtke, and Ashutosh Mahajan. 2013. Mixed-integer nonlinear optimization. Acta Numerica 22 (2013), 1–131. Google ScholarCross Ref
5. Raj C. Bose and Katherine A. Bush. 1952. Orthogonal arrays of strength two and three. The Annals of Mathematical Statistics 23, 4 (1952), 508–524. Google ScholarCross Ref
6. Kenneth A. Bush. 1952. Orthogonal arrays of index unity. The Annals of Mathematical Statistics 33, 3 (1952), 426–434. Google ScholarCross Ref
7. Stelian Coros, Philippe Beaudoin, and Michiel Van de Panne. 2009. Robust task-based control policies for physics-based characters. ACM Trans. on Graphics (SIGGRAPH Asia) 28, 5 (2009), 1–9. Google ScholarCross Ref
8. Josef Dick and Friedrich Pillichshammer. 2010. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press. Google ScholarCross Ref
9. Henri Faure and Christiane Lemieux. 2016. Irreducible Sobol’ sequences in prime power bases. Acta Arithmetica 173 (2016), 59–80. Google ScholarCross Ref
10. Henri Faure and Christiane Lemieux. 2019. Implementation of irreducible Sobol’ sequences in prime power bases. Math. Comput. Simul. 161 (2019), 13–22. Google ScholarCross Ref
11. Leonhard Grünschloß, Johannes Hanika, Ronnie Schwede, and Alexander Keller. 2008. (t, m, s)-Nets and Maximized Minimum Distance. In Monte Carlo and Quasi-Monte Carlo Methods 2006. Springer, 397–412. Google ScholarCross Ref
12. Pascal Guehl, Rémi Allegre, Jean-Michel Dischler, Bedrich Benes, and Eric Galin. 2020. Semi-Procedural Textures Using Point Process Texture Basis Functions. Computer Graphics Forum 39, 4 (2020), 159–171. Google ScholarCross Ref
13. John Halton. 1964. Radical-inverse quasi-random point sequence [G5]. Comm. ACM 7, 12 (1964), 701–702. Google ScholarCross Ref
14. Yuanzhen He and Boxin Tang. 2013. Strong orthogonal arrays and associated Latin hypercubes for computer experiments. Biometrika 100, 1 (2013), 254–260. Google ScholarCross Ref
15. Eric Heitz, Laurent Belcour, Victor Ostromoukhov, David Coeurjolly, and Jean-Claude Iehl. 2019. A Low-Discrepancy Sampler that Distributes Monte Carlo Errors as a Blue Noise in Screen Space. In ACM SIGGRAPH Talk. 1–2. Google ScholarCross Ref
16. Fred Hickernell. 1998. A generalized discrepancy and quadrature error bound. Math. Comp. 67, 221 (1998), 299–322. Google ScholarCross Ref
17. IBM. 2022. IBM ILOG CPLEX Optimizer. https://www.ibm.com/analytics/cplex-optimizerGoogle Scholar
18. Wojciech Jarosz, Afnan Enayet, Andrew Kensler, Charlie Kilpatrick, and Per Christensen. 2019. Orthogonal Array Sampling for Monte Carlo Rendering. Computer Graphics Forum 38, 4 (2019), 135–147. Google ScholarCross Ref
19. Stephen Joe and Frances Kuo. 2008. Constructing Sobol’ sequences with better two-dimensional projections. SIAM J. on Scientific Computing 30, 5 (2008), 2635–2654. Google ScholarCross Ref
20. Alexander Keller. 2004. Stratification by rank-1 lattices. In Monte Carlo and Quasi-Monte Carlo Methods 2002, Harald Niederreiter (Ed.). Springer, 299–313. Google ScholarCross Ref
21. Alexander Keller, Simon Premože, and Matthias Raab. 2012. Advanced (Quasi) Monte Carlo Methods for Image Synthesis. In ACM SIGGRAPH 2012 Courses. Article 21. Google ScholarCross Ref
22. Alexander Keller and Matthijs Van keirsbilck. 2022. Artificial Neural Networks generated by Low Discrepancy Sequences. In Monte Carlo and Quasi-Monte Carlo Methods, MCQMC 2020 (Lecture Notes in Statistics). Springer, to appear.Google Scholar
23. Leslie Kish. 1965. Survey Sampling. John Wiley & Sons.Google Scholar
24. Thomas Kollig and Alexander Keller. 2002. Efficient Multidimensional Sampling. Computer Graphics Forum (Proc. Eurographics 2002) 21, 3 (Sept. 2002), 557–563. Google ScholarCross Ref
25. Anass Lasram, Sylvain Lefebvre, and Cyrille Damez. 2012a. Procedural texture preview. In Computer Graphics Forum (Eurographics), Vol. 31. 413–420. Google ScholarCross Ref
26. Anass Lasram, Sylvain Lefebvre, and Cyrille Damez. 2012b. Scented Sliders for Procedural Textures. In EUROGRAPHICS short papers (Proceedings of the Eurographics conference (short papers)). Cagliari, Italy, 4 pages. https://hal.inria.fr/hal-00748188Google Scholar
27. Pierre L’Ecuyer and David Munger. 2016. Algorithm 958: LatticeBuilder: A General Software Tool for Constructing Rank-1 Lattice Rules. https://github.com/umontreal-simul/latnetbuilder. ACM Trans. Math. Software 42, 2, Article 15 (2016).Google ScholarDigital Library
28. Christiane Lemieux. 2009. Monte Carlo and Quasi Monte Carlo Sampling. Springer. Google ScholarCross Ref
29. Ricardo Marques, Christian Bouville, and Kadi Bouatouch. 2020. Spectral Analysis of Quadrature Rules and Fourier Truncation-Based Methods Applied to Shading Integrals. IEEE Trans. on Visualization and Computer Graphics 26, 10 (2020), 3022–3036. Google ScholarCross Ref
30. Harald Niederreiter. 1992. Random Number Generation and quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, USA. Google ScholarCross Ref
31. Art B. Owen. 1998. Monte Carlo extension of Quasi-Monte Carlo. In Proceedings of the 1998 Winter Simulation Conference. IEEE Press, 571–577. Google ScholarCross Ref
32. Art B. Owen. 2013. Monte Carlo Theory, Methods and Examples. https://statweb.stanford.edu/~owen/mc/ Preprint.Google Scholar
33. Loïs Paulin, Nicolas Bonneel, David Coeurjolly, Jean-Claude Iehl, Alexander Keller, and Victor Ostromoukhov. 2022. MatBuilder: Mastering Sampling Uniformity over Projections. https://github.com/loispaulin/matbuilderGoogle Scholar
34. Loïs Paulin, Nicolas Bonneel, David Coeurjolly, Jean-Claude Iehl, Antoine Webanck, Mathieu Desbrun, and Victor Ostromoukhov. 2020. Sliced optimal transport sampling. ACM Trans. on Graphics (SIGGRAPH) 39, 4 (2020), 99:1–99:17. Google ScholarCross Ref
35. Loïs Paulin, David Coeurjolly, Jean-Claude Iehl, Nicolas Bonneel, Alexander Keller, and Victor Ostromoukhov. 2021. Cascaded Sobol’ Sampling. ACM Trans. on Graphics (SIGGRAPH Asia) 40, 6 (2021), 274:1–274:13. Google ScholarCross Ref
36. Hélène Perrier, David Coeurjolly, Feng Xie, Matt Pharr, Pat Hanrahan, and Victor Ostromoukhov. 2018. Sequences with Low-Discrepancy Blue-Noise 2-D Projections. 37, 2 (2018), 339–353. Google ScholarCross Ref
37. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann.Google Scholar
38. Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov. 2015. Variance analysis for Monte Carlo integration. ACM Trans. on Graphics (SIGGRAPH) 34, 4 (2015), 124. Google ScholarCross Ref
39. Robin L. Plackett and J. Peter Burman. 1946. The design of optimum multifactorial experiments. Biometrika 33, 4 (1946), 305–325. Google ScholarCross Ref
40. Christophe Schlick. 1991. An Adaptive Sampling Technique for Multidimensional Integration by Ray-Tracing. In 2nd Eurographics Workshop on Rendering. Springer, Barcelona, Spain, 21–29. Google ScholarCross Ref
41. Ilya M. Sobol’. 1967. On the distribution of points in a cube and the approximate evaluation of integrals. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 7, 4 (1967), 784–802. Google ScholarCross Ref
42. Ilya M. Sobol’, Danil Asotsky, Alexander Kreinin, and Sergei Kucherenko. 2011. Construction and comparison of high-dimensional Sobol’generators. Wilmott 2011, 56 (2011), 64–79. Google ScholarCross Ref
43. Laurence A. Wolsey. 2020. Integer Programming. John Wiley & Sons.Google Scholar
44. Xiaohui Yuan, Lijun Xie, and Mohamed Abouelenien. 2018. A Regularized Ensemble Framework of Deep Learning for Cancer Detection from Multi-class, Imbalanced Training Data. Pattern Recognition 77 (2018), 160–172. Google ScholarCross Ref