Abstract
We present a framework to distribute point samples with controlled spectral properties using a regular lattice of tiles with a single sample per tile. We employ a word-based identification scheme to identify individual tiles in the lattice. Our scheme is recursive, permitting tiles to be subdivided into smaller tiles that use the same set of IDs. The corresponding framework offers a very simple setup for optimization towards different spectral properties. Small lookup tables are sufficient to store all the information needed to produce different point sets. For blue noise with varying densities, we employ the bit-reversal principle to recursively traverse sub-tiles. Our framework is also capable of delivering multi-class blue noise samples. It is well-suited for different sampling scenarios in rendering, including area-light sampling (uniform and adaptive), and importance sampling. Other applications include stippling and distributing objects.
Supplemental Material
Available for Download
Supplemental files.
- A. G. M. Ahmed, J. Guo, D. M. Yan, J. Y. Franceschi, X. Zhang, and O. Deussen. 2016. A Simple Push-Pull Algorithm for Blue-Noise Sampling. IEEE Transactions on Visualization and Computer Graphics (2016). preprint.Google Scholar
- 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 (2015), 8 pages. Google ScholarDigital Library
- 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
- Jean-Paul Allouche and Jeffrey Shallit. 1999. The ubiquitous prouhet-thue-morse sequence. In Sequences and their applications. Springer, 1--16. Google ScholarCross Ref
- 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), 86:1--8.Google ScholarDigital Library
- B. Bayer. 1973. An optimum method for two-level rendition of continuous-tone pictures. In IEEE International Conference on Communications, Vol. 1. 11--15.Google Scholar
- Gwyneth A. Bradbury, Kartic Subr, Charalampos Koniaris, Kenny Mitchell, and Tim Weyrich. 2015. Guided Ecological Simulation for Artistic Editing of Plant Distributions in Natural Scenes. Journal of Computer Graphics Techniques (JCGT) 4, 4 (19 Nov. 2015), 28--53.Google Scholar
- Michael F. Cohen, Jonathan Shade, Stefan Hiller, and Oliver Deussen. 2003. Wang Tiles for Image and Texture Generation. In ACM SIGGRAPH Conference proceedings. 287--294. Google ScholarDigital Library
- Robert L. Cook. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1 (1986), 51--72. Google ScholarDigital Library
- Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue Noise Through Optimal Transport. ACM Trans. Graph. 31, 6, Article 171 (2012), 11 pages. Google ScholarDigital Library
- Mark A. Z. Dippé and Erling Henry Wold. 1985. Antialiasing Through Stochastic Sampling. SIGGRAPH Comput. Graph. 19, 3 (July 1985), 69--78. Google ScholarDigital Library
- Fredo Durand. 2011. A Frequency Analysis of Monte Carlo and Other Numerical Integration Schemes. MIT CSAIL Tech. rep. TR-2011--052 (2011).Google Scholar
- Raanan Fattal. 2011. Blue-noise point sampling using kernel density model. ACM Trans. Graph. 30, 3 (2011), 48:1--48:12.Google ScholarDigital Library
- Andrew S Glassner. 1995. Principles of digital image synthesis. Vol. 1. Elsevier.Google Scholar
- Leonhard Grünschloß, Matthias Raab, and Alexander Keller. 2012. Monte Carlo and Quasi-Monte Carlo Methods 2010. Springer Berlin Heidelberg, Chapter Enumerating Quasi-Monte Carlo Point Sequences in Elementary Intervals, 399--408.Google Scholar
- 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
- 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
- Alexander Keller. 2012. Quasi-Monte Carlo Image Synthesis in a Nutshell. Monte Carlo and Quasi-Monte Carlo Methods (2012), 213--252.Google Scholar
- Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, and Dani Lischinski. 2006. Recursive Wang Tiles for Real-time Blue Noise. ACM Trans. Graph. 25, 3 (2006), 509--518. Google ScholarDigital Library
- Ares Lagae and Philip Dutré. 2006. An Alternative for Wang Tiles: Colored Edges Versus Colored Corners. ACM Trans. Graph. 25, 4 (2006), 1442--1459. Google ScholarDigital Library
- Ares Lagae and Philip Dutré. 2008. A Comparison of Methods for Generating Poisson Disk Distributions. Computer Graphics Forum 27, 1 (2008), 114--129. Google ScholarCross Ref
- S. Lloyd. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2 (1982), 129--137. Google ScholarDigital Library
- M. Lothaire. 2002. Algebraic Combinatorics on Words. Cambridge University Press. https://books.google.de/books?id=JcJniBQ2dD4C Google ScholarCross Ref
- 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
- Victor Ostromoukhov. 2007. Sampling with Polyominoes. ACM Trans. Graph. 26, 3 (2007), 78:1--78:6.Google ScholarDigital Library
- Victor Ostromoukhov, Charles Donohue, and Pierre-Marc Jodoin. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Trans. Graph. 23, 3 (2004), 488--495. Google ScholarDigital Library
- A. Cengiz Öztireli. 2016. Integration with Stochastic Point Processes. ACM Trans. Graph. 35, 5, Article 160 (Aug. 2016), 16 pages. Google ScholarDigital Library
- A. Cengiz Öztireli and Markus Gross. 2012. Analysis and Synthesis of Point Distributions Based on Pair Correlation. ACM Trans. Graph. 31, 6, Article 170 (2012), 10 pages. Google ScholarDigital Library
- Matt Pharr and Greg Humphreys. 2010. Physically Based Rendering, Second Edition: From Theory To Implementation (2nd ed.). Morgan Kaufmann Publishers Inc.Google Scholar
- 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
- Ravi Ramamoorthi, John Anderson, Mark Meyer, and Derek Nowrouzezahrai. 2012. A Theory of Monte Carlo Visibility Sampling. ACM Trans. Graph. 31, 5, Article 121 (2012), 16 pages. Google ScholarDigital Library
- Yuki Saka, Max Gunzburger, and John Burkardt. 2007. Latinized, improved LHS, and CVT point sets in hypercubes. International Journal of Numerical Analysis and Modeling 4, 3--4 (2007), 729--743.Google Scholar
- 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. 135--142. Google ScholarDigital Library
- Adrian Secord. 2002. Weighted Voronoi Stippling. In Proceedings of the 2Nd International Symposium on Non-photorealistic Animation and Rendering (NPAR '02). 37--43. Google ScholarDigital Library
- Kartic Subr and Jan Kautz. 2013. Fourier Analysis of Stochastic Sampling Strategies for Assessing Bias and Variance in Integration. ACM Trans. Graph. 32, 4, Article 128 (2013), 12 pages. Google ScholarDigital Library
- Robert Ulichney. 1987. Digital Halftoning. MIT Press, Cambridge, MA, USA.Google Scholar
- R.A. Ulichney. 1988. Dithering with Blue Noise. Proc. IEEE 76, 1 (1988), 56--79. Google ScholarCross Ref
- 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
- 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
- Li-Yi Wei. 2010. Multi-class Blue Noise Sampling. ACM Trans. Graph. 29, 4 (2010), 79:1--79:8.Google ScholarDigital Library
- Dong-Ming Yan, Bruno Lévy, Yang Liu, Feng Sun, and Wenping Wang. 2009. Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram. Computer Graphics Forum 28, 5 (2009), 1445--1454. Google ScholarCross Ref
- Yahan Zhou, Haibin Huang, Li-Yi Wei, and Rui Wang. 2012. Point Sampling with General Noise Spectrum. ACM Trans. Graph. 31, 4, Article 76 (2012), 11 pages. Google ScholarDigital Library
Index Terms
- An adaptive point sampler on a regular lattice
Recommendations
Screen-space blue-noise diffusion of monte carlo sampling error via hierarchical ordering of pixels
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-...
Blue-noise dithered sampling
SIGGRAPH '16: ACM SIGGRAPH 2016 TalksThe 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 ...
Line segment sampling with blue-noise properties
Line segment sampling has recently been adopted in many rendering algorithms for better handling of a wide range of effects such as motion blur, defocus blur and scattering media. A question naturally raised is how to generate line segment samples with ...
Comments