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

  • ©Raanan Fattal




    Blue-noise point sampling using kernel density model



    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

ACM Digital Library Publication: