Journal Home > Volume 1 , Issue 1
Computational Visual Media 2015, 1(1): 17-26 https://doi.org/10.1007/s41095-015-0003-7
Research Article | Open Access | Issue | Published: 08 August 2015

Poisson disk sampling through disk packing

Show Author's Information Guanghui Liang1,  Lin Lu1( ),  Zhonggui Chen2,  Chenglei Yang1
School of Computer Science and Technology, Shandong University, Jinan 250101, China.
Department of Computer Science, Xiamen University, Xiamen 361005, China.
Keywords:
disk packing, image stippling, Poisson disk sampling, power diagram
Cite this article:
Liang G, Lu L, Chen Z, et al. Poisson disk sampling through disk packing. Computational Visual Media, 2015, 1(1): 17-26. https://doi.org/10.1007/s41095-015-0003-7
Download citation
EndNote(RIS)
BibTeX

623

Views

41

Downloads

Citations

8

Crossref

N/A

WoS

9

Scopus

0

CSCD

Abstract Full text About this article

Poisson disk sampling is an important problem in computer graphics and has a wide variety of applications in imaging, geometry, rendering, etc. In this paper, we propose a novel Poisson disk sampling algorithm based on disk packing. The key idea uses the observation that a relatively dense disk packing layout naturally satisfies the Poisson disk distribution property that each point is no closer to the others than a specified minimum distance, i.e., the Poisson disk radius. We use this property to propose a relaxation algorithm that achieves a good balance between the random and uniform properties needed for Poisson disk distributions. Our algorithm is easily adapted to image stippling by extending identical disk packing to unequal disks. Experimental results demonstrate the efficacy of our approaches.


menu
Abstract
Full text
Outline
About this article

Poisson disk sampling through disk packing

Show Author's information Guanghui Liang1, Lin Lu1( ), Zhonggui Chen2, Chenglei Yang1
School of Computer Science and Technology, Shandong University, Jinan 250101, China.
Department of Computer Science, Xiamen University, Xiamen 361005, China.

Abstract

Poisson disk sampling is an important problem in computer graphics and has a wide variety of applications in imaging, geometry, rendering, etc. In this paper, we propose a novel Poisson disk sampling algorithm based on disk packing. The key idea uses the observation that a relatively dense disk packing layout naturally satisfies the Poisson disk distribution property that each point is no closer to the others than a specified minimum distance, i.e., the Poisson disk radius. We use this property to propose a relaxation algorithm that achieves a good balance between the random and uniform properties needed for Poisson disk distributions. Our algorithm is easily adapted to image stippling by extending identical disk packing to unequal disks. Experimental results demonstrate the efficacy of our approaches.

Keywords: disk packing, image stippling, Poisson disk sampling, power diagram

References(48)

[1]
Pharr, M.; Humphreys, G. Physically Based Rendering: From Theory to Implementation. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2004.
[2]
Deussen, O.; Hiller, S.; Van Overveld, C.; Strothotte, T. Floating points: A method for computing stipple drawings. Computer Graphics Forum Vol. 19, No. 3, 41-50, 2000.
DOI Google Scholar
[3]
Secord, A. Weighted Voronoi stippling. In: Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering, 37-43, 2002.
DOI
[4]
Deussen, O.; Hanrahan, P.; Lintermann, B.; Mh, R.; Pharr, M.; Prusinkiewicz, P. Realistic modeling and rendering of plant ecosystems. In: Proceedings of the 25th annual conference on Computer graphics and interactive techniques, 275-286, 1998.
DOI
[5]
Surazhsky, V.; Alliez, P.; Gotsman, C. Isotropic remeshing of surfaces: A local parameterization approach. In: 12th International Meshing Roundtable, 215-224, 2003.
[6]
Cook, R. L. Stochastic sampling in computer graphics. ACM Transactions on Graphics Vol. 5, No. 1, 51-72, 1986.
DOI Google Scholar
[7]
Jones, T. R. Efficient generation of Poisson-disk sampling patterns. Journal of Graphics, GPU, and Game Tools Vol. 11, No. 2, 27-36, 2006.
DOI Google Scholar
[8]
Dunbar, D.; Humphreys, G. A spatial data structure for fast Poisson-disk sample generation. ACM Transactions on Graphics Vol. 25, No. 3, 503-508, 2006.
DOI Google Scholar
[9]
White, K. B.; Cline, D.; Egbert, P. K. Poisson disk point sets by hierarchical dart throwing. In: IEEE Symposium on Interactive Ray Tracing, 129-132, 2007.
DOI
[10]
Ebeida, M. S.; Davidson, A. A.; Patney, A.; Knupp, P. M.; Mitchell, S. A.; Owens, J. D. Efficient maximal Poisson-disk sampling. In: ACM SIGGRAPH 2011 papers, Article No. 49, 2011.
DOI
[11]
Yan, D.-M.; Wonka, P. Gap processing for adaptive maximal Poisson-disk sampling. ACM Transactions on Graphics Vol. 32, No. 5, Article No. 148, 2013.
DOI Google Scholar
[12]
Wei, L.-Y. Parallel Poisson disk sampling. In: ACM SIGGRAPH 2008 papers, Article No. 20, 2008.
DOI
[13]
Xiang, Y.; Xin, S.-Q.; Sun, Q.; He, Y. Parallel and accurate Poisson disk sampling on arbitrary surfaces. In: SIGGRAPH Asia 2011 Sketches, Article No. 18, 2011.
DOI
[14]
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 Vol. 31, No. 2, 785-794, 2012.
DOI Google Scholar
[15]
Gamito, M. N.; Maddock, S. C. Accurate multidimensional Poisson-disk sampling. ACM Transactions on Graphics Vol. 29, No. 1, Article No. 8, 2009.
DOI Google Scholar
[16]
Dippé, M. A. Z.; Wold, E. H. Antialiasing through stochastic sampling. In: Proceedings of the 12th annual conference on Computer graphics and interactive techniques, 69-78, 1985.
DOI
[17]
Cohen, M. F.; Shade, J.; Hiller, S.; Deussen, O. Wang tiles for image and texture generation. ACM Transactions on Graphics Vol. 22, No. 3, 287-294, 2003.
DOI Google Scholar
[18]
Ostromoukhov, V.; Donohue, C.; Jodoin, P.-M. Fast hierarchical importance sampling with blue noise properties. ACM Transactions on Graphics Vol. 23, No. 3, 488-495, 2004.
DOI Google Scholar
[19]
Kopf, J.; Cohen-Or, D.; Deussen, O.; Lischinski, D. Recursive Wang tiles for real-time blue noise. ACM Transactions on Graphics Vol. 25, No. 3, 509-518, 2006.
DOI Google Scholar
[20]
Ostromoukhov, V. Sampling with polyominoes. ACM Transactions on Graphics Vol. 26, No. 3, Article No. 78, 2007.
DOI Google Scholar
[21]
Lloyd, S. Least squares quantization in pcm. IEEE Transactions on Information Theory Vol. 28, No. 2, 129-137, 1982.
DOI Google Scholar
[22]
McCool, M.; Fiume, E. Hierarchical Poisson disk sampling distributions. In: Proceedings of the conference on Graphics interface, 94-105, 1992.
[23]
Balzer, M.; Schlömer, T.; Deussen, O. Capacity-constrained point distributions: A variant of Lloyd’s method. ACM Transactions on Graphics Vol. 28, No. 3, Article No. 86, 2009.
DOI Google Scholar
[24]
Chen, Z.; Yuan, Z.; Choi, Y.-K.; Liu, L.; Wang, W. Variational blue noise sampling. IEEE Transactions on Visualization and Computer Graphics Vol. 18, No. 10, 1784-1796, 2012.
DOI Google Scholar
[25]
De Goes, F.; Breeden, K.; Ostromoukhov, V.; Desbrun, M. Blue noise through optimal transport. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 171, 2012.
DOI Google Scholar
[26]
Zhou, Y.; Huang, H.; Wei, L.-Y.; Wang, R. Point sampling with general noise spectrum. ACM Transactions on Graphics Vol. 31, No. 4, Article No. 76, 2012.
DOI Google Scholar
[27]
Öztireli, A. C.; Gross, M. Analysis and synthesis of point distributions based on pair correlation. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 170, 2012.
DOI Google Scholar
[28]
Heck, D.; Schlömer, T.; Deussen, O. Blue noise sampling with controlled aliasing. ACM Transactions on Graphics Vol. 32, No. 3, Article No. 25, 2013.
DOI Google Scholar
[29]
Wachtel, F.; Pilleboue, A.; Coeurjolly, 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 Transactions on Graphics Vol. 33, No. 4, Article No. 56, 2014.
DOI Google Scholar
[30]
Ebeida, M. S.; Awad, M. A.; Ge, X.; Mahmoud, A. H.; Mitchell, S. A.; Knupp, P. M.; Wei, L.-Y. Improving spatial coverage while preserving the blue noise of point sets. Computer-Aided Design Vol. 46, 25-36, 2014.
DOI Google Scholar
[31]
Chen, J.; Ge, X.; Wei, L.-Y.; Wang, B.; Wang, Y.; Wang, H.; Fei, Y.; Qian, K.-L.; Yong, J.-H. Wang, W. Bilateral blue noise sampling. ACM Transactions on Graphics Vol. 32, No. 6, Article No. 216, 2013.
DOI Google Scholar
[32]
Kepler, J. The Six-Cornered Snowflake. Oxford, UK: Clarendon Press, 1966.
[33]
Lubachevsky, B. D.; Graham, R. L. Curved hexagonal packings of equal disks in a circle. Discrete & Computational Geometry Vol. 18, No. 2, 179-194, 1997.
DOI Google Scholar
[34]
Szabó, P. G.; Markót, M. Cs.; Csendes, T.; Specht, E.; Casado, L. G.; García, I. New Approaches to Circle Packing in a Square: With Program Codes. New York, NY, USA: Springer-Verlag, 2007.
[35]
Graham, R. L.; Lubachevsky, B. D. Dense packings of equal disks in an equilateral triangle: From 22 to 34 and beyond. The Electronic Journal of Combinatorics Vol. 2, No. 1, A1, 1995.
DOI Google Scholar
[36]
Birgin, E. G.; Sobral, F. N. C. Minimizing the object dimensions in circle and sphere packing problems. Computers and Operations Research Vol. 35, No. 7, 2357-2375, 2008.
DOI Google Scholar
[37]
Addis, B.; Locatelli, M.; Schoen, F. Efficiently packing unequal disks in a circle. Operations Research Letters Vol. 36, No. 1, 37-42, 2008.
DOI Google Scholar
[38]
Pintér, J. D.; Kampas, F. J. MathOptimizer professional: Key features and illustrative applications. In: Nonconvex Optimization and Its Applications, Vol. 84 Global Optimization. Liberti, L.; Maculan, N. Eds. New York, NY, USA: Springer-Verlag, 263-279, 2006.
[39]
Huang, W. Q.; Li, Y.; Akeb, H.; Li, C. M. Greedy algorithms for packing unequal circles into a rectangular container. Journal of the Operational Research Society Vol. 56, No. 5, 539-548, 2005.
DOI Google Scholar
[40]
Lü, Z.; Huang, W. PERM for solving circle packing problem. Computers & Operations Research Vol. 35, No. 5, 1742-1755, 2008.
DOI Google Scholar
[41]
Wang, H.; Huang, W.; Zhang, Q.; Xu, D. An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research Vol. 141, No. 2, 440-453, 2002.
DOI Google Scholar
[42]
Lu, L.; Choi, Y.-K.; Sun, F.; Wang, W. Variational circle packing based on power diagram. Technical report. The University of Hong Kong, 2011. Available at http://vr.sdu.edu.cn/∼lulin/CP_TechReport.pdf.
[43]
Aurenhammer, F. Power diagrams: Properties, algorithms and applications. SIAM Journal on Computing Vol. 16, No. 1, 78-96, 1987.
DOI Google Scholar
[44]
Liu, Y.; Wang, W.; Lévy, B.; Sun, F.; Yan, D.-M.; Lu, L.; Yang, C. On centroidal voronoi tessellation—energy smoothness and fast computation. ACM Transactions on Graphics Vol. 28, No. 4, Article No. 101, 2009.
DOI Google Scholar
[45]
Lagae, A.; Dutré, P. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum Vol. 27, No. 1, 114-129, 2008.
DOI Google Scholar
[46]
Fabri, A.; Pion, S. CGAL: The computational geometry algorithms library. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 538-539, 2009.
DOI
[47]
Schmaltz, C.; Gwosdek, P.; Bruhn, A.; Weickert, J. Electrostatic halftoning. Computer Graphics Forum Vol. 29, No. 8, 2313-2327, 2010.
DOI Google Scholar
[48]
Fattal, R. Blue-noise point sampling using kernel density model. ACM Transactions on Graphics Vol. 30, No. 4, Article No. 48, 2011.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Revised: 19 September 2014
Accepted: 12 January 2015
Published: 08 August 2015
Issue date: March 2015

Copyright

© The Author(s) 2015

Acknowledgements

The authors would like to acknowledge the help of Prof. Wenping Wang for many valuable discussions on this work. This work was supported in part by National Natural Science Foundation of China (Nos. 61202147 and 61272243), Shandong Province Natural Science Foundation (No. ZR2012FQ026), and Fundamental Research Funds for the Central Universities (No. 20720140520).

Rights and permissions

This article is published with open access at Springerlink.com

This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.

Return