“Accurate Multidimensional Poisson-Disk Sampling” by Gamito and Maddock

  • ©Manuel Gamito and Steve C. Maddock

Conference:


Type:


Title:

    Accurate Multidimensional Poisson-Disk Sampling

Presenter(s)/Author(s):


Abstract:


    We present an accurate and efficient method to generate samples based on a Poisson-disk distribution. This type of distribution, because of its blue noise spectral properties, is useful for image sampling. It is also useful for multidimensional Monte Carlo integration and as part of a procedural object placement function. Our method extends trivially from 2D to 3D or to any higher dimensional space. We demonstrate results for up to four dimensions, which are likely to be the most useful for computer graphics applications. The method is accurate because it generates distributions with the same statistical properties of those generated with the brute-force dart-throwing algorithm, the archetype against which all other Poisson-disk sampling methods are compared. The method is efficient because it employs a spatial subdivision data structure that signals the regions of space where the insertion of new samples is allowed. The method has O(N log N) time and space complexity relative to the total number of samples. The method generates maximal distributions in which no further samples can be inserted at the completion of the algorithm. The method is only limited in the number of samples it can generate and the number of dimensions over which it can work by the available physical memory.

References:


    1. Arvo, J. 1990. A simple method for box-sphere intersection testing. In Graphics Gems, A. S. Glassner, Ed. Academic Press Professional, San Diego, CA, 335–339. 
    2. Baddeley, A. and Møller, J. 1989. Nearest-Neighbour Markov point processes and random sets. Int. Statist. Rev. 57, 2, 89–121.
    3. Bartlett, M. S. 1974. The statistical analysis of spatial pattern. Adv. App. Probab. 6, 2, 336–358.
    4. Bridson, R. 2007. Fast Poisson disk sampling in arbitrary dimensions. In ACM SIGGRAPH’07 Sketches and Applications. ACM Press, 22. 
    5. Cline, D., Jeschke, S., White, K., Razdan, A., and Wonka, P. 2009. Dart throwing on surfaces. Comput. Graph. Forum 28, 4, 1217–1226.
    6. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Trans. Graph. 22, 3, 287–294. 
    7. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51–72. 
    8. Deussen, O., Hanrahan, P., Lintermann, B., Mech, R., Pharr, M., and Prusinkiewicz, P. 1998. Realistic modelling and rendering of plant ecosystems. In Proceedings of the SIGGRAPH’98 Conference, M. Cohen, Ed. Vol. 22. ACM Press, 275–286. 
    9. Deussen, O., Hiller, S., van Overveld, C., and Strothotte, T. 2000. Floating points: A method for computing stipple drawings. Comput. Graph. Forum 19, 3, 40–51.
    10. Dickman, R., Wang, J.-S., and Jensen, I. 1991. Random sequential adsorption: Series and virial expansions. J. Chem. Phy. 94, 12, 8252–8257.
    11. Diggle, P. J., Besag, J., and Gleaves, J. T. 1976. Statistical analysis of spatial point patterns by means of distance methods. Biometrics 32, 3, 659–667.
    12. Dippé, M. A. Z. and Wold, E. H. 1985. Antialiasing through stochastic sampling. In Proceedings of the SIGGRAPH’85 Conference, B. A. Barsky, Ed. Vol. 19, 69–78. 
    13. Donev, A., Torquato, S., and Stillinger, F. H. 2005. Neighbor list collision-driven molecular dynamics simulation for nonspherical hard particles. I. Algorithmic details. J. Comput. Phys. 202, 2, 737–764. 
    14. Dunbar, D. and Humphreys, G. 2006. A spatial data structure for fast Poisson-disk sample generation. ACM Trans. Graph. 25, 3, 503–508. 
    15. Dutré, P., Bala, K., and Bekaert, P. 2006. Advanced Global Illumination, 2nd Ed. AK Peters Ltd, Wellesley, MA. 
    16. Feng, L., Hotz, I., Hamman, B., and Joy, K. I. 2008. Anisotropic noise samples. IEEE Trans. Visualiz. Comput. Graph. 14, 2, 342–354. 
    17. Fu, Y. and Zhou, B. 2008. Direct sampling on surfaces for high quality remeshing. In Proceedings of the ACM Symposium on Solid and Physical Modeling, E. Haines and M. McGuire, Eds. ACM Press, 115–124. 
    18. Glassner, A. S. 1995. Principles of Digital Image Synthesis. The Morgan Kaufmann Series in Computer Graphics. Morgan Kaufmann Publishers, San Francisco, CA. 
    19. Hachisuka, T., Jarosz, W., Weistroffer, R. P., Dale, K., Humphreys, G., Zwicker, M., and Jensen, H. W. 2008. Multi-Dimensional adaptive sampling and reconstruction for ray tracing. ACM Trans. Graph. 27, 3, 33:1–33:10. 
    20. Hiller, S., Deussen, O., and Keller, A. 2001. Tiled blue noise samples. In Vision, Modeling and Visualization 2001, B. Girod, G. Greiner, H. Niemann, and H.-P. Seidel, Eds. Akademische Verlagsgesellschaft Aka GmbH, Berlin, 256–272. 
    21. Jaeger, H. M. and Nagel, S. R. 1992. Physics of the granular state. Sci. 255, 5051, 1523–1531.
    22. Jones, T. R. 2006. Efficient generation of Poisson-disk sampling patterns. J. Graph. Tools 11, 2, 27–36.
    23. Kopf, J., Cohen-Or, D., Deussen, O., and Lichinsky, D. 2006. Recursive Wang tiles for real-time blue noise. ACM Trans. Graph. 25, 3, 509–518. 
    24. Lagae, A. and Dutré, P. 2005. A procedural object distribution function. ACM Trans. Graph. 24, 4, 1442–1461. 
    25. Lagae, A. and Dutré, P. 2006a. An alternative for Wang tiles: Colored edges versus colored corners. ACM Trans. Graph. 25, 4, 1442–1459. 
    26. Lagae, A. and Dutré, P. 2006b. Poisson sphere distributions. In Vision, Modeling and Visualization 2006, L. Kobbelt, T. Kuhlen, T. Aach, and R. Westermann, Eds. Akademische Verlagsgesellschaft Aka GmbH, Berlin, 373–379.
    27. Lagae, A. and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Comput. Graph. Forum 27, 1, 114–129.
    28. Larsson, T., Akenine-Möller, T., and Lengyel, E. 2007. On faster sphere-box overlap testing. J. Graph. Tools 12, 1, 3–8.
    29. Lehtinen, J., Zwicker, M., Turquin, E., Kontkanen, J., Durand, F., Sillion, F. X., and Aila, T. 2008. A meshless hierarchical representation for light transport. ACM Trans. Graph. 27, 3, 37. 
    30. Leneman, O. A. Z. 1966. Random sampling of random processes: Impulse processes. Inf. Control 9, 4, 347–363.
    31. Lewis, J.-P. 1989. Algorithms for solid noise synthesis. In Proceedings of the SIGGRAPH’89 Conference, J. Lane, Ed. Vol. 23. ACM Press, 263–270. 
    32. Li, H., Lo, K.-Y., Leung, M.-K., and Fu, C.-W. 2008. Dual Poisson-disk tiling: An efficient method for distributing features on arbitrary surfaces. IEEE Trans. Visualiz. Comput. Graph. 14, 5, 982–998. 
    33. Lloyd, S. P. 1982. Least squares quantization in PCM. IEEE Trans. Inf. Theory 28, 2, 129–137.
    34. Lubachevsky, B. D. and Stillinger, F. H. 1990. Geometric properties of random disk packings. J. Statist. Phys. 60, 5-6, 561–583.
    35. Lubachevsky, B. D., Stillinger, F. H., and Pinson, E. N. 1991. Disks vs. spheres: Contrasting properties of random packings. J. Statist. Phys. 64, 3-4, 501–524.
    36. Matérn, B. 1960. Spatial variation. Meddelanden från Statens Skogsforskningsinstitut 49, 1–144.
    37. McCool, M. and Fiume, E. 1992. Hierarchical Poisson disk sampling distributions. In Proceedings of Graphics Interface’92. Canadian Information Processing Society, 94–105. 
    38. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In Proceedings of the SIGGRAPH’87 Conference, M. C. Stone, Ed. Annual Conference Series, vol. 21. ACM Press, 65–72. 
    39. Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. In Proceedings of the SIGGRAPH’91 Conference, T. W. Sederberg, Ed. Vol. 25. ACM Press, 157–164. 
    40. Ostromoukhov, V. 2007a. Building 2D low-discrepancy sequences for hierarchical importance sampling using dodecagonal aperiodic tiling. In Proceedings of GraphiCon’07. 139–142.
    41. Ostromoukhov, V. 2007b. Sampling with polyominoes. ACM Trans. Graph. 26, 3, 78. 
    42. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Trans. Graph. 23, 3, 488–495. 
    43. Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 1992. Numerical Recipes in C: The Art of Scientific Computing 2nd Ed. Cambridge University Press. 
    44. Ripley, B. D. 1977. Modelling spatial patterns. J. Royal Statist. Soc. Series B 39, 172–212.
    45. Samet, H. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA. 
    46. Secord, A., Heidrich, W., and Streit, L. 2002. Fast primitive distribution for illustration. In Proceedings of the 13th Eurographics Workshop on Rendering Techniques, S. Gibson and P. Debevec, Eds. Eurographics Association, 215–226. 
    47. Shirley, P. 1992. Nonuniform random point sets via warping. In Graphics Gems III, D. Kirk, Ed. Academic Press, San Diego, CA, 80–83. 
    48. Skoge, M., Donev, A., Stillinger, F. H., and Torquato, S. 2006. Packing hyperspheres in high-dimensional Euclidean spaces. Phys. Rev. E 74, 4, 041127.
    49. Snyder, D. L. 1991. Random Point Processes in Time and Space, 2nd Ed. Springer-Verlag, Berlin.
    50. Ulichney, R. A. 1988. Dithering with blue noise. Proc. IEEE 76, 1, 56–79.
    51. Wei, L.-Y. 2008. Parallel poisson disk sampling. ACM Trans. Graphi. 27, 3, 20. 
    52. Weisstein, E. W. Hypersphere packing. From MathWorld—A Wolfram Web Resource.
    53. White, K. B., Cline, D., and Egbert, P. K. 2007. Poisson disk point sets by hierarchical dart throwing. In Proceedings of the IEEE/Eurographics Symposium on Interactive Ray Tracing, A. Keller and P. Christensen, Eds. IEEE Press, 129–132. 
    54. Worley, S. P. 1996. A cellular texture basis function. In Proceedings of the SIGGRAPH’96 Conference, H. Rushmeier, Ed. Vol. 30. ACM Press, 291–294. 
    55. Yellot, Jr, J. I. 1983. Spectral consequences of photoreceptor sampling in the rhesus retina. Sci. 221, 382–395.

ACM Digital Library Publication:


Overview Page: