Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Jiang, Min; Zhou, Y.; Wang, R.; Southern, Richard; Zhang, Jian J. (2015)
Languages: English
Types: Article

Classified by OpenAIRE into

arxiv: Astrophysics::Cosmology and Extragalactic Astrophysics, Astrophysics::Galaxy Astrophysics
We propose a novel algorithm for blue noise sampling inspired by the Smoothed Particle Hydrodynamics (SPH) method. SPH is a well-known method in fluid simulation -- it computes particle distributions to minimize the internal pressure variance. We found that this results in sample points (i.e., particles) with a high quality blue-noise spectrum. Inspired by this, we tailor the SPH method for blue noise sampling. Our method achieves fast sampling in general dimensions for both surfaces and volumes. By varying a single parameter our method can generate a variety of blue noise samples with different distribution properties, ranging from Lloyd's relaxation to Capacity Constrained Voronoi Tessellations ({CCVT}). Our method is fast and supports adaptive sampling and multi-class sampling. We have also performed experimental studies of the SPH kernel and its influence on the distribution properties of samples. We demonstrate with examples that our method can generate a variety of controllable blue noise sample patterns, suitable for applications such as image stippling and re-meshing.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • ADAMI, S., HU, X. Y., AND ADAMS, N. A. 2013. A transport-velocity formulation for smoothed particle hydrodynamics. Journal of Computational Physics 241 (May), 292-307.
    • ADAMS, B., PAULY, M., KEISER, R., AND GUIBAS, L. J. 2007. Adaptively sampled particle fluids. ACM Trans. Graph. 26, 3 (July), 48:1-48:7.
    • AKINCI, N., IHMSEN, M., AKINCI, G., SOLENTHALER, B., AND TESCHNER, M. 2012. Versatile rigid-fluid coupling for incompressible SPH. ACM Trans. Graph. 31, 4 (July), 62:1-62:8.
    • AKINCI, N., AKINCI, G., AND TESCHNER, M. 2013. Versatile surface tension and adhesion for SPH fluids. ACM Trans. Graph. 32, 6 (Nov.), 182:1-182:8.
    • ALLIEZ, P., COHEN-STEINER, D., YVINEC, M., AND DESBRUN, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3 (July), 617-625.
    • BALZER, M., SCHL O¨MER, T., AND DEUSSEN, O. 2009. Capacity-constrained point distributions: A variant of Lloyd's method. ACM Trans. Graph. 28, 3 (July), 86:1-86:8.
    • BERNARDINI, F., MITTLEMAN, J., RUSHMEIER, H., SILVA, C., AND TAUBIN, G. 1999. The ball-pivoting algorithm for surface reconstruction. IEEE Transactions on Visualization and Computer Graphics 5, 4 (Oct.), 349-359.
    • BOWERS, J., WANG, R., WEI, L.-Y., AND MALETZ, D. 2010. Parallel poisson disk sampling with spectrum analysis on surfaces. ACM Trans. Graph. 29, 6 (Dec.), 166:1-166:10.
    • CHEN, Z., YUAN, Z., CHOI, Y.-K., LIU, L., AND WANG, W. 2012. Variational blue noise sampling. IEEE Transactions on Visualization and Computer Graphics 18, 10 (Oct.), 1784-1796.
    • CHEN, J., GE, X., WEI, L.-Y., WANG, B., WANG, Y., WANG, H., FEI, Y., QIAN, K.-L., YONG, J.-H., AND WANG, W. 2013. Bilateral blue noise sampling. ACM Trans. Graph. 32, 6 (Nov.), 216:1-216:11.
    • COOK, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1 (Jan.), 51-72.
    • DE GOES, F., BREEDEN, K., OSTROMOUKHOV, V., AND DESBRUN, M. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6 (Nov.), 171:1-171:11.
    • DE GOES, F., WALLEZ, C., HUANG, J., PAVLOV, D., AND DESBRUN, M. 2015. Power particles: An incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4 (July), 50:1-50:11.
    • DIPP E´, M. A. Z., AND WOLD, E. H. 1985. Antialiasing through stochastic sampling. SIGGRAPH Comput. Graph. 19, 3 (July), 69-78.
    • DU, Q., AND EMELIANENKO, M. 2006. Acceleration schemes for computing centroidal Voronoi tessellations. Numerical Linear Algebra with Applications 13, 2-3, 173-192.
    • FATTAL, R. 2011. Blue-noise point sampling using kernel density model. ACM Trans. Graph. 30, 4 (July), 48:1-48:12.
    • GINGOLD, R. A., AND MONAGHAN, J. J. 1977. Smoothed particle hydrodynamics-theory and application to non-spherical stars. Monthly Notices of the Royal Astronomical Society 181, 375- 389.
    • GIRAULT, V., AND RAVIART, P. 1986. Finite element methods for Navier-Stokes equations: theory and algorithms. Springer series in computational mathematics. Springer-Verlag.
    • GUO, J., YAN, D.-M., JIA, X., AND ZHANG, X. 2015. Efficient maximal Poisson-disk sampling and remeshing on surfaces. Computers and Graphics 46, 72 - 79. Shape Modeling International 2014.
    • HARADA, T., TANAKA, M., KOSHIZUKA, S., AND KAWAGUCHI, Y. 2007. Real-time coupling of fluids and rigid bodies. APCOM in conjunction with EPMESC XI, 3-6.
    • HECK, D., SCHL O¨MER, T., AND DEUSSEN, O. 2013. Blue noise sampling with controlled aliasing. ACM Trans. Graph. 32, 3 (July), 25:1-25:12.
    • H E´RAULT, A., BILOTTA, G., AND DALRYMPLE, R. 2010. SPH on GPU with CUDA. Journal of Hydraulic Research 48, 1, 74-79.
    • HOETZLEIN, R. C. 2014. Fast fixed-radius nearest neighbors: Interactive million-particle fluids. In GPU Technology Conference.
    • IHMSEN, M., CORNELIS, J., SOLENTHALER, B., HORVATH, C., AND TESCHNER, M. 2014. Implicit incompressible SPH. IEEE Transactions on Visualization and Computer Graphics 20, 3 (Mar.), 426-435.
    • IHMSEN, M., ORTHMANN, J., SOLENTHALER, B., KOLB, A., AND TESCHNER, M. 2014. SPH fluids in computer graphics. In Eurographics 2014 - State of the Art Reports.
    • LI, H., NEHAB, D., WEI, L.-Y., SANDER, P. V., AND FU, C.-W. 2010. Fast capacity constrained voronoi tessellation. I3D '10, 13:1-13:7.
    • LLOYD, S. 1982. Least squares quantization in PCM. IEEE Trans. Inf. Theor. 28, 2 (Sept.), 129-137.
    • MACKLIN, M., AND M U¨LLER, M. 2013. Position based fluids. ACM Trans. Graph. 32, 4 (July), 104:1-104:12.
    • MCCOOL, M., AND FIUME, E. 1992. Hierarchical Poisson disk sampling distributions. In Proceedings of the Conference on Graphics Interface '92, 94-105.
    • MITCHELL, D. P. 1987. Generating antialiased images at low sampling densities. SIGGRAPH Comput. Graph. 21, 4 (Aug.), 65-72.
    • MONAGHAN, J. J. 1994. Simulating free surface flows with SPH. J. Comput. Phys. 110, 2 (Feb.), 399-406.
    • MONAGHAN, J. J. 2005. Smoothed particle hydrodynamics. Reports on Progress in Physics 68, 8, 1703.
    • M U¨LLER, M., CHARYPAR, D., AND GROSS, M. 2003. Particlebased fluid simulation for interactive applications. SCA '03, 154-159.
    • O¨ ZTIRELI, A. C., AND GROSS, M. 2012. Analysis and synthesis of point distributions based on pair correlation. ACM Trans. Graph. 31, 6 (Nov.), 170:1-170:10.
    • SCHECHTER, H., AND BRIDSON, R. 2012. Ghost SPH for animating water. ACM Trans. Graph. 31, 4 (July), 61:1-61:8.
    • SOLENTHALER, B., AND PAJAROLA, R. 2009. Predictivecorrective incompressible SPH. ACM Trans. Graph. 28, 3 (July), 40:1-40:6.
    • SUBR, K., AND KAUTZ, J. 2013. Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration. ACM Trans. Graph. 32, 4 (July), 128:1-128:12.
    • ULICHNEY, R. 1987. Digital Halftoning. MIT Press.
    • WACHTEL, F., PILLEBOUE, A., COEURJOLLY, D., BREEDEN, K., SINGH, G., CATHELIN, G., DE GOES, F., DESBRUN, M., AND OSTROMOUKHOV, V. 2014. Fast tile-based adaptive sampling with user-specified Fourier spectra. ACM Trans. Graph. 33, 4 (July), 56:1-56:11.
    • WEI, L.-Y., AND WANG, R. 2011. Differential domain analysis for non-uniform sampling. ACM Trans. Graph. 30, 4 (July), 50:1-50:10.
    • WEI, L.-Y. 2008. Parallel poisson disk sampling. ACM Trans. Graph. 27, 3 (Aug.), 20:1-20:9.
    • WEI, L.-Y. 2010. Multi-class blue noise sampling. ACM Trans. Graph. 29, 4 (July), 79:1-79:8.
    • XU, Y., LIU, L., GOTSMAN, C., AND GORTLER, S. J. 2011. Capacity-constrained delaunay triangulation for point distributions. Computers and Graphics 35, 3, 510 - 516.
    • XU, Y., HU, R., GOTSMAN, C., AND LIU, L. 2012. Blue noise sampling of surfaces. Computers and Graphics 36, 4, 232 - 240.
    • ZHOU, Y., HUANG, H., WEI, L.-Y., AND WANG, R. 2012. Point sampling with general noise spectrum. ACM Trans. Graph. 31, 4 (July), 76:1-76:11.
  • No related research data.
  • No similar publications.

Share - Bookmark

Funded by projects

  • NSF | RI: Small: Collaborative Re...

Cite this article