research-article

Public Access

Intersection-free rigid body dynamics

Authors:

Zachary Ferguson,

Teseo Schneider,

Francisca Gil-Ureta,

Timothy Langlois,

Chenfanfu Jiang,

Danny M. Kaufman,

Daniele PanozzoAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 40, Issue 4

Article No.: 183, Pages 1 - 16

https://doi.org/10.1145/3450626.3459802

Published: 19 July 2021 Publication History

Abstract

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.

Supplementary Material

ZIP File (a183-ferguson.zip)

a183-ferguson.zip

Download
43.22 MB

MP4 File (a183-ferguson.mp4)

Download
75.09 MB

References

[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).

[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.

Digital 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.

[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.

Digital 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.

[6]

David Baraff. 1991. Coping with Friction for Non-penetrating Rigid Body Simulation. Computer Graphics (Proceedings of SIGGRAPH) 25, 4 (July 1991), 31--41.

[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.

Digital 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.

[9]

Bernard Brogliato. 1999. Nonsmooth Mechanics. Springer-Verlag.

[10]

John Canny. 1986. Collision Detection for Moving Polyhedra. IEEE Transactions on Pattern Analysis and Machine Intelligence Pami-8, 2 (1986), 200--209.

Digital 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.

[12]

Eulalie Coevoet, Otman Benchekroun, and Paul G. Kry. 2020. Adaptive Merging for Rigid Body Simulation. ACM Transactions on Graphics (2020).

[13]

Erwin Coumans and Yunfei Bai. 2016--2019. PyBullet, a Python module for physics simulation for games, robotics and machine learning. http://pybullet.org.

[14]

Kenny Erleben. 2007. Velocity-based shock propagation for multibody dynamics animation. ACM Transactions on Graphics (2007).

[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.

Digital Library

[16]

Kenny Erleben. 2018. Methodology for Assessing Mesh-Based Contact Point Methods. ACM Transactions on Graphics 37, 3 (2018).

Digital Library

[17]

Michael Fogleman. 2017. Binary Packing for SLS printing. https://www.michaelfogleman.com/pack3d/.

[18]

F. Sebastin Grassia. 1998. Practical Parameterization of Rotations Using the Exponential Map. Journal of Graphics Tools 3, 3 (March 1998), 29--48.

Digital Library

[19]

Eran Guendelman, Robert Bridson, and Ronald Fedkiw. 2003. Nonconvex Rigid Bodies with Stacking. ACM Transactions on Graphics (Proceedings of SIGGRAPH) (2003).

[20]

Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3.

[21]

James K. Hahn. 1988. Realistic Animation of Rigid Bodies. Computer Graphics (Proceedings of SIGGRAPH) (Aug. 1988), 299--308.

[22]

Ernst Hairer, Christian Lubich, and Gerhard Wanner. 2006. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Vol. 31. Springer.

[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.

Digital Library

[24]

Shu-Wei Hsu and John Keyser. 2010. Piles of Objects. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) (2010).

[25]

Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/

[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).

[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).

[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.

Digital 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).

Digital 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.

Digital 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.

Digital 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.

[33]

Khaled Mammou. 2020. V-HACD. https://github.com/kmammou/v-hacd

[34]

Jerrold E. Marsden and Tudor S. Ratiu. 2013. Introduction to Mechanics and Symmetry. Springer.

[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.

[36]

Brian Mirtich. 2000. Timewarp Rigid Body Simulation. Annual Conference Series (Proceedings of SIGGRAPH), 193--200.

[37]

Brian Mirtich and John F. Canny. 1995. Impulse-based dynamic simulation of rigid bodies. In Symposium on Interactive 3D Graphics.

[38]

Brian Vincent Mirtich. 1996. Impulse-Based Dynamic Simulation of Rigid Body Systems. Ph.D. Dissertation.

Digital Library

[39]

Jean Jacques Moreau. 1966. Quadratic Programming in Mechanics: Dynamics of OneSided Constraints. SIAM Journal on Control 4, 1 (1966), 153--158.

[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.

[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.

[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.

Digital Library

[43]

B. Owren and B. Welfert. 2000. The Newton Iteration on Lie Groups. BIT Numerical Mathematics 40 (2000), 121--145.

Digital 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.

Digital 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.

[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.

[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.

[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.

[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.

Digital Library

[50]

SideFX. 2020. Houdini. https://www.sidefx.com/products/houdini/

[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.

[52]

John M. Snyder. 1992. Interval Analysis for Computer Graphics. Computer Graphics (Proceedings of SIGGRAPH) 26, 2 (July 1992), 121--130.

[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.

[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.

[55]

David Stewart. 2000. Rigid-Body Dynamics with Friction and Impact. SIAM Rev. 42 (March 2000), 3--39.

[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.

[57]

Min Tang, Young J. Kim, and Dinesh Manocha. 2009. C²A: Controlled Conservative Advancement for Continuous Collision Detection of Polygonal Models. In Proceedings of IEEE International Conference on Robotics and Automation. 849--854.

[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.

[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.

[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.

[61]

Richard Tonge, Feodor Benevolenski, and Andrey Voroshilov. 2012. Mass Splitting for Jitter-Free Parallel Rigid Body Simulation. ACM Transactions on Graphics (2012).

[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.

[63]

Warwick Tucker. 2011. Validated Numerics: A Short Introduction to Rigorous Computations. Princeton University Press, USA.

[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).

Digital 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).

Digital 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]

[67]

J.M.P. van Waveren. 2005. Robust Continuous Collision Detection Between Arbitrary Polyhedra Using Trajectory Parameterization of Polyhedral Features. (March 2005).

[68]

Andrew Witkin and David Baraff. 2001. Physically Based Modeling. In SIGGRAPH 2001 Course Notes.

[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).

[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.

Digital 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.

Digital 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.

Digital 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.

Digital Library

Cited By

Zhang XTao BJiang DChen BTang DLiu X(2024)Novel Probabilistic Collision Detection for Manipulator Motion Planning Using HNSWMachines10.3390/machines1205032112:5(321)Online publication date: 7-May-2024
https://doi.org/10.3390/machines12050321
Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687988
Chen XYu CNi XChu MWang BChen B(2024)A Time-Dependent Inclusion-Based Method for Continuous Collision Detection between Parametric SurfacesACM Transactions on Graphics10.1145/368796043:6(1-11)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687960
Show More Cited By

Index Terms

Intersection-free rigid body dynamics
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Collision detection
      2. Physical simulation

Recommendations

Rigid-Body Dynamics with Friction and Impact

Rigid-body dynamics with unilateral contact is a good approximation for a wide range of everyday phenomena, from the operation of car brakes to walking to rock slides. It is also of vital importance for simulating robots, virtual reality, and realistic ...
Simulation of dynamics of interacting rigid bodies including friction I: General problem and contact model

This is the first of two papers that deal with the problem of modeling contact (impact, sliding, rolling) between unconstrained rigid bodies for computer simulation of their motion. Modeling impacts and sustained contact is difficult because of the lack ...
Inverse kinematics and rigid-body dynamics for a three rotational degrees of freedom parallel manipulator

Modeling and analysis of inverse kinematics and rigid-body dynamics for a three rotational degrees of freedom (DOF) parallel manipulator are conducted in this research. In the inverse kinematics model, the position, velocity, acceleration, jerk and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 40, Issue 4

August 2021

2170 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/3450626

Editor:
Sylvain Paris
Adobe Inc.

Issue’s Table of Contents

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 July 2021

Published in TOG Volume 40, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF (National Science Foundation)
Adobe Research
Advanced Micro Devices, Inc.
nTopology

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
738
Total Downloads

Downloads (Last 12 months)319
Downloads (Last 6 weeks)32

Reflects downloads up to 08 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang XTao BJiang DChen BTang DLiu X(2024)Novel Probabilistic Collision Detection for Manipulator Motion Planning Using HNSWMachines10.3390/machines1205032112:5(321)Online publication date: 7-May-2024
https://doi.org/10.3390/machines12050321
Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687988
Chen XYu CNi XChu MWang BChen B(2024)A Time-Dependent Inclusion-Based Method for Continuous Collision Detection between Parametric SurfacesACM Transactions on Graphics10.1145/368796043:6(1-11)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687960
Lan LLu ZLong JYuan CLi XHe XWang HJiang CYang Y(2024)Efficient GPU Cloth Simulation with Non-distance Barriers and Subspace ReuseACM Transactions on Graphics10.1145/368776043:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687760
Gomez-Nogales GPrieto-Martin MRomero CComino-Trinidad MRamon-Prieto POlivier AHoyet LOtaduy MPettre JCasas D(2024)Resolving Collisions in Dense 3D Crowd AnimationsACM Transactions on Graphics10.1145/368726643:5(1-14)Online publication date: 6-Sep-2024
https://doi.org/10.1145/3687266
Chen ALiu ZYang YYuksel C(2024)Vertex Block DescentACM Transactions on Graphics10.1145/365817943:4(1-16)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658179
Huang ZTozoni DGjoka AFerguson ZSchneider TPanozzo DZorin D(2024)Differentiable solver for time-dependent deformation problems with contactACM Transactions on Graphics10.1145/365764843:3(1-30)Online publication date: 22-May-2024
https://dl.acm.org/doi/10.1145/3657648
Huang KChitalu FLin HKomura T(2024)GIPC: Fast and Stable Gauss-Newton Optimization of IPC Barrier EnergyACM Transactions on Graphics10.1145/364302843:2(1-18)Online publication date: 23-Mar-2024
https://dl.acm.org/doi/10.1145/3643028
Shen XCai RBi MLv T(2024)Preconditioned Nonlinear Conjugate Gradient Method for Real-time Interior-point HyperelasticityACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657490(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657490
Chen YLy MWojtan C(2024)Primal-Dual Non-Smooth Friction for Rigid Body AnimationACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657485(1-10)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657485
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents