“A spatial data structure for fast Poisson-disk sample generation” by Dunbar and Humphreys

  • ©Daniel Dunbar and Greg Humphreys




    A spatial data structure for fast Poisson-disk sample generation



    Sampling distributions with blue noise characteristics are widely used in computer graphics. Although Poisson-disk distributions are known to have excellent blue noise characteristics, they are generally regarded as too computationally expensive to generate in real time. We present a new method for sampling by dart-throwing in O(N log N) time and introduce a novel and efficient variation for generating Poisson-disk distributions in O(N) time and space.


    1. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Transactions on Graphics 22, 3, 287–294. Google ScholarDigital Library
    2. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Transactions on Graphics 5, 1, 51–72. Google ScholarDigital Library
    3. Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In Computer Graphics (Proceedings of SIGGRAPH 85), ACM Press, New York, NY, USA, 69–78. Google ScholarDigital Library
    4. Dunbar, D., and Humphreys, G. 2006. Using scalloped sectors to generate poisson-disk sampling patterns. Tech. Rep. CS-2006-08, University of Virginia.Google Scholar
    5. Hiller, S., Deussen, O., and Kaufmann, A. 2001. Tiled blue noise samples. In VMV ’01: Proceedings of the Vision Modeling and Visualization Conference 2001, Aka GmbH, 265–272. Google ScholarDigital Library
    6. Jones, T. 2006. Efficient generation of poisson-disk sampling patterns. Journal of Graphics Tools, to appear.Google ScholarCross Ref
    7. Kollig, T., and Keller, A. 2002. Efficient multidimensional sampling. Computer Graphics Forum 21, 3, 557–563.Google ScholarCross Ref
    8. Kollig, T., and Keller, A. 2003. Efficient illumination by high dynamic range images. Rendering Techniques, 45–51. Google ScholarDigital Library
    9. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. ACM Transactions on Graphics 25, 3. Google ScholarDigital Library
    10. Lagae, A., and Dutré, P. 2005. A procedural object distribution function. ACM Transactions on Graphics 24, 4, 1442–1461. Google ScholarDigital Library
    11. 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. Google ScholarDigital Library
    12. Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. In Computer Graphics (Proceedings of ACM SIGGRAPH 91), ACM Press, New York, NY, USA, 157–164. Google ScholarDigital Library
    13. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Transactions on Graphics 23, 3, 488–495. Google ScholarDigital Library
    14. Shirley, P. 1991. Discrepancy as a quality measure for sample distributions. In Proceedings of Eurographics, 183–194.Google Scholar
    15. Ulichney, R. A. 1988. Dithering with blue noise. In Proc. of the IEEE 76, 56–79.Google ScholarCross Ref
    16. Yellot, J. I. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. Science 221, 382–385.Google ScholarCross Ref

ACM Digital Library Publication:

Overview Page: