“The power particle-in-cell method” by Qu, Li, Goes and Jiang

This paper introduces a new weighting scheme for particle-grid transfers that generates hybrid Lagrangian/Eulerian fluid simulations with uniform particle distributions and precise volume control. At its core, our approach reformulates the construction of Power Particles [de Goes et al. 2015] by computing volume-constrained density kernels. We employ these optimized kernels as particle domains within the Generalized Interpolation Material Point method (GIMP) in order to incorporate Power Particles into the Particle-In-Cell framework, hence the name the Power Particle-In-Cell method. We address the construction of volume-constrained density kernels as a regularized optimal transportation problem and describe an iterative solver based on localized Gaussian convolutions that leads to a significant performance speedup compared to [de Goes et al. 2015]. We also present novel extensions for handling free surfaces and solid obstacles that bypass the need for cell clipping and ghost particles. We demonstrate the advantages of our transfer weights by improving hybrid schemes for fluid simulation such as the Fluid Implicit Particle (FLIP) method and the Affine Particle-In-Cell (APIC) method with volume preservation and robustness to varying particle-per-cell ratio, while retaining low numerical dissipation, conserving linear and angular momenta, and avoiding particle reseeding or post-process relaxations.

1. Ryoichi Ando, Nils Thürey, and Reiji Tsuruno. 2012. Preserving Fluid Sheets with Adaptively Sampled Anisotropic Particles. IEEE Transactions on Visualization and Computer Graphics 18, 8 (2012), 1202–1214.Google ScholarDigital Library
2. Ryoichi Ando, Nils Thürey, and Chris Wojtan. 2013. Highly Adaptive Liquid Simulations on Tetrahedral Meshes. ACM Transactions on Graphics 32, 4, Article 103 (2013), 10 pages.Google ScholarDigital Library
3. Franz Aurenhammer. 1987. Power Diagrams: Properties, Algorithms and Applications. SIAM J. Comput. 16, 1 (1987), 78–96.Google ScholarDigital Library
4. Franz Aurenhammer, Friedrich Hoffmann, and Boris Aronov. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1 (1998), 61–76.Google ScholarCross Ref
5. Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-Constrained Point Distributions: A Variant of Lloyd’s Method. In ACM SIGGRAPH. Article 86, 8 pages.Google Scholar
6. Scott G. Bardenhagen and Edward M. Kober. 2004. The generalized interpolation material point method. Computer Modeling in Engineering and Sciences 5, 6 (2004), 477–496.Google Scholar
7. Christopher Batty, Florence Bertails, and Robert Bridson. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Transactions on Graphics 26, 3 (2007), 100–es.Google ScholarDigital Library
8. Markus Becker and Matthias Teschner. 2007. Weakly compressible SPH for free surface flows. In Symposium on Computer Animation. 209–217.Google Scholar
9. Jan Bender and Dan Koschier. 2016. Divergence-free SPH for incompressible and viscous fluids. IEEE Transactions on Visualization and Computer Graphics 23, 3 (2016), 1193–1206.Google ScholarDigital Library
10. Nicolas Bonneel, Michiel van de Panne, Sylvain Paris, and Wolfgang Heidrich. 2011. Displacement Interpolation Using Lagrangian Mass Transport. ACM Transactions on Graphics 30, 6 (2011), 1–12.Google ScholarDigital Library
11. Jeremiah U Brackbill and Hans M Ruppel. 1986. FLIP: A method for adaptively zoned, particle-in-cell calculations of fluid flows in two dimensions. J. Comput. Phys. 65, 2 (1986), 314–343.Google ScholarDigital Library
12. Robert Bridson. 2015. Fluid simulation for computer graphics. CRC press.Google ScholarDigital Library
13. Rainer Burkard, Mauro Dell’Amico, and Silvano Martello. 2009. Assignment Problems. Society for Industrial and Applied Mathematics.Google Scholar
14. Lenaïc Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. 2018. Scaling algorithms for unbalanced optimal transport problems. Math. Comput. 87, 314 (2018), 2563–2609.Google ScholarCross Ref
15. Jens Cornelis, Markus Ihmsen, Andreas Peer, and Matthias Teschner. 2014. IISPH-FLIP for incompressible fluids. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 255–262.Google Scholar
16. Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, USA.Google ScholarDigital Library
17. Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems 26 (2013), 2292–2300.Google Scholar
18. Marco Cuturi and Gabriel Peyré. 2018. Semidual Regularized Optimal Transport. SIAM Rev. 60, 4 (2018), 941–965.Google ScholarDigital Library
19. Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power Particles: an incompressible fluid solver based on power diagrams. ACM Transactions on Graphics 34, 4 (2015), 50–1.Google ScholarDigital Library
20. Denis Demidov. 2019. AMGCL: An efficient, flexible, and extensible algebraic multigrid implementation. Lobachevskii Journal of Mathematics 40, 5 (2019), 535–546.Google ScholarCross Ref
21. Ounan Ding, Tamar Shinar, and Craig Schroeder. 2020. Affine particle in cell method for MAC grids and fluid simulation. J. Comput. Phys. 408 (2020), 109311.Google ScholarCross Ref
22. Yun Fei, Qi Guo, Rundong Wu, Li Huang, and Ming Gao. 2021. Revisiting integration in the material point method: a scheme for easier separation and less dissipation. ACM Transactions on Graphics 40, 4 (2021), 1–16.Google ScholarDigital Library
23. Florian Ferstl, Ryoichi Ando, Chris Wojtan, Rüdiger Westermann, and Nils Thuerey. 2016. Narrow Band FLIP for Liquid Simulations. Computer Graphics Forum 35, 2 (2016), 225–232.Google ScholarCross Ref
24. Nick Foster and Dimitri Metaxas. 1996. Realistic animation of liquids. Graphical models and image processing 58, 5 (1996), 471–483.Google Scholar
25. Chuyuan Fu, Qi Guo, Theodore Gast, Chenfanfu Jiang, and Joseph Teran. 2017. A polynomial particle-in-cell method. ACM Transactions on Graphics 36, 6 (2017), 1–12.Google ScholarDigital Library
26. Ming Gao, Andre Pradhana Tampubolon, Chenfanfu Jiang, and Eftychios Sifakis. 2017. An adaptive generalized interpolation material point method for simulating elastoplastic materials. ACM Transactions on Graphics 36, 6 (2017), 1–12.Google ScholarDigital Library
27. Frederic Gibou, Ronald P Fedkiw, Li-Tien Cheng, and Myungjoo Kang. 2002. A second-order-accurate symmetric discretization of the Poisson equation on irregular domains. J. Comput. Phys. 176, 1 (2002), 205–227.Google ScholarDigital Library
28. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
29. Francis H Harlow. 1962. The particle-in-cell method for numerical solution of problems in fluid dynamics. Technical Report. Los Alamos Scientific Lab., N. Mex.Google Scholar
30. 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 37, 4 (2018), 1–14.Google ScholarDigital Library
31. Yuanming Hu, Xinxin Zhang, Ming Gao, and Chenfanfu Jiang. 2019. On hybrid lagrangian-eulerian simulation methods: practical notes and high-performance aspects. In ACM SIGGRAPH Courses. 16.Google Scholar
32. Markus Ihmsen, Jens Cornelis, Barbara Solenthaler, Christopher Horvath, and Matthias Teschner. 2013. Implicit incompressible SPH. IEEE Transactions on Visualization and Computer Graphics 20, 3 (2013), 426–435.Google ScholarDigital Library
33. Markus Ihmsen, Jens Orthmann, Barbara Solenthaler, Andreas Kolb, and Matthias Teschner. 2014. SPH fluids in computer graphics. In EUROGRAPHICS 2014/S. LEFEBVRE AND M. SPAGNUOLO. Citeseer.Google Scholar
34. Chenfanfu Jiang, Theodore Gast, and Joseph Teran. 2017a. Anisotropic elastoplasticity for cloth, knit and hair frictional contact. ACM Transactions on Graphics 36, 4 (2017), 1–14.Google ScholarDigital Library
35. Chenfanfu Jiang, Craig Schroeder, Andrew Selle, Joseph Teran, and Alexey Stomakhin. 2015. The affine particle-in-cell method. ACM Transactions on Graphics 34, 4 (2015), 1–10.Google ScholarDigital Library
36. Chenfanfu Jiang, Craig Schroeder, and Joseph Teran. 2017b. An angular momentum conserving affine-particle-in-cell method. J. Comput. Phys. 338 (2017), 137–164.Google ScholarDigital Library
37. Chenfanfu Jiang, Craig Schroeder, Joseph Teran, Alexey Stomakhin, and Andrew Selle. 2016. The material point method for simulating continuum materials. In ACM SIGGRAPH Courses. 1–52.Google Scholar
38. Byungsoo Kim, Vinicius C. Azevedo, Markus Gross, and Barbara Solenthaler. 2019. Transport-Based Neural Style Transfer for Smoke Simulations. ACM Transactions on Graphics 38, 6, Article 188 (2019), 11 pages.Google ScholarDigital Library
39. Byungsoo Kim, Vinicius C. Azevedo, Markus Gross, and Barbara Solenthaler. 2020. Lagrangian Neural Style Transfer for Fluids. ACM Transactions on Graphics 39, 4, Article 52 (2020), 10 pages.Google ScholarDigital Library
40. Gergely Klár, Theodore Gast, Andre Pradhana, Chuyuan Fu, Craig Schroeder, Chenfanfu Jiang, and Joseph Teran. 2016. Drucker-prager elastoplasticity for sand animation. ACM Transactions on Graphics 35, 4 (2016), 1–12.Google ScholarDigital Library
41. Philip A. Knight. 2008. The Sinkhorn-Knopp Algorithm: Convergence and Applications. SIAM J. Matrix Anal. Appl. 30, 1 (2008), 261–275.Google ScholarDigital Library
42. Dan Koschier, Jan Bender, Barbara Solenthaler, and Matthias Teschner. 2020. Smoothed particle hydrodynamics techniques for the physics based simulation of fluids and solids. arXiv preprint arXiv:2009.06944 (2020).Google Scholar
43. Tassilo Kugelstadt, Andreas Longva, Nils Thurey, and Jan Bender. 2019. Implicit density projection for volume conserving liquids. IEEE Transactions on Visualization and Computer Graphics (2019).Google Scholar
44. Frank Losasso, Jerry Talton, Nipun Kwatra, and Ronald Fedkiw. 2008. Two-way coupled SPH and particle level set fluid simulation. IEEE Transactions on Visualization and Computer Graphics 14, 4 (2008), 797–804.Google ScholarDigital Library
45. Bruno Lévy. 2022. Partial optimal transport for a constant-volume Lagrangian mesh with free boundaries. J. Comput. Phys. 451 (2022), 110838.Google ScholarDigital Library
46. Miles Macklin and Matthias Müller. 2013. Position based fluids. ACM Transactions on Graphics 32, 4 (2013), 1–12.Google ScholarDigital Library
47. Manish Mandad, David Cohen-Steiner, Leif Kobbelt, Pierre Alliez, and Mathieu Desbrun. 2017. Variance-Minimizing Transport Plans for Inter-Surface Mapping. ACM Transactions on Graphics 36, 4, Article 39 (2017), 14 pages.Google ScholarDigital Library
48. Quentin Mérigot and Jean-Marie Mirebeau. 2016. Minimal Geodesics Along Volume-Preserving Maps Through Semi-discrete Optimal Transport. SIAM J. Numer. Anal. 54, 6 (2016), 3465–3492.Google ScholarDigital Library
49. Joseph J. Monaghan. 2005. Smoothed particle hydrodynamics. Reports on Progress in Physics 68, 8 (2005), 1703–1759.Google ScholarCross Ref
50. Patrick Mullen, Alexander McKenzie, Yiying Tong, and Mathieu Desbrun. 2007. A Variational Approach to Eulerian Geometry Processing. In ACM SIGGRAPH.Google Scholar
51. Ken Museth, Jeff Lait, John Johanson, Jeff Budsberg, Ron Henderson, Mihai Alden, Peter Cucka, David Hill, and Andrew Pearce. 2013. OpenVDB: an open-source data structure and toolkit for high-resolution volumes. In ACM SIGGRAPH Courses. 1–1.Google Scholar
52. Rafael Nakanishi, Filipe Nascimento, Rafael Campos, Paulo Pagliosa, and Afonso Paiva. 2020. RBF liquids: an adaptive PIC solver using RBF-FD. ACM Transactions on Graphics 39, 6 (2020), 1–13.Google ScholarDigital Library
53. Gabriel Peyré, Marco Cuturi, et al. 2019. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning 11, 5–6 (2019), 355–607.Google ScholarDigital Library
54. Stefan Reinhardt, Tim Krake, Bernhard Eberhardt, and Daniel Weiskopf. 2019. Consistent shepard interpolation for SPH-based fluid animation. ACM Transactions on Graphics (TOG) 38, 6 (2019), 1–11.Google ScholarDigital Library
55. Syuhei Sato, Yoshinori Dobashi, and Theodore Kim. 2021. Stream-Guided Smoke Simulations. ACM Transactions on Graphics 40, 4, Article 161 (2021), 7 pages.Google ScholarDigital Library
56. Takahiro Sato, Chris Wojtan, Nils Thuerey, Takeo Igarashi, and Ryoichi Ando. 2018. Extended Narrow Band FLIP for Liquid Simulations. Computer Graphics Forum (2018). Google ScholarCross Ref
57. Richard Sinkhorn. 1967. Diagonal Equivalence to Matrices with Prescribed Row and Column Sums. The American Mathematical Monthly 74, 4 (1967), 402–405.Google ScholarCross Ref
58. Barbara Solenthaler and Renato Pajarola. 2009. Predictive-corrective incompressible SPH. In ACM SIGGRAPH. 1–6.Google Scholar
59. Justin Solomon, Fernando de Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics 34, 4 (2015), 1–11.Google ScholarDigital Library
60. Justin Solomon, Gabriel Peyré, Vladimir G. Kim, and Suvrit Sra. 2016. Entropic Metric Alignment for Correspondence Problems. ACM Transactions on Graphics 35, 4, Article 72 (2016), 13 pages.Google ScholarDigital Library
61. Alexey Stomakhin, Craig Schroeder, Lawrence Chai, Joseph Teran, and Andrew Selle. 2013. A material point method for snow simulation. ACM Transactions on Graphics 32, 4 (2013), 1–10.Google ScholarDigital Library
62. Alexey Stomakhin, Craig Schroeder, Chenfanfu Jiang, Lawrence Chai, Joseph Teran, and Andrew Selle. 2014. Augmented MPM for phase-change and varied materials. ACM Transactions on Graphics 33, 4 (2014), 1–11.Google ScholarDigital Library
63. Deborah Sulsky, Shi-Jian Zhou, and Howard L Schreyer. 1995. Application of a particle-in-cell method to solid mechanics. Computer Physics Communications 87, 1–2 (1995), 236–252.Google ScholarCross Ref
64. Tetsuya Takahashi and Ming C Lin. 2019. A Geometrically Consistent Viscous Fluid Solver with Two-Way Fluid-Solid Coupling. In Computer Graphics Forum, Vol. 38. 49–58.Google ScholarCross Ref
65. Kiwon Um, Seungho Baek, and JungHyun Han. 2014. Advanced hybrid particle-grid method with sub-grid particle correction. In Computer Graphics Forum, Vol. 33. 209–218.Google ScholarDigital Library
66. Yonghao Yue, Breannan Smith, Christopher Batty, Changxi Zheng, and Eitan Grinspun. 2015. Continuum foam: A material point method for shear-dependent flows. ACM Transactions on Graphics 34, 5 (2015), 1–20.Google ScholarDigital Library
67. Xiao Zhai, Fei Hou, Hong Qin, and Aimin Hao. 2018. Fluid simulation with adaptive staggered power particles on gpus. IEEE Transactions on Visualization and Computer Graphics 26, 6 (2018), 2234–2246.Google ScholarCross Ref
68. Yongning Zhu and Robert Bridson. 2005. Animating sand as a fluid. ACM Transactions on Graphics 24, 3 (2005), 965–972.Google ScholarDigital Library