Top

Published in:

2024 | OriginalPaper | Chapter

Quasi-Monte Carlo Algorithms (Not Only) for Graphics Software

Authors : Alexander Keller, Carsten Wächter, Nikolaus Binder

Published in: Monte Carlo and Quasi-Monte Carlo Methods

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Quasi-Monte Carlo methods have become the industry standard in computer graphics. For that purpose, efficient algorithms for low discrepancy sequences are discussed. In addition, numerical pitfalls encountered in practice are revealed. We then take a look at massively parallel quasi-Monte Carlo integro-approximation for image synthesis by light transport simulation. Beyond superior uniformity, low discrepancy points may be optimized with respect to additional criteria, such as noise characteristics at low sampling rates or the quality of low-dimensional projections.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Randomized Complexity of Vector-Valued Approximation

next chapter Sequential Estimation Using Hierarchically Stratified Domains with Latin Hypercube Sampling

https://en.cppreference.com/w/cpp/language/operator_arithmetic.

Code for the generation of such tables is found at https://gruenschloss.org.

Belcour, L., Heitz, E.: Lessons learned and improvements when building screen-space samplers with blue-noise error distribution. ACM SIGGRAPH 2021 Talks, Article No.: 9, pp. 1–2. https://arxiv.org/abs/2105.12620

Cools, R., Kuo, F., Nuyens, D.: Constructing embedded lattice rules for multivariate integration. SIAM J. Sci. Comput. 28, 2162–2188 (2006)MathSciNetCrossRef

Downey, A.B.: Generating pseudo-random floating-point values (2007). https://allendowney.com/research/rand/

Faure, H.: Good permutations for extreme discrepancy. J. Number Theory 42, 47–56 (1992)MathSciNetCrossRef

Faure, H., Lemieux, C.: Generalized Halton sequences in 2008: A comparative study. ACM Trans. Model. Comput. Simul. 19(4), 15:1–15:31 (2009)

Georgiev, I., Fajardo, M.: Blue-noise dithered sampling. ACM SIGGRAPH 2016 Talks (2016)

Gerber, M., Chopin, N.: Sequential quasi-Monte Carlo. J. Roy. Stat. Soc. Ser. B (Stat. Methodol.) 77(3), 509–579 (2015). http://www.jstor.org/stable/24774819

Goda, T., L’Ecuyer, P.: Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights. SIAM J. Sci. Comput. 44(4), A2765–A2788 (2022). https://doi.org/10.1137/22M1473625

Goda, T., Suzuki, K., Matsumoto, M.: A universal median quasi-Monte Carlo integration. SIAM J. Numer. Anal. 62(1), 533–566 (2024)

10.

Goldberg, D.: What every computer scientist should know about floating-point arithmetic. ACM Comput. Surv. 23(1), 5–48 (1991)MathSciNetCrossRef

11.

Grünschloß, L., Keller, A.: \((t, m, s)\)-nets and maximized minimum distance, Part II. In: L’Ecuyer, P., Owen , A. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2008, pp. 395–409. Springer (2009). http://gruenschloss.org/diag0m2/diag0m2.pdf

12.

Grünschloß, L., Raab, M., Keller, A.: Enumerating quasi-Monte Carlo point sequences in elementary intervals. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 399–408. Springer (2012). http://gruenschloss.org/sample-enum/sample-enum.pdf

13.

Heitz, E., Belcour, L., Ostromoukhov, V., Coeurjolly, D., Iehl, J.C.: A low-discrepancy sampler that distributes Monte Carlo errors as a blue noise in screen space. ACM SIGGRAPH 2019 Talks. https://hal.archives-ouvertes.fr/hal-02150657

14.

Hickernell, F., Hong, H., L’Ecuyer, P., Lemieux, C.: Extensible lattice sequences for quasi-Monte Carlo quadrature. SIAM J. Sci. Comput. 22, 1117–1138 (2001)MathSciNetCrossRef

15.

Hickernell, F.J., Kritzer, P., Kuo, F.Y., Nuyens, D.: Weighted compound integration rules with higher order convergence for all \(N\). Numer. Algorithms 59, 161–183 (2012). https://doi.org/10.1007/s11075-011-9482-5

16.

Hickernell, F.J., Niederreiter, H.: The existence of good extensible rank-1 lattices. J. Complex. 19, 286–300 (2003)MathSciNetCrossRef

17.

Hong, H.S.: Digital Nets and Sequences for Quasi-Monte Carlo Methods. Ph.D. thesis, Hong Kong Baptist University (2002)

18.

Joe, S., Kuo, F.: Remark on algorithm 659: implementing Sobol’s quasirandom sequence generator. ACM Trans. Math. Softw. 29(1), 49–57 (2003)MathSciNetCrossRef

19.

Joe, S., Kuo, F.: Constructing Sobol’ sequences with better two-dimensional projections. SIAM J. Sci. Comput. 30(5), 2635–2654 (2008)MathSciNetCrossRef

20.

Joe, S., Kuo, F.: Notes on generating Sobol’ sequences. Technical report, School of Mathematics and Statistics, University of New South Wales (2008). http://web.maths.unsw.edu.au/~fkuo/sobol/joe-kuo-notes.pdf

21.

Keller, A.: Myths of computer graphics. In: Niederreiter, H. (ed.) Monte Carlo and Quasi-Monte Carlo Methods 2004, pp. 217–243. Springer (2006)

22.

Keller, A.: Quasi-Monte Carlo image synthesis in a nutshell. In: Dick, J., Kuo, F., Peters, G., Sloan, I. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2012, pp. 203–238. Springer (2013)

23.

Keller, A., Binder, N., Wächter, C.: Construction of a rank-1 lattice sequence based on primitive polynomials. In: Larcher, G., Pillichshammer, F., Winterhof, A., Xing, C. (eds.) Applied Algebra and Number Theory, pp. 204–215. Cambridge University Press (2014). https://doi.org/10.1017/CBO9781139696456.013

24.

Keller, A., Georgiev, I., Ahmed, A., Christensen, P., Pharr, M.: My favorite samples. In: ACM SIGGRAPH 2019 Courses, SIGGRAPH ’19, pp. 15:1–15:271. ACM, New York, NY, USA (2019). https://doi.org/10.1145/3305366.3329901

25.

Keller, A., Grünschloß, L.: Parallel quasi-Monte Carlo integration by partitioning low discrepancy sequences. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, pp. 487–498. Springer (2012). http://gruenschloss.org/parqmc/parqmc.pdf

26.

Keller, A., Premože, S., Raab, M.: Advanced (quasi) Monte Carlo methods for image synthesis. In: ACM SIGGRAPH 2012 Courses, SIGGRAPH ’12. Association for Computing Machinery, New York, NY, USA (2012). https://doi.org/10.1145/2343483.2343502

27.

Keller, A., Wächter, C., Binder, N.: Rendering along the Hilbert curve. In: Botev, Z., Keller, A., Lemieux, C., Tuffin, B. (eds.) Advances in Modeling and Simulation: Festschrift for Pierre L’Ecuyer, pp. 319–332. Springer (2022)

28.

Keller, A., Wächter, C., Raab, M., Seibert, D., Antwerpen, D., Korndörfer, J., Kettner, L.: The Iray light transport simulation and rendering system. CoRR abs/1705.01263 (2017). http://arxiv.org/abs/1705.01263

29.

Kritzer, P., Kuo, F.Y., Nuyens, D., Ullrich, M.: Lattice rules with random \(n\) achieve nearly the optimal \({O}(n^{-\alpha -1/2})\) error independently of the dimension. J. Approx. Theory 240, 96–113 (2019)MathSciNetCrossRef

30.

L’Ecuyer, P., Lemieux, C.: Recent Advances in randomized quasi-Monte Carlo methods. In: Dror, M., L’Ecuyer, P., Szidarovszky, F. (eds.) Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications, pp. 419–474. Kluwer Academic Publishers (2002)

31.

Leimkühler, T., Singh, G., Myszkowski, K., Seidel, H.P., Ritschel, T.: Deep point correlation design. ACM Trans. Graph. 38(6) (2019). https://doi.org/10.1145/3355089.3356562

32.

Liu, H., Han, H., Jiang, M.: Rank-1 lattices for efficient path integral estimation. Computer Graphics Forum 40(2), 91–102 (2021). https://doi.org/10.1111/cgf.142617

33.

L’Ecuyer, P., Marion, P., Godin, M., Puchhammer, F.: A tool for custom construction of QMC and RQMC point sets. In: International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, pp. 51–70. Springer (2022)

34.

Maize, E.: Contributions to the Theory of Error Reduction in Quasi-Monte Carlo Methods. Ph.D. thesis, The Claremont Graduate School (1980)

35.

Maize, E., Sepikas, J., Spanier, J.: Accelerating the convergence of lattice methods by importance sampling-based transformations. In: Plaskota, L., Woźniakowski, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2010, Springer Proceedings in Mathematics & Statistics, vol. 23, pp. 557–572. Springer (2012)

36.

Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia (1992)CrossRef

37.

Owen, A.B.: Monte Carlo extension of quasi-Monte Carlo. In: Proceedings of the 1998 Winter Simulation Conference, pp. 571–577. IEEE Press (1998)

38.

Owen, A.B.: On dropping the first Sobol’ point. In: Keller, A. (ed.) Monte Carlo and Quasi-Monte Carlo Methods 2020, pp. 71–86. Springer International Publishing, Cham (2022)CrossRef

39.

Pan, Z., Owen, A.B.: Super-polynomial accuracy of one dimensional randomized nets using the median-of-means. Math. Comput. 92(344), 805–837 (2023). https://arxiv.org/abs/2111.12676

40.

Paulin, L., Coeurjolly, D., Bonneel, N., Iehl, J.C., Keller, A., Ostromoukhov, V.: MatBuilder: Mastering sampling uniformity over projections. ACM Trans. Graph. 41(4), 84:1–84:13 (2022)

41.

Paulin, L., Coeurjolly, D., Bonneel, N., Iehl, J.C., Ostromoukhov, V., Keller, A.: Generator matrices by solving integer linear programs. In: Hinrichs, A., Kritzer, P., Pillichshammer, F. (eds.) Monte Carlo and Quasi-Monte Carlo Methods, pp. XX–YY. Springer International Publishing, Cham (2024, This volume)

42.

Pharr, M., Jacob, W., Humphreys, G.: Physically Based Rendering - From Theory to Implementation, 4th edn. Morgan Kaufmann (2023)

43.

Walker, A.J.: Fast generation of uniformly distributed pseudorandom numbers with floating-point representation. Electron. Lett. 10, 533–534 (1974)CrossRef

44.

Warren, H.S.: Hacker’s Delight. Pearson Education (2012). https://books.google.de/books?id=VicPJYM0I5QC

Title: Quasi-Monte Carlo Algorithms (Not Only) for Graphics Software
Authors: Alexander Keller
Carsten Wächter
Nikolaus Binder
Publisher: Springer International Publishing
Book: Monte Carlo and Quasi-Monte Carlo Methods
Print ISBN: 978-3-031-59761-9

Electronic ISBN: 978-3-031-59762-6

Copyright Year: 2024
DOI: https://doi.org/10.1007/978-3-031-59762-6_18

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"