“Intersection-free rigid body dynamics” by Ferguson, Li, Schneider, Ureta, Langlois, et al. …

We introduce the first implicit time-stepping algorithm for rigid body dynamics, with contact and friction, that guarantees intersection-free configurations at every time step.Our algorithm explicitly models the curved trajectories traced by rigid bodies in both collision detection and response. For collision detection, we propose a conservative narrow phase collision detection algorithm for curved trajectories, which reduces the problem to a sequence of linear CCD queries with minimal separation. For time integration and contact response, we extend the recently proposed incremental potential contact framework to reduced coordinates and rigid body dynamics.We introduce a benchmark for rigid body simulation and show that our approach, while less efficient than alternatives, can robustly handle a wide array of complex scenes, which cannot be simulated with competing methods, without requiring per-scene parameter tuning.

1. Mihai Anitescu and Gary D. Hart. 2004a. A Constraint-Stabilized Time-Stepping Approach for Rigid Multibody Dynamics with Joints, Contact and Friction. Internat. J. Numer. Methods Engrg. (2004).Google Scholar
2. Mihai Anitescu and Gary D. Hart. 2004b. A Fixed-Point Iteration Approach for Multi-body Dynamics with Contact and Small Friction. Mathematical Programming 101, 1 (2004), 3–32.Google ScholarDigital Library
3. Mihai Anitescu and Florian R. Potra. 1997. Formulating Dynamic Multirigid-Body Contact Problems with Friction as Solvable Linear Complementarity Problems. ASME Nonlinear Dynamics 14 (1997), 231–247.Google ScholarCross Ref
4. Uri M. Ascher and Linda R. Petzold. 1998. Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations (1st ed.). Society for Industrial and Applied Mathematics, USA.Google ScholarDigital Library
5. David Baraff. 1989. Analytical Methods for Dynamic Simulation of Non-Penetrating Rigid Bodies. Computer Graphics (Proceedings of SIGGRAPH) 23, 3 (July 1989), 223–232.Google Scholar
6. David Baraff. 1991. Coping with Friction for Non-penetrating Rigid Body Simulation. Computer Graphics (Proceedings of SIGGRAPH) 25, 4 (July 1991), 31–41.Google Scholar
7. David Baraff. 1994. Fast Contact Force Computation for Nonpenetrating Rigid Bodies. In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’94). Association for Computing Machinery, New York, NY, 23–34.Google ScholarDigital Library
8. Jan Bender, Kenny Erleben, Jeff Trinkle, and Erwin Coumans. 2012. Interactive Simulation of Rigid Body Dynamics in Computer Graphics. In Eurographics 2012 – State of the Art Reports, Marie-Paule Cani and Fabio Ganovelli (Eds.). The Eurographics Association.Google Scholar
9. Bernard Brogliato. 1999. Nonsmooth Mechanics. Springer-Verlag.Google Scholar
10. John Canny. 1986. Collision Detection for Moving Polyhedra. IEEE Transactions on Pattern Analysis and Machine Intelligence Pami-8, 2 (1986), 200–209.Google ScholarDigital Library
11. Michael B. Cline and Dinesh K. Pai. 2003. Post-stabilization for rigid body simulation with contact and constraints. In Proceedings of IEEE International Conference on Robotics and Automation.Google Scholar
12. Eulalie Coevoet, Otman Benchekroun, and Paul G. Kry. 2020. Adaptive Merging for Rigid Body Simulation. ACM Transactions on Graphics (2020).Google Scholar
13. Erwin Coumans and Yunfei Bai. 2016–2019. PyBullet, a Python module for physics simulation for games, robotics and machine learning. http://pybullet.org.Google Scholar
14. Kenny Erleben. 2007. Velocity-based shock propagation for multibody dynamics animation. ACM Transactions on Graphics (2007).Google Scholar
15. 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, New York, NY, Article 13, 12 pages.Google ScholarDigital Library
16. Kenny Erleben. 2018. Methodology for Assessing Mesh-Based Contact Point Methods. ACM Transactions on Graphics 37, 3 (2018).Google ScholarDigital Library
17. Michael Fogleman. 2017. Binary Packing for SLS printing. https://www.michaelfogleman.com/pack3d/.Google Scholar
18. F. Sebastin Grassia. 1998. Practical Parameterization of Rotations Using the Exponential Map. Journal of Graphics Tools 3, 3 (March 1998), 29–48.Google ScholarDigital Library
19. Eran Guendelman, Robert Bridson, and Ronald Fedkiw. 2003. Nonconvex Rigid Bodies with Stacking. ACM Transactions on Graphics (Proceedings of SIGGRAPH) (2003).Google Scholar
20. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3.Google Scholar
21. James K. Hahn. 1988. Realistic Animation of Rigid Bodies. Computer Graphics (Proceedings of SIGGRAPH) (Aug. 1988), 299–308.Google Scholar
22. Ernst Hairer, Christian Lubich, and Gerhard Wanner. 2006. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Vol. 31. Springer.Google Scholar
23. David Harmon, Daniele Panozzo, Olga Sorkine, and Denis Zorin. 2011. Interference-Aware Geometric Modeling. ACM Transactions on Graphics 30, 6 (Dec. 2011), 1–10.Google ScholarDigital Library
24. Shu-Wei Hsu and John Keyser. 2010. Piles of Objects. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) (2010).Google Scholar
25. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/Google Scholar
26. Couro Kane, Jerrold E Marsden, Michael Ortiz, and Matthew West. 2000. Variational Integrators and the Newmark Algorithm for Conservative and Dissipative Mechanical Systems. Internat. J. Numer. Methods Engrg. 49, 10 (Dec. 2000).Google ScholarCross Ref
27. Danny M. Kaufman, Shinjiro Sueda, Doug L. James, and Dinesh K. Pai. 2008. Staggered Projections for Frictional Contact in Multibody Systems. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) 27, 5 (2008).Google Scholar
28. Michael Lerch, German Tischler, Jürgen Wolff Von Gudenberg, Werner Hofschuster, and Walter Krämer. 2006. FILIB++, a Fast Interval Library Supporting Containment Computations. ACM Trans. Math. Software 32, 2 (June 2006), 299–324.Google ScholarDigital Library
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 Transactions on Graphics 39, 4 (2020).Google ScholarDigital Library
30. Per Lötstedt. 1982. Numerical Simulation of Time-Dependent Contact Friction Problems in Rigid Body Mechanics. SIAM Journal of Scientific Statistical Computing 5, 2 (1982), 370–393.Google ScholarDigital Library
31. Libin Lu, Matthew J. Morse, Abtin Rahimian, Georg Stadler, and Denis Zorin. 2019. Scalable Simulation of Realistic Volume Fraction Red Blood Cell Flows through Vascular Networks. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’19). Association for Computing Machinery, New York, NY, Article 6, 30 pages.Google ScholarDigital Library
32. M. Macklin, K. Erleben, M. Müller, N. Chentanez, S. Jeschke, and T. Y. Kim. 2020. Primal/Dual Descent Methods for Dynamics. In Proceedings of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation (SCA ’20). Eurographics Association, Goslar, DEU, Article 9, 12 pages.Google Scholar
33. Khaled Mammou. 2020. V-HACD. https://github.com/kmammou/v-hacdGoogle Scholar
34. Jerrold E. Marsden and Tudor S. Ratiu. 2013. Introduction to Mechanics and Symmetry. Springer.Google Scholar
35. Hammad Mazhar, Toby Heyn, Dan Negrut, and Alessandro Tasora. 2015. Using Nesterov’s Method to Accelerate Multibody Dynamics with Friction and Contact. 34, 3, Article 32 (May 2015), 14 pages.Google Scholar
36. Brian Mirtich. 2000. Timewarp Rigid Body Simulation. Annual Conference Series (Proceedings of SIGGRAPH), 193–200.Google Scholar
37. Brian Mirtich and John F. Canny. 1995. Impulse-based dynamic simulation of rigid bodies. In Symposium on Interactive 3D Graphics.Google Scholar
38. Brian Vincent Mirtich. 1996. Impulse-Based Dynamic Simulation of Rigid Body Systems. Ph.D. Dissertation.Google ScholarDigital Library
39. Jean Jacques Moreau. 1966. Quadratic Programming in Mechanics: Dynamics of OneSided Constraints. SIAM Journal on Control 4, 1 (1966), 153–158.Google ScholarCross Ref
40. Jean Jacques Moreau. 1988. Unilateral Contact and Dry Friction in Finite Freedom Dynamics. Nonsmooth Mechanics and Applications, CISM Courses and Lectures 302 (1988), 1–82.Google Scholar
41. 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 (1991), 217–243.Google ScholarCross Ref
42. Matthias Müller, Miles Macklin, Nuttapong Chentanez, Stefan Jeschke, and Tae-Yong Kim. 2020. Detailed Rigid Body Simulation with Extended Position Based Dynamics. Computer Graphics Forum 39, 8 (2020), 101–112.Google ScholarDigital Library
43. B. Owren and B. Welfert. 2000. The Newton Iteration on Lie Groups. BIT Numerical Mathematics 40 (2000), 121–145.Google ScholarDigital Library
44. Jia Pan, Liangjun Zhang, and Dinesh Manocha. 2012. Collision-Free and Smooth Trajectory Computation in Cluttered Environments. The International Journal of Robotics Research 31, 10 (2012), 1155–1175.Google ScholarDigital Library
45. Xavier Provot. 1997. Collision and Self-Collision Handling in Cloth Model Dedicated to Design Garments. In Computer Animation and Simulation. Springer, 177–189.Google Scholar
46. Stéphane Redon, Abderrahmane Kheddar, and Sabine Coquillart. 2002a. Fast Continuous Collision Detection between Rigid Bodies. Computer Graphics Forum 21, 3 (2002), 279–287.Google ScholarCross Ref
47. Stéphane Redon, Abderrahmane Kheddar, and Sabine Coquillart. 2002b. Gauss’ least constraints principle and rigid body simulations. In Proceedings of IEEE International Conference on Robotics and Automation, Vol. 1. 517–522.Google Scholar
48. Rodrigues. 1840. Des lois géométriques qui régissent les déplacements d’un système solide dans l’espace, et de la variation des coordonnées provenant de ces déplacements considérés indépendamment des causes qui peuvent les produire. Journal de Mathématiques Pures et Appliquées (1840), 380–440.Google Scholar
49. Fabian Schwarzer, Mitul Saha, and Jean-Claude Latombe. 2005. Adaptive Dynamic Collision Checking for Single and Multiple Articulated Robots in Complex Environments. IEEE Transactions on Robotics 21 (July 2005), 338–353.Google ScholarDigital Library
50. SideFX. 2020. Houdini. https://www.sidefx.com/products/houdini/Google Scholar
51. Breannan Smith, Danny M. Kaufman, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun. 2012. Reflections on Simultaneous Impact. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 31, 4 (2012), 106:1–106:12.Google Scholar
52. John M. Snyder. 1992. Interval Analysis for Computer Graphics. Computer Graphics (Proceedings of SIGGRAPH) 26, 2 (July 1992), 121–130.Google Scholar
53. John M. Snyder, Adam R. Woodbury, Kurt Fleischer, Bena Currin, and Alan H. Barr. 1993. Interval Methods for Multi-Point Collisions between Time-Dependent Curved Surfaces. Annual Conference Series (Proceedings of SIGGRAPH), 321–334.Google Scholar
54. Jos Stam. 2009. Nucleus: Towards a Unified Dynamics Solver for Computer Graphics. Proceedings of IEEE International Conference on Computer-Aided Design and Computer Graphics (2009), 1–11.Google ScholarCross Ref
55. David Stewart. 2000. Rigid-Body Dynamics with Friction and Impact. SIAM Rev. 42 (March 2000), 3–39.Google Scholar
56. David Stewart and J.C. Trinkle. 2000. An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Coulomb Friction. Proceedings of IEEE International Conference on Robotics and Automation 1, 162–169.Google Scholar
57. Min Tang, Young J. Kim, and Dinesh Manocha. 2009. C2A: Controlled Conservative Advancement for Continuous Collision Detection of Polygonal Models. In Proceedings of IEEE International Conference on Robotics and Automation. 849–854.Google Scholar
58. Min Tang, Young J. Kim, and Dinesh Manocha. 2011. CCQ: Efficient Local Planning Using Connection Collision Query. Springer Berlin Heidelberg, Berlin, Heidelberg, 229–247.Google Scholar
59. Alessandro Tasora, Radu Serban, Hammad Mazhar, Arman Pazouki, Daniel Melanz, Jonathan Fleischmann, Michael Taylor, Hiroyuki Sugiyama, and Dan Negrut. 2016. Chrono: An Open Source Multi-physics Dynamics Engine. Springer, 19–49.Google Scholar
60. Emanuel Todorov, Tom Erez, and Yuval Tassa. 2012. MuJoCo: A physics engine for model-based control. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. 5026–5033.Google ScholarCross Ref
61. Richard Tonge, Feodor Benevolenski, and Andrey Voroshilov. 2012. Mass Splitting for Jitter-Free Parallel Rigid Body Simulation. ACM Transactions on Graphics (2012).Google Scholar
62. Jeff Trinkle, Jong-Shi Pang, Sandra Sudarsky, and Grace Lo. 1995. On Dynamic Multi-Rigid-Body Contact Problems with Coulomb Friction. Technical Report. Texas A&M University, Department of Computer Science.Google Scholar
63. Warwick Tucker. 2011. Validated Numerics: A Short Introduction to Rigorous Computations. Princeton University Press, USA.Google Scholar
64. Etienne Vouga, Breannan Smith, Danny M. Kaufman, Rasmus Tamstorf, and Eitan Grinspun. 2017. All’s Well That Ends Well: Guaranteed Resolution of Simultaneous Rigid Body Impact. ACM Transactions on Graphics 36, 4 (July 2017).Google ScholarDigital Library
65. Bin Wang, François Faure, and Dinesh K. Pai. 2012. Adaptive Image-based Intersection Volume. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 31, 4 (July 2012).Google ScholarDigital Library
66. Bolun Wang, Zachary Ferguson, Teseo Schneider, Xin Jiang, Marco Attene, and Daniele Panozzo. 2020. A Large Scale Benchmark and an Inclusion-Based Algorithm for Continuous Collision Detection. arXiv:2009.13349 [cs.GR]Google Scholar
67. J.M.P. van Waveren. 2005. Robust Continuous Collision Detection Between Arbitrary Polyhedra Using Trajectory Parameterization of Polyhedral Features. (March 2005).Google Scholar
68. Andrew Witkin and David Baraff. 2001. Physically Based Modeling. In SIGGRAPH 2001 Course Notes.Google Scholar
69. Hongyi Xu, Yili Zhao, and Jernej Barbič. 2014. Implicit Multibody Penalty-based Distributed Contact. IEEE Transactions on Visualization and Computer Graphics 20, 9 (2014).Google ScholarCross Ref
70. Liangjun Zhang, Young J. Kim, and Dinesh Manocha. 2007a. C-DIST: Efficient Distance Computation for Rigid and Articulated Models in Configuration Space. In Proceedings of ACM Symposium on Solid and Physical Modeling (Beijing, China) (SPM ’07). Association for Computing Machinery, New York, NY, 159–169.Google ScholarDigital Library
71. Liangjun Zhang, Young J. Kim, Gokul Varadhan, and Dinesh Manocha. 2007b. Generalized Penetration Depth Computation. Computer-Aided Design 39, 8 (2007), 625–638.Google ScholarDigital Library
72. Xinyu Zhang, Minkyoung Lee, and Young J Kim. 2006. Interactive Continuous Collision Detection for Non-convex Polyhedra. The Visual Computer 22, 9-11 (2006), 749–760.Google ScholarDigital Library
73. Xinyu Zhang, Stephane Redon, Minkyoung Lee, and Young J. Kim. 2007c. Continuous Collision Detection for Articulated Models Using Taylor Models and Temporal Culling. ACM Transactions on Graphics 26, 3 (July 2007), 15–es.Google ScholarDigital Library