“Optimizing dyadic nets” by Ahmed and Wonka

We explore the space of (0, m, 2)-nets in base 2 commonly used for sampling. We present a novel constructive algorithm that can exhaustively generate all nets — up to m-bit resolution — and thereby compute the exact number of distinct nets. We observe that the construction algorithm holds the key to defining a transformation operation that lets us transform one valid net into another one. This enables the optimization of digital nets using arbitrary objective functions. For example, we define an analytic energy function for blue noise, and use it to generate nets with high-quality blue-noise frequency power spectra. We also show that the space of (0, 2)-sequences is significantly smaller than nets with the same number of points, which drastically limits the optimizability of sequences.

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, 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
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. Abdalla G. M. Ahmed and Peter Wonka. 2020. Screen-Space Blue-Noise Diffusion of Monte Carlo Sampling Error via Hierarchical Ordering of Pixels. ACM Trans. Graph. 39, 6, Article 244 (Nov. 2020), 15 pages. Google ScholarDigital Library
5. I.A. Antonov and V.M. Saleev. 1979. An Economic Method of Computing LP-sequences. U. S. S. R. Comput. Math. and Math. Phys. 19, 1 (1979), 252–256. Google ScholarCross Ref
6. 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
7. R. Bridson. 2007. Fast Poisson-Disk Sampling in Arbitrary Dimensions. In ACM SIGGRAPH 2007 Sketches.Google Scholar
8. Brent Burley. 2020. Practical Hash-Based Owen Scrambling. Journal of Computer Graphics Techniques (JCGT) 10, 4 (29 December 2020), 1–20. http://jcgt.org/published/0009/04/01/Google Scholar
9. 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
10. 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
11. David Coeurjolly and Hélène Perrier. 2019. Uni(corn|form) Tool Kit. https://utkteam.github.io/utk/, as of 2021-01-27.Google Scholar
12. Robert L. Cook. 1986. Stochastic Sampling in Computer Graphics. ACM Trans. Graph. 5, 1 (Jan. 1986), 51–72. Google ScholarDigital Library
13. 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
14. Josef Dick and Friedrich Pillichshammer. 2010. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press. Google ScholarCross Ref
15. 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, 69–78. Google ScholarDigital Library
16. 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
17. Fredo Durand. 2011. A Frequency Analysis of Monte Carlo and Other Numerical Integration Schemes. MIT CSAIL Tech. Rep. TR-2011-052 (2011).Google Scholar
18. 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
19. 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
20. 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
21. 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
22. Raanan Fattal. 2011. Blue-Noise Point Sampling Using Kernel Density Model. In ACM SIGGRAPH 2011 Papers (Vancouver, British Columbia, Canada) (SIGGRAPH ’11). ACM, Article 48, 12 pages. Google ScholarDigital Library
23. Henri Faure and Shu Tezuka. 2002. Another Random Scrambling of Digital (t,s)-Sequences. In Monte Carlo and Quasi-Monte Carlo Methods 2000, Kai-Tai Fang, Harald Niederreiter, and Fred J. Hickernell (Eds.). Springer, 242–256.Google Scholar
24. 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
25. Iliyan Georgiev and Marcos Fajardo. 2016. Blue-Noise Dithered Sampling. In ACM SIGGRAPH 2016 Talks. 1–1.Google Scholar
26. 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
27. Leonhard Grünschloß, Johannes Hanika, Ronnie Schwede, and Alexander Keller. 2008. (t, m, s)-Nets and Maximized Minimum Distance. In Monte Carlo and Quasi-Monte Carlo Methods 2006, Alexander Keller, Stefan Heinrich, and Harald Niederreiter (Eds.). Springer, 397–412.Google Scholar
28. Leonhard Grünschloß and Alexander Keller. 2009. (t, m, s)-Nets and Maximized Minimum Distance, Part II. In Monte Carlo and Quasi-Monte Carlo Methods 2008. Springer, 395–409.Google Scholar
29. 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, 399–408.Google Scholar
30. Kenneth M. Hanson. 2003. Quasi-Monte Carlo: Halftoning in High Dimensions?. In Computational Imaging, Charles A. Bouman and Robert L. Stevenson (Eds.), Vol. 5016. International Society for Optics and Photonics, SPIE, 161 — 172. Google ScholarCross Ref
31. Kenneth M Hanson. 2005. Halftoning and Quasi-Monte Carlo. Los Alamos National Library (2005), 430–442.Google Scholar
32. 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
33. 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
34. 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 (Los Angeles, California) (SIGGRAPH ’19). Association for Computing Machinery, Article 68, 2 pages. Google ScholarDigital Library
35. Andrew Helmer. 2020. A C++ implementation of Progressive Multi-Jittered Sample Sequences. https://github.com/Andrew-Helmer/pmj-cpp/tree/master/sample_sequences, as of 2021-04-23.Google Scholar
36. 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
37. 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
38. 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
39. Alexander Keller. 2006. Myths of Computer Graphics. In Monte Carlo and Quasi-Monte Carlo Methods 2004. Springer, 217–243.Google Scholar
40. 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, 213–249.Google Scholar
41. Alexander Keller, Iliyan Georgiev, Abdalla Ahmed, Per Christensen, and Matt Pharr. 2019. My Favorite Samples. In ACM SIGGRAPH 2019 Courses (Los Angeles, California) (SIGGRAPH ’19). Association for Computing Machinery, Article 15, 271 pages. Google ScholarDigital Library
42. Andrew Kensler. 2013. Correlated Multi-Jittered Sampling. Pixar Technical Memo 13-01 7 (2013), 86–112.Google Scholar
43. Thomas Kollig and Alexander Keller. 2002. Efficient Multidimensional Sampling. In Computer Graphics Forum, Vol. 21. 557–563.Google ScholarCross Ref
44. Lauwerens Kuipers and Harald Niederreiter. 1974. Uniform Distribution of Sequences. John Wiley & Sons. http://opac.inria.fr/record=b1083239 A Wiley-Interscience publication.Google Scholar
45. Ares Lagae and Philip Dutré. 2008. A Comparison of Methods for Generating Poisson-Disk Distributions. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 114–129.Google Scholar
46. G Larcher and F Pillichshammer. 2003. Sums of Distances to the Nearest Integer and the Discrepancy of Digital Nets. Acta Arithmetica 106 (2003), 379–408.Google ScholarCross Ref
47. Michael McCool and Eugene Fiume. 1992. Hierarchical Poisson-Disk Sampling Distributions. In Proceedings of the Conference on Graphics Interface ’92 (Vancouver, British Columbia, Canada). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 94–105. http://dl.acm.org/citation.cfm?id=155294.155306Google ScholarDigital Library
48. Don P. Mitchell. 1991. Spectrally Optimal Sampling for Distribution Ray Tracing. SIGGRAPH Comput. Graph. 25, 4 (July 1991), 157–164. Google ScholarDigital Library
49. Don P Mitchell. 1992. Ray Tracing and Irregularities of Distribution. In Third Eurographics Workshop on Rendering. 61–69.Google Scholar
50. 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 22 (May 2018), 20 pages. Google ScholarDigital Library
51. Harald Niederreiter. 1987. Point Sets and Sequences with Small Discrepancy. Monatshefte für Mathematik 104, 4 (1987), 273–337.Google ScholarCross Ref
52. Harald Niederreiter. 1988. Low-Discrepancy and Low-Dispersion Sequences. Journal of Number Theory 30, 1 (1988), 51 — 70. Google ScholarCross Ref
53. Harald Niederreiter. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM.Google Scholar
54. Harald Niederreiter. 2005. Constructions of (t,m,s)-Nets and (t,s)-Sequences. Finite Fields and Their Applications 11, 3 (2005), 578–600. Ten Year Anniversary Edition! Google ScholarDigital Library
55. 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, 299–317.Google Scholar
56. Art B. Owen. 1998. Scrambling Sobol’and Niederreiter-Xing Points. Journal of Complexity 14, 4 (1998), 466–489.Google ScholarDigital Library
57. Art B. Owen. 2003. Variance with Alternative Scramblings of Digital Nets. ACM Trans. Model. Comput. Simul. 13, 4 (Oct. 2003), 363–378. Google ScholarDigital Library
58. A. Cengiz Öztireli. 2016. Integration with Stochastic Point Processes. ACM Trans. Graph. 35, 5, Article 160 (Aug. 2016), 16 pages. Google ScholarDigital Library
59. 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
60. A. Cengiz Öztireli, Marc Alexa, and Markus Gross. 2010. Spectral Sampling of Manifolds. ACM Transactions on Graphics (TOG) 29, 6 (2010), 1–8.Google ScholarDigital Library
61. 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
62. 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
63. Matt Pharr. 2019. Efficient Generation of Points that Satisfy Two-Dimensional Elementary Intervals. Journal of Computer Graphics Techniques (JCGT) 8, 1 (27 February 2019), 56–68. http://jcgt.org/published/0008/01/04/Google Scholar
64. 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
65. 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
66. 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
67. 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
68. 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
69. 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 (Vancouver, British Columbia, Canada) (HPG ’11). ACM, 135–142. Google ScholarDigital Library
70. 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
71. Claude E Shannon. 1948. A Mathematical Theory of Communication. The Bell System Technical Journal 27, 3 (1948), 379–423.Google ScholarCross Ref
72. Peter Shirley. 1991. Discrepancy as a Quality Measure for Sample Distributions. In Proc. Eurographics ’91, Vol. 91. 183–194.Google Scholar
73. Il’ya Meerovich Sobol’. 1967. On the Distribution of Points in a Cube and the Approximate Evaluation of Integrals. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 7, 4 (1967), 784–802.Google Scholar
74. Sergej Stoppel and Stefan Bruckner. 2019. LinesLab: A Flexible Low-Cost Approach for the Generation of Physical Monochrome Art. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 110–124.Google Scholar
75. 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
76. Robert Ulichney. 1987. Digital Halftoning. MIT Press, Cambridge, MA, USA.Google ScholarDigital Library
77. R.A. Ulichney. 1988. Dithering with Blue Noise. Proc. IEEE 76, 1 (Jan 1988), 56–79. Google ScholarCross Ref
78. 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
79. J.G. van der Corput. 1935. Verteilungsfunktionen. Proceedings of the Nederlandse Akademie van Wetenschappen 38 (1935), 813–821.Google Scholar
80. Li-Yi Wei. 2010. Multi-Class Blue-Noise Sampling. ACM Trans. Graph. 29, 4, Article 79 (July 2010), 8 pages. Google ScholarDigital Library
81. SK Zaremba. 1968. The Mathematical Basis of Monte Carlo and Quasi-Monte Carlo Methods. SIAM review 10, 3 (1968), 303–314.Google Scholar
82. 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