“Screen-space blue-noise diffusion of monte carlo sampling error via hierarchical ordering of pixels” by Ahmed and Wonka
Conference:
Type(s):
Title:
- Screen-space blue-noise diffusion of monte carlo sampling error via hierarchical ordering of pixels
Session/Category Title: Light transport: Sampling
Presenter(s)/Author(s):
Abstract:
We present a novel technique for diffusing Monte Carlo sampling error as a blue noise in screen space. We show that automatic diffusion of sampling error can be achieved by ordering the pixels in a way that preserves locality, such as Morton’s Z-ordering, and assigning the samples to the pixels from successive sub-sequences of a single low-discrepancy sequence, thus securing well-distributed samples for each pixel, local neighborhoods, and the whole image. We further show that a blue-noise distribution of the error is attainable by scrambling the Z-ordering to induce isotropy. We present an efficient technique to implement this hierarchical scrambling by defining a context-free grammar that describes infinite self-similar lookup trees. Our concept is scalable to arbitrary image resolutions, sample dimensions, and sample count, and supports progressive and adaptive sampling.
References:
1. A. G. M. Ahmed, J. Guo, D. M. Yan, J. Y. Franceschia, X. Zhang, and O. Deussen. 2017a. A Simple Push-Pull Algorithm for Blue-Noise Sampling. IEEE Transactions on Visualization and Computer Graphics 23, 12 (Dec. 2017), 2496–2508. Google ScholarCross Ref
2. Abdalla G. M. Ahmed, Hui Huang, and Oliver Deussen. 2015. AA Patterns for Point Sets with Controlled Spectral Properties. ACM Trans. Graph. 34, 6, Article 212 (Oct. 2015), 8 pages. Google ScholarDigital Library
3. Abdalla G. M. Ahmed, Till Niese, Hui Huang, and Oliver Deussen. 2017b. An Adaptive Point Sampler on a Regular Lattice. ACM Trans. Graph. 36, 4, Article 138 (July 2017), 13 pages. Google ScholarDigital Library
4. 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. Graph. 35, 6, Article 247 (Nov. 2016), 13 pages. Google ScholarDigital Library
5. Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-Constrained Point Distributions: A Variant of Lloyd’s Method. ACM Trans. Graph. 28, 3, Article 86 (July 2009), 8 pages. Google ScholarDigital Library
6. R. Bridson. 2007. Fast Poisson-Disk Sampling in Arbitrary Dimensions. In ACM SIGGRAPH 2007 Sketches.Google Scholar
7. Zhonggui Chen, Zhan Yuan, Yi-King Choi, Ligang Liu, and Wenping Wang. 2012. Variational Blue Noise Sampling. IEEE Transactions on Visualization and Computer Graphics 18, 10 (Oct. 2012), 1784–1796. Google ScholarDigital Library
8. Per Christensen, Andrew Kensler, and Charlie Kilpatrick. 2018. Progressive Multi-Jittered Sample Sequences. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 21–33.Google Scholar
9. Michael F. Cohen, Jonathan Shade, Stefan Hiller, and Oliver Deussen. 2003. Wang Tiles for Image and Texture Generation. ACM Trans. Graph. 22, 3 (July 2003), 287–294. Google ScholarDigital Library
10. Robert L. Cook. 1986. Stochastic Sampling in Computer Graphics. ACM Trans. Graph. 5, 1 (Jan. 1986), 51–72. Google ScholarDigital Library
11. Robert L. Cook, Thomas Porter, and Loren Carpenter. 1984. Distributed Ray Tracing. In Proceedings of the 11th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’84). ACM, New York, NY, USA, 137–145. Google ScholarDigital Library
12. Roy Cranley and Thomas NL Patterson. 1976. Randomization of Number-Theoretic Methods for Multiple Integration. SIAM J. Numer. Anal. 13, 6 (1976), 904–914.Google ScholarDigital Library
13. Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue Noise through Optimal Transport. ACM Trans. Graph. 31, 6, Article 171 (Nov. 2012), 11 pages. Google ScholarDigital Library
14. Mark A. Z. Dippé and Erling Henry Wold. 1985. Antialiasing through Stochastic Sampling. In Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’85). ACM, New York, NY, USA, 69–78. Google ScholarDigital Library
15. Daniel Dunbar and Greg Humphreys. 2006. A Spatial Data Structure for Fast Poisson-Disk Sample Generation. ACM Trans. Graph. 25, 3 (July 2006), 503–508. Google ScholarDigital Library
16. Fredo Durand. 2011. A Frequency Analysis of Monte Carlo and Other Numerical Integration Schemes. MIT CSAIL Tech. Rep. TR-2011-052 (2011).Google Scholar
17. Mohamed S. Ebeida, Muhammad A. Awad, Xiaoyin Ge, Ahmed H. Mahmoud, Scott A. Mitchell, Patrick M. Knupp, and Li-Yi Wei. 2014. Improving Spatial Coverage while Preserving the Blue Noise of Point Sets. Computer-Aided Design 46, Supplement C (2014), 25–36. 2013 SIAM Conference on Geometric and Physical Modeling. Google ScholarDigital Library
18. Mohamed S. Ebeida, Andrew A. Davidson, Anjul Patney, Patrick M. Knupp, Scott A. Mitchell, and John D. Owens. 2011. Efficient Maximal Poisson-Disk Sampling. ACM Trans. Graph. 30, 4, Article 49 (July 2011), 12 pages. Google ScholarDigital Library
19. Mohamed S. Ebeida, Scott A. Mitchell, Anjul Patney, Andrew A. Davidson, and John D. Owens. 2012. A Simple Algorithm for Maximal Poisson-Disk Sampling in High Dimensions. Comp. Graph. Forum 31, 2pt4 (May 2012), 785–794. Google ScholarDigital Library
20. Y. Eldar, M. Lindenbaum, M. Porat, and Y. Y. Zeevi. 1997. The Farthest-Point Strategy for Progressive Image Sampling. Trans. Img. Proc. 6, 9 (Sept. 1997), 1305–1315. Google ScholarDigital Library
21. Raanan Fattal. 2011. Blue-Noise Point Sampling Using Kernel Density Model. In ACM SIGGRAPH 2011 Papers (SIGGRAPH ’11). ACM, New York, NY, USA, Article 48, 12 pages. Google ScholarDigital Library
22. Ilja Friedel and Alexander Keller. 2002. Fast Generation of Randomized Low-Discrepancy Point Sets. In Monte Carlo and Quasi-Monte Carlo Methods 2000. Springer, 257–273.Google Scholar
23. Manuel N. Gamito and Steve C. Maddock. 2009. Accurate Multidimensional Poisson-Disk Sampling. ACM Trans. Graph. 29, 1, Article 8 (Dec. 2009), 19 pages. Google ScholarDigital Library
24. Iliyan Georgiev and Marcos Fajardo. 2016. Blue-Noise Dithered Sampling. In ACM SIGGRAPH 2016 Talks. 1–1.Google Scholar
25. 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 Berlin Heidelberg, Berlin, Heidelberg, 399–408.Google Scholar
26. Daniel Heck, Thomas Schlömer, and Oliver Deussen. 2013. Blue Noise Sampling with Controlled Aliasing. ACM Trans. Graph. 32, 3, Article 25 (July 2013), 12 pages.Google ScholarDigital Library
27. 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.Google Scholar
28. Eric Heitz, Laurent Belcour, V. 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 2019 Talks (SIGGRAPH ’19). Association for Computing Machinery, New York, NY, USA, Article 68, 2 pages. Google ScholarDigital Library
29. Wojciech Jarosz, Afnan Enayet, Andrew Kensler, Charlie Kilpatrick, and Per Christensen. 2019. Orthogonal Array Sampling for Monte Carlo Rendering. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 135–147.Google Scholar
30. Min Jiang, Yahan Zhou, Rui Wang, Richard Southern, and Jian Jun Zhang. 2015. Blue Noise Sampling Using an SPH-Based Method. ACM Trans. Graph. 34, 6, Article 211 (2015), 11 pages. Google ScholarDigital Library
31. Thouis R Jones. 2006. Efficient Generation of Poisson-Disk Sampling Patterns. Journal of graphics, gpu, and game tools 11, 2 (2006), 27–36.Google ScholarCross Ref
32. Alexander Keller. 2013. Quasi-Monte Carlo Image Synthesis in a Nutshell. In Monte Carlo and Quasi-Monte Carlo Methods 2012, Josef Dick, Frances Y. Kuo, Gareth W. Peters, and Ian H. Sloan (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 213–249.Google Scholar
33. Andrew Kensler. 2013. Correlated Multi-Jittered Sampling. Pixar Technical Memo 13–01 7 (2013), 86–112.Google Scholar
34. Thomas Kollig and Alexander Keller. 2002. Efficient Multidimensional Sampling. In Computer Graphics Forum, Vol. 21. 557–563.Google ScholarCross Ref
35. Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, and Dani Lischinski. 2006. Recursive Wang Tiles for Real-Time Blue Noise. ACM Trans. Graph. 25, 3 (July 2006), 509–518. Google ScholarDigital Library
36. Christopher Kulla, Alejandro Conty, Clifford Stein, and Larry Gritz. 2018. Sony Pictures Imageworks Arnold. ACM Trans. Graph. 37, 3, Article 29 (Aug. 2018), 18 pages. Google ScholarDigital Library
37. Ares Lagae and Philip Dutré. 2006. An Alternative for Wang Tiles: Colored Edges Versus Colored Corners. ACM Trans. Graph. 25, 4 (Oct. 2006), 1442–1459. Google ScholarDigital Library
38. Michael McCool and Eugene Fiume. 1992. Hierarchical Poisson-Disk Sampling Distributions. In Proceedings of the Conference on Graphics Interface ’92. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 94–105. http://dl.acm.org/citation.cfm?id=155294.155306Google ScholarDigital Library
39. Don P. Mitchell. 1991. Spectrally Optimal Sampling for Distribution Ray Tracing. SIGGRAPH Comput. Graph. 25, 4 (July 1991), 157–164. Google ScholarDigital Library
40. Scott A. Mitchell, Mohamed S. Ebeida, Muhammad A. Awad, Chonhyon Park, Anjul Patney, Ahmad A. Rushdi, Laura P. Swiler, Dinesh Manocha, and Li-Yi Wei. 2018. Spoke-Darts for High-Dimensional Blue-Noise Sampling. ACM Trans. Graph. 37, 2, Article Article 22 (May 2018), 20 pages. Google ScholarDigital Library
41. GM Morton. 1966. A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing. (1966).Google Scholar
42. Victor Ostromoukhov. 2007. Sampling with Polyominoes. ACM Trans. Graph. 26, 3, Article 78 (July 2007). Google ScholarDigital Library
43. Victor Ostromoukhov, Charles Donohue, and Pierre-Marc Jodoin. 2004. Fast Hierarchical Importance Sampling with Blue-Noise Properties. In ACM SIGGRAPH 2004 Papers (SIGGRAPH ’04). ACM, New York, NY, USA, 488–495. Google ScholarDigital Library
44. Victor Ostromoukhov, Roger D. Hersch, and Isaac Amidror. 1994. Rotated Dispersed Dither: A New Technique for Digital Halftoning. In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’94). Association for Computing Machinery, New York, NY, USA, 123–130. Google ScholarDigital Library
45. 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, Harald Niederreiter and Peter Jau-Shyong Shiue (Eds.). Springer New York, New York, NY, 299–317.Google Scholar
46. Art B Owen. 1998. Scrambling Sobol’and Niederreiter-Xing Points. Journal of complexity 14, 4 (1998), 466–489.Google ScholarDigital Library
47. A. Cengiz Öztireli. 2016. Integration with Stochastic Point Processes. ACM Trans. Graph. 35, 5, Article 160 (Aug. 2016), 16 pages. Google ScholarDigital Library
48. A. Cengiz Öztireli. 2020. A Comprehensive Theory and Variational Framework for Anti-aliasing Sampling Patterns. Computer Graphics Forum 39, 4 (2020), 133–148. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.14059 Google ScholarCross Ref
49. A. Cengiz Öztireli and Markus Gross. 2012. Analysis and Synthesis of Point Distributions Based on Pair Correlation. ACM Trans. Graph. 31, 6, Article 170 (Nov. 2012), 10 pages. Google ScholarDigital Library
50. 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. Computer Graphics Forum (Proceedings of Eurographics) 37, 2 (2018), 339–353.Google ScholarCross Ref
51. Matt Pharr and Greg Humphreys. 2010. Physically-Based Rendering: from Theory to Implementation (2nd ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.Google Scholar
52. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically Based Rendering: From Theory to Implementation (3rd ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.Google ScholarDigital Library
53. Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov. 2015. Variance Analysis for Monte Carlo Integration. ACM Trans. Graph. 34, 4, Article 124 (July 2015), 14 pages. Google ScholarDigital Library
54. Bernhard Reinert, Tobias Ritschel, Hans-Peter Seidel, and Iliyan Georgiev. 2016. Projective Blue-Noise Sampling. Computer Graphics Forum 35, 1 (2016), 285–295. Google ScholarDigital Library
55. Thomas Schlömer, Daniel Heck, and Oliver Deussen. 2011. Farthest-Point Optimized Point Sets with Maximized Minimum Distance. In Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics (HPG ’11). ACM, New York, NY, USA, 135–142. Google ScholarDigital Library
56. Thomas Schlömer and Oliver Deussen. 2011. Accurate Spectral Analysis of Two-Dimensional Point Sets. Journal of Graphics, GPU, and Game Tools 15, 3 (2011), 152–160. arXiv:http://dx.doi.org/10.1080/2151237X.2011.609773 Google ScholarCross Ref
57. Peter Shirley. 1991. Discrepancy as a Quality Measure for Sample Distributions. In Proc. Eurographics ’91, Vol. 91. 183–194.Google Scholar
58. Robert Ulichney. 1987. Digital Halftoning. MIT Press, Cambridge, MA, USA.Google ScholarDigital Library
59. R.A. Ulichney. 1988. Dithering with Blue Noise. Proc. IEEE 76, 1 (Jan 1988), 56–79. Google ScholarCross Ref
60. Robert A Ulichney. 1993. Void-and-Cluster Method for Dither Array Generation. In IS&T/SPIE’s Symposium on Electronic Imaging: Science and Technology. International Society for Optics and Photonics, 332–343.Google Scholar
61. Luiz Velho and Jonas de Miranda Gomes. 1991. Digital Halftoning with Space Filling Curves. In Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’91). Association for Computing Machinery, New York, NY, USA, 81–90. Google ScholarDigital Library
62. Florent Wachtel, Adrien Pilleboue, David Coeurjolly, Katherine Breeden, Gurprit Singh, Gaël Cathelin, Fernando de Goes, Mathieu Desbrun, and Victor Ostromoukhov. 2014. Fast Tile-Based Adaptive Sampling with User-Specified Fourier Spectra. ACM Trans. Graph. 33, 4, Article 56 (July 2014), 11 pages. Google ScholarDigital Library
63. Yahan Zhou, Haibin Huang, Li-Yi Wei, and Rui Wang. 2012. Point Sampling with General Noise Spectrum. ACM Trans. Graph. 31, 4, Article 76 (July 2012), 11 pages. Google ScholarDigital Library
