“VEMPIC: particle-in-polyhedron fluid simulation for intricate solid boundaries” by Tao, Batty, Ben-Chen, Fiume and Levin

The comprehensive visual modeling of fluid motion has historically been a challenging task, due in no small part to the difficulties inherent in geometries that are non-manifold, open, or thin. Modern geometric cut-cell mesh generators have been shown to produce, both robustly and quickly, workable volumetric elements in the presence of these problematic geometries, and the resulting volumetric representation would seem to offer an ideal infrastructure with which to perform fluid simulations. However, cut-cell mesh elements are general polyhedra that often contain holes and are non-convex; it is therefore difficult to construct the explicit function spaces required to employ standard functional discretizations, such as the Finite Element Method. The Virtual Element Method (VEM) has recently emerged as a functional discretization that successfully operates with complex polyhedral elements through a weak formulation of its function spaces. We present a novel cut-cell fluid simulation framework that exactly represents boundary geometry during the simulation. Our approach enables, for the first time, detailed fluid simulation with “in-the-wild” obstacles, including ones that contain non-manifold parts, self-intersections, and extremely thin features. Our key technical contribution is the generalization of the Particle-In-Cell fluid simulation methodology to arbitrary polyhedra using VEM. Coupled with a robust cut-cell generation scheme, this produces a fluid simulation algorithm that can operate on previously infeasible geometries without requiring any additional mesh modification or repair.

1. 2020. Intel oneTBB. URl: http://github.com/oneapi-src/oneTBB (2020).Google Scholar
2. Michael J Aftosmis, Marsha J Berger, and John E Melton. 1998. Robust and efficient Cartesian mesh generation for component-based geometry. AIAA journal 36, 6 (1998), 952–960.Google ScholarCross Ref
3. Ryoichi Ando, Nils Thürey, and Chris Wojtan. 2013. Highly adaptive liquid simulations on tetrahedral meshes. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–10.Google ScholarDigital Library
4. Vinicius C Azevedo, Christopher Batty, and Manuel M Oliveira. 2016. Preserving geometry and topology for fluid flows with thin obstacles and narrow gaps. ACM Transactions on Graphics (TOG) 35, 4 (2016), 97.Google ScholarDigital Library
5. Christopher Batty, Florence Bertails, and Robert Bridson. 2007. A fast variational framework for accurate solid-fluid coupling. In ACM Transactions on Graphics (TOG), Vol. 26. ACM, 100.Google ScholarDigital Library
6. Christopher Batty and Robert Bridson. 2008. Accurate viscous free surfaces for buckling, coiling, and rotating liquids. (2008).Google Scholar
7. L Beirão da Veiga, Franco Brezzi, Andrea Cangiani, Gianmarco Manzini, L Donatella Marini, and Alessandro Russo. 2013. Basic principles of virtual element methods. Mathematical Models and Methods in Applied Sciences 23, 01 (2013), 199–214.Google ScholarCross Ref
8. L Beirão da Veiga, Franco Brezzi, Luisa Donatella Marini, and Alessandro Russo. 2014. The hitchhiker’s guide to the virtual element method. Mathematical models and methods in applied sciences 24, 08 (2014), 1541–1573.Google Scholar
9. Blender Online Community. 2018. Blender – a 3D modelling and rendering package. Blender Foundation, Stichting Blender Foundation, Amsterdam. http://www.blender.orgGoogle Scholar
10. Morten Bojsen-Hansen and Chris Wojtan. 2013. Liquid surface tracking with error compensation. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–13.Google ScholarDigital Library
11. Landon Boyd and Robert Bridson. 2012. MultiFLIP for energetic two-phase fluid simulation. ACM Transactions on Graphics (TOG) 31, 2 (2012), 1–12.Google ScholarDigital Library
12. Jeremiah U Brackbill, Douglas B Kothe, and Hans M Ruppel. 1988. FLIP: a low-dissipation, particle-in-cell method for fluid flow. Computer Physics Communications 48, 1 (1988), 25–38.Google ScholarCross Ref
13. Franco Brezzi, Annalisa Buffa, and Konstantin Lipnikov. 2009. Mimetic finite differences for elliptic problems. ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique 43, 2 (2009), 277–295.Google ScholarCross Ref
14. F Brezzi and LD Marini. 2014. Virtual element and discontinuous Galerkin methods. In Recent developments in discontinuous Galerkin finite element methods for partial differential equations. Springer, 209–221.Google Scholar
15. Robert Bridson. 2007. Fast Poisson disk sampling in arbitrary dimensions. SIGGRAPH sketches 10 (2007), 1.Google Scholar
16. Yi-Lu Chen, Jonathan Meier, Barbara Solenthaler, and Vinicius C Azevedo. 2020. An extended cut-cell method for sub-grid liquids tracking with surface tension. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–13.Google ScholarDigital Library
17. Alexandre Joel Chorin. 1968. Numerical solution of the Navier-Stokes equations. Mathematics of computation 22, 104 (1968), 745–762.Google Scholar
18. Pascal Clausen, Martin Wicke, Jonathan R Shewchuk, and James F O’brien. 2013. Simulating liquids and solid-liquid interactions with lagrangian meshes. ACM Transactions on Graphics (TOG) 32, 2 (2013), 1–15.Google ScholarDigital Library
19. Gilles Daviet and Florence Bertails-Descoubes. 2016. A semi-implicit material point method for the continuum simulation of granular materials. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–13.Google ScholarDigital Library
20. Blanca Ayuso de Dios, Konstantin Lipnikov, and Gianmarco Manzini. 2016. The non-conforming virtual element method. ESAIM: Mathematical Modelling and Numerical Analysis 50, 3 (2016), 879–904.Google ScholarCross Ref
21. Fernando De Goes, Andrew Butts, and Mathieu Desbrun. 2020. Discrete differential operators on polygonal meshes. ACM Transactions on Graphics (TOG) 39, 4 (2020), 110–1.Google Scholar
22. Fernando De Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power particles: an incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4 (2015), 50–1.Google Scholar
23. Mathieu Desbrun and Marie-Paule Gascuel. 1996. Smoothed particles: A new paradigm for animating highly deformable bodies. In Computer Animation and Simulation’96. Springer, 61–76.Google ScholarDigital Library
24. Essex Edwards and Robert Bridson. 2012. A high-order accurate particle-in-cell method. Internat. J. Numer. Methods Engrg. 90, 9 (2012), 1073–1088.Google ScholarCross Ref
25. Essex Edwards and Robert Bridson. 2014. Detailed water with coarse grids: Combining surface meshes and adaptive discontinuous galerkin. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–9.Google ScholarDigital Library
26. Yu Fang, Ziyin Qu, Minchen Li, Xinxin Zhang, Yixin Zhu, Mridul Aanjaneya, and Chenfanfu Jiang. 2020. IQ-MPM: an interface quadrature material point method for non-sticky strongly two-way coupled nonlinear solids and fluids. ACM Transactions on Graphics (TOG) 39, 4 (2020), 51–1.Google ScholarDigital Library
27. Ronald Fedkiw, Jos Stam, and Henrik Wann Jensen. 2001. Visual simulation of smoke. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques. 15–22.Google ScholarDigital Library
28. Yun Fei, Christopher Batty, Eitan Grinspun, and Changxi Zheng. 2018. A multi-scale model for simulating liquid-fabric interactions. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–16.Google ScholarDigital Library
29. Florian Ferstl, Ryoichi Ando, Chris Wojtan, Rüdiger Westermann, and Nils Thuerey. 2016. Narrow band FLIP for liquid simulations. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 225–232.Google Scholar
30. Nick Foster and Dimitri Metaxas. 1996. Realistic animation of liquids. Graphical models and image processing 58, 5 (1996), 471–483.Google Scholar
31. Uriel Frisch and Andrei Nikolaevich Kolmogorov. 1995. Turbulence: the legacy of AN Kolmogorov. Cambridge university press.Google Scholar
32. Chuyuan Fu, Qi Guo, Theodore Gast, Chenfanfu Jiang, and Joseph Teran. 2017. A polynomial particle-in-cell method. ACM Transactions on Graphics (TOG) 36, 6 (2017), 1–12.Google ScholarDigital Library
33. Steven Gagniere, David Hyde, Alan Marquez-Razon, Chenfanfu Jiang, Ziheng Ge, Xuchen Han, Qi Guo, and Joseph Teran. 2020. A hybrid Lagrangian/Eulerian collocated velocity advection and projection method for fluid simulation. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 1–14.Google Scholar
34. Eran Guendelman, Andrew Selle, Frank Losasso, and Ronald Fedkiw. 2005. Coupling water and smoke to thin deformable and rigid shells. ACM Transactions on Graphics (TOG) 24, 3 (2005), 973–981.Google ScholarDigital Library
35. Gaël Guennebaud, Benoit Jacob, et al. 2010. Eigen. URl: http://eigen.tuxfamily.org 3 (2010).Google Scholar
36. Ken Hayami. 2018. Convergence of the Conjugate Gradient Method on Singular Systems. Google ScholarCross Ref
37. Anil Nirmal Hirani. 2003. Discrete exterior calculus. Ph.D. Dissertation. California Institute of Technology.Google ScholarDigital Library
38. Yuanming Hu, Yu Fang, Ziheng Ge, Ziyin Qu, Yixin Zhu, Andre Pradhana, and Chenfanfu Jiang. 2018. A moving least squares material point method with displacement discontinuity and two-way rigid body coupling. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–14.Google ScholarDigital Library
39. David AB Hyde and Ronald Fedkiw. 2019. A unified approach to monolithic solid-fluid coupling of sub-grid and more resolved solids. J. Comput. Phys. 390 (2019), 490–526.Google ScholarDigital Library
40. Chenfanfu Jiang, Craig Schroeder, Andrew Selle, Joseph Teran, and Alexey Stomakhin. 2015. The Affine Particle-in-Cell Method. ACM Trans. Graph. 34, 4, Article 51 (July 2015), 10 pages. Google ScholarDigital Library
41. Pushkar Joshi, Mark Meyer, Tony DeRose, Brian Green, and Tom Sanocki. 2007. Harmonic Coordinates for Character Articulation. ACM Trans. Graph. 26, 3 (July 2007), 71–es. Google ScholarDigital Library
42. Peter Kaufmann, Sebastian Martin, Mario Botsch, Eitan Grinspun, and Markus Gross. 2009b. Enrichment textures for detailed cutting of shells. In ACM SIGGRAPH 2009 papers. 1–10.Google ScholarDigital Library
43. Peter Kaufmann, Sebastian Martin, Mario Botsch, and Markus Gross. 2009a. Flexible simulation of deformable models using discontinuous galerkin fem. Graphical Models 71, 4 (2009), 153–167.Google ScholarDigital Library
44. Theodore Kim and John Delaney. 2013. Subspace Fluid Re-Simulation. ACM Trans. Graph. 32, 4, Article 62 (jul 2013), 9 pages. Google ScholarDigital Library
45. Theodore Kim, Nils Thürey, Doug James, and Markus Gross. 2008. Wavelet turbulence for fluid simulation. ACM Transactions on Graphics (TOG) 27, 3 (2008), 1–6.Google ScholarDigital Library
46. Dan Koschier, Jan Bender, and Nils Thuerey. 2017. Robust eXtended finite elements for complex cutting of deformables. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1–13.Google ScholarDigital Library
47. William E Lorensen and Harvey E Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm. ACM siggraph computer graphics 21, 4 (1987), 163–169.Google Scholar
48. Chaoyang Lyu, Wei Li, Mathieu Desbrun, and Xiaopei Liu. 2021. Fast and Versatile Fluid-Solid Coupling for Turbulent Flow Simulation. (2021).Google Scholar
49. Sebastian Martin, Peter Kaufmann, Mario Botsch, Martin Wicke, and Markus Gross. 2008. Polyhedral finite elements using harmonic basis functions. In Computer graphics forum, Vol. 27. Wiley Online Library, 1521–1529.Google Scholar
50. Michael Mengolini, Matías F Benedetto, and Alejandro M Aragón. 2019. An engineering perspective to the virtual element method and its interplay with the standard finite element method. Computer Methods in Applied Mechanics and Engineering 350 (2019), 995–1023.Google ScholarCross Ref
51. Olivier Mercier, Cynthia Beauchemin, Nils Thuerey, Theodore Kim, and Derek Nowrouzezahrai. 2015. Surface turbulence for particle-based liquid simulations. ACM Transactions on Graphics (TOG) 34, 6 (2015), 1–10.Google ScholarDigital Library
52. Marek Krzysztof Misztal, Kenny Erleben, Adam Bargteil, Jens Fursund, Brian Bunch Christensen, Jakob Andreas Bærentzen, and Robert Bridson. 2013. Multiphase flow of immiscible fluids on unstructured moving meshes. IEEE transactions on visualization and computer graphics 20, 1 (2013), 4–16.Google Scholar
53. Nicolas Moës, John Dolbow, and Ted Belytschko. 1999. A finite element method for crack growth without remeshing. International journal for numerical methods in engineering 46, 1 (1999), 131–150.Google Scholar
54. Neil Molino, Zhaosheng Bao, and Ron Fedkiw. 2004. A virtual node algorithm for changing mesh topology during simulation. ACM Transactions on Graphics (TOG) 23, 3 (2004), 385–392.Google ScholarDigital Library
55. Joe J Monaghan. 1992. Smoothed particle hydrodynamics. Annual review of astronomy and astrophysics 30, 1 (1992), 543–574.Google Scholar
56. Patrick Mullen, Keenan Crane, Dmitry Pavlov, Yiying Tong, and Mathieu Desbrun. 2009. Energy-preserving integrators for fluid animation. ACM Transactions on Graphics (TOG) 28, 3 (2009), 1–8.Google ScholarDigital Library
57. Michael B. Nielsen, Konstantinos Stamatelos, Morten Bojsen-Hansen, Duncan Brinsmead, Yannick Pomerleau, Marcus Nordenstam, and Robert Bridson. 2018. A Collocated Spatially Adaptive Approach to Smoke Simulation in Bifrost. In ACM SIGGRAPH 2018 Talks (Vancouver, British Columbia, Canada) (SIGGRAPH ’18). Association for Computing Machinery, New York, NY, USA, Article 77, 2 pages. Google ScholarDigital Library
58. Tobias Pfaff, Nils Thuerey, and Markus Gross. 2012. Lagrangian vortex sheets for animating fluids. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–8.Google ScholarDigital Library
59. Daniel Ram, Theodore Gast, Chenfanfu Jiang, Craig Schroeder, Alexey Stomakhin, Joseph Teran, and Pirouz Kavehpour. 2015. A material point method for viscoelastic fluids, foams and sponges. In Proceedings of the 14th ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 157–163.Google ScholarDigital Library
60. Andrew Selle, Ronald Fedkiw, Byungmoon Kim, Yingjie Liu, and Jarek Rossignac. 2008. An unconditionally stable MacCormack method. Journal of Scientific Computing 35, 2 (2008), 350–371.Google ScholarDigital Library
61. Nicholas Sharp and Keenan Crane. 2020. A laplacian for nonmanifold triangle meshes. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 69–80.Google Scholar
62. Eftychios Sifakis, Kevin G Der, and Ronald Fedkiw. 2007a. Arbitrary cutting of deformable tetrahedralized objects. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation. 73–80.Google ScholarDigital Library
63. Eftychios Sifakis, Tamar Shinar, Geoffrey Irving, and Ronald Fedkiw. 2007b. Hybrid simulation of deformable solids. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation. 81–90.Google ScholarDigital Library
64. Funshing Sin, Adam W Bargteil, and Jessica K Hodgins. 2009. A point-based method for animating incompressible flow. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics symposium on computer animation. 247–255.Google ScholarDigital Library
65. Tommaso Sorgente, Silvia Biasotti, Gianmarco Manzini, and Michela Spagnuolo. 2022. The role of mesh quality and mesh quality indicators in the virtual element method. Advances in Computational Mathematics 48, 1 (2022), 1–34.Google ScholarDigital Library
66. Jos Stam. 1999. Stable fluids. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques. 121–128.Google ScholarDigital Library
67. Alexey Stomakhin, Craig Schroeder, Lawrence Chai, Joseph Teran, and Andrew Selle. 2013. A material point method for snow simulation. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–10.Google ScholarDigital Library
68. Deborah Sulsky, Zhen Chen, and Howard L Schreyer. 1994. A particle method for history-dependent materials. Computer methods in applied mechanics and engineering 118, 1–2 (1994), 179–196.Google Scholar
69. Michael Tao, Christopher Batty, Eugene Fiume, and David IW Levin. 2019. Mandoline: robust cut-cell generation for arbitrary triangle meshes. ACM Transactions on Graphics (TOG) 38, 6 (2019), 1–17.Google ScholarDigital Library
70. Yun Teng, David IW Levin, and Theodore Kim. 2016. Eulerian solid-fluid coupling. ACM Transactions on Graphics (TOG) 35, 6 (2016), 1–8.Google ScholarDigital Library
71. Nils Thuerey and Tobias Pfaff. 2018. MantaFlow. http://mantaflow.com.Google Scholar
72. Ty Trusty, Honglin Chen, and David I.W. Levin. 2021. The Shape Matching Element Method: Direct Animation of Curved Surface Models. ACM Transactions on Graphics (2021). Google ScholarDigital Library
73. Ingo Wald, Sven Woop, Carsten Benthin, Gregory S Johnson, and Manfred Ernst. 2014. Embree: a kernel framework for efficient CPU ray tracing. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–8.Google ScholarDigital Library
74. Omar Zarifi and Christopher Batty. 2017. A positive-definite cut-cell method for strong two-way coupling between fluids and deformable bodies. In Proceedings of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation (Los Angeles California). ACM, New York, NY, USA.Google ScholarDigital Library
75. Yongning Zhu and Robert Bridson. 2005. Animating sand as a fluid. ACM Transactions on Graphics (TOG) 24, 3 (2005), 965–972.Google ScholarDigital Library