“Primal-dual Non-smooth Friction for Rigid Body Animation”
Conference:
Type(s):
Title:
- Primal-dual Non-smooth Friction for Rigid Body Animation
Presenter(s)/Author(s):
Abstract:
Our novel contact solver, based on an primal-dual interior point algorithm, efficiently and robustly simulates the non-smooth transition between static and dynamic friction. Our algorithm is well suited for large systems of tightly packed objects with many contacts, which we demonstrate with complex granular flows and interlocking assemblies of rigid bodies.
References:
[1]
Vincent Acary, Paul Armand, Hoang Minh Nguyen, and Maksym Shpakovych. 2024. Second-order cone programming for frictional contact mechanics using interior point algorithm. Optimization Methods and Software 0, 0 (2024), 1?30. https://doi.org/10.1080/10556788.2023.2296438 arXiv:https://doi.org/10.1080/10556788.2023.2296438
[2]
Vincent Acary, Maurice Br?mond, and Olivier Huber. 2018. On Solving Contact Problems with Coulomb Friction: Formulations and Numerical Comparisons. Springer International Publishing, Cham, 375?457. https://doi.org/10.1007/978-3-319-75972-2_10
[3]
Vincent Acary, Maurice Bremond, Olivier Huber, Franck Perignon, and Roger Pissard-Gibollet. 2023. Siconos. https://hal.science/hal-04056972
[4]
Vincent Acary and Franck P?rignon. 2007. Siconos: A Software Platform for Modeling, Simulation, Analysis and Control of Nonsmooth Dynamical Systems. SNE Simulation News Europe 17, 3/4 (Dec. 2007), 19?26. https://inria.hal.science/inria-00522740
[5]
P. Alart and A. Curnier. 1991. A mixed formulation for frictional contact problems prone to Newton like solution methods.Comput. Methods Appl. Mech. Eng. 92, 3 (1991), 353?375.
[6]
Sheldon Andrews, Kenny Erleben, and Zachary Ferguson. 2022. Contact and Friction Simulation for Computer Graphics. In ACM SIGGRAPH 2022 Courses (Hybrid Event, Vancouver, Canada) (SIGGRAPH ?22). Association for Computing Machinery, New York, NY, USA, Article 2, 124 pages.
[7]
J. Baumgarte. 1972. Stabilization of constraints and integrals of motion in dynamical systems. Computer Methods in Applied Mechanics and Engineering 1, 1 (1972), 1?16. https://doi.org/10.1016/0045-7825(72)90018-7
[8]
Florence Bertails-Descoubes, Florent Cadoux, Gilles Daviet, and Vincent Acary. 2011. A Nonsmooth Newton Solver for Capturing Exact Coulomb Friction in Fiber Assemblies. ACM Trans. Graph. 30, 1, Article 6 (feb 2011), 14 pages. https://doi.org/10.1145/1899404.1899410
[9]
S.P. Boyd and L. Vandenberghe. 2004. Convex Optimization. Number Teil 1 in Berichte ?ber verteilte messysteme. Cambridge University Press. https://books.google.at/books?id=mYm0bLd3fcoC
[10]
Bernard Brogliato. 1999. Nonsmooth mechanics. Models, dynamics and control. 2nd ed.Communications and Control Engineering Series. London: Springer. xx, 552 p.
[11]
George E. Brown, Matthew Overby, Zahra Forootaninia, and Rahul Narain. 2018. Accurate Dissipative Forces in Optimization Integrators. ACM Trans. Graph. 37, 6, Article 282 (Dec. 2018), 14 pages. https://doi.org/10.1145/3272127.3275011
[12]
Peter W. Christensen, Anders Klarbring, Jong-Shi Pang, and Nicolas Stromberg. 1998. Formulation and comparison of algorithms for frictional contact problems.Int. J. Numer. Methods Eng. 42, 1 (1998), 145?173.
[13]
Gilles Daviet. 2020. Simple and Scalable Frictional Contacts for Thin Nodal Objects. ACM Trans. Graph. 39, 4, Article 61 (July 2020), 16 pages. https://doi.org/10.1145/3386569.3392439
[14]
Gilles Daviet, Florence Bertails-Descoubes, and Laurence Boissieux. 2011. A hybrid iterative solver for robustly capturing Coulomb friction in hair dynamics. ACM Transactions on Graphics 30 (2011), 139:1?139:12. Issue 6.
[15]
Denis Demidov. 2020. AMGCL ?A C++ library for efficient solution of large sparse linear systems. Software Impacts 6 (2020), 100037. https://doi.org/10.1016/j.simpa.2020.100037
[16]
Nikita Doikov, Konstantin Mishchenko, and Yurii Nesterov. 2024. Super-Universal Regularized Newton Method. SIAM Journal on Optimization 34, 1 (2024), 27?56. https://doi.org/10.1137/22M1519444
[17]
Nikita Doikov and Yurii Nesterov. 2023. Gradient regularization of Newton method with Bregman distances. Mathematical Programming (03 2023). https://doi.org/10.1007/s10107-023-01943-7
[18]
Kenny Erleben. 2007. Velocity-Based Shock Propagation for Multibody Dynamics Animation. ACM Trans. Graph. 26, 2 (jun 2007), 12?es. https://doi.org/10.1145/1243980.1243986
[19]
Kenny Erleben. 2017. Rigid body contact problems using proximal operators. In Proceedings of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation (Los Angeles, California) (SCA ?17). Association for Computing Machinery, New York, NY, USA, Article 13, 12 pages. https://doi.org/10.1145/3099564.3099575
[20]
Z. Ferguson, M. Li, T. Schneider, F. Gil-Ureta, T. Langlois, C. Jiang, D. Zorin, D. M. Kaufman, and D. Panozzo. 2021. Intersection-Free Rigid Body Dynamics. ACM Trans. Graph. 40, 4, Article 183 (jul 2021), 16 pages. https://doi.org/10.1145/3450626.3459802
[21]
Anders Forsgren, Philip E. Gill, and Margaret H. Wright. 2002. Interior Methods for Nonlinear Optimization. SIAM Rev. 44, 4 (2002), 525?597. https://doi.org/10.1137/S0036144502414942
[22]
Eran Guendelman, Robert Bridson, and Ronald Fedkiw. 2003. Nonconvex rigid bodies with stacking. ACM Trans. Graph. 22, 3 (jul 2003), 871?878. https://doi.org/10.1145/882262.882358
[23]
Ga?l Guennebaud, Beno?t Jacob, 2010. Eigen v3. http://eigen.tuxfamily.org.
[24]
Danny Kaufman, Timothy Edmunds, and Dinesh K. Pai. 2005. Fast frictional dynamics for rigid bodies. ACM Transactions on Graphics (Proc. ACM SIGGRAPH?05) 24, 3 (2005), 946?956.
[25]
Danny Kaufman, Shinjiro Sueda, Doug L. James, and Dinesh K. Pai. 2008. Staggered Projections for Frictional Contact in Multibody Systems. ACM Transactions on Graphics (Proc. ACM SIGGRAPH Asia?08) 27, 5 (2008), 164:1?164:11.
[26]
L. Lan, D. M. Kaufman, M. Li, C. Jiang, and Y. Yang. 2022. Affine Body Dynamics: Fast, Stable and Intersection-Free Simulation of Stiff Materials. ACM Trans. Graph. 41, 4, Article 67 (jul 2022), 14 pages. https://doi.org/10.1145/3528223.3530064
[27]
Remco I Leine and Henk Nijmeijer. 2013. Dynamics and bifurcations of non-smooth mechanical systems. Vol. 18. Springer Science & Business Media.
[28]
Jie Li, Gilles Daviet, Rahul Narain, Florence Bertails-Descoubes, Matthew Overby, George Brown, and Laurence Boissieux. 2018. An Implicit Frictional Contact Solver for Adaptive Cloth Simulation. ACM Transactions on Graphics 37, 4, Article 52 (Aug. 2018), 15 pages.
[29]
Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection-and Inversion-Free, Large-Deformation Dynamics. ACM Trans. Graph. 39, 4, Article 49 (aug 2020), 20 pages. https://doi.org/10.1145/3386569.3392425
[30]
Tongqing Li, Yuxing Peng, Zhencai Zhu, Shengyong Zou, and Zixin Yin. 2017. Discrete Element Method Simulations of the Inter-Particle Contact Parameters for the Mono-Sized Iron Ore Particles. Materials 10, 5 (2017). https://doi.org/10.3390/ma10050520
[31]
Micka?l Ly, Jean Jouve, Laurence Boissieux, and Florence Bertails-Descoubes. 2020. Projective Dynamics with Dry Frictional Contact. ACM Transactions on Graphics 39, 4 (2020), Article 57:1?8. https://doi.org/10.1145/3386569.3392396
[32]
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. https://doi.org/10.1145/3338695
[33]
M. Macklin, K. Erleben, M. M?ller, N. Chentanez, S. Jeschke, and T.Y. Kim. 2020. Primal/Dual Descent Methods for Dynamics. Computer Graphics Forum 39, 8 (2020), 89?100. https://doi.org/10.1111/cgf.14104
[34]
Miles Macklin, Matthias M?ller, and Nuttapong Chentanez. 2016. XPBD: Position-Based Simulation of Compliant Constrained Dynamics. In Proceedings of the 9th International Conference on Motion in Games (Burlingame, California) (MIG ?16). Association for Computing Machinery, New York, NY, USA, 49?54. https://doi.org/10.1145/2994258.2994272
[35]
Konstantin Mishchenko. 2023. Regularized Newton Method with Global Math 72 Convergence. SIAM Journal on Optimization 33, 3 (2023), 1440?1462. https://doi.org/10.1137/22M1488752 arXiv:https://doi.org/10.1137/22M1488752
[36]
J.-J. Moreau. 1988. Unilateral contact and dry friction in finite freedom dynamics.Nonsmooth mechanics and applications, CISM Courses Lect. 302, 1-82 (1988).
[37]
M. M?ller, M. Macklin, N. Chentanez, S. Jeschke, and T.-Y. Kim. 2020. Detailed Rigid Body Simulation with Extended Position Based Dynamics. Computer Graphics Forum 39, 8 (2020), 101?112. https://doi.org/10.1111/cgf.14105
[38]
M. A. Otaduy, R. Tamstorf, D. Steinemann, and M. H. Gross. 2009. Implicit Contact Handling for Deformable Objects. Computer Graphics Forum (Proc. Eurographics?09) 28, 2 (apr 2009). http://www.gmrv.es/Publications/2009/OTSG09
[39]
Jia Pan, Sachin Chitta, and Dinesh Manocha. 2012. FCL: A general purpose library for collision and proximity queries. In 2012 IEEE International Conference on Robotics and Automation. 3859?3866. https://doi.org/10.1109/ICRA.2012.6225337
[40]
Morten Silcowitz, Sarah Niebe, and Kenny Erleben. 2009. Nonsmooth Newton Method for Fischer Function Reformulation of Contact Force Problems for Interactive Rigid Body Simulation. In Workshop in Virtual Reality Interactions and Physical Simulation “VRIPHYS” (2009), Hartmut Prautzsch, Alfred Schmitt, Jan Bender, and Matthias Teschner (Eds.). The Eurographics Association. https://doi.org/10.2312/PE/vriphys/vriphys09/105-114
[41]
Morten Silcowitz, Sarah Niebe, and Kenny Erleben. 2010. A nonsmooth nonlinear conjugate gradient method for interactive contact force problems. The Visual Computer 26 (06 2010), 893?901. https://doi.org/10.1007/s00371-010-0502-6
[42]
B. Smith, D. M. Kaufman, E. Vouga, R. Tamstorf, and E. Grinspun. 2012. Reflections on Simultaneous Impact. ACM Trans. Graph. 31, 4, Article 106 (July 2012), 12 pages. https://doi.org/10.1145/2185520.2185602
[43]
Georg Sperl, Rahul Narain, and Chris Wojtan. 2020. Homogenized yarn-level cloth. ACM Transactions on Graphics (TOG) 39, 4 (2020), 48?1.
[44]
Georg Sperl, Rosa M S?nchez-Banderas, Manwen Li, Chris Wojtan, and Miguel A Otaduy. 2022. Estimation of yarn-level simulation models for production fabrics. ACM Transactions on Graphics (TOG) 41, 4 (2022), 1?15.
[45]
Shiyu Wei, Han Wei, Henrik Saxen, and Yaowei Yu. 2022. Numerical Analysis of the Relationship between Friction Coefficient and Repose Angle of Blast Furnace Raw Materials by Discrete Element Method. Materials 15, 3 (2022). https://doi.org/10.3390/ma15030903
[46]
Margaret H. Wright. 2005. The interior-point revolution in optimization: History, recent developments, and lasting consequences. Bull. Amer. Math. Soc. 42, 1 (Jan. 2005), 39?56. https://doi.org/10.1090/S0273-0979-04-01040-7
[47]
K. Yamane and Y. Nakamura. 2006. Stable penalty-based model of frictional contacts. In Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006.1904?1909. https://doi.org/10.1109/ROBOT.2006.1641984
[48]
Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended Cured Quasi-Newton for Distortion Optimization. ACM Trans. Graph. 37, 4, Article 40 (jul 2018), 14 pages. https://doi.org/10.1145/3197517.3201359
