“Quad-optimized Low-discrepancy Sequences” – ACM SIGGRAPH HISTORY ARCHIVES

“Quad-optimized Low-discrepancy Sequences”

  • ©

Conference:


Type(s):


Title:

    Quad-optimized Low-discrepancy Sequences

Presenter(s)/Author(s):



Abstract:


    This paper introduces multi-dimensional low-discrepancy sequences, in base 3 instead of the usual base 2, optimized over groups of 4 consecutive dimensions, while keeping good uniformity for non-optimized n-tuples of dimensions. We improve over Sobol’ sequences in terms of sample uniformity in 2D and 4D.

References:


    [1]
    Abdalla GM Ahmed, Jing Ren, and Peter Wonka. 2022. Gaussian blue noise. ACM Transactions on Graphics (TOG) 41, 6 (2022), 1?15.

    [2]
    Abdalla GM Ahmed, Mikhail Skopenkov, Markus Hadwiger, and Peter Wonka. 2023. Analysis and synthesis of digital dyadic sequences. ACM Transactions on Graphics (TOG) 42, 6 (2023), 1?17.

    [3]
    Ilya A Antonov and VM Saleev. 1979. An economic method of computing LP? -sequences. U. S. S. R. Comput. Math. and Math. Phys. 19, 1 (1979), 252?256.

    [4]
    Brent Burley. 2020. Practical hash-based Owen scrambling. Journal of Computer Graphics Techniques (JCGT) 10, 4 (2020), 29.

    [5]
    Per Christensen, Julian Fong, Jonathan Shade, Wayne Wooten, Brenden Schubert, Andrew Kensler, Stephen Friedman, Charlie Kilpatrick, Cliff Ramshaw, Marc Bannister, 2018. Renderman: An advanced path-tracing architecture for movie rendering. ACM Transactions on Graphics (TOG) 37, 3 (2018), 1?21.

    [6]
    Fernando De Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue noise through optimal transport. ACM Transactions on Graphics (TOG) 31, 6 (2012), 1?11.

    [7]
    Henri Faure and Christiane Lemieux. 2016. Irreducible Sobol?sequences in prime power bases. Acta Arithmetica 173, 1 (2016), 59?80.

    [8]
    Henri Faure and Christiane Lemieux. 2019. Implementation of irreducible Sobol?sequences in prime power bases. Mathematics and Computers in Simulation 161 (2019), 13?22.

    [9]
    Glyn Harman. 2010. Variations on the Koksma-Hlawka inequality. Unif. Distrib. Theory 5, 1 (2010), 65?78.

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

    [11]
    Andrew Helmer, Per H Christensen, and Andrew Kensler. 2021. Stochastic Generation of (t, s) Sample Sequences. In EGSR (DL). 21?33.

    [12]
    Stephen Joe and Frances Y Kuo. 2008. Constructing Sobol sequences with better two-dimensional projections. SIAM Journal on Scientific Computing 30, 5 (2008), 2635?2654.

    [13]
    Harald Niederreiter. 1992. Random number generation and quasi-Monte Carlo methods. SIAM.

    [14]
    Art B Owen. 1995. Randomly permuted (t, m, s)-nets and (t, s)-sequences. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing: Proceedings of a conference at the University of Nevada, Las Vegas, Nevada, USA, June 23?25, 1994. Springer, 299?317.

    [15]
    Lo?s Paulin, Nicolas Bonneel, David Coeurjolly, Jean-Claude Iehl, Alex Keller, and Victor Ostromoukhov. 2022. MatBuilder: Mastering Sampling Uniformity Over Projections. ACM Transactions on Graphics (SIGGRAPH) 41, 4 (Aug 2022).

    [16]
    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, 4 (2020), 99.

    [17]
    Lo?s Paulin, David Coeurjolly, Nicolas Bonneel, Jean-Claude Iehl, Victor Ostromoukhov, and Alex Keller. 2023. Generator Matrices by Solving Integer Linear Programs. Technical Report arXiv:2302.13943.

    [18]
    Lo?s Paulin, David Coeurjolly, Jean-Claude Iehl, Nicolas Bonneel, Alexander Keller, and Victor Ostromoukhov. 2021. Cascaded Sobol?Sampling. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1?13.

    [19]
    Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2023. Physically based rendering: From theory to implementation. MIT Press.

    [20]
    Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov. 2015. Variance analysis for Monte Carlo integration. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1?14.

    [21]
    Corentin Sala?n, Iliyan Georgiev, Hans-Peter Seidel, and Gurprit Singh. 2022. Scalable multi-class sampling via filtered sliced optimal transport. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) 41, 6 (2022). https://doi.org/10.1145/3550454.3555484

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


ACM Digital Library Publication:



Overview Page:



Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org