“Backward steps in rigid body simulation” by Twigg and James

  • ©Christopher D. Twigg and Doug L. James




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


    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.Google Scholar
    2. Baraff, D. 1991. Coping with friction for non-penetrating rigid body simulation. In Computer Graphics (Proc. SIGGRAPH 91), 31–40. Google ScholarDigital Library
    3. Baraff, D. 1994. Fast contact force computation for nonpene-trating rigid bodies. In Proc. of ACM SIGGRAPH 1994, 23–34. Google ScholarDigital Library
    4. Baraff, D. 2001. Rigid body simulation. In Physically Based Modeling: SIGGRAPH 2001 Course 25.Google Scholar
    5. Chenney, S., and Forsyth, D. A. 2000. Sampling plausible solutions to multi-body constraint problems. In Proc. of ACM SIGGRAPH 2000, 219–228. Google ScholarDigital Library
    6. Cottle, R. W., Pang, J.-S., and Stone, R. E. 1992. The Linear Complementarity Problem. Academic Press.Google Scholar
    7. Gear, C. W., and Kevrekidis, I. G. 2004. Computing in the past with forward integration. Physics Letters A 321, 5, 335–342.Google ScholarCross Ref
    8. Guendelman, E., Bridson, R., and Fedkiw, R. P. 2003. Nonconvex rigid bodies with stacking. ACM Trans. on Graphics 22, 3, 871–878. Google ScholarDigital Library
    9. Hahn, J. K. 1988. Realistic animation of rigid bodies. In Computer Graphics (Proc. of SIGGRAPH 88), 299–308. Google ScholarDigital Library
    10. Hunt, K., and Crossley, F. 1975. Coefficient of restitution interpreted as damping in vibroimpact. Trans. ASME, Journal of Applied Mechanics, 440–445.Google ScholarCross Ref
    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. Google ScholarDigital 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. Google ScholarDigital Library
    13. Lankarani, H. M., and Nikravesh, P. E. 1994. Continuous contact force models for impact analysis in multibody systems. Nonlinear Dynamics, 193–207.Google Scholar
    14. Leimkuhler, B., and Reich, S. 2005. Simulating Hamiltonian Dynamics. Cambridge University Press.Google Scholar
    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. Google ScholarDigital Library
    16. Milenkovic, V. J., and Schmidl, H. 2001. Optimization-based animation. In Proc. of ACM SIGGRAPH 2001, 37–46. Google ScholarDigital Library
    17. Mirtich, B., and Canny, J. 1995. Impulse-based simulation of rigid bodies. In 1995 Symposium on Interactive 3D Graphics, 181–188. Google ScholarDigital Library
    18. Mirtich, B. 2000. Timewarp rigid body simulation. In Proc. of ACM SIGGRAPH 2000, 193–200. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital Library
    21. Reichenbach, H. 1999. The Direction of Time. Dover Publications.Google Scholar
    22. Smith, R. 2006. Open Dynamics Engine v0.5 Users Guide, Feb.Google Scholar
    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.Google ScholarCross Ref
    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.Google Scholar
    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.Google ScholarCross Ref
    26. Stewart, D. E. 2000. Rigid body dynamics with friction and impact. SIAM Review 42, 1, 3–39. Google ScholarDigital 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.). Google ScholarDigital Library
    28. Twigg, C. D. 2008. Controlling Rigid Multibody Dynamics via Browsing and Time Reversal. PhD thesis, Carnegie Mellon University. Google ScholarDigital 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. Google ScholarDigital Library
    30. Witkin, A., and Kass, M. 1988. Spacetime constraints. In Computer Graphics (Proc. of SIGGRAPH 88), 159–168. Google ScholarDigital Library
    31. Witkin, A. P. 2001. Constrained dynamics. In Physically Based Modeling: SIGGRAPH 2001 Course 25.Google Scholar
    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. Google ScholarDigital Library

ACM Digital Library Publication: