“AA patterns for point sets with controlled spectral properties” by Ahmed, Huang and Deussen
Conference:
Type(s):
Title:
- AA patterns for point sets with controlled spectral properties
Session/Category Title: Sampling and Light Transport
Presenter(s)/Author(s):
Abstract:
We describe a novel technique for the fast production of large point sets with different spectral properties. In contrast to tile-based methods we use so-called AA Patterns: ornamental point sets obtained from quantization errors. These patterns have a discrete and structured number-theoretic nature, can be produced at very low costs, and possess an inherent structural indexing mechanism equivalent to those used in recursive tiling techniques. This allows us to generate, manipulate and store point sets very efficiently. The technique outperforms existing methods in speed, memory footprint, quality, and flexibility. This is demonstrated by a number of measurements and comparisons to existing point generation algorithms.
References:
1. Ahmed, A. G. M. 2011. AA Patterns. In EG 2011 – Posters, Eurographics Association, Llandudno, UK, 35–36. Accessible online at http://diglib.eg.org/EG/DL/conf/EG2011/posters/035-036.pdf.
2. Ahmed, A. G. M. 2011. Mathematical Hints for Parameter Selection for AA Patterns. In Bridges Coimbra, The Bridges Organization, 271–278.
3. Ahmed, A. G. M. 2011. Pixel Patterns from Quantization Artifacts of Forward Affine Mapping. Journal of Graphics, GPU, and Game Tools 15, 2, 73–94.
4. Ahmed, A. G. M. 2012. On the Fractal Behaviour of AA Patterns. In Theory and Practice of Computer Graphics, Eurographics Association, Rutherford, United Kingdom, Hamish Carr and Silvester Czanner, Ed., 93–97.
5. Balzer, M., Schlömer, T., and Deussen, O. 2009. Capacity-constrained point distributions: A variant of lloyd’s method. In ACM SIGGRAPH 2009 Papers, ACM, New York, NY, USA, SIGGRAPH ’09, 86:1–86:8.
6. Chen, Z., Yuan, Z., Choi, Y.-K., Liu, L., and Wang, W. 2012. Variational blue noise sampling. IEEE Transactions on Visualization and Computer Graphics 18, 10 (Oct.), 1784–1796.
7. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. In ACM SIGGRAPH 2003 Papers, ACM, New York, NY, USA, SIGGRAPH ’03, 287–294.
8. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1 (Jan.), 51–72.
9. de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6 (Nov.), 171:1–171:11.
10. Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’85, 69–78.
11. Fattal, R. 2011. Blue-noise point sampling using kernel density model. In ACM SIGGRAPH 2011 Papers, ACM, New York, NY, USA, SIGGRAPH ’11, 48:1–48:12.
12. Heck, D., Schlömer, T., and Deussen, O. 2013. Blue noise sampling with controlled aliasing. ACM Trans. Graph. 32, 3 (July), 25:1–25:12.
13. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. ACM Trans. Graph. 25, 3 (July), 509–518.
14. Kuipers, L., and Niederreiter, H. 1974. Uniform distribution of sequences. Pure and applied mathematics. John Wiley & Sons, New York. A Wiley-Interscience publication.
15. Lagae, A., and Dutré, P. 2006. An alternative for wang tiles: Colored edges versus colored corners. ACM Trans. Graph. 25, 4 (Oct.), 1442–1459.
16. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating poisson disk distributions. In Computer Graphics Forum, vol. 27, Wiley Online Library, 114–129.
17. McCool, M., and Fiume, E. 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.
18. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’87, 65–72.
19. Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM.
20. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. In ACM SIGGRAPH 2004 Papers, ACM, New York, NY, USA, SIGGRAPH ’04, 488–495.
21. Ostromoukhov, V. 2007. Sampling with polyominoes. ACM Trans. Graph. 26, 3 (July).
22. Öztireli, A. C., and Gross, M. 2012. Analysis and synthesis of point distributions based on pair correlation. ACM Trans. Graph. 31, 6 (Nov.), 170:1–170:10.
23. Schlömer, T., and Deussen, O. 2010. Semi-stochastic tilings for example-based texture synthesis. In Proceedings of the 21st Eurographics Conference on Rendering, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, EGSR’10, 1431–1439.
24. Schlömer, T., Heck, D., and Deussen, O. 2011. Farthest-point optimized point sets with maximized minimum distance. In Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, ACM, New York, NY, USA, HPG ’11, 135–142.
25. Schmaltz, C., Gwosdek, P., Bruhn, A., and Weickert, J. 2010. Electrostatic halftoning. Computer Graphics Forum 29, 8, 2313–2327.
26. Ulichney, R. 1988. Dithering with blue noise. Proceedings of the IEEE 76, 1 (Jan), 56–79.
27. Wachtel, F., Pilleboue, A., Coeurjolly, D., Breeden, K., Singh, G., Cathelin, G., de Goes, F., Desbrun, M., and Ostromoukhov, V. 2014. Fast tile-based adaptive sampling with user-specified fourier spectra. ACM Trans. Graph. 33, 4 (July), 56:1–56:11.
28. Xu, Y., Liu, L., Gotsman, C., and Gortler, S. J. 2011. Capacity-constrained delaunay triangulation for point distributions. Computers & Graphics 35, 3, 510–516. Shape Modeling International (SMI) Conference 2011.
29. Zhou, Y., Huang, H., Wei, L.-Y., and Wang, R. 2012. Point sampling with general noise spectrum. ACM Trans. Graph. 31, 4 (July), 76:1–76:11.
