More Web Proxy on the site http://driver.im/

research-article

MatBuilder: mastering sampling uniformity over projections

Authors:

Nicolas Bonneel,

David Coeurjolly,

Jean-Claude Iehl,

Alexander Keller,

Victor OstromoukhovAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 41, Issue 4

Article No.: 84, Pages 1 - 13

https://doi.org/10.1145/3528223.3530063

Published: 22 July 2022 Publication History

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.

Supplemental Material

MP4 File

presentation

Download
84.06 MB

ZIP File

supplemental material

Download
165.76 MB

References

[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.

[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.

Digital Library

[3]

Abdalla G. M. Ahmed and Peter Wonka. 2021. Optimizing Dyadic Nets. ACM Trans. on Graphics (SIGGRAPH) 40, 4, Article 141 (2021), 17 pages.

Digital Library

[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.

[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.

[6]

Kenneth A. Bush. 1952. Orthogonal arrays of index unity. The Annals of Mathematical Statistics 33, 3 (1952), 426--434.

[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.

Digital Library

[8]

Josef Dick and Friedrich Pillichshammer. 2010. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press.

Digital Library

[9]

Henri Faure and Christiane Lemieux. 2016. Irreducible Sobol' sequences in prime power bases. Acta Arithmetica 173 (2016), 59--80.

[10]

Henri Faure and Christiane Lemieux. 2019. Implementation of irreducible Sobol' sequences in prime power bases. Math. Comput. Simul. 161 (2019), 13--22.

Digital Library

[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.

[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.

[13]

John Halton. 1964. Radical-inverse quasi-random point sequence [G5]. Comm. ACM 7, 12 (1964), 701--702.

Digital Library

[14]

Yuanzhen He and Boxin Tang. 2013. Strong orthogonal arrays and associated Latin hypercubes for computer experiments. Biometrika 100, 1 (2013), 254--260.

[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.

[16]

Fred Hickernell. 1998. A generalized discrepancy and quadrature error bound. Math. Comp. 67, 221 (1998), 299--322.

Digital Library

[17]

IBM. 2022. IBM ILOG CPLEX Optimizer. https://www.ibm.com/analytics/cplex-optimizer

[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.

[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.

Digital Library

[20]

Alexander Keller. 2004. Stratification by rank-1 lattices. In Monte Carlo and Quasi-Monte Carlo Methods 2002, Harald Niederreiter (Ed.). Springer, 299--313.

[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.

[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.

[23]

Leslie Kish. 1965. Survey Sampling. John Wiley & Sons.

[24]

Thomas Kollig and Alexander Keller. 2002. Efficient Multidimensional Sampling. Computer Graphics Forum (Proc. Eurographics 2002) 21, 3 (Sept. 2002), 557--563.

[25]

Anass Lasram, Sylvain Lefebvre, and Cyrille Damez. 2012a. Procedural texture preview. In Computer Graphics Forum (Eurographics), Vol. 31. 413--420.

Digital Library

[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-00748188

[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).

Digital Library

[28]

Christiane Lemieux. 2009. Monte Carlo and Quasi Monte Carlo Sampling. Springer.

[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.

[30]

Harald Niederreiter. 1992. Random Number Generation and quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, USA.

Digital Library

[31]

Art B. Owen. 1998. Monte Carlo extension of Quasi-Monte Carlo. In Proceedings of the 1998 Winter Simulation Conference. IEEE Press, 571--577.

[32]

Art B. Owen. 2013. Monte Carlo Theory, Methods and Examples. https://statweb.stanford.edu/~owen/mc/ Preprint.

[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/matbuilder

[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.

Digital Library

[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.

[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.

[37]

Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann.

[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.

Digital Library

[39]

Robin L. Plackett and J. Peter Burman. 1946. The design of optimum multifactorial experiments. Biometrika 33, 4 (1946), 305--325.

[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.

[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.

[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.

[43]

Laurence A. Wolsey. 2020. Integer Programming. John Wiley & Sons.

[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.

Digital Library

Cited By

Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
Ostromoukhov VBonneel NCoeurjolly DIehl J(2024)Quad-Optimized Low-Discrepancy SequencesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657431(1-9)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657431
Kirk NLemieux C(2024)An Improved Halton Sequence for Implementation in Quasi-Monte Carlo Methods2024 Winter Simulation Conference (WSC)10.1109/WSC63780.2024.10838773(431-442)Online publication date: 15-Dec-2024
https://doi.org/10.1109/WSC63780.2024.10838773
Show More Cited By

Index Terms

MatBuilder: mastering sampling uniformity over projections
1. Computing methodologies
  1. Computer graphics
    1. Rendering
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Permutations and combinations
  2. Mathematical analysis
    1. Numerical analysis
      1. Number-theoretic computations
    2. Quadrature

Recommendations

Generalized resampled importance sampling: foundations of ReSTIR

As scenes become ever more complex and real-time applications embrace ray tracing, path sampling algorithms that maximize quality at low sample counts become vital. Recent resampling algorithms building on Talbot et al.'s [2005] resampled importance ...
Cascaded Sobol' sampling

Rendering quality is largely influenced by the samplers used in Monte Carlo integration. Important factors include sample uniformity (e.g., low discrepancy) in the high-dimensional integration domain, sample uniformity in lower-dimensional projections, ...
Latin supercube sampling for very high-dimensional simulations
Special issue on uniform random number generation

This article introduces Latin supercube sampling (LSS) for very high-dimensional simulations such as arise in particle transport, finance, and queueing. LSS is developed as a combination of two widely used methods: Latin hypercube sampling (LHS) and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 41, Issue 4

July 2022

1978 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3528223

Issue’s Table of Contents

Copyright © 2022 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 July 2022

Published in TOG Volume 41, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ANR

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
148
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)3

Reflects downloads up to 01 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
Ostromoukhov VBonneel NCoeurjolly DIehl J(2024)Quad-Optimized Low-Discrepancy SequencesACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657431(1-9)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657431
Kirk NLemieux C(2024)An Improved Halton Sequence for Implementation in Quasi-Monte Carlo Methods2024 Winter Simulation Conference (WSC)10.1109/WSC63780.2024.10838773(431-442)Online publication date: 15-Dec-2024
https://doi.org/10.1109/WSC63780.2024.10838773
Rusch TKirk NBronstein MLemieux CRus D(2024)Message-Passing Monte Carlo: Generating low-discrepancy point sets via graph neural networksProceedings of the National Academy of Sciences10.1073/pnas.2409913121121:40Online publication date: 26-Sep-2024
https://doi.org/10.1073/pnas.2409913121
Clément FDoerr CPaquete L(2024)Heuristic approaches to obtain low-discrepancy point sets via subset selectionJournal of Complexity10.1016/j.jco.2024.10185283:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.jco.2024.101852
Choi SDing YHickernell FRathinavel JSorokin A(2024)Challenges in Developing Great Quasi-Monte Carlo SoftwareMonte Carlo and Quasi-Monte Carlo Methods10.1007/978-3-031-59762-6_9(209-222)Online publication date: 13-Jul-2024
https://doi.org/10.1007/978-3-031-59762-6_9
Paulin LCoeurjolly DBonneel NIehl JOstromoukhov VKeller A(2024)Generator Matrices by Solving Integer Linear ProgramsMonte Carlo and Quasi-Monte Carlo Methods10.1007/978-3-031-59762-6_26(525-541)Online publication date: 13-Jul-2024
https://doi.org/10.1007/978-3-031-59762-6_26
Keller AWächter CBinder N(2024)Quasi-Monte Carlo Algorithms (Not Only) for Graphics SoftwareMonte Carlo and Quasi-Monte Carlo Methods10.1007/978-3-031-59762-6_18(373-391)Online publication date: 13-Jul-2024
https://doi.org/10.1007/978-3-031-59762-6_18
Doignies BBonneel NCoeurjolly DDigne JPaulin LIehl JOstromoukhov V(2023)Example-Based Sampling with Diffusion ModelsSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618243(1-11)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1145/3610548.3618243
Clément FVermetten DDe Nobel JJesus APaquete LDoerr CSilva SPaquete L(2023)Computing Star Discrepancies with Numerical Black-Box Optimization AlgorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590456(1330-1338)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590456
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents