“Multi-class blue noise sampling” by Wei

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 on blue noise sampling with a single class of samples. This could be insufficient for common natural as well as man-made phenomena requiring multiple classes of samples, such as object placement, imaging sensors, and stippling patterns.We extend blue noise sampling to multiple classes where each individual class as well as their unions exhibit blue noise characteristics. We propose two flavors of algorithms to generate such multi-class blue noise samples, one extended from traditional Poisson hard disk sampling for explicit control of sample spacing, and another based on our soft disk sampling for explicit control of sample count. Our algorithms support uniform and adaptive sampling, and are applicable to both discrete and continuous sample space in arbitrary dimensions. We study characteristics of samples generated by our methods, and demonstrate applications in object placement, sensor layout, and color stippling.

1. Alliez, P., de Verdière, É. C., Devillers, O., and Isenburg, M. 2003. Isotropic surface remeshing. In Shape Modeling International, 49–58. Google ScholarDigital Library
2. Balzer, M., Schlömer, T., and Deussen, O. 2009. Capacity-constrained point distributions: A variant of Lloyd’s method. In SIGGRAPH ’09, 86:1–8. Google ScholarDigital Library
3. Baqai, F., Lee, J.-H., Agar, A., and Allebach, J. 2005. Digital color halftoning. Signal Processing Magazine, IEEE 22, 1 (Jan.), 87–96.Google ScholarCross Ref
4. Ben Ezra, M., Lin, Z., and Wilburn, B. 2007. Penrose pixels super-resolution in the detector layout domain. In ICCV ’07, 1–8.Google Scholar
5. Bridson, R. 2007. Fast Poisson disk sampling in arbitrary dimensions. In SIGGRAPH ’07 Sketches & Applications. Google ScholarDigital Library
6. Cline, D., Jeschke, S., Razdan, A., White, K., and Wonka, P. 2009. Dart throwing on surfaces. In EGSR ’09, 1217–1226. Google ScholarDigital Library
7. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. In SIGGRAPH ’03, 287–294. Google ScholarDigital Library
8. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51–72. Google ScholarDigital Library
9. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast Poisson-disk sample generation. In SIGGRAPH ’06, 503–508. Google ScholarDigital Library
10. Fu, Y., and Zhou, B. 2008. Direct sampling on surfaces for high quality remeshing. In SPM ’08, 115–124. Google ScholarDigital Library
11. Jones, T. R. 2006. Efficient generation of Poisson-disk sampling patterns. journal of graphics tools 11, 2, 27–36.Google Scholar
12. Kim, D., Son, M., Lee, Y., Kang, H., and Lee, S. 2008. Feature-guided image stippling. Computer Graphics Forum 27, 4, 1209–1216.Google ScholarDigital Library
13. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive Wang tiles for real-time blue noise. In SIGGRAPH ’06, 509–518. Google ScholarDigital Library
14. Lagae, A., and Dutré, P. 2005. A procedural object distribution function. ACM Trans. Graph. 24, 4, 1442–1461. Google ScholarDigital Library
15. Lagae, A., and Dutré, P. 2006. An alternative for Wang tiles: colored edges versus colored corners. ACM Trans. Graph. 25, 4, 1442–1459. Google ScholarDigital Library
16. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 21, 1, 114–129.Google ScholarCross Ref
17. Lloyd, S. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2, 129–137.Google ScholarDigital Library
18. McClure, M. 2002. A stochastic cellular automaton for three-coloring penrose tiles. Computers & Graphics 26, 3, 519–524.Google Scholar
19. McCool, M., and Fiume, E. 1992. Hierarchical Poisson disk sampling distributions. In Graphics Interface ’92, 94–105. Google ScholarDigital Library
20. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In SIGGRAPH ’87, 65–72. Google ScholarDigital Library
21. Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. SIGGRAPH Comput. Graph. 25, 4, 157–164. Google ScholarDigital Library
22. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. In SIGGRAPH ’04, 488–495. Google ScholarDigital Library
23. Ostromoukhov, V. 2007. Sampling with polyominoes. In SIGGRAPH ’07, 78:1–6. Google ScholarDigital Library
24. Pang, W.-M., Qu, Y., Wong, T.-T., Cohen-Or, D., and Heng, P.-A. 2008. Structure-aware halftoning. In SIGGRAPH ’08, 89:1–8. Google ScholarDigital Library
25. Turk, G. 1992. Re-tiling polygonal surfaces. In SIGGRAPH ’92, 55–64. Google ScholarDigital Library
26. Wang, M., and Parker, K. 1999. Properties of combined blue noise patterns. ICIP 4, 328–332.Google Scholar
27. Wei, L.-Y. 2008. Parallel Poisson disk sampling. In SIGGRAPH ’08, 20:1–9. Google ScholarDigital Library
28. White, K., Cline, D., and Egbert, P. 2007. Poisson disk point sets by hierarchical dart throwing. In Symposium on Interactive Ray Tracing, 129–132. Google ScholarDigital Library
29. Yellott, J. I. J. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. Science 221, 382–385.Google ScholarCross Ref