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

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