“Parallel Poisson disk sampling” by Wei

Sampling is important for a variety of graphics applications include rendering, imaging, and geometry processing. However, producing sample sets with desired efficiency and blue noise statistics has been a major challenge, as existing methods are either sequential with limited speed, or are parallel but only through pre-computed datasets and thus fall short in producing samples with blue noise statistics. We present a Poisson disk sampling algorithm that runs in parallel and produces all samples on the fly with desired blue noise properties. Our main idea is to subdivide the sample domain into grid cells and we draw samples concurrently from multiple cells that are sufficiently far apart so that their samples cannot conflict one another. We present a parallel implementation of our algorithm running on a GPU with constant cost per sample and constant number of computation passes for a target number of samples. Our algorithm also works in arbitrary dimension, and allows adaptive sampling from a user-specified importance field. Furthermore, our algorithm is simple and easy to implement, and runs faster than existing techniques.

1. Akenine-Möller, T., Munkberg, J., and Hasselgren, J. 2007. Stochastic rasterization using time-continuous triangles. In GH ’07: Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, 7–16. Google ScholarDigital Library
2. Bridson, R. 2007. Fast poisson disk sampling in arbitrary dimensions. In SIGGRAPH ’07: ACM SIGGRAPH 2007 Sketches & Applications. Google ScholarDigital Library
3. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. In SIGGRAPH ’03: ACM SIGGRAPH 2003 Papers, 287–294. Google ScholarDigital Library
4. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51–72. Google ScholarDigital Library
5. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast poisson-disk sample generation. In SIGGRAPH ’06: ACM SIGGRAPH 2006 Papers, 503–508. Google ScholarDigital Library
6. Jones, T. R. 2006. Efficient generation of poisson-disk sampling patterns. journal of graphics tools 11, 2, 27–36.Google Scholar
7. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. In SIGGRAPH ’06: ACM SIGGRAPH 2006 Papers, 509–518. Google ScholarDigital Library
8. Lagae, A., and Dutré, P. 2005. A procedural object distribution function. ACM Trans. Graph. 24, 4, 1442–1461. Google ScholarDigital Library
9. Lagae, A., and Dutré, P. 2006. An alternative for wang tiles: colored edges versus colored corners. ACM Trans. Graph. 25, 4, 1442–1459. Google ScholarDigital Library
10. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum. to appear.Google Scholar
11. Lawrence, J., Rusinkiewicz, S., and Ramamoorthi, R. 2005. Adaptive numerical cumulative distribution functions for efficient importance sampling. In Eurographics Symposium on Rendering. Google ScholarCross Ref
12. Lefebvre, S., and Hoppe, H. 2005. Parallel controllable texture synthesis. In SIGGRAPH ’05: ACM SIGGRAPH 2005 Papers, 777–786. Google ScholarDigital Library
13. McCool, M., and Fiume, E. 1992. Hierarchical poisson disk sampling distributions. In Proceedings of the conference on Graphics interface ’92, 94–105. Google ScholarDigital Library
14. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In SIGGRAPH ’87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, 65–72. Google ScholarDigital Library
15. Mitchell, D. P. 1991. Spectrally optimal sampling for distribution ray tracing. SIGGRAPH Comput. Graph. 25, 4, 157–164. Google ScholarDigital Library
16. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. In SIGGRAPH ’04: ACM SIGGRAPH 2004 Papers, 488–495. Google ScholarDigital Library
17. Ostromoukhov, V. 2007. Sampling with polyominoes. In SIGGRAPH ’07: ACM SIGGRAPH 2007 Papers, 78. Google ScholarDigital Library
18. Popat, K., and Picard, R. W. 1997. Cluster based probability model and its application to image and texture processing. IEEE Trans. Image Processing 6, 2, 268–284. Google ScholarDigital Library
19. Turk, G. 1992. Re-tiling polygonal surfaces. In SIGGRAPH ’92: Proceedings of the 19th annual conference on Computer graphics and interactive techniques, 55–64. Google ScholarDigital Library
20. 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 ScholarDigital Library
21. Wei, L.-Y., and Levoy, M. 2000. Fast texture synthesis using tree-structured vector quantization. In SIGGRAPH ’00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, 479–488. Google ScholarDigital Library
22. Wei, L.-Y., and Levoy, M. 2002. Order-independent texture synthesis. Tech. Rep. TR-2002-01, Computer Science Department, Stanford University.Google Scholar
23. White, K., Cline, D., and Egbert, P. 2007. Poisson disk point sets by hierarchical dart throwing. In Symposium on Interactive Ray Tracing, 129–132. Google ScholarDigital Library