research-article

Backward steps in rigid body simulation

Authors:

Christopher D. Twigg,

Doug L. JamesAuthors Info & Claims

SIGGRAPH '08: ACM SIGGRAPH 2008 papers

Article No.: 25, Pages 1 - 10

https://doi.org/10.1145/1399504.1360624

Published: 01 August 2008 Publication History

Abstract

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 bodies involving frictional contact is mathematically ill-posed, and can lack unique solutions. We instead propose time-reversed rigid body integrators that can sample possible solutions when unique ones do not exist. We also discuss challenges related to dissipation-related energy gain, sensitivity to initial conditions, stacking, constraints and articulation, rolling, sliding, skidding, bouncing, high angular velocities, rapid velocity growth from micro-collisions, and other problems encountered when going against the usual flow of time.

Supplementary Material

MOV File (a25-twigg.mov)

Download
25.52 MB

References

[1]

Anitescu, M., And Potra, F. A. 1996. Formulating dynamic multi-rigid-body contact problems with friction as solvable Linear Complementarity Problems. Nonlinear Dynamics 14, 3 (Oct.), 231--247.

[2]

Baraff, D. 1991. Coping with friction for non-penetrating rigid body simulation. In Computer Graphics (Proc. SIGGRAPH 91), 31--40.

Digital Library

[3]

Baraff, D. 1994. Fast contact force computation for nonpene-trating rigid bodies. In Proc. of ACM SIGGRAPH 1994, 23--34.

Digital Library

[4]

Baraff, D. 2001. Rigid body simulation. In Physically Based Modeling: SIGGRAPH 2001 Course 25.

[5]

Chenney, S., and Forsyth, D. A. 2000. Sampling plausible solutions to multi-body constraint problems. In Proc. of ACM SIGGRAPH 2000, 219--228.

Digital Library

[6]

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

[7]

Gear, C. W., and Kevrekidis, I. G. 2004. Computing in the past with forward integration. Physics Letters A 321, 5, 335--342.

[8]

Guendelman, E., Bridson, R., and Fedkiw, R. P. 2003. Nonconvex rigid bodies with stacking. ACM Trans. on Graphics 22, 3, 871--878.

Digital Library

[9]

Hahn, J. K. 1988. Realistic animation of rigid bodies. In Computer Graphics (Proc. of SIGGRAPH 88), 299--308.

Digital Library

[10]

Hunt, K., and Crossley, F. 1975. Coefficient of restitution interpreted as damping in vibroimpact. Trans. ASME, Journal of Applied Mechanics, 440--445.

[11]

Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. ACM Trans. on Graphics 24, 3 (Aug.), 946--956.

Digital Library

[12]

Kharevych, L., Yang, W., Tong, Y., Kanso, E., Marsden, J. E., Schröder, P., and Desbrun, M. 2006. Geometric, variational integrators for computer animation. In 2006 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 43--52.

Digital Library

[13]

Lankarani, H. M., and Nikravesh, P. E. 1994. Continuous contact force models for impact analysis in multibody systems. Nonlinear Dynamics, 193--207.

[14]

Leimkuhler, B., and Reich, S. 2005. Simulating Hamiltonian Dynamics. Cambridge University Press.

[15]

McNamara, A., Treuille, A., Popović, Z., and Stam, J. 2004. Fluid control using the adjoint method. ACM Trans. on Graphics 23, 3 (Aug.), 449--456.

Digital Library

[16]

Milenkovic, V. J., and Schmidl, H. 2001. Optimization-based animation. In Proc. of ACM SIGGRAPH 2001, 37--46.

Digital Library

[17]

Mirtich, B., and Canny, J. 1995. Impulse-based simulation of rigid bodies. In 1995 Symposium on Interactive 3D Graphics, 181--188.

Digital Library

[18]

Mirtich, B. 2000. Timewarp rigid body simulation. In Proc. of ACM SIGGRAPH 2000, 193--200.

Digital Library

[19]

Popović, J., Seitz, S. M., Erdmann, M., Popović, Z., and Witkin, A. P. 2000. Interactive manipulation of rigid body simulations. In Proc. of ACM SIGGRAPH 2000, 209--218.

Digital Library

[20]

Popović, J., Seitz, S. M., and Erdmann, M. 2003. Motion sketching for control of rigid-body simulations. ACM Trans. on Graphics 22, 4 (Oct.), 1034--1054.

Digital Library

[21]

Reichenbach, H. 1999. The Direction of Time. Dover Publications.

[22]

Smith, R. 2006. Open Dynamics Engine v0.5 Users Guide, Feb.

[23]

Stewart, D. E., and Trinkle, J. C. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction. Intl. J. Num. Meth. Eng. 39, 2673--2691.

[24]

Stewart, D. E., and Trinkle, J. C. 1997. Dynamics, friction, and complementarity problems. In Complementarity and Variational Problems, M. C. Ferris and J. S. Pang, Eds. SIAM, 425--439.

[25]

Stewart, D. 1998. Convergence of a time-stepping scheme for rigid body dynamics and resolution of Painlevé's problems. Archive Rational Mechanics and Analysis 145, 3, 215--260.

[26]

Stewart, D. E. 2000. Rigid body dynamics with friction and impact. SIAM Review 42, 1, 3--39.

Digital Library

[27]

Twigg, C. D., and James, D. L. 2007. Many-worlds browsing for control of multibody dynamics. ACM Trans. on Graphics (SIGGRAPH 2007) 26, 3 (Aug.).

Digital Library

[28]

Twigg, C. D. 2008. Controlling Rigid Multibody Dynamics via Browsing and Time Reversal. PhD thesis, Carnegie Mellon University.

Digital Library

[29]

Weinstein, R., Teran, J., and Fedkiw, R. 2006. Dynamic simulation of articulated rigid bodies with contact and collision. IEEE Trans. on Visualization and Computer Graphics 12, 3 (May), 365--374.

Digital Library

[30]

Witkin, A., and Kass, M. 1988. Spacetime constraints. In Computer Graphics (Proc. of SIGGRAPH 88), 159--168.

Digital Library

[31]

Witkin, A. P. 2001. Constrained dynamics. In Physically Based Modeling: SIGGRAPH 2001 Course 25.

[32]

Wojtan, C., Mucha, P. J., and Turk, G. 2006. Keyframe control of complex particle systems using the adjoint method. In Proc. 2006 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 15--23.

Digital Library

Cited By

Chandra KChen TLi TRagan-Kelley JTenenbaum JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Inferring the future by imagining the pastProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667048(21196-21216)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667048
James DLevin D(2023)ViCMA: Visual Control of Multibody AnimationsSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618223(1-11)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1145/3610548.3618223
Chen YLi MLan LSu HYang YJiang C(2022)A unified newton barrier method for multibody dynamicsACM Transactions on Graphics10.1145/3528223.353007641:4(1-14)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530076
Show More Cited By

Index Terms

Backward steps in rigid body simulation
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Physical simulation
    2. Shape modeling
  2. Modeling and simulation
    1. Simulation types and techniques
      1. Simulation by animation
2. Mathematics of computing
  1. Continuous mathematics
    1. Topology
      1. Geometric topology

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 ...
ADD: analytically differentiable dynamics for multi-body systems with frictional contact

We present a differentiable dynamics solver that is able to handle frictional contact for rigid and deformable objects within a unified framework. Through a principled mollification of normal and tangential contact forces, our method circumvents the ...
Timewarp rigid body simulation
SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques

The traditional high-level algorithms for rigid body simulation work well for moderate numbers of bodies but scale poorly to systems of hundreds or more moving, interacting bodies. The problem is unnecessary synchronization implicit in these methods. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '08: ACM SIGGRAPH 2008 papers

August 2008

887 pages

ISBN:9781450301121

DOI:10.1145/1399504

Copyright © 2008 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 ACM 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]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SIGGRAPH '08

Sponsor:

SIGGRAPH

SIGGRAPH '08: Special Interest Group on Computer Graphics and Interactive Techniques Conference

August 11 - 15, 2008

California, Los Angeles

Acceptance Rates

SIGGRAPH '08 Paper Acceptance Rate 90 of 518 submissions, 17%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
1,426
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chandra KChen TLi TRagan-Kelley JTenenbaum JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Inferring the future by imagining the pastProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667048(21196-21216)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667048
James DLevin D(2023)ViCMA: Visual Control of Multibody AnimationsSIGGRAPH Asia 2023 Conference Papers10.1145/3610548.3618223(1-11)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.1145/3610548.3618223
Chen YLi MLan LSu HYang YJiang C(2022)A unified newton barrier method for multibody dynamicsACM Transactions on Graphics10.1145/3528223.353007641:4(1-14)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530076
Nayak SOtte M(2022)Bidirectional Sampling-Based Motion Planning Without Two-Point Boundary Value SolutionIEEE Transactions on Robotics10.1109/TRO.2022.318194738:6(3636-3654)Online publication date: Dec-2022
https://doi.org/10.1109/TRO.2022.3181947
Bangaru SMichel JMu KBernstein GLi TRagan-Kelley J(2021)Systematically differentiating parametric discontinuitiesACM Transactions on Graphics10.1145/3450626.345977540:4(1-18)Online publication date: Aug-2021
https://doi.org/10.1145/3450626.3459775
Ma PTian YPan ZRen BManocha D(2018)Fluid directed rigid body control using deep reinforcement learningACM Transactions on Graphics10.1145/3197517.320133437:4(1-11)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201334
Huang LGao C(2014)Nonuniform Parametric Human Body Based on Model ReuseProceedings of the 2014 5th International Conference on Digital Home10.1109/ICDH.2014.82(406-411)Online publication date: 28-Nov-2014
https://dl.acm.org/doi/10.1109/ICDH.2014.82
English RLentine MFedkiw R(2013)Interpenetration Free Simulation of Thin Shell Rigid BodiesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2012.17919:6(991-1004)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1109/TVCG.2012.179
Hsu SKeyser J(2012)Automated constraint placement to maintain pile shapeACM Transactions on Graphics10.1145/2366145.236616931:6(1-6)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1145/2366145.2366169
De Witt TLessig CFiume E(2012)Fluid simulation using Laplacian eigenfunctionsACM Transactions on Graphics10.1145/2077341.207735131:1(1-11)Online publication date: 2-Feb-2012
https://dl.acm.org/doi/10.1145/2077341.2077351
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten