“Efficient maximal poisson-disk sampling” by Ebeida, Patney, Mitchell, Davidson, Knupp, et al. …

  • ©Mohamed S. Ebeida, Anjul Patney, Scott A. Mitchell, Andrew Davidson, Patrick Knupp, and John D. Owens




    Efficient maximal poisson-disk sampling



    We solve the problem of generating a uniform Poisson-disk sampling that is both maximal and unbiased over bounded non-convex domains. To our knowledge this is the first provably correct algorithm with time and space dependent only on the number of points produced. Our method has two phases, both based on classical dart-throwing. The first phase uses a background grid of square cells to rapidly create an unbiased, near-maximal covering of the domain. The second phase completes the maximal covering by calculating the connected components of the remaining uncovered voids, and by using their geometry to efficiently place unbiased samples that cover them. The second phase converges quickly, overcoming a common difficulty in dart-throwing methods. The deterministic memory is O(n) and the expected running time is O(n log n), where n is the output size, the number of points in the final sample. Our serial implementation verifies that the log n dependence is minor, and nearly O(n) performance for both time and memory is achieved in practice. We also present a parallel implementation on GPUs to demonstrate the parallel-friendly nature of our method, which achieves 2.4x the performance of our serial version.


    1. Attali, D., and Boissonnat, J.-D. 2004. A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces. Discrete & Computational Geometry 31, 3 (Feb.), 369–384. Google ScholarCross Ref
    2. Bolander, J. E., and Saito, S. 1998. Fracture analyses using spring networks with random geometry. Engineering Fracture Mechanics 61, 5-6, 569–591.Google ScholarCross Ref
    3. Bowers, J., Wang, R., Wei, L.-Y., and Maletz, D. 2010. Parallel Poisson disk sampling with spectrum analysis on surfaces. ACM Transactions on Graphics 29 (Dec.), 166:1–166:10. Google ScholarDigital Library
    4. Bridson, R. 2007. Fast Poisson disk sampling in arbitrary dimensions. In ACM SIGGRAPH 2007 Sketches, 22. Google Scholar
    5. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Transactions on Graphics 22, 3 (July), 287–294. Google ScholarDigital Library
    6. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Transactions on Graphics 5, 1 (Jan.), 51–72. Google ScholarDigital Library
    7. Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In Computer Graphics (Proceedings of SIGGRAPH 85), 69–78. Google Scholar
    8. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast Poisson-disk sample generation. ACM Transactions on Graphics 25, 3 (July), 503–508. Google ScholarDigital Library
    9. Edelsbrunner, H., and Shah, N. R. 1992. Incremental topological flipping works for regular triangulations. In Proceedings of the Eighth Annual Symposium on Computational Geometry, 43–52. Google Scholar
    10. Gamito, M. N., and Maddock, S. C. 2009. Accurate multidimensional Poisson-disk sampling. ACM Transactions on Graphics 29, 1 (Dec.), 8:1–8:19. Google ScholarDigital Library
    11. Jirásek, M., and Bazant, Z. P. 1995. Particle model for quasibrittle fracture and its application to sea ice. Journal of Engineering Mechanics 121, 1016–1025.Google ScholarCross Ref
    12. Jones, T. R. 2006. Efficient generation of Poisson-disk sampling patterns. journal of graphics tools 11, 2, 27–36.Google Scholar
    13. Lagae, A., and Dutré, P. 2005. A procedural object distribution function. ACM Transactions on Graphics 24, 4 (Oct.), 1442–1461. Google ScholarDigital Library
    14. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 27, 1 (Mar.), 114–129.Google ScholarCross Ref
    15. Matérn, B. 1960. Spatial variation. Meddelanden från Statens Skogsforskningsinstitut 49, 1–140.Google Scholar
    16. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In Computer Graphics (Proceedings of SIGGRAPH 87), 65–72. Google Scholar
    17. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Transactions on Graphics 23, 3 (Aug.), 488–495. Google ScholarDigital Library
    18. Ostromoukhov, V. 2007. Sampling with polyominoes. ACM Transactions on Graphics 26, 3 (July), 78:1–78:6. Google ScholarDigital Library
    19. Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google Scholar
    20. Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Graphics Hardware 2007, 97–106. Google ScholarDigital Library
    21. Turk, G. 1993. Generating random points in triangles. In Graphics Gems, A. Glassner, Ed. Academic Press, July, ch. 5, 24–28. Google Scholar
    22. Tzeng, S., and Wei, L.-Y. 2008. Parallel white noise generation on a GPU via cryptographic hash. In I3D ’08: Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, 79–87. Google Scholar
    23. Wei, L.-Y. 2008. Parallel Poisson disk sampling. ACM Transactions on Graphics 27, 3 (Aug.), 20:1–20:9. Google ScholarDigital Library
    24. White, K. B., Cline, D., and Egbert, P. K. 2007. Poisson disk point sets by hierarchical dart throwing. In RT ’07: Proceedings of the 2007 IEEE Symposium on Interactive Ray Tracing, 129–132. Google ScholarDigital Library

ACM Digital Library Publication: