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

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