A Survey of Blue-Noise Sampling and Its Applications

详细信息    查看全文

• 作者：Dong-Ming Yan ; Jian-Wei Guo ; Bin Wang&#8230
• 关键词：blue ; noise sampling ; Poisson ; disk sampling ; Lloyd relaxation ; rendering ; remeshing
• 刊名：Journal of Computer Science and Technology
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：30
• 期：3
• 页码：439-452
• 全文大小：12,196 KB
• 参考文献：[1]Mitchell D P. Generating antialiased images at low sampling densities. In Proc. the 14th ACM SIGGRAPH, July 1987, pp.65鈥?2.
  [2]Fattal R. Blue-noise point sampling using kernel density model. ACM Trans. Graphics, 2011, 30(4): 48:1鈥?8: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鈥?1:8.
  [6]Lagae A, Dutr茅 P. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum, 2008, 27(1): 114鈥?29.
  [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鈥?418.View Article
  [9]Ostling A, Harte J, Green J. Self-similarity and clustering in the spatial distribution of species. Science, 2000, 290(5492): 671鈥?71.View Article
  [10]Lau D L, Ulichney R, Arce G R. Blue and green noise halftoning models. IEEE Signal Processing Magazine, 2003, 20(4): 28鈥?8View Article
  [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鈥?9: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鈥?94View Article
  [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鈥?0:9.
  [16]Gamito M N, Maddock S C. Accurate multidimensional Poisson-disk sampling. ACM Trans. Graphics, 2009, 29(1): 8:1鈥?: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鈥?2.View Article
  [19]Dunbar D, Humphreys G. A spatial data structure for fast Poisson-disk sample generation. ACM Trans. Graphics, 2006, 25(3): 503鈥?08.View Article
  [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鈥?82.View Article
  [22]Wei L Y. Multi-class blue noise sampling. ACM Trans. Graphics, 2010, 29(4): 79:1鈥?9:8
  [23]Ip C Y, Yal赂cin 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鈥?6.View Article
  [25]Yan D M, Wonka P. Gap processing for adaptive maximal Poisson-disk sampling. ACM Trans. Graphics, 2013, 32(5): 148:1鈥?48: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鈥?18.View Article
  [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鈥?226View Article
  [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鈥?66: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鈥?24.View Article
  [32]Geng B, Zhang H, Wang H, Wang G. Approximate Poisson disk sampling on mesh. Science China Information Sciences, 2013, 56(9): 1鈥?2.View Article
  [33]Yan D M, Wonka P. Adaptive maximal Poisson-disk sampling on surfaces. In Proc. ACM SIGGRAPH Asia Technical Briefs, Nov. 28鈥揇ec. 1, 2012, pp.21:1鈥?1: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鈥?427.View Article
  [35]Medeiros E, Ingrid L, Pesco S, Silva C. Fast adaptive blue noise on polygonal surfaces. Graphical Models, 2014, 76(1): 17鈥?9.View Article
  [36]Guo J, Yan D M, Jia X, Zhang X. Efficient maximal Poisson-disk sampling and remeshing on surfaces. Computers & Graphics, 2015, 46: 72鈥?9.View Article
  [37]Yan D M, Wallner J, Wonka P. Unbiased sampling and meshing of isosurfaces. IEEE Trans. Vis. and Comp. Graphics, 2014, 20(11): 1579鈥?589.View Article
  [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鈥?437.View Article
  [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鈥?4.View Article
  [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鈥?454.
  [43]Lloyd S P. Least squares quantization in PCM. IEEE Transactions on Information Theory, 1982, 28(2): 129鈥?37.View Article MATH MathSciNet
  [44]Du Q, Faber V, Gunzburger M. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Review, 1999, 41(4): 637鈥?76.View Article MATH MathSciNet
  [45]Alliez P, de Verdi`ere E C, Devillers O, Isenburg M. Centroidal Voronoi diagrams for isotropic surface remeshing. Graphical Models, 2005, 67(3): 204鈥?31.View Article MATH
  [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鈥?96.View Article MATH MathSciNet
  [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鈥?81.View Article
  [48]Balzer M Schl枚mer T, Deussen O. Capacity-constrained point distributions: A variant of Lloyd鈥檚 method. ACM Trans. Graphics, 2009, 28(6): 86:1鈥?6: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鈥?16.View Article
  [51]Xu Y, Hu R, Gotsman C, Liu L. Blue noise sampling of surfaces. Computers & Graphics, 2012, 36(4): 232鈥?40.View Article
  [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鈥?796.View Article
  [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鈥?01:17.
  [54]de Goes F, Breeden K, Ostromoukhov V, Desbrun M. Blue noise through optimal transport. ACM Trans. Graphic, 2012, 31(6): 171:1鈥?71: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鈥?3.
  [56]Chen R, Gotsman C. Parallel bluenoise sampling by constrained farthest point optimization. Computer Graphics Forum, 2012, 31(5): 1775鈥?785.View Article
  [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鈥?76.View Article
  [58]脰ztireli A C, Alexa M, Gross M. Spectral sampling of manifolds. ACM Trans. Graphics, 2010, 29(6): 168:1鈥?68:8.
  [59]Chen J, Ge X, Wei L W et al. Bilateral blue noise sampling. ACM Trans. Graphics, 2013, 32(6): 216:1鈥?16: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鈥?6.View Article
  [61]Hiller S, Deussen O, Keller A. Tiled blue noise samples. In Proc. the 16th Vision Modeling and Visualization Conference, October 2001, pp.265鈥?72.
  [62]Wang H. Proving theorems by pattern recognition, II. Bell Systems Technical Journal, 1961, 40(1): 1鈥?2.View Article
  [63]Wang H. Games, logic and computers. Scientific American, 1965, 213(5): 98鈥?06.View Article
  [64]Lagae A, Dutr茅 P. A procedural object distribution function. ACM Trans. Graphics, 2005, 24(4): 1442鈥?461.View Article
  [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鈥?18.View Article
  [66]Ostromoukhov V, Donohue C, Jodoin P M. Fast hierarchical importance sampling with blue noise properties. ACM Trans. Graphics, 2004, 23(3): 488鈥?95.View Article
  [67]Ostromoukhov V. Sampling with polyominoes. ACM Trans. Graphics, 2007, 26(3): 78:1鈥?8: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鈥?6:11.
  [69]Kalantari N K, Sen P. Fast generation of approximate blue noise point sets. Computer Graphics Forum, 2012, 31(4): 1529鈥?535.View Article
  [70]Kalantari N K, Sen P. Efficient computation of blue noise point sets through importance sampling. Computer Graphics Forum, 2011, 30(4): 1215鈥?221.View Article
  [71]Zhou Y, Huang H, Wei L Y, Wang R. Point sampling with general noise spectrum. ACM Trans. Graph., 2012, 31(4): 76:1鈥?6:11.
  [72]Heck D, Schl枚mer T, Deussen O. Blue noise sampling with controlled aliasing. ACM Trans. Graphics, 2013, 32(3): 25:1鈥?5: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鈥?27: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鈥?:16.
  [77]Feng L, Hotz I, Hamann B, Joy K I. Anisotropic noise samples. IEEE Trans. Vis. and Comp. Graphics, 2008, 14(2): 342鈥?54.View Article
  [78]Li H, Wei L Y, Sander P, Fu C W. Anisotropic blue noise sampling. ACM Trans. Graphics, 2010, 29(6): 167:1鈥?67: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鈥?157.View Article
  [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鈥?60.View Article
  [82]脰ztireli A C, Gross M. Analysis and synthesis of point distributions based on pair correlation. ACM Trans. Graphics, 2012, 31(6): 170:1鈥?70: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鈥?28: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鈥?74.View Article
  [87]Spencer B, Jones M W. Progressive photon relaxation. ACM Trans. Graphics, 2013, 32(1): 7:1鈥?: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鈥?7.View Article
  [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鈥?515.View Article
  [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鈥?85.
  [93]Chew L P. Guaranteed-quality triangular meshes. Technical Report, 89鈥?83, Department of Computer Science, Cornell University, April 1989.
  
• 作者单位：Dong-Ming Yan (1) (2)
  Jian-Wei Guo (2)
  Bin Wang (3)
  Xiao-Peng Zhang (2)
  Peter Wonka (1) (4)
  
  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.
  
• 刊物类别：Computer Science
• 刊物主题：Computer Science, general
  Software Engineering
  Theory of Computation
  Data Structures, Cryptology and Information Theory
  Artificial Intelligence and Robotics
  Information Systems Applications and The Internet
  Chinese Library of Science
  
• 出版者：Springer Boston
• ISSN：1860-4749

文摘

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.