“An adaptive point sampler on a regular lattice” by Ahmed, Niese, Huang and Deussen
Conference:
Type(s):
Title:
- An adaptive point sampler on a regular lattice
Session/Category Title: Random Sampling
Presenter(s)/Author(s):
Moderator(s):
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.
References:
1. 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
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 (2015), 8 pages. Google ScholarDigital Library
3. 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
4. Jean-Paul Allouche and Jeffrey Shallit. 1999. The ubiquitous prouhet-thue-morse sequence. In Sequences and their applications. Springer, 1–16. Google ScholarCross Ref
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 (2009), 86:1–8.Google ScholarDigital Library
6. 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
7. 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
8. 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
9. Robert L. Cook. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1 (1986), 51–72. Google ScholarDigital Library
10. 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
11. 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
12. Fredo Durand. 2011. A Frequency Analysis of Monte Carlo and Other Numerical Integration Schemes. MIT CSAIL Tech. rep. TR-2011–052 (2011).Google Scholar
13. Raanan Fattal. 2011. Blue-noise point sampling using kernel density model. ACM Trans. Graph. 30, 3 (2011), 48:1–48:12.Google ScholarDigital Library
14. Andrew S Glassner. 1995. Principles of digital image synthesis. Vol. 1. Elsevier.Google Scholar
15. 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
16. 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
17. 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
18. Alexander Keller. 2012. Quasi-Monte Carlo Image Synthesis in a Nutshell. Monte Carlo and Quasi-Monte Carlo Methods (2012), 213–252.Google Scholar
19. 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
20. 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
21. 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
22. S. Lloyd. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2 (1982), 129–137. Google ScholarDigital Library
23. M. Lothaire. 2002. Algebraic Combinatorics on Words. Cambridge University Press. https://books.google.de/books?id=JcJniBQ2dD4C Google ScholarCross Ref
24. 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
25. Victor Ostromoukhov. 2007. Sampling with Polyominoes. ACM Trans. Graph. 26, 3 (2007), 78:1–78:6.Google ScholarDigital Library
26. 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
27. A. Cengiz Öztireli. 2016. Integration with Stochastic Point Processes. ACM Trans. Graph. 35, 5, Article 160 (Aug. 2016), 16 pages. Google ScholarDigital Library
28. 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
29. Matt Pharr and Greg Humphreys. 2010. Physically Based Rendering, Second Edition: From Theory To Implementation (2nd ed.). Morgan Kaufmann Publishers Inc.Google Scholar
30. 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
31. 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
32. 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
33. 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
34. 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
35. 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
36. Robert Ulichney. 1987. Digital Halftoning. MIT Press, Cambridge, MA, USA.Google Scholar
37. R.A. Ulichney. 1988. Dithering with Blue Noise. Proc. IEEE 76, 1 (1988), 56–79. Google ScholarCross Ref
38. 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
39. 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
40. Li-Yi Wei. 2010. Multi-class Blue Noise Sampling. ACM Trans. Graph. 29, 4 (2010), 79:1–79:8.Google ScholarDigital Library
41. 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
42. 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
