“Timewarp rigid body simulation” by Mirtich

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. Jefferson’s timewarp algorithm [22] is a technique for alleviating this problem in parallel discrete event simulation. Rigid body dynamics, though a continuous process, exhibits many aspects of a discrete one. With modification, the timewarp algorithm can be used in a uniprocessor rigid body simulator to give substantial performance improvements for simulations with large numbers of bodies. This paper describes the limitations of the traditional high-level simulation algorithms, introduces Jefferson’s algorithm, and extends and optimizes it for the rigid body case. It addresses issues particular to rigid body simulation, such as collision detection and contact group management, and describes how to incorporate these into the timewarp framework. Quantitative experimental results indicate that the timewarp algorithm offers significant performance improvements over traditional high-level rigid body simulation algorithms, when applied to systems with hundreds of bodies. It also helps pave the way to parallel implementations, as the paper discusses.

1. D. Baraffand A. Witkin. Large Steps in Cloth Simulation. In Michael Cohen, editor, SIGGRAPH 98 Conference Proceedings, Annual Conference Series, pages 43-54. ACM SIGGRAPH, Addison Wesley, July 1998.
2. David Baraff. Curved Surfaces and Coherence for Non-Penetrating Rigid Body Simulation. In Computer Graphics (SIGGRAPH 90 Conference Proceedings), volume 24, pages 19-28. August 1990.
3. David Baraff. Dynamic Simulation of Non-Penetrating Rigid Bodies. Ph.D. thesis, Department of Computer Science, Cornell University, March 1992.
4. David Baraff. Fast Contact Force Computation for Nonpenetrating Rigid Bodies. In SIGGRAPH 94 Conference Proceedings, Annual Conference Series, pages 23-34. ACM SIGGRAPH, Addison Wesley, 1994.
5. David Baraff. Interactive Simulation of Solid Rigid Bodies. IEEE Computer Graphics and Applications, 15(3):63-75, May 1995.
6. Ronen Barzel and Alan H. Barr. A Modeling System Based on Dynamic Constraints. In Computer Graphics (SIGGRAPH 88 Conference Proceedings), volume 22, pages 179-188. August 1988.
7. J. Basch, L.J. Guibas, and J. Hershberger. Data Structures for Mobile Data. In Proceedings of 8th Symposium on Discrete Algorithms. 1997. To appear in J. of Algorithms.
8. Raymond M. Brach. Mechanical impact Dynamics; Rigid Body Collisions. John Wiley & Sons, Inc., 1991.
9. David C. Brogan, Ronald A. Metoyer, and Jessica K. Hodgins. Dynamically Simulated Characters in Virtual Environments. IEEE Computer Graphics and Applications, 18(5):58-69, September 1998.
10. Stephen Cameron. Enhancing GJK: Computing Minimum Penetration Distances between Convex Polyhedra. In Proceedings of international Conference on Robotics and Automation. IEEE, April 1997.
11. Deborah A. Carlson and Jessica K. Hodgins. Simulation Levels of Detail for Real-time Animation. In Proc. of Graphics interface ’97, pages 1-8. 1997.
12. Anindya Chatterjee and Andy Ruina. A New Algebraic Rigid Body Collision Law Based on Impulse Space Considerations. Journal of Applied Mechanics, 65:939-951, December 1998.
13. Stephen Chenney, Jeffrey Ichnowski, and David Forsyth. Dynamics Modeling and Culling. IEEE Computer Graphics and Applications, 19(2):79-87, March/April 1999.
14. Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, and Madhav K. Ponamgi. I-COLLIDE: An Interactive and Exact Collision Detection System for Large- Scaled Environments. In Symposium on interactive 3D Graphics, pages 189- 196. ACM SIGGRAPH, April 1995.
15. J. Dongarra, A. Lumsdaine, R. Pozo, and K. Remington. A Sparse Matrix Library in C++ for High Performance Architectures. In Proceedings of the Second Object Oriented Numerics Conference, pages 214-218. 1992. www. math. nis t. gov/iml + +.
16. R. Featherstone. The Calculation of Robot Dynamics Using Articulated-Body Inertias. international Journal of Robotics Research, 2(1): 13-30, 1983.
17. S. Gottschalk, M. C. Lin, and D. Manocha. OBB-Tree: A Hierarchical Structure for Rapid Interference Detection. In Holly Rushmeier, editor, SIGGRAPH 96 Conference Proceedings, Annual Conference Series. ACM SIGGRAPH, Addison Wesley, August 1996.
18. Brian Von Herzen, Alan H. Barr, and Harold R. Zatz. Geometric Collisions for Time-Dependent Parametric Surfaces. In Computer Graphics (SIGGRAPH 90 Conference Proceedings), pages 39-48.1990.
19. Jessica K. Hodgins and Nancy S. Pollard. Adapting Simulated Behaviors for New Characters. In Turner Whitted, editor, SIGGRAPH 97 Conference Proceedings, Annual Conference Series, pages 153-162. ACM SIGGRAPH, Addison Wesley, August 1997.
20. Jessica K. Hodgins, Wayne L. Wooten, David C. Brogan, and James F. O’Brien. Animating Human Athletics. In SIGGRAPH 95 Conference Proceedings, Annual Conference Series, pages 71-78. ACM SIGGRAPH, Addison Wesley, 1956.
21. Philip M. Hubbard. Approximating Polyhedra with Spheres for Time-Critical Collision Detection. ACM Transactions on Graphics, 15(3), July 1996.
22. David R. Jefferson. Virtual Time. ACM Transactions on Programming Languages and Systems, 7(3):404-425, July 1985.
23. V.V. Kamat. A Survey of Techniques for simulation of Dynamic Dynamic Collision Detection and Response. Computer Graphics in india, 17(4):379-385, 1993.
24. Kathryn W. Lilly. Efficient Dynamic Simulation of Robotic Mechanisms. Kluwer Academic Publishers, Norwell, 1993.
25. Victor J. Milenkovic. Position-Based Physics: Simulating the Motion of Many Highly Interacting Spheres and Polyhedra. In Holly Rushmeier, editor, SIG- GRAPH 96 Conference Proceedings, Annual Conference Series, pages 129-136. ACM SIGGRAPH, Addison Wesley, August 1996.
26. Brian Mirtich. impulse-based Dynamic Simulation of Rigid Body Systems. Ph.D. thesis, University of California, Berkeley, December 1996.
27. Brian Mirtich. V-Clip: Fast and Robust Polyhedral Collision Detection. ACM Transactions on Graphics, 17(3):177-208, July 1998. Mitsubishi Electric Research Lab Technical Report TR97-05.
28. J. Thomas Ngo and Joe Marks. Spacetime Constraints Revisited. In SIGGRAPH 93 Conference Proceedings, Annual Conference Series, pages 343-350. ACM SIGGRAPH, Addison Wesley, 1993.
29. M. Overmars. Point Location in Fat Subdivisions. information Processing Letters, 44:261-265, 1992.
30. William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian R. Flannery. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, Cambridge, second edition, 1992.
31. Edward J. Routh. Elementary Rigid Dynamics. Macmillan, London, 1905.
32. Karl Sims. Evolving Virtual Creatures. In SIGGRAPH 94 Conference Proceedings, Annual Conference Series, pages 15-22. ACM SIGGRAPH, 1994.
33. John M. Snyder, Adam R. Woodbury, Kurt Fleischer, Bena Currin, and Alan H. BAIT. Interval Methods for Multi-Point Collisions between Time-Dependent Curved Surfaces. In SIGGRAPH 93 Conference Proceedings, Annual Conference Series, pages 321-333. ACM SIGGRAPH, Addison Wesley, 1993.
34. Peng Song, Peter R. Kraus, Vijay Kumar, and Pierre Dupont. Analysis of Rigid Body Dynamic Models for Simulation of Systems with Frictional Contacts, June 1999. Submitted to ASME Journal of Applied Mechanics.
35. D.E. Stewart and J.C. Trinkle. An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Inelastic Collisions and Coulomb Friction. international Journal of Numerical Methods in Engineering, 39:2673-2691, 1996.
36. J.C. Trinkle, J.S. Pang, S. Sudarsky, and G. Lo. On Dynamic Multi-Rigid-Body Contact Problems with Coulomb Friction. Zeitschriftfur Angewandte Mathematik und Mechanik, 77(4):267-279, 1997.
37. Andrew Witkin, Michael Gleicher, and William Welch. Interactive Dynamics. Computer Graphics, 24(2): 11-22, March 1990.