“Power particles: an incompressible fluid solver based on power diagrams”
Conference:
Type(s):
Title:
- Power particles: an incompressible fluid solver based on power diagrams
Session/Category Title: Wave-Particle Fluidity
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
