research-article

A Fast and Stable Penalty Method for Rigid Body Simulation

Author:

Evan DrumwrightAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 14, Issue 1

Pages 231 - 240

https://doi.org/10.1109/TVCG.2007.70416

Published: 01 January 2008 Publication History

Abstract

Two methods have been used extensively to model resting contact for rigid body simulation. The first approach, the penalty method, applies virtual springs to surfaces in contact to minimize interpenetration. This method, as typically implemented, results in oscillatory behavior and considerable penetration. The second approach, based on formulating resting contact as a linear complementarity problem, determines the resting contact forces analytically to prevent interpenetration. The analytical method exhibits expected-case polynomial complexity in the number of contact points, and may fail to find a solution in polynomial time when friction is modeled. We present a fast penalty method that minimizes oscillatory behavior and leads to little penetration during resting contact; our method compares favorably to the analytical method with regard to these two measures, while exhibiting much faster performance both asymptotically and empirically.

References

[1]

D. Baraff, “Fast Contact Force Computation for Nonpenetrating Rigid Bodies,” Proc. ACM SIGGRAPH '94, July 1994.

Digital Library

[2]

B. Mirtich, “Impulse-Based Dynamic Simulation of Rigid Body Systems,” PhD dissertation, Univ. of California, Berkeley, 1996.

Digital Library

[3]

E. Guendelman, R. Bridson, and R. Fedkiw, “Nonconvex Rigid Bodies with Stacking,” ACM Trans. Graphics, vol. 22, no. 3, pp. 871-878, 2003.

Digital Library

[4]

D. Stewart and J. Trinkle, “An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Coulomb Friction,” Proc. IEEE Int'l Conf. Robotics and Automation (ICRA '00), Apr. 2000.

[5]

M. Moore and J. Wilhelms, “Collision Detection and Response for Computer Animation,” Proc. Int'l Conf. Computer Graphics and Interactive Techniques, pp. 289-298, 1988.

Digital Library

[6]

C.W. Gear, Numerical Initial Value Problems in Ordinary Differential Equations. Prentice Hall, 1971.

Digital Library

[7]

J.K. Hahn, “Realistic Animation of Rigid Bodies,” Computer Graphics, vol. 22, no. 4, 1988.

Digital Library

[8]

D. Baraff, “Linear-Time Dynamics Using Lagrange Multipliers,” Proc. Computer Graphics, Aug. 1996.

Digital Library

[9]

P. Löstedt, “Mechanical Systems of Rigid Bodies Subject to Unilateral Constraints,” SIAM J. Applied Math., 1982.

[10]

D. Baraff, “An Introduction to Physically Based Modeling: Rigid Body Simulation II—Nonpenetration Constraints,” technical report, Robotics Inst., Carnegie Mellon Univ., 1997.

[11]

E. Kokkevis, “Practical Physics for Articulated Characters,” Proc. Game Developers Conf., 2004.

[12]

D. Ruspini and O. Khatib, “A Framework for Multi-Contact Multi-Body Dynamic Simulation and Haptic Display,” Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS '00), 2000.

[13]

R.W. Cottle, J.-S. Pang, and R. Stone, The Linear Complementarity Problem. Academic Press, 1992.

[14]

P. Löstedt, “Numerical Simulation of Time-Dependent Contact Friction Problems in Rigid Body Mechanics,” SIAM J. Scientific Statistical Computing, vol. 5, no. 2, pp. 370-393, 1984.

Digital Library

[15]

D. Baraff, “Coping with Friction for Non-Penetrating Rigid Body Simulation,” Computer Graphics, vol. 25, no. 4, pp. 31-40, 1991.

Digital Library

[16]

R. Featherstone, Robot Dynamics Algorithms. Kluwer Academic Publishers, 1987.

Digital Library

[17]

W.J. Stronge, “Rigid Body Collisions with Friction,” Proc. Royal Soc. London A, vol. 431, pp. 169-181, 1990.

[18]

J.J. Moreau, “Standard Inelastic Shocks and the Dynamics of Unilateral Constraints,” C.I.S.M. Courses and Lectures, vol. 288, G.del Piero and F. Maceri, eds., pp. 173-221, Springer, 1985.

[19]

J.J. Moreau, “Unilateral Contact and Dry Friction in Finite Freedom Dynamics,” Nonsmooth Mechanics and Applications, J.J.Moreau and P.D. Panagiotopoulos, eds., pp. 1-82, Springer, 1988.

[20]

M.D.P.M. Marques, “Differential Inclusions in Nonsmooth Mechanical Problems: Shocks and Dry Friction,” Progress in Nonlinear Differential Equations and Their Applications, vol. 9, Birkhäuser, 1993.

[21]

J.J. Moreau, “Numerical Experiments in Granular Dynamics: Vibration-Induced Sized Segregation,” Contact Mechanics, M.Raous, M. Jean, and J.J. Moreau, eds., pp. 347-358, Plenum Press, 1995.

[22]

D.E. Stewart and J.C. Trinkle, “An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Inelastic Collisions and Coulomb Friction,” Int'l J. Numerical Methods in Eng., vol. 39, no. 15, pp.2673-2691, 1996.

[23]

M. Anitescu and F.A. Potra, “Formulating Dynamic Multi-Rigid-Body Contact Problems with Friction as Solvable Linear Complementarity Problems,” Nonlinear Dynamics, vol. 14, pp. 231-247, 1997.

[24]

M. Anitescu, F. Potra, and D. Stewart, “Time-Stepping for Three Dimensional Rigid Body Dynamics,” Computer Methods in Applied Mechanics and Eng., vol. 177, pp. 183-197, 1999.

[25]

M. Anitescu and F.A. Potra, “A Time-Stepping Method for Stiff Multi-Rigid-Body Dynamics with Contact and Friction,” Int'l J.Numerical Methods in Eng., vol. 55, pp. 753-784, 2002.

[26]

M. Anitescu and G. Hart, “A Constraint-Stabilized Time-Stepping Approach for Rigid Multibody Dynamics with Joints, Contacts, and Friction,” Int'l J. Numerical Methods in Eng., vol. 60, no. 14, pp.2335-2371, 2004.

[27]

F.A. Potra, M. Anitescu, B. Gavrea, and J. Trinkle, “A Linearly Implicit Trapezoidal Method for Stiff Multibody Dynamics with Contact, Joints, and Friction,” Int'l J. Numerical Methods in Eng., vol. 66, no. 7, pp. 1079-1124, 2006.

[28]

R. Weinstein, J. Teran, and R. Fedkiw, “Pre-Stabilization for Rigid Body Articulation with Contact and Collision,” Proc. ACM SIGGRAPH '05, 2005.

Digital Library

[29]

R. Weinstein, J. Teran, and R. Fedkiw, “Dynamic Simulation of Articulated Rigid Bodies with Contact and Collision,” IEEE Trans. Visualization and Computer Graphics, vol. 12, no. 3, pp. 365-374, May/June 2006.

Digital Library

[30]

D. Baraff, “Analytical Methods for Dynamic Simulation of Non-Penetrating Rigid Bodies,” Computer Graphics, vol. 23, no. 3, July 1989.

Digital Library

[31]

H. Schmidl and V.J. Milenkovic, “A Fast Impulsive Contact Suite for Rigid Body Simulation,” IEEE Trans. Visualization and Computer Graphics, vol. 10, no. 2, pp. 189-197, Mar./Apr. 2004.

Digital Library

[32]

S. Hasegawa and M. Sato, “Real-Time Rigid Body Simulation for Haptic Interactions Based on Contact Volume of Polygonal Objects,” Proc. Eurographics '04, 2004.

[33]

L. Love and W. Book, “Contact Stability Analysis of Virtual Walls,” Proc. Dynamic Systems and Control Division ASME, 1995.

[34]

D. Muller and F. Preparata, “Finding the Intersection of Two Convex Polyhedra,” Theoretical Computer Science, vol. 7, pp. 217-236, 1978.

[35]

D. Baraff, “An Introduction to Physically Based Modeling: Rigid Body Simulation II—Constrained Rigid Body Dynamics,” technical report, Robotics Inst., Carnegie Mellon Univ., 1997.

[36]

J. O'Rourke, Computational Geometry in C, second ed. Cambridge Univ. Press, 2001.

Digital Library

[37]

Y. Hwang, E. Inohira, A. Konno, and M. Uchiyama, “An Order n Dynamic Simulator for a Humanoid Robot with a Virtual Spring-Damper Contact Model,” Proc. IEEE Int'l Conf. Robotics and Automation (ICRA '03), Sept. 2003.

[38]

K. Yamane and Y. Nakamura, “Stable Penalty-Based Model of Frictional Contacts,” Proc. IEEE Int'l Conf. Robotics and Automation (ICRA '06), May 2006.

[39]

J.G. Ziegler and N.B. Nichols, “Optimal Settings for Automatic Controllers,” Trans. Am. Soc. Mechanical Eng., vol. 64, pp. 759-762.

[40]

R. Barzel, J.F. Hughes, and D.N. Wood, “Plausible Motion Simulation for Computer Graphics Animation,” Proc. Eurographics Workshop Computer Animation and Simulation, R. Boulic and G.Hégron, eds., pp. 183-197, 1996.

Digital Library

[41]

K.G. Murty, Linear Complementarity, Linear and Nonlinear Programming. Heldermann, 1988.

[42]

M. Kass, “An Introduction to Continuum Dynamics for Computer Graphics,” technical report, Pixar, 1997.

[43]

M.C. Lin and J.F. Canny, “A Fast Algorithm for Incremental Distance Calculation,” Proc. IEEE Int'l Conf. Robotics and Automation (ICRA '91), pp. 1008-1014, 1991.

[44]

B. Mirtich, “V-Clip: Fast and Robust Polyhedral Collision Detection,” ACM Trans. Graphics, vol. 17, no. 3, pp. 177-208, 1998.

Digital Library

[45]

S.F. Frisken, R.N. Perry, A.P. Rockwood, and T.R. Jones, “Adaptively Sampled Distance Fields: A General Representation of Shape for Computer Graphics,” Proc. ACM SIGGRAPH '00, 2000.

Digital Library

[46]

M.W. Jones, J.A. Baerentzen, and M. Sramek, “3D Distance Fields: A Survey of Techniques and Applications,” IEEE Trans. Visualization and Computer Graphics, vol. 12, no. 4, pp. 581-599, July/Aug. 2006.

Digital Library

[47]

S. Fisher and M.C. Lin, “Deformed Distance Fields for Simulation of Non-Penetrating Flexible Bodies,” Proc. Eurographic Workshop Computer Animation and Simulation, pp. 99-111, 2001.

Digital Library

[48]

Y.J. Kim, M.A. Otaduy, M.C. Lin, and D. Manocha, “Fast Penetration Depth Computation for Physically-Based Animation,” Proc. Symp. Computer Animation (SCA '02), 2002.

Digital Library

Cited By

Truong NYuksel CWatcharopas CLevine JKirby R(2022)Particle Merging-and-SplittingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.309377628:12(4546-4557)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TVCG.2021.3093776
Bargteil AShinar TKry P(2020)An introduction to physics-based animationSIGGRAPH Asia 2020 Courses10.1145/3415263.3419147(1-57)Online publication date: 17-Nov-2020
https://dl.acm.org/doi/10.1145/3415263.3419147
Macklin MErleben KMüller MChentanez NJeschke SKim TLevin DKry P(2020)Primal/dual descent methods for dynamicsProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.1111/cgf.14104(1-12)Online publication date: 6-Oct-2020
https://dl.acm.org/doi/10.1111/cgf.14104
Show More Cited By

Recommendations

Backward steps in rigid body simulation

Physically based simulation of rigid body dynamics is commonly done by time-stepping systems forward in time. In this paper, we propose methods to allow time-stepping rigid body systems back-ward in time. Unfortunately, reverse-time integration of rigid ...
Coping with friction for non-penetrating rigid body simulation

Algorithms and computational complexity measures for simulating the motion of contacting bodies with friction are presented. The bodies are restricted to be perfectly rigid bodies that contact at finitely many points. Contact forces between bodies must ...
Coping with friction for non-penetrating rigid body simulation
SIGGRAPH '91: Proceedings of the 18th annual conference on Computer graphics and interactive techniques

Algorithms and computational complexity measures for simulating the motion of contacting bodies with friction are presented. The bodies are restricted to be perfectly rigid bodies that contact at finitely many points. Contact forces between bodies must ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics Volume 14, Issue 1

January 2008

244 pages

ISSN:1077-2626

Issue’s Table of Contents

Copyright © 2008.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 January 2008

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Truong NYuksel CWatcharopas CLevine JKirby R(2022)Particle Merging-and-SplittingIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.309377628:12(4546-4557)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1109/TVCG.2021.3093776
Bargteil AShinar TKry P(2020)An introduction to physics-based animationSIGGRAPH Asia 2020 Courses10.1145/3415263.3419147(1-57)Online publication date: 17-Nov-2020
https://dl.acm.org/doi/10.1145/3415263.3419147
Macklin MErleben KMüller MChentanez NJeschke SKim TLevin DKry P(2020)Primal/dual descent methods for dynamicsProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.1111/cgf.14104(1-12)Online publication date: 6-Oct-2020
https://dl.acm.org/doi/10.1111/cgf.14104
Bargteil AShinar T(2019)An introduction to physics-based animationACM SIGGRAPH 2019 Courses10.1145/3305366.3328050(1-57)Online publication date: 28-Jul-2019
https://dl.acm.org/doi/10.1145/3305366.3328050
Bargteil AShinar T(2018)An introduction to physics-based animationACM SIGGRAPH 2018 Courses10.1145/3214834.3214849(1-1)Online publication date: 12-Aug-2018
https://dl.acm.org/doi/10.1145/3214834.3214849
Pan ZManocha D(2018)Position-Based Time-Integrator for Frictional Articulated Body Dynamics2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS.2018.8593817(1-8)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1109/IROS.2018.8593817
Kim MLee YLee YLee D(2017)Haptic rendering and interactive simulation using passive midpoint integrationInternational Journal of Robotics Research10.1177/027836491773182136:12(1341-1362)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1177/0278364917731821
Tang MManocha DOtaduy MTong R(2012)Continuous penalty forcesACM Transactions on Graphics10.1145/2185520.218560331:4(1-9)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1145/2185520.2185603
Erez TSmart W(2010)A scalable method for solving high-dimensional continuous POMDPs using local approximationProceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence10.5555/3023549.3023568(160-167)Online publication date: 8-Jul-2010
https://dl.acm.org/doi/10.5555/3023549.3023568
Hsu SKeyser J(2010)Piles of objectsACM Transactions on Graphics10.1145/1882261.186618129:6(1-6)Online publication date: 15-Dec-2010
https://dl.acm.org/doi/10.1145/1882261.1866181
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents