Abstract
In this paper we describe sample elimination for generating Poisson disk sample sets with a desired size. We introduce a greedy sample elimination algorithm that assigns a weight to each sample in a given set and eliminates the ones with greater weights in order to pick a subset of a desired size with Poisson disk property without having to specify a Poisson disk radius. This new algorithm is simple, computationally efficient, and it can work in any sampling domain, producing sample sets with more pronounced blue noise characteristics than dart throwing. Most importantly, it allows unbiased progressive (adaptive) sampling and it scales better to high dimensions than previous methods. However, it cannot guarantee maximal coverage. We provide a statistical analysis of our algorithm in 2D and higher dimensions as well as results from our tests with different example applications.
Supporting Information
| Filename | Description |
|---|---|
| cgf12538-sup-0001-S1.mp430.3 MB | Supporting Information |
Please note: The publisher is not responsible for the content or functionality of any supporting information supplied by the authors. Any queries (other than missing content) should be directed to the corresponding author for the article.
References
- Bridson R.: Fast poisson disk sampling in arbitrary dimensions. In ACM SIGGRAPH'07 sketches (2007). 2
- Balzer M., Schlömer T., Deussen O.: Capacity-constrained point distributions: A variant of Lloyd's method. ACM Trans. on Graph. (SIGGRAPH'09) 28, 3 (2009), 86:1–8. 2
- Bowers J., Wang R., Wei L.-Y., Maletz D.: Parallel poisson disk sampling with spectrum analysis on surfaces. ACM Trans. Graph. (SIGGRAPH ASIA'10) 29, 6 (2010), 166. 2, 7
- Corsini M., Cignoni P., Scopigno R.: Efficient and flexible sampling with blue noise properties of triangular meshes. IEEE Trans. on Vis. & Comp. Graph. 18, 6 (2012), 914–924. 2, 7
- Cline D., Jeschke S., White K., Razdan A., Wonka P.: Dart throwing on surfaces. Computer Graphics Forum (EGSR'09) (2009), 1217–1226. 2
- Cook R.L.: Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1 (1986), 51–72. 1, 2
- Cohen M.F., Shade J., Hiller S., Deussen O.: Wang tiles for image and texture generation. ACM Trans. Graph. (SIGGRAPH'03) 22, 3 (2003), 287–294. 2
- Dunbar D., Humphreys G.: A spatial data structure for fast poisson-disk sample generation. ACM Transactions on Graphics (SIGGRAPH'06) 25, 3 (2006), 503–508. 2
- Dippé M. A. Z., Wold E.H.: Antialiasing through stochastic sampling. SIGGRAPH'85 19, 3 (1985), 69–78. 1, 2
10.1145/325165.325182 Google Scholar
- Ebeida M.S., Davidson A.A., Patney A., Knupp P.M., Mitchell S.A., Owens J.D.: Efficient maximal poisson-disk sampling. ACM ToG (SIGGRAPH'11) 30, 4 (2011), 49. 2
- Ebeida M.S., Mahmoud A.H., Awad M.A., Mohammed M.A., Mitchell S.A., Rand A., Owens J.D.: Sifted disks. Comp. Graphics Forum 32, 2 (2013), 509–518. 2
- Ebeida M.S., Mitchell S.A., Patney A., Davidson A.A., Owens J.D.: A simple algorithm for maximal poisson-disk sampling in high dimensions. Computer Graphics Forum 31, 2 (2012), 785–794. 2, 7
- Fattal R.: Blue-noise point sampling using kernel density model. ACM Trans. Graph. (SIGGRAPH'11) 28, 3 (2011), 1–10. 2
- Gamito M.N., Maddock S.C.: Accurate multidimensional poisson-disk sampling. ACM ToG 29, 1 (2009), 8:1–8:19. 2, 7
- Geng B., Zhang H., Wang H., Wang G.: Approximate poisson disk sampling on mesh. Science China Information Sciences 56, 9 (2013), 1–12. 2
- Hiller S., Deussen O., Keller A.: Tiled blue noise samples. In Proceedings of the Vision Modeling and Visualization Conference 2001 (2001), pp. 265–272.
- Jones T.R., Karger D.R.: Linear-time poisson-disk patterns. Journal of Graph., GPU, and Game Tools 15 (2011). 2
- Jones T.R.: Efficient generation of poisson-disk sampling patterns. Journal of Graph., GPU, and Game Tools 11, 2 (2006), 27–36. 2
10.1080/2151237X.2006.10129217 Google Scholar
- Kopf J., Cohen-Or D., Deussen O., Lischinski D.: Recursive wang tiles for real-time blue noise. ACM Transactions on Graphics (SIGGRAPH'06) 25, 3 (2006), 509–518. 2
- Kalantari N.K., Sen P.: Efficient Computation of Blue Noise Point Sets through Importance Sampling. Computer Graphics Forum (EGSR'11) 30, 4 (2011), 1215 UU 1221. 2
- Kalantari N.K., Sen P.: Fast generation of approximate blue noise point sets. CG. Forum 31, 4 (2012), 1529–1535. 2
- Lagae A., Dutré P.: A procedural object distribution function. ACM Transactions on Graphics 24, 4 (2005), 1442–1461. 2
- McCool M., Fiume E.: Hierarchical poisson disk sampling distributions. In Proc. Graphics interface ‘92 (1992), pp. 94–105. 2, 6
- Mitchell D.P.: Spectrally optimal sampling for distribution ray tracing. SIGGRAPH'91 25, 4 (1991), 157–164. 2
10.1145/127719.122736 Google Scholar
- Mitchell S.A., Rand A., Ebeida M.S., Bajaj C.: Variable radii Poisson-disk sampling. In Proc. of the 24th Canadian Conference on Computational Geometry (2012), pp. 185–190. 2, 6
- Ostromoukhov V., Donohue C., Jodoin P.-M.: Fast hierarchical importance sampling with blue noise properties. ACM Trans. on Graphics (SIGGRAPH'04) 23, 3 (2004), 488–495. 2
- Ostromoukhov V.: Sampling with polyominoes. ACM Trans. Graph. (SIGGRAPH'07) 26, 3 (2007). 2
- Schlömer T., Deussen O.: Accurate spectral analysis of two-dimensional point sets. Journal of Graphics, GPU, and Game Tools 15, 3 (2011), 152–160. 4
10.1080/2151237X.2011.609773 Google Scholar
- Schlömer T., Heck D., Deussen O.: Farthest-point optimized point sets with maximized minimum distance. In Proceedings ACM HPG'11 (2011), pp. 135–142. 2
- Turk G.: Generating textures on arbitrary surfaces using reaction-diffusion. In Proc. SIGGRAPH'91 (1991), pp. 289–298. 2
- White K.B., Cline D., Egbert P.K.: Poisson disk point sets by hierarchical dart throwing. In Proceedings of the 2007 IEEE Symp. on Interactive Ray Tracing (2007), pp. 129–132. 2
- Wei L.-Y.: Parallel poisson disk sampling. ACM Transactions on Graphics (SIGGRAPH'08) 27, 3 (2008), 20:1–20:9. 2, 7
- Witkin A.P., Heckbert P.S.: Using particles to sample and control implicit surfaces. In Proceedings of SIGGRAPH'94 (1994), pp. 269–277. 2
- Wachtel F., Pilleboue A., Coeuriolly D., Breeden K., Singh G., Cathelin G., de Goes F., Desbrun M., Ostromoukhov V.: Fast tile-based adaptive sampling with user-specified fourier spectra. ACM Trans. Graph. 33, 4 (July 2014), 56:1–56:11. 2
- Xu Y., Liu L., Gotsman C., Gortler S.J.: Capacity-constrained delaunay triangulation for point distributions. Computers & Graphics (Proceedings of Shape Modeling International) 35, 3 (2011), 510–516. 2
- Yan D.-M., Wonka P.: Gap processing for adaptive maximal poisson-disk sampling. ACM Trans. Graph. 32, 5 (Oct. 2013), 148:1–148:15. 2
- Ying X., Xin S.-Q., Sun Q., He Y.: An intrinsic algorithm for parallel poisson disk sampling on arbitrary surfaces. IEEE Trans. on Vis. & Comp. Graph. 19, 9 (2013), 1425–1437. 2, 7
- Zhou Y., Huang H., Wei L.-Y., Wang R.: Point sampling with general noise spectrum. ACM Transactions on Graphics 31, 4 (2012), 76:1–76:11. 2
