›› 2015, Vol. 30 ›› Issue (3): 439-452.doi: 10.1007/s11390-015-1535-0

Special Issue: Surveys; Computer Graphics and Multimedia

• Special Section on Computational Visual Media • Previous Articles     Next Articles

A Survey of Blue-Noise Sampling and Its Applications

Dong-Ming Yan1,2(严冬明), Member, CCF, ACM, Jian-Wei Guo2(郭建伟), Bin Wang3(王斌), Xiao-Peng Zhang2(张晓鹏), Peter Wonka1,4   

  1. 1. Visual Computing Center, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia;
    2. National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China;
    3. School of Software, Tsinghua University, Beijing 100084, China;
    4. Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287, U.S.A.
  • Received:2015-03-09 Revised:2015-04-02 Online:2015-05-05 Published:2015-05-05
  • About author:Dong-Ming Yan is a research scientist at King Abdullah University of Science and Technology (KAUST), and he is also an associate professor at National Laboratory of Pattern Recognition (NLPR), the Institute of Automation of the Chinese Academy of Sciences (CASIA), Beijing. He received his Ph.D. degree in computer science from Hong Kong University in 2010, and M.S. and B.S. degrees in computer science and technology from Tsinghua University in 2005 and 2002, respectively. His research interests include computer graphics, geometric processing and visualization.
  • Supported by:

    This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61372168, 61373071, 61372190, and 61331018, the Scientific Research Foundation for the Returned Overseas Chinese Scholars of State Education Ministry of China, the Visual Computing Center at King Abudullah University of Science and Technology (KAUST), and the Open Funding Project of the State Key Laboratory of Virtual Reality Technology and Systems, Beihang University, under Grant Nos. BUAA-VR-15KF-06 and BUAA-VR-14KF-10.

PDF

2846

In this paper, we survey recent approaches to blue-noise sampling and discuss their beneficial applications. We discuss the sampling algorithms that use points as sampling primitives and classify the sampling algorithms based on various aspects, e.g., the sampling domain and the type of algorithm. We demonstrate several well-known applications that can be improved by recent blue-noise sampling techniques, as well as some new applications such as dynamic sampling and blue-noise remeshing.

[1] Mitchell D P. Generating antialiased images at low sampling densities. In Proc. the 14th ACM SIGGRAPH, July 1987, pp.65-72.

[2] Fattal R. Blue-noise point sampling using kernel density model. ACM Trans. Graphics, 2011, 30(4): 48:1-48:12

[3] Wu F, Dong W, Kong Y et al. Featureaware natural texture synthesis. The Visual Computer. (to be appeared)

[4] Deussen O, Hanrahan P, Lintermann B et al. Realistic modeling and rendering of plant ecosystems. In Proc. the 25th ACM SIGGRAPH, July 1998, pp.275-286.

[5] Schechter H, Bridson R. Ghost SPH for animating water. ACM Trans. Graphics, 2012, 31(4): 61:1-61:8.

[6] Lagae A, Dutré P. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum, 2008, 27(1): 114-129.

[7] Tzeng S,Wei L Y. Parallel white noise generation on a GPU via cryptographic hash. In Proc. the 2008 Symp. Interactive 3D Graphics and Games, February 2008, pp.79-87.

[8] Condit R, Ashton P S, Baker P et al. Spatial patterns in the distribution of tropical tree species. Science, 2000, 288(5470): 1414-1418.

[9] Ostling A, Harte J, Green J. Self-similarity and clustering in the spatial distribution of species. Science, 2000, 290(5492): 671-671.

[10] Lau D L, Ulichney R, Arce G R. Blue and green noise halftoning models. IEEE Signal Processing Magazine, 2003, 20(4): 28-38

[11] Schlömer T, Heck D, Deussen O. Farthest-point optimized point sets with maximized minimum distance. In Proc. ACM SIGGRAPH Symposium on High Performance Graphics, August 2011, pp.135-142.

[12] Ebeida M S, Patney A, Mitchell S A et al. Efficient maximal Poisson-disk sampling. ACM Trans. Graphics, 2011, 30(4): 49:1-49:12.

[13] Ebeida M S, Mitchell S A, Patney A et al. A simple algorithm for maximal Poisson-disk sampling in high dimensions. Computer Graphics Forum, 2012 31(2): 785-794

[14] Bridson R. Fast Poisson disk sampling in arbitrary dimensions. In Proc. ACM SIGGRAPH 2007 Sketches, August 2007, Article No. 22.

[15] Wei L Y. Parallel Poisson disk sampling. ACM Trans. Graphics, 2008, 27(3): 20:1-20:9.

[16] Gamito M N, Maddock S C. Accurate multidimensional Poisson-disk sampling. ACM Trans. Graphics, 2009, 29(1): 8:1-8:19.

[17] Ebeida M S, Mitchell S A, Patney A et al. Exercises in high-dimensional sampling: Maximal Poisson-disk sampling and k-d Darts. In Topological and Statistical Methods for Complex Data, Bennett J, Vivodtzev F, Pascucci V(eds.), Springer-Verlag, 2015, pp.221-238.

[18] Cook R L. Stochastic sampling in computer graphics. ACM Trans. Graphics, 1986, 5(1): 51-72.

[19] Dunbar D, Humphreys G. A spatial data structure for fast Poisson-disk sample generation. ACM Trans. Graphics, 2006, 25(3): 503-508.

[20] White K B, Cline D, Egbert P K. Poisson disk point sets by hierarchical dart throwing. In Proc. IEEE Symposium on Interactive Ray Tracing, Sept. 2007, pp.129-132.

[21] Jones T R, Karger D R. Linear-time Poisson-disk patterns. Journal of Graphics, GPU, and Game Tools, 2011, 15(3): 177-182.

[22] Wei L Y. Multi-class blue noise sampling. ACM Trans. Graphics, 2010, 29(4): 79:1-79:8

[23] Ip C Y, Yalçin M A, Luebke D, Varshney A. Pixelpie: Maximal Poisson-disk sampling with rasterization. In Proc. the 5th High-Performance Graphics Conference, July 2013, pp.17-26.

[24] Jones T R. Efficient generation of Poisson-disk sampling patterns. Journal of Graphics Tools, 2006, 11(2): 27-36.

[25] Yan D M, Wonka P. Gap processing for adaptive maximal Poisson-disk sampling. ACM Trans. Graphics, 2013, 32(5): 148:1-148:15.

[26] Mitchell S A, Rand A, Ebeida M S, Bajaj C L. Variable radii Poisson disk sampling. In Proc. the 24th Canadian Conference on Computational Geometry (CCCG), August 2012, pp.185-190.

[27] Ebeida M S, Mahmoud A H, Awad M A et al. Sifted disks. Computer Graphics Forum, 2013, 32(2): 509-518.

[28] Yuksel C. Sample elimination for generating Poisson disk sample sets. Computer Graphics Forum, 2015, 37(2). (to be appeared)

[29] Cline D, Jeschke S, White K, Razdan A, Wonka P. Dart throwing on surfaces. Computer Graphics Forum, 2009, 28(4): 1217-1226

[30] Bowers J,Wang R,Wei L Y, Maletz D. Parallel Poisson disk sampling with spectrum analysis on surfaces. ACM Trans. Graphics, 2010, 29(6): 166:1-166:10

[31] Corsini M, Cignoni P, Scopigno R. Efficient and flexible sampling with blue noise properties of triangular meshes. IEEE Trans. Vis. and Comp. Graphics, 2012, 18(6): 914-924.

[32] Geng B, Zhang H, Wang H, Wang G. Approximate Poisson disk sampling on mesh. Science China Information Sciences, 2013, 56(9): 1-12.

[33] Yan D M, Wonka P. Adaptive maximal Poisson-disk sampling on surfaces. In Proc. ACM SIGGRAPH Asia Technical Briefs, Nov. 28–Dec. 1, 2012, pp.21:1-21:4,.

[34] Yan D M, Bao G B, Zhang X, Wonka P. Low-resolution remeshing using the localized restricted Voronoi diagram. IEEE Trans. Vis. and Comp. Graphics, 2014, 20(10): 1418-1427.

[35] Medeiros E, Ingrid L, Pesco S, Silva C. Fast adaptive blue noise on polygonal surfaces. Graphical Models, 2014, 76(1): 17-29.

[36] Guo J, Yan D M, Jia X, Zhang X. Efficient maximal Poisson-disk sampling and remeshing on surfaces. Computers & Graphics, 2015, 46: 72-79.

[37] Yan D M, Wallner J, Wonka P. Unbiased sampling and meshing of isosurfaces. IEEE Trans. Vis. and Comp. Graphics, 2014, 20(11): 1579-1589.

[38] Fu Y, Zhou B. Direct sampling on surfaces for high quality remeshing. In Proc. ACM Symposium on Solid and Physical Modeling, June 2008, pp.115-124.

[39] Ying X, Xin S Q, Sun Q, He Y. An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces. IEEE Trans. Vis. and Comp. Graphics, 2013, 19(9): 1425-1437.

[40] Ying X, Li Z, He Y. A parallel algorithm for improving the maximal property of Poisson disk sampling. Computer-Aided Design, 2014, 46: 37-44.

[41] Peyrot J L, Payan F, Antonini M. Direct blue noise resampling of meshes of arbitrary topology. The Visual Computer, 2014. (to be appeared)

[42] Yan D M, Lévy B, Liu Y et al. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Computer Graphics Forum, 2009, 28(5): 1445-1454.

[43] Lloyd S P. Least squares quantization in PCM. IEEE Transactions on Information Theory, 1982, 28(2): 129-137.

[44] Du Q, Faber V, Gunzburger M. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Review, 1999, 41(4): 637-676.

[45] Alliez P, de Verdière E C, Devillers O, Isenburg M. Centroidal Voronoi diagrams for isotropic surface remeshing. Graphical Models, 2005, 67(3): 204-231.

[46] Rong G, Jin M, Shuai L, Guo X. Centroidal Voronoi tessellation in universal covering space of manifold surfaces. Comp. Aided Geom. Design, 2011, 28(8): 475-496.

[47] Valette S, Chassery J M, Prost R. Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams. IEEE Trans. Vis. and Comp. Graphics, 2008, 14(2): 369-381.

[48] Balzer M Schlömer T, Deussen O. Capacity-constrained point distributions: A variant of Lloyd's method. ACM Trans. Graphics, 2009, 28(6): 86:1-86:8.

[49] Li D, Nehab D, Wei L Y, Sander P V, Fu C W. Fast capacity constrained Voronoi tessellation. In Proc. the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, Feb. 2010, Article No. 13.

[50] Xu Y, Liu L, Gotsman C, Gortler S J. Capacity-constrained Delaunay triangulation for point distributions. Computers & Graphics, 2011, 35(3): 510-516.

[51] Xu Y, Hu R, Gotsman C, Liu L. Blue noise sampling of surfaces. Computers & Graphics, 2012, 36(4): 232-240.

[52] Chen Z, Yuan Z, Choi Y K, Liu L, Wang W. Variational blue noise sampling. IEEE Trans. Vis. and Comp. Graphics, 2012, 18(10): 1784-1796.

[53] Liu Y, Wang W, Lévy B et al. On centroidal Voronoi tessellation — Energy smoothness and fast computation. ACM Trans. Graphics, 2009, 28(4): 101:1-101:17.

[54] de Goes F, Breeden K, Ostromoukhov V, Desbrun M. Blue noise through optimal transport. ACM Trans. Graphic, 2012, 31(6): 171:1-171:11

[55] Kanamori Y, Szego Z, Nishita T. Deterministic blue noise sampling by solving largest empty circle problems. The Journal of the Institute of Image Electronics Engineers of Japan, 2011, 40(1): 6-13.

[56] Chen R, Gotsman C. Parallel bluenoise sampling by constrained farthest point optimization. Computer Graphics Forum, 2012, 31(5): 1775-1785.

[57] Yan D M, Guo J, Jia X, Zhang X, Wonka P. Bluenoise remeshing with farthest point optimization. Computer Graphics Forum, 2014, 33(5): 167-176.

[58] Öztireli A C, Alexa M, Gross M. Spectral sampling of manifolds. ACM Trans. Graphics, 2010, 29(6): 168:1-168:8.

[59] Chen J, Ge X, Wei L W et al. Bilateral blue noise sampling. ACM Trans. Graphics, 2013, 32(6): 216:1-216:11.

[60] Ebeida M S, Awad M A, Ge X et al. Improving spatial coverage while preserving the blue noise of point sets. Computer-Aided Design, 2014, 46: 25-36.

[61] Hiller S, Deussen O, Keller A. Tiled blue noise samples. In Proc. the 16th Vision Modeling and Visualization Conference, October 2001, pp.265-272.

[62] Wang H. Proving theorems by pattern recognition, II. Bell Systems Technical Journal, 1961, 40(1): 1-42.

[63] Wang H. Games, logic and computers. Scientific American, 1965, 213(5): 98-106.

[64] Lagae A, Dutré P. A procedural object distribution function. ACM Trans. Graphics, 2005, 24(4): 1442-1461.

[65] Kopf J, Cohen-Or D, Deussen O, Lischinski D. Recursive Wang tiles for real-time blue noise. ACM Trans. Graphics, 2006, 25(3): 509-518.

[66] Ostromoukhov V, Donohue C, Jodoin P M. Fast hierarchical importance sampling with blue noise properties. ACM Trans. Graphics, 2004, 23(3): 488-495.

[67] Ostromoukhov V. Sampling with polyominoes. ACM Trans. Graphics, 2007, 26(3): 78:1-78:6.

[68] Wachtel F, Pilleboue A, Coeurjolly D et al. Fast tile-based adaptive sampling with user-specified fourier spectra. ACM Trans. Graphics, 2014, 33(4): 56:1-56:11.

[69] Kalantari N K, Sen P. Fast generation of approximate blue noise point sets. Computer Graphics Forum, 2012, 31(4): 1529-1535.

[70] Kalantari N K, Sen P. Efficient computation of blue noise point sets through importance sampling. Computer Graphics Forum, 2011, 30(4): 1215-1221.

[71] Zhou Y, Huang H, Wei L Y, Wang R. Point sampling with general noise spectrum. ACM Trans. Graph., 2012, 31(4): 76:1-76:11.

[72] Heck D, Schlömer T, Deussen O. Blue noise sampling with controlled aliasing. ACM Trans. Graphics, 2013, 32(3): 25:1-25:12.

[73] Mitchell S A, Mohammed M A, Mahmoud A H, Ebeida M S. Delaunay quadrangulations by two-coloring vertices. In Proc. the 23rd International Meshing Roundtable, October 2014, pp.364-376.

[74] Tzeng S, Patney A, Davidson A et al. High-quality parallel depth-of-field using line samples. In Proc. the 4th ACM SIGGRAPH/Eurographics Conference on High-Performance Graphics, June 2012, pp.23-31.

[75] Sun X, Zhou K, Guo J et al. Line segment sampling with blue-noise properties. ACM Trans. Graphics, 2013, 32(4): 127:1-127:14.

[76] Ebeida M S, Patney A, Mitchell S A et al. k-d Darts: Sampling by k-dimensional flat searches. ACM Trans. Graphics, 2014, 33(1): 3:1-3:16.

[77] Feng L, Hotz I, Hamann B, Joy K I. Anisotropic noise samples. IEEE Trans. Vis. and Comp. Graphics, 2008, 14(2): 342-354.

[78] Li H, Wei L Y, Sander P, Fu C W. Anisotropic blue noise sampling. ACM Trans. Graphics, 2010, 29(6): 167:1-167:12.

[79] Quinn J A, Langbein F C, Lai Y K, Martin R R. Generalized anisotropic stratified surface sampling. IEEE Trans. Vis. and Comp. Graphics, 2013, 19(7): 1143-1157.

[80] Ulichney R. Digital Halftoning. Cambridge, USA: MIT Press, 1987.

[81] Schlömer T, Deussen O. Accurate spectral analysis of twodimensional point sets. Journal of Graphics, GPU, and Game Tools, 2011, 15(3): 152-160.

[82] ¨Oztireli A C, Gross M. Analysis and synthesis of point distributions based on pair correlation. ACM Trans. Graphics, 2012, 31(6): 170:1-170:10.

[83] Subr K, Kautz J. Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration. ACM Trans. Graphics, 2013, 32(4): 128:1-128:12.

[84] Wei L Y, Wang R. Differential domain analysis for nonuniform sampling. ACM Trans. Graphics, 2011, 30(4): Article No. 50.

[85] Frey P, Borouchaki H. Surface mesh evaluation. In Proc. the 6th Int. Meshing Roundtable, October 1997, pp.363-374.

[86] Cignoni P, Rocchini C, Scopigno R. Metro: Measuring error on simplified surfaces. Computer Graphics Forum, 1998, 17(2): 167-174.

[87] Spencer B, Jones M W. Progressive photon relaxation. ACM Trans. Graphics, 2013, 32(1): 7:1-7:11.

[88] Secord A. Weighted Voronoi stippling. In Proc. the 2nd International Symposium on Non-Photorealistic Animation and Rendering, June 2002, pp.37-43.

[89] Ascencio-Lopez I, Meruvia-Pastor O, Hidalgo-Silva H. Adaptive incremental stippling using the Poisson-disk distribution. Journal of Graphics, GPU, and Game Tools, 2010, 15(1): 29-47.

[90] Ge X, Wei L Y, Wang Y, Wang H. Bilateral blue noise sampling: Additional algorithms and applications. Technical Report, OSU-CISRC-8/13-TR17, The Ohio State University, 2013.

[91] Ebeida M S, Mitchell S A, Davidson A A et al. Efficient and good Delaunay meshes from random points. Computer-Aided Design, 2011, 43(11): 1506-1515.

[92] Guo J, Yan D M, Bao G, Dong W, Zhang X, Wonka P. Efficient triangulation of Poisson-disk sampled point sets. The Visual Computer, 2014, 30(6/7/8): 773-785.

[93] Chew L P. Guaranteed-quality triangular meshes. Technical Report, 89-983, Department of Computer Science, Cornell University, April 1989.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .
[3] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[4] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[5] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[6] Lian Lin; Zhang Yili; Tang Changjie;. A Non-Recursive Algorithm Computing Set Expressions[J]. , 1988, 3(4): 310 -316 .
[7] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[8] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[9] Jin Lingzi;. TrapML-A Metalanguage for Transformational Programming[J]. , 1990, 5(4): 388 -399 .
[10] Cai Shijie; Zhang Fuyan;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved