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

research-article

Cascaded Sobol' sampling

Authors:

David Coeurjolly,

Jean-Claude Iehl,

Nicolas Bonneel,

Alexander Keller,

Victor OstromoukhovAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 40, Issue 6

Article No.: 275, Pages 1 - 13

https://doi.org/10.1145/3478513.3480482

Published: 10 December 2021 Publication History

Abstract

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, and lack of dominant structures that could result in aliasing artifacts. A widely used and successful construction is the Sobol' sequence that guarantees good high-dimensional uniformity and consequently results in faster convergence of quasi-Monte Carlo integration. We show that this sequence exhibits low uniformity and dominant structures in low-dimensional projections. These structures impair quality in the context of rendering, as they precisely occur in the 2-dimensional projections used for sampling light sources, reflectance functions, or the camera lens or sensor. We propose a new cascaded construction, which, despite dropping the sequential aspect of Sobol' samples, produces point sets exhibiting provably perfect dyadic partitioning (and therefore, excellent uniformity) in consecutive 2-dimensional projections, while preserving good high-dimensional uniformity. By optimizing the initialization parameters and performing Owen scrambling at finer levels of binary representations, we further improve over Sobol's integration convergence rate. Our method does not incur any overhead as compared to the generation of the Sobol' sequence, is compatible with Owen scrambling and can be used in rendering applications.

Supplementary Material

ZIP File (a275-paulin.zip)

Supplemental files.

Download
61.95 MB

References

[1]

Abdalla GM 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. Graph. 35, 6 (2016), 247.

Digital Library

[2]

Abdalla GM Ahmed and Peter Wonka. 2020. Screen-space blue-noise diffusion of Monte Carlo sampling error via hierarchical ordering of pixels. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1--15.

Digital Library

[3]

Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-constrained point distributions: a variant of Lloyd's method. ACM Trans. Graph. 28, 3 (2009).

Digital Library

[4]

Benedikt Bitterli. 2016. Rendering resources. https://benedikt-bitterli.me/resources/.

[5]

Robert Bridson. 2007. Fast Poisson Disk Sampling in Arbitrary Dimensions. In ACM SIGGRAPH Sketches. 22--23.

Digital Library

[6]

Brent Burley. 2020. Practical Hash-based Owen Scrambling. Journal of Computer Graphics Techniques (JCGT) 10, 4 (2020), 1--20.

[7]

Per Christensen, Andrew Kensler, and Charlie Kilpatrick. 2018. Progressive Multi-Jittered Sample Sequences. Computer Graphics Forum 37, 4 (2018), 21--33.

[8]

Roy Cranley and Thomas NL Patterson. 1976. Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal. 13, 6 (1976), 904--914.

Digital Library

[9]

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

Digital Library

[10]

Raanan Fattal. 2011. Blue-Noise Point Sampling Using Kernel Density Model. ACM Trans. Graph. 30 (2011), 48:1--48:12.

Digital Library

[11]

Iliyan Georgiev and Marcos Fajardo. 2016. Blue-Noise Dithered Sampling. 35:1--35:1.

[12]

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.

[13]

Leonhard Grünschloß, Matthias Raab, and Alexander Keller. 2012. Enumerating Quasi-Monte Carlo Point Sequences in Elementary Intervals. In Monte Carlo and Quasi-Monte Carlo Methods 2010, Leszek Plaskota and Henryk Woźniakowski (Eds.). Springer, 399--408.

[14]

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

Digital Library

[15]

Daniel Heck, Thomas Schlömer, and Oliver Deussen. 2013. Blue Noise Sampling with Controlled Aliasing. ACM Trans. Graph. 32, 3 (2013), 25:1--25:12. Eric Heitz and Laurent Belcour. 2019. Distributing Monte Carlo Errors as a Blue Noise in Screen Space by Permuting Pixel Seeds Between Frames. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 149--158.

Digital Library

[16]

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.

Digital Library

[17]

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

Digital Library

[18]

Edmund Hlawka. 1961. Funktionen von beschränkter Variation in der Theorie der Gleichverteilung. Annali di Matematica Pura ed Applicata 54, 1 (1961), 325--333.

[19]

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.

[20]

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

[21]

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

[22]

Alexander Keller. 2013. Quasi-Monte Carlo Image Synthesis in a Nutshell. In Monte Carlo and Quasi-Monte Carlo Methods 2012, Joseph Dick, Frances Kuo, Gareth Peters, and Ian Sloan (Eds.). Springer, 203--238.

[23]

Lauwerens Kuipers and Harald Niederreiter. 2012. Uniform distribution of sequences. Courier Corporation.

[24]

Pierre L'Ecuyer and David Munger. 2016. Lattice Builder: A General Software Tool for Constructing Rank-1 Lattice Rules. https://github.com/umontreal-simul/latnetbuilder.

[25]

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

[26]

Hongli Liu, Honglei Han, and Min Jiang. 2021. Rank-1 Lattices for Efficient Path Integral Estimation. Computer Graphics Forum (2021).

[27]

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

Digital Library

[28]

Victor Ostromoukhov, Charles Donohue, and Pierre-Marc Jodoin. 2004. Fast Hierarchical Importance Sampling with Blue Noise Properties. ACM Transactions on Graphics 23, 3 (2004), 488--495. Proc. SIGGRAPH 2004.

Digital Library

[29]

Art Owen. 1995. Randomly Permuted (t, m, s)-Nets and (t, s)-Sequences. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (Lecture Notes in Statistics, Vol. 106), Harald Niederreiter and Peter Shiue (Eds.). Springer, 299--315.

[30]

Art Owen. 1998. Scrambling Sobol' and Niederreiter-Xing Points. Journal of Complexity 14, 4 (1998), 466--489.

Digital Library

[31]

Lois Paulin, Nicolas Bonneel, David Coeurjolly, Jean-Claude Iehl, Antoine Webanck, Mathieu Desbrun, and Victor Ostromoukhov. 2020. Sliced optimal transport sampling. ACM Trans. Graph 39 (2020).

[32]

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. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 339--353.

[33]

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

Digital Library

[34]

Bernhard Reinert, Tobias Ritschel, Hans-Peter Seidel, and Iliyan Georgiev. 2016. Projective blue-noise sampling. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 285--295.

Digital Library

[35]

Gurprit Singh, Cengiz Öztireli, Abdalla GM Ahmed, David Coeurjolly, Kartic Subr, Oliver Deussen, Victor Ostromoukhov, Ravi Ramamoorthi, and Wojciech Jarosz. 2019. Analysis of sample correlations for Monte Carlo rendering. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 473--491.

[36]

Neil James Alexander Sloane. 2017. The On-Line Encyclopedia of Integer Sequences. https://oeis.org/A058943 (2017).

[37]

Il'ya Meerovich 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.

[38]

Yahan Zhou, Haibin Huang, Li-Yi Wei, and Rui Wang. 2012. Point sampling with general noise spectrum. ACM Trans. Graph. 31, 4 (2012), 76.

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
Gaits FMellado NBouyjou GGarcia DBasarab A(2024)Efficient Stratified 3-D Scatterer Sampling for Freehand Ultrasound SimulationIEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control10.1109/TUFFC.2023.332401471:1(127-140)Online publication date: Jan-2024
https://doi.org/10.1109/TUFFC.2023.3324014
Show More Cited By

Index Terms

Cascaded Sobol' sampling
1. Computing methodologies
  1. Computer graphics
    1. Rendering

Recommendations

MatBuilder: mastering sampling uniformity over projections

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 ...
Acceleration of the Multiple-Try Metropolis algorithm using antithetic and stratified sampling
Abstract
The Multiple-Try Metropolis is a recent extension of the Metropolis algorithm in which the next state of the chain is selected among a set of proposals. We propose a modification of the Multiple-Try Metropolis algorithm which allows for the use of ...
On the exact t-value of Niederreiter and Sobol' sequences

This paper studies several well-known families of (t,s)-sequences. First we determine the exact t-value of Niederreiter sequences. Then we analyze the exact t-value of generalized Niederreiter sequences and we show that, for a range of dimensions of ...

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 40, Issue 6

December 2021

1351 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3478513

Issue’s Table of Contents

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 December 2021

Published in TOG Volume 40, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
187
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)2

Reflects downloads up to 23 Jan 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
Gaits FMellado NBouyjou GGarcia DBasarab A(2024)Efficient Stratified 3-D Scatterer Sampling for Freehand Ultrasound SimulationIEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control10.1109/TUFFC.2023.332401471:1(127-140)Online publication date: Jan-2024
https://doi.org/10.1109/TUFFC.2023.3324014
Xing ZCheng HCheng J(2023)Deep Learning Method Based on Physics-Informed Neural Network for 3D Anisotropic Steady-State Heat Conduction ProblemsMathematics10.3390/math1119404911:19(4049)Online publication date: 24-Sep-2023
https://doi.org/10.3390/math11194049
Ahmed ASkopenkov MHadwiger MWonka P(2023)Analysis and Synthesis of Digital Dyadic SequencesACM Transactions on Graphics10.1145/361830842:6(1-17)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618308
Bærentzen JFrisvad JMartínez J(2023)Curl Noise JitteringSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618163(1-11)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1145/3610548.3618163
Zhang WWang BXu JZhao C(2022)High-quality quasi-monochromatic near-field radiative heat transfer designed by adaptive hybrid Bayesian optimizationScience China Technological Sciences10.1007/s11431-022-2065-265:12(2910-2920)Online publication date: 7-Nov-2022
https://doi.org/10.1007/s11431-022-2065-2
Keller AWächter CBinder N(2022)Rendering Along the Hilbert CurveAdvances in Modeling and Simulation10.1007/978-3-031-10193-9_16(319-332)Online publication date: 1-Dec-2022
https://doi.org/10.1007/978-3-031-10193-9_16
Keller AVan keirsbilck M(2022)Artificial Neural Networks Generated by Low Discrepancy SequencesMonte Carlo and Quasi-Monte Carlo Methods10.1007/978-3-030-98319-2_15(291-311)Online publication date: 21-May-2022
https://doi.org/10.1007/978-3-030-98319-2_15

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.

Media

Figures

Other

Tables

View Issue’s Table of Contents