“Blue-noise point sampling using kernel density model” by Fattal

Stochastic point distributions with blue-noise spectrum are used extensively in computer graphics for various applications such as avoiding aliasing artifacts in ray tracing, halftoning, stippling, etc. In this paper we present a new approach for generating point sets with high-quality blue noise properties that formulates the problem using a statistical mechanics interacting particle model. Points distributions are generated by sampling this model. This new formulation of the problem unifies randomness with the requirement for equidistant point spacing, responsible for the enhanced blue noise spectral properties. We derive a highly efficient multi-scale sampling scheme for drawing random point distributions from this model. The new scheme avoids the critical slowing down phenomena that plagues this type of models. This derivation is accompanied by a model-specific analysis.Altogether, our approach generates high-quality point distributions, supports spatially-varying spatial point density, and runs in time that is linear in the number of points generated.

1. 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, 86:1–86:8. Google Scholar
2. Besag, J. 1994. Discussion: Markov chains for exploring posterior distributions. Annals of Statistics 2, 4, 1734–1741.Google ScholarCross Ref
3. Binney, J., Dowrick, N., Fisher, A., and Newman, M. 1986. The Theory of Critical Phenomena. Clarendon Press, Oxford. Google Scholar
4. Bowers, J., Wang, R., Wei, L.-Y., and Maletz, D. 2010. Parallel poisson disk sampling with spectrum analysis on surfaces. In ACM SIGGRAPH Asia 2010 papers, ACM, New York, NY, USA, 166:1–166:10. Google Scholar
5. 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, 287–294. Google Scholar
6. Cook, R. L., Porter, T., and Carpenter, L. 1984. Distributed ray tracing. In ACM SIGGRAPH 1984 papers, ACM, New York, NY, USA, 137–145. Google Scholar
7. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5 (January), 51–72. Google ScholarDigital Library
8. Deussen, O., Hanrahan, P., Lintermann, B., Měch, R., Pharr, M., and Prusinkiewicz, P. 1998. Realistic modeling and rendering of plant ecosystems. In ACM SIGGRAPH 1998 papers, ACM, New York, NY, USA, 275–286. Google Scholar
9. Deussen, O., Hiller, S., van Overveld, C., and Strothotte, T. 2000. Floating points: A method for computing stipple drawings. Computer Graphics Forum 19, 40–51.Google ScholarCross Ref
10. Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In ACM SIGGRAPH 1985 Papers, ACM, New York, NY, USA, 69–78. Google Scholar
11. Dress, C., and Krauth, W. 1995. Cluster algorithm for hard spheres and related systems. Journal of Physics A: Mathematical and General 28, 23.Google ScholarCross Ref
12. Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal voronoi tessellations: Applications and algorithms. SIAM Review 41, 4, 637–676. Google ScholarDigital Library
13. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast poisson-disk sample generation. In ACM SIGGRAPH 2006 Papers, ACM, New York, NY, USA, SIGGRAPH ’06, 503–508. Google Scholar
14. Floyd, R. W., and Steinberg, L. 1976. An Adaptive Algorithm for Spatial Greyscale. Proceedings of the Society for Information Display 17, 2, 75–77.Google Scholar
15. Gamito, M. N., and Maddock, S. C. 2009. Accurate multidimensional poisson-disk sampling. ACM Trans. Graph. 29 (December), 8:1–8:19. Google ScholarDigital Library
16. Goodman, J., and Sokal, A. D. 1989. Multigrid monte carlo method. conceptual foundations. Phys. Rev. D 40, 6 (Sep), 2035–2071.Google ScholarCross Ref
17. Grenander, U., and Miller, M. I. 1994. Representations of knowledge in complex systems. Journal of the Royal Statistical Society. Series B (Methodological) 56, 4, 549–603.Google ScholarCross Ref
18. Hiller, S., Deussen, O., and Keller, A. 2001. Tiled blue noise samples. In Proc. of Vision Modeling and Visualization, Aka GmbH, 265–272. Google ScholarDigital Library
19. Jones, T. R. 2006. Efficient generation of poisson-disk sampling patterns. Graphics, Fpu, and Game Tools 11, 2, 27–36.Google ScholarCross Ref
20. Kollig, T., and Keller, A. 2003. Efficient illumination by high dynamic range images. In Proc. of Eurographics workshop on Rendering, Eurographics Association, Aire-la-Ville, Switzerland, 45–50. Google ScholarDigital Library
21. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. In ACM SIGGRAPH 2006 Papers, ACM, New York, NY, USA, 509–518. Google Scholar
22. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating poisson disk distributions. Computer Graphics Forum 27, 1 (March), 114–129.Google ScholarCross Ref
23. Landau, D., and Binder, K. 2005. A Guide to Monte Carlo Simulations in Statistical Physics. Cambridge University Press, New York, NY, USA. Google Scholar
24. Li, H., Nehab, D., Wei, L.-Y., Sander, P., and Fu, C.-W. 2009. Fast capacity constrained voronoi tessellation. Microsoft Research, no. MSR-TR-2009-174.Google Scholar
25. Li, H., Wei, L.-Y., Sander, P. V., and Fu, C.-W. 2010. Anisotropic blue noise sampling. In ACM SIGGRAPH Asia 2010 papers, ACM, New York, NY, USA, 167:1–167:12. Google Scholar
26. Liu, J., and Luijten, E. 2004. Rejection-free geometric cluster algorithm for complex fluids. Phys. Rev. Lett. 92, 3 (Jan), 035504.Google ScholarCross Ref
27. Lloyd, S. 1982. Least squares quantization in pcm. Information Theory, IEEE Transactions on 28, 2, 129–137.Google ScholarDigital Library
28. McCool, M., and Fiume, E. 1992. Hierarchical poisson disk sampling distributions. In Proc. of Graphics interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 94–105. Google ScholarDigital Library
29. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In ACM SIGGRAPH 1987 Papers, ACM, New York, NY, USA, 65–72. Google Scholar
30. Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. 157–164.Google Scholar
31. 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, 488–495. Google Scholar
32. Öztireli, A. C., Alexa, M., and Gross, M. 2010. Spectral sampling of manifolds. In ACM SIGGRAPH Asia 2010 papers, ACM, New York, NY, USA, SIGGRAPH ASIA ’10, 168:1–168:8. Google Scholar
33. Robert, C. P., and Casella, G. 2005. Monte Carlo Statistical Methods (Springer Texts in Statistics). Springer-Verlag New York, Inc., Secaucus, NJ, USA. Google Scholar
34. Roberts, G. O., and Rosenthal, J. S. 1998. Optimal scaling of discrete approximations to langevin diffusions. Journal of the Royal Statistical Society. Series B (Statistical Methodology) 60, 1, 255–268.Google ScholarCross Ref
35. Schmaltz, C., Gwosdek, P., Bruhn, A., and Weickert, J. 2010. Electrostatic halftoning. Computer Graphics Forum 29, 8, 2313–2327.Google ScholarCross Ref
36. Secord, A. 2002. Weighted voronoi stippling. In Proc. int. symposium on Non-photorealistic animation and rendering, ACM, New York, NY, USA, 37–43. Google Scholar
37. Shade, J., Cohen, M. F., and Mitchell, D. P. 2000. Tiling layered depth images. 231–242.Google Scholar
38. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proc. of ACM national conference, ACM, New York, NY, USA, 517–524. Google Scholar
39. Surazhsky, V., Alliez, P., and Gotsman, C. 2003. Isotropic remeshing of surfaces: a local parameterization approach. In Proc. of 12th Int. Meshing Roundtable, 215–224.Google Scholar
40. Trottenberg, U., Oosterlee, C. W., and Schuller, A. 2001. Multigrid. Accademic Press, London, UK. Google Scholar
41. Wei, L.-Y. 2008. Parallel poisson disk sampling. In ACM SIGGRAPH 2008 papers, ACM, New York, NY, USA, 20:1–20:9. Google Scholar
42. Wei, L.-Y. 2010. Multi-class blue noise sampling. In ACM SIGGRAPH 2010 papers, ACM, New York, NY, USA, 79:1–79:8. Google Scholar
43. White, K. B., Cline, D., and Egbert, P. K. 2007. Poisson disk point sets by hierarchical dart throwing. Symposium on Interactive Ray Tracing 0, 129–132. Google Scholar
44. Whitted, T. 1979. An improved illumination model for shaded display. ACM, New York, NY, USA, ACM SIGGRAPH 1979 papers, 14–. Google Scholar
45. Yellot, J. I. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. 382–385.Google Scholar