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

research-article

Open access

Screen-space blue-noise diffusion of monte carlo sampling error via hierarchical ordering of pixels

Authors:

Abdalla G. M. Ahmed,

Peter WonkaAuthors Info & Claims

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

Article No.: 244, Pages 1 - 15

https://doi.org/10.1145/3414685.3417881

Published: 27 November 2020 Publication History

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.

Supplementary Material

ZIP File (a244-ahmed.zip)

Supplemental material.

Download
442.82 MB

MP4 File (3414685.3417881.mp4)

Presentation video

Download
21.04 MB

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.

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

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

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

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

Digital Library

[6]

R. Bridson. 2007. Fast Poisson-Disk Sampling in Arbitrary Dimensions. In ACM SIGGRAPH 2007 Sketches.

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

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

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

Digital Library

[10]

Robert L. Cook. 1986. Stochastic Sampling in Computer Graphics. ACM Trans. Graph. 5, 1 (Jan. 1986), 51--72.

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

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

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

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

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

Digital Library

[16]

Fredo Durand. 2011. A Frequency Analysis of Monte Carlo and Other Numerical Integration Schemes. MIT CSAIL Tech. Rep. TR-2011-052 (2011).

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

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

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

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

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

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

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

Digital Library

[24]

Iliyan Georgiev and Marcos Fajardo. 2016. Blue-Noise Dithered Sampling. In ACM SIGGRAPH 2016 Talks. 1--1.

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

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

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

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

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

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

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

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

[33]

Andrew Kensler. 2013. Correlated Multi-Jittered Sampling. Pixar Technical Memo 13--01 7 (2013), 86--112.

[34]

Thomas Kollig and Alexander Keller. 2002. Efficient Multidimensional Sampling. In Computer Graphics Forum, Vol. 21. 557--563.

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

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

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

Digital 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.155306

Digital Library

[39]

Don P. Mitchell. 1991. Spectrally Optimal Sampling for Distribution Ray Tracing. SIGGRAPH Comput. Graph. 25, 4 (July 1991), 157--164.

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

Digital Library

[41]

GM Morton. 1966. A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing. (1966).

[42]

Victor Ostromoukhov. 2007. Sampling with Polyominoes. ACM Trans. Graph. 26, 3, Article 78 (July 2007).

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

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

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

[46]

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

Digital Library

[47]

A. Cengiz Öztireli. 2016. Integration with Stochastic Point Processes. ACM Trans. Graph. 35, 5, Article 160 (Aug. 2016), 16 pages.

Digital 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

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

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

[51]

Matt Pharr and Greg Humphreys. 2010. Physically-Based Rendering: from Theory to Implementation (2nd ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

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

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

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

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

Digital 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

[57]

Peter Shirley. 1991. Discrepancy as a Quality Measure for Sample Distributions. In Proc. Eurographics '91, Vol. 91. 183--194.

[58]

Robert Ulichney. 1987. Digital Halftoning. MIT Press, Cambridge, MA, USA.

Digital Library

[59]

R.A. Ulichney. 1988. Dithering with Blue Noise. Proc. IEEE 76, 1 (Jan 1988), 56--79.

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

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

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

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

Digital Library

Cited By

Donnelly WWolfe ABütepage JValdés J(2024)FAST: Filter-Adapted Spatio-Temporal Sampling for Real-Time RenderingProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36512837:1(1-16)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3651283
Shen ZChen CZhang RYu HLi L(2024)Perception-JND-driven path tracing for reducing sample budgetThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-023-03199-w40:11(7651-7665)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s00371-023-03199-w
Hinojosa CLiu SGhanem B(2024)ColorMAE: Exploring Data-Independent Masking Strategies in Masked AutoEncodersComputer Vision – ECCV 202410.1007/978-3-031-72661-3_25(432-449)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72661-3_25
Show More Cited By

Index Terms

Screen-space blue-noise diffusion of monte carlo sampling error via hierarchical ordering of pixels
1. Computing methodologies
  1. Computer graphics
    1. Rendering

Recommendations

Perceptual Error Optimization for Monte Carlo Rendering
Synthesizing realistic images involves computing high-dimensional light-transport integrals. In practice, these integrals are numerically estimated via Monte Carlo integration. The error of this estimation manifests itself as conspicuous aliasing or ...
Blue-noise dithered sampling
SIGGRAPH '16: ACM SIGGRAPH 2016 Talks

The visual fidelity of a Monte Carlo rendered image depends not only on the magnitude of the pixel estimation error but also on its distribution over the image. To this end, state-of-the-art methods use high-quality stratified sampling patterns, which ...
Multi-class blue noise sampling
SIGGRAPH '10: ACM SIGGRAPH 2010 papers

Sampling is a core process for a variety of graphics applications. Among existing sampling methods, blue noise sampling remains popular thanks to its spatial uniformity and absence of aliasing artifacts. However, research so far has been mainly focused ...

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

December 2020

1605 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3414685

Editor:
Karol Myszkowski
MPI Informatik

Issue’s Table of Contents

Copyright © 2020 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: 27 November 2020

Published in TOG Volume 39, 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

17
Total Citations
View Citations
945
Total Downloads

Downloads (Last 12 months)342
Downloads (Last 6 weeks)30

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Donnelly WWolfe ABütepage JValdés J(2024)FAST: Filter-Adapted Spatio-Temporal Sampling for Real-Time RenderingProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36512837:1(1-16)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3651283
Shen ZChen CZhang RYu HLi L(2024)Perception-JND-driven path tracing for reducing sample budgetThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-023-03199-w40:11(7651-7665)Online publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1007/s00371-023-03199-w
Hinojosa CLiu SGhanem B(2024)ColorMAE: Exploring Data-Independent Masking Strategies in Masked AutoEncodersComputer Vision – ECCV 202410.1007/978-3-031-72661-3_25(432-449)Online publication date: 29-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72661-3_25
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
Ahmed APharr MWonka P(2023)ART-Owen ScramblingACM Transactions on Graphics10.1145/361830742:6(1-11)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618307
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
Korać MSalaün CGeorgiev IGrittmann PSlusallek PMyszkowski KSingh G(2023)Perceptual error optimization for Monte Carlo animation renderingSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618146(1-10)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1145/3610548.3618146
Salaün CGeorgiev ISeidel HSingh G(2022)Scalable Multi-Class Sampling via Filtered Sliced Optimal TransportACM Transactions on Graphics10.1145/3550454.355548441:6(1-14)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555484
Paulin LBonneel NCoeurjolly DIehl JKeller AOstromoukhov V(2022)MatBuilderACM Transactions on Graphics10.1145/3528223.353006341:4(1-13)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530063
Chizhov VGeorgiev IMyszkowski KSingh G(2022)Perceptual Error Optimization for Monte Carlo RenderingACM Transactions on Graphics10.1145/350400241:3(1-17)Online publication date: 7-Mar-2022
https://dl.acm.org/doi/10.1145/3504002
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Issue’s Table of Contents