“Affine body dynamics: fast, stable and intersection-free simulation of stiff materials” by Lan, Kaufman, Li, Jiang and Yang

Simulating stiff materials in applications where deformations are either not significant or else can safely be ignored is a fundamental task across fields. Rigid body modeling has thus long remained a critical tool and is, by far, the most popular simulation strategy currently employed for modeling stiff solids. At the same time, rigid body methods continue to pose a number of well known challenges and trade-offs including intersections, instabilities, inaccuracies, and/or slow performances that grow with contact-problem complexity. In this paper we revisit the stiff body problem and present ABD, a simple and highly effective affine body dynamics framework, which significantly improves state-of-the-art for simulating stiff-body dynamics. We trace the challenges in rigid-body methods to the necessity of linearizing piecewise-rigid trajectories and subsequent constraints. ABD instead relaxes the unnecessary (and unrealistic) constraint that each body’s motion be exactly rigid with a stiff orthogonality potential, while preserving the rigid body model’s key feature of a small coordinate representation. In doing so ABD replaces piecewise linearization with piecewise linear trajectories. This, in turn, combines the best of both worlds: compact coordinates ensure small, sparse system solves, while piecewise-linear trajectories enable efficient and accurate constraint (contact and joint) evaluations. Beginning with this simple foundation, ABD preserves all guarantees of the underlying IPC model we build it upon, e.g., solution convergence, guaranteed non-intersection, and accurate frictional contact. Over a wide range and scale of simulation problems we demonstrate that ABD brings orders of magnitude performance gains (two- to three-orders on the CPU and an order more when utilizing the GPU, obtaining 10, 000× speedups) over prior IPC-based methods, while maintaining simulation quality and nonintersection of trajectories. At the same time ABD has comparable or faster timings when compared to state-of-the-art rigid body libraries optimized for performance without guarantees, and successfully and efficiently solves challenging simulation problems where both classes of prior rigid body simulation methods fail altogether.

1. Marc Alexa, Daniel Cohen-Or, and David Levin. 2000. As-rigid-as-possible shape interpolation. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques. 157–164.Google ScholarDigital Library
2. Mihai Anitescu and Florian A Potra. 1997. Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems. Nonlinear Dynamics 14, 3 (1997), 231–247.Google ScholarCross Ref
3. David Baraff. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Proceedings of the 16th annual conference on Computer graphics and interactive techniques. 223–232.Google ScholarDigital Library
4. David Baraff. 1991. Coping with friction for non-penetrating rigid body simulation. ACM SIGGRAPH computer graphics 25, 4 (1991), 31–41.Google Scholar
5. David Baraff. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of the 21st annual conference on Computer graphics and interactive techniques. 23–34.Google ScholarDigital Library
6. David Baraff. 1995. Interactive simulation of solid rigid bodies. IEEE Computer Graphics and Applications 15, 3 (1995), 63–75.Google ScholarDigital Library
7. Joachim Baumgarte. 1972. Stabilization of constraints and integrals of motion in dynamical systems. Computer methods in applied mechanics and engineering 1, 1 (1972), 1–16.Google Scholar
8. Jan Bender, Kenny Erleben, and Jeff Trinkle. 2014. Interactive simulation of rigid body dynamics in computer graphics. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 246–270.Google Scholar
9. Gino van den Bergen. 1997. Efficient collision detection of complex deformable models using AABB trees. Journal of graphics tools 2, 4 (1997), 1–13.Google ScholarDigital Library
10. Javier Bonet and Richard D Wood. 1997. Nonlinear continuum mechanics for finite element analysis. Cambridge university press.Google Scholar
11. Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques. 594–603.Google ScholarDigital Library
12. Tyson Brochu, Essex Edwards, and Robert Bridson. 2012. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–7.Google ScholarDigital Library
13. Michael B Cline and Dinesh 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. IEEE, 3744–3751.Google ScholarCross Ref
14. Eulalie Coevoet, Otman Benchekroun, and Paul G Kry. 2020. Adaptive merging for rigid body simulation. ACM Transactions on Graphics (TOG) 39, 4 (2020), 35–1.Google ScholarDigital Library
15. Erwin Coumans. 2015. Bullet physics simulation. In ACM SIGGRAPH 2015 Courses. 1.Google ScholarDigital Library
16. Peter A Cundall and Otto DL Strack. 1979. A discrete numerical model for granular assemblies. geotechnique 29, 1 (1979), 47–65.Google Scholar
17. Evan Drumwright. 2007. A fast and stable penalty method for rigid body simulation. IEEE transactions on visualization and computer graphics 14, 1 (2007), 231–240.Google Scholar
18. Christian Duriez, Frederic Dubois, Abderrahmane Kheddar, and Claude Andriot. 2005. Realistic haptic rendering of interacting deformable objects in virtual environments. IEEE transactions on visualization and computer graphics 12, 1 (2005), 36–47.Google Scholar
19. Kenny Erleben. 2007. Velocity-based shock propagation for multibody dynamics animation. ACM Transactions on Graphics (TOG) 26, 2 (2007), 12–es.Google ScholarDigital Library
20. Kenny Erleben. 2017. Rigid body contact problems using proximal operators. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 1–12.Google ScholarDigital Library
21. Yu Fang, Minchen Li, Chenfanfu Jiang, and Danny M. Kaufman. 2021. Guaranteed Globally Injective 3D Deformation Processing. ACM Trans. Graph. (SIGGRAPH) 40, 4, Article 75 (2021).Google ScholarDigital Library
22. Zachary Ferguson, Minchen Li, Teseo Schneider, Francisca Gil-Ureta, Timothy Langlois, Chenfanfu Jiang, Denis Zorin, Danny M Kaufman, and Daniele Panozzo. 2021. Intersection-free rigid body dynamics. ACM Transactions on Graphics 40, 4 (2021), 183.Google ScholarDigital Library
23. Susan Fisher and Ming C Lin. 2001. Fast penetration depth estimation for elastic bodies using deformed distance fields. In Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No. 01CH37180), Vol. 1. IEEE, 330–336.Google ScholarCross Ref
24. Stefan Gottschalk, Ming C Lin, and Dinesh Manocha. 1996. OBBTree: A hierarchical structure for rapid interference detection. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. ACM, 171–180.Google ScholarDigital Library
25. Gaël Guennebaud, Benoit Jacob, et al. 2010. Eigen. URl: http://eigen.tuxfamily.org 3 (2010).Google Scholar
26. Ernst Hairer and Gilles Vilmart. 2006. Preprocessed discrete Moser-Veselov algorithm for the full dynamics of a rigid body. Journal of Physics A: Mathematical and General 39, 42 (2006), 13225.Google ScholarCross Ref
27. Shoichi Hasegawa, Nobuaki Fujii, Katsuhito Akahane, Yasuharu Koike, and Makoto Sato. 2004. Real-time rigid body simulation for haptic interactions based on contact volume of polygonal objects. Transactions of the Society of Instrument and Control Engineers 40, 2 (2004), 122–131.Google ScholarCross Ref
28. Kris K Hauser, Chen Shen, and James F O’Brien. 2003. Interactive Deformation Using Modal Analysis with Constraints.. In Graphics Interface, Vol. 3. 16–17.Google Scholar
29. Philip Martyn Hubbard. 1995. Collision detection for interactive graphics applications. IEEE Trans. on Visualization and Computer Graphics 1, 3 (1995), 218–230.Google ScholarDigital Library
30. Takeo Igarashi, Tomer Moscovich, and John F Hughes. 2005. As-rigid-as-possible shape manipulation. ACM transactions on Graphics (TOG) 24, 3 (2005), 1134–1141.Google Scholar
31. Doug L James and Dinesh K Pai. 2004. BD-tree: output-sensitive collision detection for reduced deformable models. ACM Trans. Graph. (TOG) 23, 3 (2004), 393–398.Google ScholarDigital Library
32. Danny M Kaufman, Timothy Edmunds, and Dinesh K Pai. 2005. Fast frictional dynamics for rigid bodies. In ACM SIGGRAPH 2005 Papers. 946–956.Google ScholarDigital Library
33. Danny M Kaufman, Shinjiro Sueda, Doug L James, and Dinesh K Pai. 2008. Staggered projections for frictional contact in multibody systems. In ACM SIGGRAPH Asia 2008 papers. 1–11.Google Scholar
34. Shankar Krishnan, M Gopi, M Lin, Dinesh Manocha, and A Pattekar. 1998. Rapid and accurate contact determination between spline models using ShellTrees. Computer Graphics Forum 17, 3 (1998), 315–326.Google ScholarCross Ref
35. Lei Lan, Yin Yang, Danny Kaufman, Junfeng Yao, Minchen Li, and Chenfanfu Jiang. 2021. Medial IPC: accelerated incremental potential contact with medial elastics. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–16.Google ScholarDigital Library
36. Minchen Li. 2020. Robust and Accurate Simulation of Elastodynamics and Contact. Ph.D. Dissertation. University of Pennsylvania.Google Scholar
37. 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 transactions on graphics (2020).Google ScholarDigital Library
38. Minchen Li, Danny M. Kaufman, and Chenfanfu Jiang. 2021b. Codimensional Incremental Potential Contact. ACM Trans. Graph. (SIGGRAPH) 40, 4, Article 170 (2021).Google ScholarDigital Library
39. Xuan Li, Yu Fang, Minchen Li, and Chenfanfu Jiang. 2021a. BFEMP: Interpenetrationfree MPM-FEM coupling with barrier contact. Computer Methods in Applied Mechanics and Engineering (2021), 114350.Google Scholar
40. 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. 49–54.Google ScholarDigital Library
41. Khaled Mamou, E Lengyel, and AK Peters. 2016. Volumetric hierarchical approximate convex decomposition. In Game Engine Gems 3. AK Peters, 141–158.Google Scholar
42. Hammad Mazhar, Toby Heyn, Dan Negrut, and Alessandro Tasora. 2015. Using Nesterov’s method to accelerate multibody dynamics with friction and contact. ACM Transactions on Graphics (TOG) 34, 3 (2015), 1–14.Google ScholarDigital Library
43. Jean J Moreau. 1988. Unilateral contact and dry friction in finite freedom dynamics. In Nonsmooth mechanics and Applications. Springer, 1–82.Google Scholar
44. Guy M Morton. 1966. A computer oriented geodetic data base and a new technique in file sequencing. (1966).Google Scholar
45. Jürgen Moser and Alexander P Veselov. 1991. Discrete versions of some classical integrable systems and factorization of matrix polynomials. Communications in Mathematical Physics 139, 2 (1991), 217–243.Google ScholarCross Ref
46. Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position based dynamics. Journal of Visual Communication and Image Representation 18, 2 (2007), 109–118.Google ScholarDigital Library
47. Matthias Müller, Miles Macklin, Nuttapong Chentanez, Stefan Jeschke, and Tae-Yong Kim. 2020. Detailed rigid body simulation with extended position based dynamics. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 101–112.Google Scholar
48. Developer Z Nvidia. 2011. Physx sdk. URL Httpdeveloper Nvidia Comphysx-Downloads (2011).Google Scholar
49. Miguel A Otaduy, Daniel Germann, Stephane Redon, and Markus Gross. 2007. Adaptive deformations with fast tight bounds. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation. 181–190.Google ScholarDigital Library
50. Mark Pauly, Dinesh K Pai, and Leonidas J Guibas. 2004. Quasi-rigid objects in contact. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation. 109–119.Google ScholarDigital Library
51. Albert Peiret, Sheldon Andrews, József Kövecses, Paul G Kry, and Marek Teichmann. 2019. Schur complement-based substructuring of stiff multibody systems with contact. ACM Transactions on Graphics (TOG) 38, 5 (2019), 1–17.Google ScholarDigital Library
52. Stephane Redon, Ming C Lin, Dinesh Manocha, and Young J Kim. 2005. Fast continuous collision detection for articulated models. (2005).Google Scholar
53. Peng Song and Vijay Kumar. 2003. Distributed compliant model for efficient dynamic simulation of systems with frictional contacts. In International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Vol. 37009. 1009–1018.Google ScholarCross Ref
54. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, Vol. 4. 109–116.Google ScholarDigital Library
55. David E Stewart. 2000. Rigid-body dynamics with friction and impact. SIAM review 42, 1 (2000), 3–39.Google Scholar
56. Min Tang, Dinesh Manocha, Miguel A Otaduy, and Ruofeng Tong. 2012. Continuous penalty forces. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–9.Google ScholarDigital Library
57. Min Tang, Ruofeng Tong, Zhendong Wang, and Dinesh Manocha. 2014. Fast and exact continuous collision detection with bernstein sign classification. ACM Transactions on Graphics (TOG) 33, 6 (2014), 1–8.Google ScholarDigital Library
58. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically deformable models. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques. 205–214.Google ScholarDigital Library
59. Matthias Teschner, Stefan Kimmerle, Bruno Heidelberger, Gabriel Zachmann, Laks Raghupathi, Arnulph Fuhrmann, M-P Cani, François Faure, Nadia Magnenat-Thalmann, Wolfgang Strasser, et al. 2005. Collision detection for deformable objects. In Computer graphics forum, Vol. 24. Wiley Online Library, 61–81.Google Scholar
60. Emanuel Todorov, Tom Erez, and Yuval Tassa. 2012. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 5026–5033.Google ScholarCross Ref
61. Jeffrey C Trinkle, JA Tzitzouris, and Jong-Shi Pang. 2001. Dynamic multi-rigid-body systems with concurrent distributed contacts. Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 359, 1789 (2001), 2575–2593.Google Scholar
62. Bolun Wang, Zachary Ferguson, Teseo Schneider, Xin Jiang, Marco Attene, and Daniele Panozzo. 2021. A Large-scale Benchmark and an Inclusion-based Algorithm for Continuous Collision Detection. ACM Transactions on Graphics (TOG) 40, 5 (2021), 1–16.Google ScholarDigital Library
63. Endong Wang, Qing Zhang, Bo Shen, Guangyong Zhang, Xiaowei Lu, Qing Wu, and Yajuan Wang. 2014. Intel math kernel library. In High-Performance Computing on the Intel® Xeon Phi™. Springer, 167–188.Google Scholar
64. Hongyi Xu, Yili Zhao, and Jernej Barbič. 2014. Implicit multibody penalty-baseddistributed contact. IEEE transactions on visualization and computer graphics 20, 9 (2014), 1266–1279.Google ScholarCross Ref
65. Gabriel Zachmann. 2002. Minimal hierarchical collision detection. In ACM symposium on Virtual reality software and technology. ACM, 121–128.Google ScholarDigital Library
66. Gabriel Zachmann and Elmar Langetepe. 2003. Geometric data structures for computer graphics. Eurographics Assoc.Google Scholar
67. Yidong Zhao, Jinhyun Choo, Yupeng Jiang, Minchen Li, Chenfanfu Jiang, and Kenichi Soga. 2022. A barrier method for frictional contact on embedded interfaces. Computer Methods in Applied Mechanics and Engineering 393 (2022), 114820.Google ScholarCross Ref