“Power particles: an incompressible fluid solver based on power diagrams”

  • ©Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun



Session Title:

    Wave-Particle Fluidity


    Power particles: an incompressible fluid solver based on power diagrams




    This paper introduces a new particle-based approach to incompressible fluid simulation. We depart from previous Lagrangian methods by considering fluid particles no longer purely as material points, but also as volumetric parcels that partition the fluid domain. The fluid motion is described as a time series of well-shaped power diagrams (hence the name power particles), offering evenly spaced particles and accurate pressure computations. As a result, we circumvent the typical excess damping arising from kernel-based evaluations of internal forces or density without having recourse to auxiliary Eulerian grids. The versatility of our solver is demonstrated by the simulation of multiphase flows and free surfaces.


    1. Adams, B., Pauly, M., Keiser, R., and Guibas, L. J. 2007. Adaptively sampled particle fluids. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    2. Akinci, N., Akinci, G., and Teschner, M. 2013. Versatile surface tension and adhesion for SPH fluids. ACM Trans. Graph. 32, 6. Google ScholarDigital Library
    3. Alduan, I., and Otaduy, M. A. 2011. SPH granular flow with friction and cohesion. In Symp. on Comp. Anim., 219–228. Google ScholarDigital Library
    4. Ando, R., Thürey, N., and Wojtan, C. 2013. Highly adaptive liquid simulations on tetrahedral meshes. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
    5. Aurenhammer, F., Hoffmann, F., and Aronov, B. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1, 61–76.Google ScholarCross Ref
    6. Aurenhammer, F. 1987. Power diagrams: properties, algorithms and applications. SIAM J. on Computing 16(1), 78–96. Google ScholarDigital Library
    7. Batty, C., and Bridson, R. 2008. Accurate viscous free surfaces for buckling, coiling, and rotating liquids. In Symp. on Comp. Anim., 219–228. Google ScholarDigital Library
    8. Becker, M., and Teschner, M. 2007. Weakly compressible SPH for free surface flows. In Symp. on Comp. Anim., 209–217. Google ScholarDigital Library
    9. Bodin, K., Lacoursiere, C., and Servin, M. 2012. Constraint Fluids. IEEE Trans. Vis. Comput. Graphics 18, 516–526. Google ScholarDigital Library
    10. Boyd, L., and Bridson, R. 2012. MultiFLIP for energetic two-phase fluid simulation. ACM Trans. Graph. 31, 2. Google ScholarDigital Library
    11. Brackbill, J., Kothe, D., and Ruppel, H. 1988. FLIP: A low-dissipation, particle-in-cell method for fluid flow. Computer Physics Communications 48, 1, 25–38.Google ScholarCross Ref
    12. Bridson, R. 2008. Fluid Simulation for Computer Graphics. AK Peters/CRC Press. Google ScholarDigital Library
    13. Brochu, T., Batty, C., and Bridson, R. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph. 29, 4. Google ScholarDigital Library
    14. Busaryev, O., Dey, T., Wang, H., and Ren, Z. 2012. Animating bubble interactions in a liquid foam. ACM Trans. Graph. 31, 4. Google ScholarDigital Library
    15. CGAL, 2015. Computational Geometry Algorithms Library (release 4.5). http://www.cgal.org.Google Scholar
    16. Clausen, P., Wicke, M., Shewchuk, J., and O’Brien, J. 2013. Simulating liquids and solid-liquid interactions with lagrangian meshes. ACM Trans. Graph. 32, 2. Google ScholarDigital Library
    17. Clavet, S., Beaudoin, P., and Poulin, P. 2005. Particle-based viscoelastic fluid simulation. In Symp. on Comp. Anim., 219–228. Google ScholarDigital Library
    18. Cornelis, J., Ihmsen, M., Peer, A., and Teschner, M. 2014. IISPH-FLIP for incompressible fluids. Comp. Graph. Forum 33, 2. Google ScholarDigital Library
    19. Cummins, S. J., and Rudman, M. 1999. An SPH projection method. J. Comp. Physics 152, 2, 584–607. Google ScholarDigital Library
    20. de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6. Google ScholarDigital Library
    21. de Goes, F., Alliez, P., Owhadi, H., and Desbrun, M. 2013. On the equilibrium of simplicial masonry structures. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
    22. Desbrun, M., and Gascuel, M.-P. 1996. Smoothed Particles: A new paradigm for animating highly deformable bodies. In EG Computer Animation Symp., 61–76. Google ScholarDigital Library
    23. Ellero, M., Serrano, M., and Español, P. 2007. Incompressible Smoothed Particle Hydrodynamics. J. Comp. Physics 226, 2, 1731–1752. Google ScholarDigital Library
    24. Enright, D., Losasso, F., and Fedkiw, R. 2005. A fast and accurate semi-Lagrangian particle level set method. Comput. Struct. 83, 6-7, 479–490. Google ScholarDigital Library
    25. Erleben, K., Misztal, M. K., and BÆrentzen, J. A. 2011. Mathematical foundation of the optimization-based fluid animation method. In Symp. on Comp. Anim., 101–110. Google ScholarDigital Library
    26. Feldman, B. E., O’Brien, J. F., Klingner, B. M., and Goktekin, T. G. 2005. Fluids in deforming meshes. In Symp. on Comp. Anim., 255–259. Google ScholarDigital Library
    27. Golin, M. J., and Na, H. 2003. On the average complexity of 3D Voronoi diagrams of random points on convex polytopes. Computational Geometry 25, 3, 197–231. Google ScholarDigital Library
    28. Harlow, F. H. 1963. The particle-in-cell method for numerical solution of problems in fluid dynamics. Experimental arithmetic, high-speed computations and mathematics.Google Scholar
    29. He, X., Liu, N., Li, S., Wang, H., and Wang, G. 2012. Local Poisson SPH for viscous incompressible fluids. Comp. Graph. Forum 31, 6, 1948–1958. Google ScholarDigital Library
    30. Hietel, D., Steiner, K., and Struckmeier, J. 2000. A finite-volume particle method for compressible flows. Math. Models Methods Appl. Sci. 10, 9, 1363–1382.Google ScholarCross Ref
    31. Hong, J.-M., and Kim, C.-H. 2005. Discontinuous fluids. ACM Trans. Graph. 24, 3. Google ScholarDigital Library
    32. Hu, X. Y., and Adams, N. A. 2007. An incompressible multiphase SPH method. J. Comp. Physics 227, 1, 264–278. Google ScholarDigital Library
    33. Ihmsen, M., Akinci, N., Becker, M., and Teschner, M. 2011. A parallel SPH implementation on multi-core CPUs. Comp. Graph. Forum 30, 1, 99–112.Google ScholarCross Ref
    34. Ihmsen, M., Cornelis, J., Solenthaler, B., Horvath, C., and Teschner, M. 2013. Implicit Incompressible SPH. IEEE Trans. Vis. Comput. Graphics 99. Google ScholarDigital Library
    35. Ihmsen, M., Orthmann, J., Solenthaler, B., Kolb, A., and Teschner, M. 2014. SPH fluids in computer graphics. Eurographics STAR Report.Google Scholar
    36. Irving, G., Schroeder, C., and Fedkiw, R. 2007. Volume conserving finite element simulations of deformable models. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    37. Kang, N., and Sagong, D. 2014. Incompressible SPH using the divergence-free condition. Comp. Graph. Forum 33, 7, 219–228. Google ScholarDigital Library
    38. Klingner, B. M., Feldman, B. E., Chentanez, N., and O’Brien, J. F. 2006. Fluid animation with dynamic meshes. ACM Trans. Graph. 25, 3. Google ScholarDigital Library
    39. Lee, H., and Han, S. 2010. Solving the shallow water equations using 2D SPH particles for interactive applications. The Visual Computer 26, 6-8, 865–872. Google ScholarDigital Library
    40. Liu, Y., Hao, P., Snyder, J., Wang, W., and Guo, B. 2013. Computing self-supporting surfaces by regular triangulation. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
    41. Lloyd, S. 1982. Least squares quantization in PCM. IEEE Trans. Inf. Theory 28, 2, 129–137. Google ScholarDigital Library
    42. Losasso, F., Talton, J., Kwatra, N., and Fedkiw, R. 2008. Two-way coupled SPH and particle level set fluid simulation. IEEE Trans. Vis. Comput. Graphics 14, 4, 797–804. Google ScholarDigital Library
    43. Lucy, L. B. 1977. A numerical approach to the testing of the fission hypothesis. Astronomical Journal 82, 1013–1024.Google ScholarCross Ref
    44. Macklin, M., and Müller, M. 2013. Position based fluids. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
    45. Misztal, M., Erleben, K., Bargteil, A., Fursund, J., Christensen, B., Baerentzen, J., and Bridson, R. 2013. Multiphase flow of immiscible fluids on unstructured moving meshes. IEEE Trans. Vis. Comput. Graphics 20, 1. Google ScholarDigital Library
    46. Monaghan, J. 2000. SPH without a tensile instability. J. Comp. Physics 159, 2, 290–311. Google ScholarDigital Library
    47. Monaghan, J. J. 2005. Smoothed Particle Hydrodynamics. Reports on Progress in Physics 68, 1703–1759.Google ScholarCross Ref
    48. Mullen, P., Crane, K., Pavlov, D., Tong, Y., and Desbrun, M. 2009. Energy-preserving integrators for fluid animation. ACM Trans. Graph. 28, 3. Google ScholarDigital Library
    49. Mullen, P., Memari, P., de Goes, F., and Desbrun, M. 2011. HOT: Hodge-Optimized Triangulations. ACM Trans. Graph. 30, 4. Google ScholarDigital Library
    50. Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. In Symp. on Comp. Anim., 154–159. Google ScholarDigital Library
    51. Museth, K. 2013. VDB: High-resolution sparse volumes with dynamic topology. ACM Trans. Graph. 32, 3. Google ScholarDigital Library
    52. Oñate, E., Idelsohn, S., del Pin, F., and Aubry, R. 2004. The Particle Finite Element Method: An Overview. Int. J. Comp. Meth. 1, 2, 267–307.Google ScholarCross Ref
    53. Premože, S., Tasdizen, T., Bigler, J., Lefohn, A., and Whitaker, R. T. 2003. Particle-based simulation of fluids. Comp. Graph. Forum 22, 3, 401–410.Google ScholarCross Ref
    54. Raveendran, K., Wojtan, C., and Turk, G. 2011. Hybrid Smoothed Particle Hydrodynamics. In Symp. on Comp. Anim., 33–42. Google ScholarDigital Library
    55. Ren, B., Li, C., Yan, X., Lin, M. C., Bonet, J., and Hu, S.-M. 2014. Multiple-fluid sph simulation using a mixture model. ACM Trans. Graph. 33, 5. Google ScholarDigital Library
    56. Rycroft, C. H. 2009. Voro++: A three-dimensional Voronoi cell library in C++. Chaos: An Interdisciplinary Journal of Non-linear Science 19, 4.Google Scholar
    57. Schechter, H., and Bridson, R. 2012. Ghost SPH for animating water. ACM Trans. Graph. 31, 4. Google ScholarDigital Library
    58. Serrano, M., Español, P., and Zúniga, I. 2005. Voronoi fluid particle model for Euler equations. J. Statistical Physics 121, 133–147.Google ScholarCross Ref
    59. Shadloo, M. S., Zainali, A., Sadek, S. H., and Yildiz, M. 2011. Improved incompressible Smoothed Particle Hydrodynamics method for simulating flow around bluff bodies. Comput. Methods in Appl. Mech. Eng. 200, 9-12, 1008–1020.Google ScholarCross Ref
    60. Shao, S., and Lo, E. Y. 2003. Incompressible SPH method for simulating Newtonian and non-Newtonian flows with a free surface. Advances in Water Resources 26, 7, 787–800.Google ScholarCross Ref
    61. Side Effects, 2014. Houdini engine. http://www.sidefx.com.Google Scholar
    62. Sin, F., Bargteil, A. W., and Hodgins, J. K. 2009. A point-based method for animating incompressible flow. In Symp. on Comp. Anim., 247–255. Google ScholarDigital Library
    63. Solenthaler, B., and Pajarola, R. 2008. Density contrast SPH interfaces. In Symp. on Comp. Anim., 211–218. Google ScholarDigital Library
    64. Solenthaler, B., and Pajarola, R. 2009. Predictive-corrective incompressible SPH. ACM Trans. Graph. 28, 3. Google ScholarDigital Library
    65. Solenthaler, B., Bucher, P., Chentanez, N., Mller, M., and Gross, M. 2011. SPH-based shallow water simulation. In VRIPHYS, 39–46.Google Scholar
    66. Springel, V. 2010. E pur si muove: Galilean-invariant cosmological hydrodynamical simulations on a moving mesh. Mon. Not. Roy. Astron. Soc. 401, 2, 791–851.Google ScholarCross Ref
    67. Stam, J., and Fiume, E. 1995. Depicting fire and other gaseous phenomena using diffusion processes. In SIGGRAPH, 129–136. Google ScholarDigital Library
    68. Stam, J. 1999. Stable fluids. In SIGGRAPH, 121–128. Google ScholarDigital Library
    69. Steinhoff, J., and Underhill, D. 1994. Modification of the Euler equations for vorticity confinement: Application to the computation of interacting vortex rings. Physics of Fluids 6, 8, 2738–2744.Google ScholarCross Ref
    70. Takahashi, T., Dobashi, Y., Fujishiro, I., Nishita, T., and Lin, M. C. 2015. Implicit formulation for SPH-based viscous fluids. Comp. Graph. Forum.Google Scholar
    71. Tang, T. 2004. Moving mesh methods for computational fluid dynamics. In Contemporary Mathematics, no. 383, 141–173.Google Scholar
    72. Whitehurst, R. 1995. A free Lagrange method for gas dynamics. Mon. Not. Roy. Astron. Soc. 277, 2, 655–680.Google ScholarCross Ref
    73. Yan, D.-M., Wang, K., Lévy, B., and Alonso, L. 2011. Computing 2D periodic centroidal Voronoi tessellation. In Int. Symp. on Voronoi Diagrams, 177–184. Google ScholarDigital Library
    74. Yan, D.-M., Wang, W., Lévy, B., and Liu, Y. 2013. Efficient computation of clipped Voronoi diagram. Computer-Aided Design 45, 4, 843–852. Google ScholarDigital Library
    75. Zheng, W., Zhu, B., Kim, B., and Fedkiw, R. 2015. A new incompressibility discretization for a hybrid particle MAC grid representation with surface tension. J. of Comp. Physics 280, 96–142.Google ScholarDigital Library
    76. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3, 965–972. Google ScholarDigital Library

ACM Digital Library Publication: