“FrictionalMonolith: a monolithic optimization-based approach for granular flow with contact-aware rigid-body coupling” by Takahashi and Batty
Conference:
Type(s):
Title:
- FrictionalMonolith: a monolithic optimization-based approach for granular flow with contact-aware rigid-body coupling
Session/Category Title: Turbulence and Fluids
Presenter(s)/Author(s):
Abstract:
We propose FrictionalMonolith, a monolithic pressure-friction-contact solver for more accurately, robustly, and efficiently simulating two-way interactions of rigid bodies with continuum granular materials or inviscid liquids. By carefully formulating the components of such systems within a single unified minimization problem, our solver can simultaneously handle unilateral incompressibility and implicit integration of friction for the interior of the continuum, frictional contact resolution among the rigid bodies, and mutual force exchanges between the continuum and rigid bodies. Our monolithic approach eliminates various problematic artifacts in existing weakly coupled approaches, including loss of volume in the continuum material, artificial drift and slip of the continuum at solid boundaries, interpenetrations of rigid bodies, and simulation instabilities. To efficiently handle this challenging monolithic minimization problem, we present a customized solver for the resulting quadratically constrained quadratic program that combines elements of staggered projections, augmented Lagrangian methods, inexact projected Newton, and active-set methods. We demonstrate the critical importance of a unified treatment and the effectiveness of our proposed solver in a range of practical scenarios.
References:
1. Mridul Aanjaneya, Chengguizi Han, Ryan Goldade, and Christopher Batty. 2019. An Efficient Geometric Multigrid Solver for Viscous Liquids. Proc. ACM Comput. Graph. Interact. Tech. 2, 2, Article 14 (July 2019), 21 pages.
2. Muzaffer Akbay, Nicholas Nobles, Victor Zordan, and Tamar Shinar. 2018. An extended partitioned method for conservative solid-fluid coupling. ACM Transactions on Graphics 37 (2018), 1–12.
3. Nadir Akinci, Markus Ihmsen, Gizem Akinci, Barbara Solenthaler, and Matthias Teschner. 2012. Versatile Rigid-fluid Coupling for Incompressible SPH. ACM Transactions on Graphics 31, 4, Article 62 (2012), 62:1–62:8 pages.
4. Iván Alduán and Miguel A. Otaduy. 2011. SPH Granular Flow with Friction and Cohesion. In Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 25–32.
5. Iván Alduan, Ángel Tena, and Miguel A. Otaduy. 2009. Simulation of High-Resolution Granular Media. In CEIG 09 – Congreso Espanol de Informatica Grafica.
6. Mihai Anitescu and Gary D. Hart. 2004. A constraint-stabilized time-stepping approach for rigid multibody dynamics with joints, contact and friction. Internat. J. Numer. Methods Engrg. 60, 14 (2004), 2335–2371.
7. Mihai Anitescu and Alessandro Tasora. 2010. An iterative approach for cone complementarity problems for nonsmooth dynamics. Computational Optimization and Applications 47 (10 2010), 207–235.
8. Stefan Band, Christoph Gissler, Markus Ihmsen, Jens Cornelis, Andreas Peer, and Matthias Teschner. 2018a. Pressure Boundaries for Implicit Incompressible SPH. ACM Trans. Graph. 37, 2, Article 14 (2018).
9. Stefan Band, Christoph Gissler, Andreas Peer, and Matthias Teschner. 2018b. MLS pressure boundaries for divergence-free and viscous SPH fluids. Computers & Graphics 76 (2018), 37 — 46.
10. Christopher Batty, Florence Bertails, and Robert Bridson. 2007. A Fast Variational Framework for Accurate Solid-fluid Coupling. ACM Trans. Graph. 26, 3, Article 100 (2007).
11. Markus Becker, Hendrik Tessendorf, and Matthias Teschner. 2009. Direct Forcing for Lagrangian Rigid-Fluid Coupling. IEEE Transactions on Visualization and Computer Graphics 15, 3 (2009), 493–503.
12. Nathan Bell, Yizhou Yu, and Peter J. Mucha. 2005. Particle-based Simulation of Granular Materials. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 77–86.
13. Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. 2011. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Found. Trends Mach. Learn. 3, 1 (Jan. 2011), 1–122.
14. Christopher Brandt, Leonardo Scandolo, Elmar Eisemann, and Klaus Hildebrandt. 2019. The reduced immersed method for real-time fluid-elastic solid interaction and contact simulation. ACM Transactions on Graphics 38 (2019).
15. Robert Bridson. 2015. Fluid Simulation for Computer Graphics. A K Peters/CRC Press.
16. Mark Carlson, Peter Mucha, and Greg Turk. 2004. Rigid Fluid: Animating the Interplay Between Rigid Bodies and Fluid. ACM Transactions on Graphics 23 (2004).
17. Nuttapong Chentanez and Matthias Mueller-Fischer. 2012. A Multigrid Fluid Pressure Solver Handling Separating Solid Boundary Conditions. IEEE Transactions on Visualization and Computer Graphics 18, 8 (2012), 1191–1201.
18. M. B. Cline and D. K. Pai. 2003. Post-stabilization for rigid body simulation with contact and constraints. In 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422), Vol. 3. 3744–3751 vol.3.
19. Gilles Daviet. 2020. Simple and Scalable Frictional Contacts for Thin Nodal Objects. ACM Trans. Graph. 39, 4, Article 61 (July 2020), 16 pages.
20. Gilles Daviet and Florence Bertails-Descoubes. 2016. A Semi-implicit Material Point Method for the Continuum Simulation of Granular Materials. ACM Trans. Graph. 35, 4, Article 102 (2016), 102:1–102:13 pages.
21. Gilles Daviet, Florence Bertails-Descoubes, and Laurence Boissieux. 2011. A Hybrid Iterative Solver for Robustly Capturing Coulomb Friction in Hair Dynamics. ACM Trans. Graph. 30, 6 (Dec. 2011), 1–12.
22. Saibal De, Eduardo Corona, Paramsothy Jayakumar, and Shravan Veerapaneni. 2019. Scalable Solvers for Cone Complementarity Problems in Frictional Multibody Dynamics. In 2019 IEEE High Performance Extreme Computing Conference (HPEC). 1–7.
23. Ounan Ding and Craig Schroeder. 2020. Penalty Force for Coupling Materials with Coulomb Friction. IEEE Transactions on Visualization and Computer Graphics 26, 7 (2020), 2443–2455.
24. Zdenek Dostal and Joachim Schoberl. 2005. Minimizing Quadratic Functions Subject to Bound Constraints with the Rate of Convergence and Finite Termination. Computational Optimization and Applications 30, 1 (2005), 23–43.
25. Kenny Erleben. 2007. Velocity-Based Shock Propagation for Multibody Dynamics Animation. ACM Trans. Graph. 26, 2 (June 2007), 12–es.
26. Kenny Erleben. 2017. Rigid Body Contact Problems Using Proximal Operators. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’17). Association for Computing Machinery, Article 13, 12 pages.
27. 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 Trans. Graph. 39, 4, Article 51 (2020).
28. Anders Forsgren, Philip E. Gill, and Margaret H. Wright. 2002. Interior Methods for Nonlinear Optimization. SIAM Rev. 44, 4 (2002), 525–597.
29. Ming Gao, Andre Pradhana, Xuchen Han, Qi Guo, Grant Kot, Eftychios Sifakis, and Chenfanfu Jiang. 2018. Animating Fluid Sediment Mixture in Particle-Laden Flows. ACM Trans. Graph. 37, 4, Article 149 (July 2018).
30. Dan Gerszewski and Adam W. Bargteil. 2013. Physics-based Animation of Large-scale Splashing Liquids. ACM Transactions on Graphics 32, 6, Article 185 (2013), 6 pages.
31. 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.
32. Christoph Gissler, Andreas Peer, Stefan Band, Jan Bender, and Matthias Teschner. 2019. Interlinked SPH Pressure Solvers for Strong Fluid-Rigid Coupling. ACM Transactions on Graphics 38 (2019), 1–13.
33. Tolga G. Goktekin, Adam W. Bargteil, and James F. O’Brien. 2004. A Method for Animating Viscoelastic Fluids. ACM Trans. Graph. 23, 3 (2004), 463–468.
34. Eran Guendelman, Andrew Selle, Frank Losasso, and Ronald Fedkiw. 2005. Coupling water and smoke to thin deformable and rigid shells. ACM Trans. Graph. 24 (2005), 973–981.
35. Xuchen Han, Theodore F. Gast, Qi Guo, Stephanie Wang, Chenfanfu Jiang, and Joseph Teran. 2019. A Hybrid Material Point Method for Frictional Contact with Diverse Materials. Proc. ACM Comput. Graph. Interact. Tech. 2, 2, Article 17 (2019).
36. 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 Trans. Graph. 37, 4, Article 150 (2018).
37. David A.B. 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.
38. Markus Ihmsen, Arthur Wahl, and Matthias Teschner. 2013. A Lagrangian framework for simulating granular material with high detail. Computers & Graphics 37, 7 (2013), 800–808.
39. Chenfanfu Jiang, Theodore Gast, and Joseph Teran. 2017. Anisotropic elastoplasticity for cloth, knit and hair frictional contact. ACM Transactions on Graphics 36 (07 2017), 1–14.
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 (2015), 51:1–51:10 pages.
41. Chenfanfu Jiang, Craig Schroeder, Joseph Teran, Alexey Stomakhin, and Andrew Selle. 2016. The material point method for simulating continuum materials. In ACM SIGGRAPH 2016 Courses. 1–52.
42. Yupeng Jiang, Minchen Li, Chenfanfu Jiang, and Fernando Alonso-Marroquin. 2020. A hybrid material-point spheropolygon-element method for solid and granular material interaction. Internat. J. Numer. Methods Engrg. (2020).
43. Danny M. Kaufman. 2009. Coupled Principles for Computational Frictional Contact Mechanics.
44. M. Danny Kaufman, Shinjiro Sueda, L. Doug James, and K. Dinesh Pai. 2008. Staggered projections for frictional contact in multibody systems. ACM Trans. Graph. (2008), 164–11.
45. Gergely Klár, Theodore Gast, Andre Pradhana, Chuyuan Fu, Craig Schroeder, Chenfanfu Jiang, and Joseph Teran. 2016. Drucker-prager Elastoplasticity for Sand Animation. ACM Trans. Graph. 35, 4, Article 103 (2016), 103:1–103:12 pages.
46. Bryan Klingner, Bryan Feldman, Nuttapong Chentanez, and James O’Brien. 2006. Fluid animation with dynamic meshes. ACM Trans. Graph. 25 (2006), 820–825.
47. Dan Koschier and Jan Bender. 2017. Density Maps for Improved SPH Boundary Handling. In Proceedings of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation. Article 1, 10 pages.
48. J. Kružík, D. Horák, M. Čermák, L. Pospíšil, and M. Pecha. 2020. Active set expansion strategies in MPRGP algorithm. Advances in Engineering Software 149 (2020), 102895.
49. 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), 1–1.
50. Junyu Lai, Yangang Chen, Yu Gu, Christopher Batty, and Justin W.L. Wan. 2020. Fast and Scalable Solvers for the Fluid Pressure Equations with Separating Solid Boundary Conditions. Computer Graphics Forum 39, 2 (2020), 23–33.
51. Egor Larionov, Christopher Batty, and Robert Bridson. 2017. Variational Stokes: A Unified Pressure-viscosity Solver for Accurate Viscous Liquids. ACM Trans. Graph. 36, 4, Article 101 (July 2017), 101:1–101:11 pages.
52. Egor Larionov, Ye Fan, and Dinesh K. Pai. 2021. Frictional Contact on Smooth Elastic Solids. ACM Trans. Graph. 40, 2, Article 15 (April 2021), 17 pages.
53. Quentin Le Lidec, Igor Kalevatykh, Ivan Laptev, Cordelia Schmid, and Justin Carpentier. 2021. Differentiable simulation for physical system identification. IEEE Robotics and Automation Letters (2021). https://hal.archives-ouvertes.fr/hal-03025616
54. Toon Lenaerts and Philip Dutré. 2009. Mixing Fluids and Granular Materials. Computer Graphics Forum 28, 2 (2009), 213–218.
55. Jie Li, Gilles Daviet, Rahul Narain, Florence Bertails-Descoubes, Matthew Overby, George E. Brown, and Laurence Boissieux. 2018. An Implicit Frictional Contact Solver for Adaptive Cloth Simulation. ACM Trans. Graph. 37, 4, Article 52 (July 2018), 15 pages.
56. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020a. Incremental Potential Contact: Intersection-and Inversion-Free, Large-Deformation Dynamics. ACM Trans. Graph. 39, 4, Article 49 (July 2020), 20 pages.
57. Minchen Li, Danny M. Kaufman, and Chenfanfu Jiang. 2020b. Codimensional Incremental Potential Contact. arXiv:cs.GR/2012.04457
58. Mickaël Ly, Jean Jouve, Laurence Boissieux, and Florence Bertails-Descoubes. 2020. Projective Dynamics with Dry Frictional Contact. ACM Trans. Graph. 39, 4, Article 57 (July 2020), 8 pages.
59. Miles Macklin, Kenny Erleben, Matthias Müller, Nuttapong Chentanez, Stefan Jeschke, and Viktor Makoviychuk. 2019. Non-Smooth Newton Methods for Deformable Multi-Body Dynamics. ACM Trans. Graph. 38, 5, Article 140 (Oct. 2019), 20 pages.
60. Miles Macklin, Matthias Müller, Nuttapong Chentanez, and Tae-Yong Kim. 2014. Unified Particle Physics for Real-time Applications. ACM Transactions on Graphics 33, 4, Article 153 (2014), 12 pages.
61. Hammad Mazhar, Toby Heyn, Dan Negrut, and Alessandro Tasora. 2015. Using Nesterov’s Method to Accelerate Multibody Dynamics with Friction and Contact. ACM Trans. Graph. 34, 3, Article 32 (May 2015), 14 pages.
62. Daniel Melanz, Luning Fang, Paramsothy Jayakumar, and Dan Negrut. 2017. A comparison of numerical methods for solving multibody dynamics problems with frictional contact modeled via differential variational inequalities. Computer Methods in Applied Mechanics and Engineering 320 (2017), 668 — 693.
63. Matthias Müller, Nuttapong Chentanez, Miles Macklin, and Stefan Jeschke. 2017. Long Range Constraints for Rigid Body Simulations. In Proceedings of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation (SCA ’17). Association for Computing Machinery, Article 14, 10 pages.
64. Rahul Narain, Abhinav Golas, and Ming C. Lin. 2010. Free-flowing Granular Materials with Two-way Solid Coupling. ACM Transactions on Graphics 29, 6, Article 173 (2010), 10 pages.
65. Rahul Narain, Armin Samii, and James F. O’Brien. 2012. Adaptive Anisotropic Remeshing for Cloth Simulation. ACM Trans. Graph. 31, 6, Article 152 (2012), 10 pages.
66. Yen Ting Ng, Chohong Min, and Frédéric Gibou. 2009. An efficient fluid-solid coupling algorithm for single-phase flows. J. Comput. Phys. 228, 23 (2009), 8807 — 8829.
67. Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (second ed.). Springer, New York, NY, USA.
68. Koichi Onoue and Tomoyuki Nishita. 2003. Virtual Sandbox. In Proceedings of the 11th Pacific Conference on Computer Graphics and Applications (PG ’03). 252.
69. Charles Peskin . 2002. Peskin, C.S.: The immersed boundary method. Acta Numerica 11, 479-517. Acta Numerica 11 (01 2002), 479 — 517.
70. Mathieu Renouf and Pierre Alart. 2005. Conjugate gradient type algorithms for frictional multi-contact problems: applications to granular materials. Computer Methods in Applied Mechanics and Engineering 194, 18 (2005), 2019 — 2041.
71. Avi Robinson-Mosher, R. Elliot English, and Ronald Fedkiw. 2009. Accurate Tangential Velocities for Solid Fluid Coupling. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’09). 227–236.
72. Avi Robinson-Mosher, Craig Schroeder, and Ronald Fedkiw. 2011. A Symmetric Positive Definite Formulation for Monolithic Fluid Structure Interaction. J. Comput. Phys. 230, 4 (Feb. 2011), 1547–1566.
73. Avi Robinson-Mosher, Tamar Shinar, Jon Gretarsson, Jonathan Su, and Ronald Fedkiw. 2008. Two-way Coupling of Fluids to Rigid and Deformable Solids and Shells. ACM Trans. Graph. 27, 3, Article 46 (2008), 9 pages.
74. Morten Silcowitz, Sarah Niebe, and Kenny Erleben. 2009. Nonsmooth Newton Method for Fischer Function Reformulation of Contact Force Problems for Interactive Rigid Body Simulation. VRIPHYS 2009 – 6th Workshop on Virtual Reality Interactions and Physical Simulations, 105–114.
75. Morten Silcowitz, Sarah Niebe, and Kenny Erleben. 2010. Projected Gauss-Seidel Subspace Minimization Method for Interactive Rigid Body Dynamics – Improving Animation Quality using a Projected Gauss-Seidel Subspace Minimization Method. GRAPP 2010 – Proceedings of the International Conference on Computer Graphics Theory and Applications 229, 38–45.
76. Morten Silcowitz-Hansen, Sarah Niebe, and Kenny Erleben. 2010. A nonsmooth nonlinear conjugate gradient method for interactive contact force problems. The Visual Computer 26 (2010), 893–901.
77. Russell Smith. 2008. Open Dynamics Engine. http://www.ode.org/
78. David E. Stewart. 2000. Rigid-Body Dynamics with Friction and Impact. SIAM Rev. 42, 1 (2000), 3–39.
79. Robert W. Sumner, James F. O’Brien, and Jessica K. Hodgins. 1999. Animating Sand, Mud, and Snow. Computer Graphics Forum 18, 1 (1999), 17–26.
80. Tetsuya Takahashi and Christopher Batty. 2020. Monolith: a monolithic pressure-viscosity-contact solver for strong two-way rigid-rigid rigid-fluid coupling. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–16.
81. Tetsuya Takahashi and Ming C. Lin. 2019. A Geometrically Consistent Viscous Fluid Solver with Two-Way Fluid-Solid Coupling. Computer Graphics Forum 38, 2 (2019), 49–58.
82. Andre Pradhana Tampubolon, Theodore Gast, Gergely Klár, Chuyuan Fu, Joseph Teran, Chenfanfu Jiang, and Ken Museth. 2017. Multi-species Simulation of Porous Sand and Water Mixtures. ACM Trans. Graph. 36, 4, Article 105 (2017), 105:1–105:11 pages.
83. Jie Tan, Kristin Siu, and C. Karen Liu. 2012. Contact Handling for Articulated Rigid Bodies Using LCP. Technical Report GIT-GVU-15-01-2. Georgia Institute of Technology, School of Interactive Computing.
84. Yun Teng, David I. W. Levin, and Theodore Kim. 2016. Eulerian Solid-Fluid Coupling. ACM Trans. Graph. 35, 6, Article 200 (2016), 8 pages.
85. Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust Quasistatic Finite Elements and Flesh Simulation. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’05). 181–190.
86. Emanuel Todorov. 2010. Implicit nonlinear complementarity: A new approach to contact dynamics. Proceedings – IEEE International Conference on Robotics and Automation, 2322 — 2329.
87. Emanuel Todorov. 2011. A convex, smooth and invertible contact model for trajectory optimization. 1071–1076.
88. Richard Tonge, Feodor Benevolenski, and Andrey Voroshilov. 2012. Mass Splitting for Jitter-Free Parallel Rigid Body Simulation. ACM Transactions on Graphics 31 (2012).
89. Mickeal Verschoor and Andrei C. Jalba. 2019. Efficient and Accurate Collision Response for Elastically Deformable Models. ACM Trans. Graph. 38, 2, Article 17 (March 2019), 20 pages.
90. Guowei Yan, Wei Li, Ruigang Yang, and Huamin Wang. 2018. Inexact Descent Methods for Elastic Parameter Optimization. In SIGGRAPH Asia 2018 Technical Papers (SIGGRAPH Asia ’18). Article 253, 14 pages.
91. Yonghao Yue, Breannan Smith, Peter Yichen Chen, Maytee Chantharayukhonthorn, Ken Kamrin, and Eitan Grinspun. 2018. Hybrid Grains: Adaptive Coupling of Discrete and Continuum Simulations of Granular Media. ACM Trans. Graph. 37, 6, Article 283 (2018), 19 pages.
92. Bo Zhu and Xubo Yang. 2010. Animating Sand as a Surface Flow. In Eurographics 2010 – Short Papers.
93. Kuixin Zhu, Xiaowei He, Sheng Li, Hongan Wang, and Guoping Wang. 2021. Shallow Sand Equations: Real-Time Height Field Simulation of Dry Granular Flows. IEEE Transactions on Visualization and Computer Graphics 27, 3 (2021), 2073–2084.
94. Yongning Zhu and Robert Bridson. 2005. Animating Sand As a Fluid. ACM Trans. Graph. 24, 3 (2005), 965–972.
95. Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended Cured Quasi-Newton for Distortion Optimization. ACM Trans. Graph. 37, 4, Article 40 (July 2018), 14 pages.
