“Spoke-Darts for High-Dimensional Blue Noise Sampling” by Mitchell, Ebeida, Awad and Park

  • ©Scott A. Mitchell, Mohamed S. Ebeida, Muhammad A. Awad, and Chonhyon Park

Conference:


Type(s):


Title:

    Spoke-Darts for High-Dimensional Blue Noise Sampling

Session/Category Title:   Flattening, Unflattening and Sampling

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    Blue noise sampling has proved useful for many graphics applications, but remains underexplored in high-dimensional spaces due to the difficulty of generating distributions and proving properties about them. We present a blue noise sampling method with good quality and performance across different dimensions. The method, spoke-dart sampling, shoots rays from prior samples and selects samples from these rays. It combines the advantages of two major high-dimensional sampling methods: the locality of advancing front with the dimensionality-reduction of hyperplanes, specifically line sampling. We prove that the output sampling is saturated with high probability, with bounds on distances between pairs of samples and between any domain point and its nearest sample. We demonstrate spoke-dart applications for approximate Delaunay graph construction, global optimization, and robotic motion planning. Both the blue-noise quality of the output distribution and the adaptability of the intermediate processes of our method are useful in these applications.

References:


    1. Abdalla G. M. Ahmed, Till Niese, Hui Huang, and Oliver Deussen. 2017. An adaptive point sampler on a regular lattice. ACM Trans. Graph. 36, 4, Article 138 (July 2017), 13 pages. Google ScholarDigital Library
    2. Abdalla G. M. Ahmed, Hélène Perrier, David Coeurjolly, Victor Ostromoukhov, Jianwei Guo, Dong-Ming Yan, Hui Huang, and Oliver Deussen. 2016. Low-discrepancy blue noise sampling. ACM Trans. Graph. 35, 6, Article 247 (Nov. 2016), 13 pages. Google ScholarDigital Library
    3. Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Lévy, and Mathieu Desbrun. 2003. Anisotropic polygonal remeshing. ACM Trans. Graph. 22, 3 (July 2003), 485–493. Google ScholarDigital Library
    4. Muhammad A. Awad, Mohamed S. Ebeida, Scott A. Mitchell, Anjul Patney, Ahmad A. Rushdi, and Laura P. Swiler. 2016. SpokeDartsPublic Open-source Software. v. 1.0, https://github.com/samitch/SpokeDartsPublic. (2016).Google Scholar
    5. Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-constrained point distributions: A variant of lloyd’s method. ACM Trans. Graph. 28, 3, Article 86 (July 2009), Article 86, 8 pages. Google ScholarDigital Library
    6. C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. 1996. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4 (Dec. 1996), 469–483. Google ScholarDigital Library
    7. Jakob Bossek. 2017. smoof: Single- and multi-objective optimization test functions. The R Journal (2017). https://journal.r-project.org/archive/2017/RJ-2017-004/index.html.Google Scholar
    8. Robert Bridson. 2007. Fast Poisson disk sampling in arbitrary dimensions. In SIGGRAPH’07: ACM SIGGRAPH 2007 Sketches & Applications. 5. Google ScholarDigital Library
    9. John Burkardt. 2011. TEST OPT: Optimization of a scalar function test problems. (2011). http://people.sc.fsu.edu/ jburkardt/m_src/test_opt/test_opt.html.Google Scholar
    10. Jiating Chen, Xiaoyin Ge, Li-Yi Wei, Bin Wang, Yusu Wang, Huamin Wang, Yun Fei, Kang-Lai Qian, Jun-Hai Yong, and Wenping Wang. 2013. Bilateral blue noise sampling. ACM Trans. Graph. 32, 6, Article 216 (Nov. 2013), 11 pages. Google ScholarDigital Library
    11. David Cline, Stefan Jeschke, Anshuman Razdan, Kenric White, and Peter Wonka. 2009. Dart throwing on surfaces. In EGSR’09. 1217–1226. Google ScholarDigital Library
    12. Robert L. Cook. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1 (1986), 51–72. Google ScholarDigital Library
    13. Ioan A. Şucan, Mark Moll, and Lydia E. Kavraki. 2012. The open motion planning library. IEEE Robotics & Automation Magazine 19, 4 (2012), 72–82. http://ompl.kavrakilab.org.Google ScholarCross Ref
    14. Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6, Article 171 (Nov. 2012), Article 171, 11 pages. Google ScholarDigital Library
    15. Mark A. Z. Dippé and Erling Henry Wold. 1985. Antialiasing through stochastic sampling. In SIGGRAPH’85. 69–78. Google ScholarDigital Library
    16. Daniel Dunbar and Greg Humphreys. 2006. A spatial data structure for fast poisson-disk sample generation. ACM Trans. Graph. 25, 3 (July 2006), 503–508. Google ScholarDigital Library
    17. Rex A. Dwyer. 1989. Higher-dimensional voronoi diagrams in linear expected time. In Proceedings of the 5th Annual Symposium on Computational Geometry (SCG’89). ACM, New York, 326–333. Google ScholarDigital Library
    18. Mohamed S. Ebeida, Muhammad A. Awad, Xiaoyin Ge, Ahmed H. Mahmoud, Scott A. Mitchell, Patrick M. Knupp, and Li-Yi Wei. 2014. Improving spatial coverage while preserving blue noise of point sets. Computer-Aided Design 46 (January 2014), 25–36. Google ScholarDigital Library
    19. Mohamed S. Ebeida, Andrew A. Davidson, Anjul Patney, Patrick M. Knupp, Scott A. Mitchell, and John D. Owens. 2011. Efficient maximal poisson-disk sampling. ACM Trans. Graph. 30, 4, Article 49 (July 2011), 12 pages. Google ScholarDigital Library
    20. Mohamed S. Ebeida, Scott A. Mitchell, Anjul Patney, Andrew A. Davidson, and John D. Owens. 2012. A simple algorithm for maximal poisson-disk sampling in high dimensions. Comp. Graph. Forum 31, 2pt4 (2012), 785–794. Google ScholarDigital Library
    21. Mohamed S. Ebeida, Anjul Patney, Scott A. Mitchell, Keith R. Dalbey, Andrew A. Davidson, and John D. Owens. 2014. k-d darts: Sampling by k-dimensional flat searches. ACM Trans. Graph. 33, 1, Article 3 (Feb. 2014), 16 pages. Google ScholarDigital Library
    22. Raanan Fattal. 2011. Blue-noise point sampling using kernel density model. ACM Trans. Graph. 30, 4, Article 48 (July 2011), Article 48, 12 pages. Google ScholarDigital Library
    23. Manuel N. Gamito and Steve C. Maddock. 2009. Accurate multidimensional poisson-disk sampling. ACM Trans. Graph. 29, 1 (2009), 1–19. Google ScholarDigital Library
    24. Samuel Gerber, P. Bremer, Valerio Pascucci, and Ross Whitaker. 2010. Visual exploration of high dimensional scalar functions. IEEE Transactions on Visualization and Computer Graphics 16, 6 (2010), 1271–1280. Google ScholarDigital Library
    25. Daniel Heck, Thomas Schlömer, and Oliver Deussen. 2013. Blue noise sampling with controlled aliasing. ACM Trans. Graph. 32, 3, Article 25 (July 2013), 12 pages. Google ScholarDigital Library
    26. Reiner Horst, Panos M. Pardalos, and H. Edwin Romeijn. 2002. Handbook of Global Optimization. Vol. 2. Springer.Google Scholar
    27. Wenzel Jakob. 2010. Mitsuba Renderer. Retrieved from http://www.mitsuba-renderer.org.Google Scholar
    28. Momin Jamil and Xin-She Yang. 2013. A literature survey of benchmark functions for global optimization problems. Intl. Journal of Mathematical Modelling and Numerical Optimization 4, 2 (2013), 150–194.Google ScholarCross Ref
    29. Min Jiang, Yahan Zhou, Rui Wang, Richard Southern, and Jian Jun Zhang. 2015. Blue noise sampling using an SPH-based method. ACM Trans. Graph. 34, 6, Article 211 (Oct. 2015), 11 pages. Google ScholarDigital Library
    30. Donald R. Jones, Cary D. Perttunen, and Bruce E. Stuckman. 1993. Lipschitzian optimization without the lipschitz constant. Journal of Optimization Theory and Applications 79, 1 (1993), 157–181.Google ScholarDigital Library
    31. Thouis R. Jones. 2006. Efficient generation of poisson-disk sampling patterns. Journal of Graphics Tools 11, 2 (2006), 27–36.Google ScholarCross Ref
    32. Bhavya Kailkhura, Jayaraman J. Thiagarajan, Peer-Timo Bremer, and Pramod K. Varshney. 2016. Stair blue noise sampling. ACM Trans. Graph. 35, 6, Article 248 (Nov. 2016), 10 pages. Google ScholarDigital Library
    33. Alexander Keller, Simon Premoze, and Matthias Raab. 2012. Advanced (quasi) monte carlo methods for image synthesis. In ACM SIGGRAPH 2012 Courses (SIGGRAPH’12). Article 21, 46 pages. Google ScholarDigital Library
    34. Thomas Kollig and Alexander Keller. 2003. Efficient illumination by high dynamic range images. In EGRW’03. 45–50. http://dl.acm.org/citation.cfm?id=882404.882411 Google ScholarDigital Library
    35. Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, and Dani Lischinski. 2006. Recursive wang tiles for real-time blue noise. ACM Trans. Graph. 25, 3 (July 2006), 509–518. Google ScholarDigital Library
    36. James J. Kuffner and Steven M. Lavalle. 2000. RRT-connect: An efficient approach to single-query path planning. In Proceedings of the IEEE Conference on Robotics and Automation. 995–1001.Google Scholar
    37. Ares Lagae and Philip Dutré. 2005. A procedural object distribution function. ACM Trans. Graph. 24, 4 (2005), 1442–1461. Google ScholarDigital Library
    38. Ares Lagae and Philip Dutré. 2008. A comparison of methods for generating poisson disk distributions. Computer Graphics Forum 21, 1 (2008), 114–129.Google ScholarCross Ref
    39. S. M. LaValle and J. J. Kuffner. 2001. Randomized kinodynamic planning. International Journal of Robotics Research 20, 5 (2001), 378–400.Google ScholarCross Ref
    40. Kuan Yew Leong. 2016. Test functions for optimization. Retrieved from http://mathworks.com/matlabcentral/fileexchange/59737-test-functions.Google Scholar
    41. Hongwei Li, Li-Yi Wei, Pedro V. Sander, and Chi-Wing Fu. 2010. Anisotropic blue noise sampling. ACM Trans. Graph. 29, 6, Article 167 (Dec. 2010), Article 167, 12 pages. Google ScholarDigital Library
    42. Xiang-Yang Li, Shang-Hua Teng, and Alper Üngör. 2000. Biting: Advancing front meets sphere packing. Internat. J. Numer. Methods Engrg. 49, 1–2 (2000), 61–81.Google ScholarCross Ref
    43. Jianfei Liu. 1991. Automatic triangulation of N-dimensional euclidean domains. In Proceedings of CAD/Graphics’91. 238–241.Google Scholar
    44. Jianfei Liu, Shuixiang Li, and Yongqiang Chen. 2008. A fast and practical method to pack spheres for mesh generation. Acta Mechanica Sinica 24, 4 (2008), 439–447.Google ScholarCross Ref
    45. S. Lloyd. 1983. An optimization approach to relaxation labeling algorithms. Image and Vision Computing 1, 2 (1983).Google Scholar
    46. R. M. Mersereau and A. V. Oppenheim. 1974. Digital reconstruction of multidimensional signals from their projections. Proc. IEEE 62, 10 (Oct 1974), 1319–1338.Google ScholarCross Ref
    47. Gary L. Miller and Donald R. Sheehy. 2013. A new approach to output-sensitive voronoi diagrams and delaunay triangulations. In SoCG’13. 281–288. Google ScholarDigital Library
    48. Gary L. Miller, Donald R. Sheehy, and Ameya Velingker. 2013. A fast algorithm for well-spaced points and approximate delaunay graphs. In SoCG’13. 289–298. Google ScholarDigital Library
    49. Don P. Mitchell. 1987. Generating antialiased images at low sampling densities. In SIGGRAPH’87. 65–72. Google ScholarDigital Library
    50. Scott A. Mitchell, Alexander Rand, Mohamed S. Ebeida, and Chadrajit Bajaj. 2012. Variable radii poisson-disk sampling, extended version. In Proceedings of the 24th Canadian Conference on Computational Geometry. 1–9. http://2012.cccg.ca/papers/paper15-extended.pdf.Google Scholar
    51. Marius Muja and David G. Lowe. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP (1). 331–340.Google Scholar
    52. Mervin E. Muller. 1959. A note on a method for generating points uniformly on n-dimensional spheres. Commun. ACM 2, 4 (April 1959), 19–20. Google ScholarDigital Library
    53. Harald Niederreiter. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM. Google ScholarDigital Library
    54. Mark H. Overmars. 2005. Path planning for games. In Proceedings of the 3rd International Game Design and Technology Workshop. 29–33.Google Scholar
    55. A. Cengiz Öztireli, Marc Alexa, and Markus Gross. 2010. Spectral sampling of manifolds. ACM Trans. Graph. 29, 6, Article 168 (Dec. 2010), 8 pages. Google ScholarDigital Library
    56. A. Cengiz Öztireli and Markus Gross. 2012. Analysis and synthesis of point distributions based on pair correlation. ACM Trans. Graph. 31, 6, Article 170 (Nov. 2012), Article 170, 10 pages. Google ScholarDigital Library
    57. Jia Pan, Liangjun Zhang, Ming C. Lin, and Dinesh Manocha. 2010. A hybrid approach for simulating human motion in constrained environments. Computer Animation and Virtual Worlds 21, 3–4 (2010), 137–149. Google ScholarDigital Library
    58. Chonhyon Park, Jia Pan, and Dinesh Manocha. 2016. Parallel motion planning using poisson-disk sampling. IEEE Transactions on Robotics (2016). Google ScholarDigital Library
    59. Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov. 2015. Variance analysis for monte carlo integration. ACM Trans. Graph. 34, 4, Article 124 (July 2015), 14 pages. Google ScholarDigital Library
    60. Bernhard Reinert, Tobias Ritschel, Hans-Peter Seidel, and Iliyan Georgiev. 2016. Projective blue-noise sampling. Computer Graphics Forum 35, 1 (2016), 285–295. Google ScholarDigital Library
    61. Hagit Schechter and Robert Bridson. 2012. Ghost SPH for animating water. ACM Trans. Graph. 31, 4, Article 61 (2012), 8 pages. Google ScholarDigital Library
    62. Thomas Schlömer and Oliver Deussen. 2011. Accurate spectral analysis of two-dimensional point sets. Journal of Graphics, GPU, and Game Tools 15, 3 (2011), 152–160.Google ScholarCross Ref
    63. Peter Shirley. 1991. Discrepancy as a quality measure for sample distributions. In Eurographics’91. 183–194.Google Scholar
    64. Bruno O. Shubert. 1972. A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9, 3 (1972), 379–388.Google ScholarDigital Library
    65. Kartic Subr and Jan Kautz. 2013. Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration. ACM Trans. Graph. 32, 4, Article 128 (July 2013), 12 pages. Google ScholarDigital Library
    66. Xin Sun, Kun Zhou, Jie Guo, Guofu Xie, Jingui Pan, Wencheng Wang, and Baining Guo. 2013. Line segment sampling with blue-noise properties. ACM Trans. Graph. 32, 4, Article 127 (July 2013), 14 pages. Google ScholarDigital Library
    67. Robert A. Ulichney. 1988. Dithering with blue noise. Proc. IEEE 76, 1 (1988), 56–79.Google ScholarCross Ref
    68. Tong Wang and Reiji Suda. 2017. Fast maximal poisson-disk sampling by randomized tiling. In HPG’17. Article 16, 10 pages. Google ScholarDigital Library
    69. Li-Yi Wei and Rui Wang. 2011. Differential domain analysis for non-uniform sampling. ACM Trans. Graph. 30, 4, Article 50 (July 2011), 10 pages. Google ScholarDigital Library
    70. Eric W. Weisstein. 1999. Hypersphere Packing. Retrieved from http://mathworld.wolfram.com/HyperspherePacking.html.Google Scholar
    71. Jeroen A. S. Witteveen and Gianluca Iaccarino. 2012. Simplex stochastic collocation with random sampling and extrapolation for nonhypercube probability spaces. SIAM Journal on Scientific Computing 34, 2 (2012), A814–A838. Google ScholarDigital Library
    72. Katsu Yamane, James J. Kuffner, and Jessica K. Hodgins. 2004. Synthesizing animations of human manipulation tasks. ACM Trans. Graph. 23, 3 (2004), 532–539. Google ScholarDigital Library
    73. Dong-Ming Yan and Peter Wonka. 2013. Gap processing for adaptive maximal poisson-disk sampling. ACM Trans. Graph. 32, 5, Article 148 (Oct. 2013), 15 pages. Google ScholarDigital Library
    74. Xin-She Yang. 2010. Appendix A: Test Problems in Optimization. John Wiley and Sons, Inc., 261–266.Google Scholar

ACM Digital Library Publication:


Overview Page: