Timewarp rigid body simulation

ABSTRACT

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.

REFERENCES

• 1: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 2: David Baraff, Curved surfaces and coherence for non-penetrating rigid body simulation, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.19-28, Aug. 1990
• 3: David Baraff, Dynamic simulation of nonpenetrating rigid bodies, Cornell University, Ithaca, NY, 1992
• 4: David Baraff, Fast contact force computation for nonpenetrating rigid bodies, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.23-34, July 1994 [doi>10.1145/192161.192168]
• 5: David Baraff, Interactive Simulation of Solid Rigid Bodies, IEEE Computer Graphics and Applications, v.15 n.3, p.63-75, May 1995 [doi>10.1109/38.376615]
• 6: Ronen Barzel , Alan H. Barr, A modeling system based on dynamic constraints, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.179-188, June 1988
• 7: Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
• 8: Raymond M. Brach. Mechanical impact Dynamics; Rigid Body Collisions. John Wiley & Sons, Inc., 1991.
• 9: David C. Brogan , Ronald A. Metoyer , Jessica K. Hodgins, Dynamically Simulated Characters in Virtual Environments, IEEE Computer Graphics and Applications, v.18 n.5, p.58-69, September 1998 [doi>10.1109/38.708561]
• 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 , Jessica K. Hodgins, Simulation levels of detail for real-time animation, Proceedings of the conference on Graphics interface '97, p.1-8, May 1997, Kelowna, British Columbia, Canada
• 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 , David Forsyth, Dynamics Modeling and Culling, IEEE Computer Graphics and Applications, v.19 n.2, p.79-87, March 1999 [doi>10.1109/38.749126]
• 14: Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
• 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 , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 18: Brian Von Herzen , Alan H. Barr , Harold R. Zatz, Geometric collisions for time-dependent parametric surfaces, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.39-48, September 1990, Dallas, TX, USA
• 19: Jessica K. Hodgins , Nancy S. Pollard, Adapting simulated behaviors for new characters, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.153-162, August 1997 [doi>10.1145/258734.258822]
• 20: Jessica K. Hodgins , Wayne L. Wooten , David C. Brogan , James F. O'Brien, Animating human athletics, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.71-78, September 1995 [doi>10.1145/218380.218414]
• 21: Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996 [doi>10.1145/231731.231732]
• 22: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 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, MA, 1993
• 25: Victor J. Milenkovic, Position-based physics: simulating the motion of many highly interacting spheres and polyhedra, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.129-136, August 1996 [doi>10.1145/237170.237222]
• 26: Brian Vincent Mirtich, Impulse-based dynamic simulation of rigid body systems, 1996
• 27: Brian Mirtich, V-Clip: fast and robust polyhedral collision detection, ACM Transactions on Graphics (TOG), v.17 n.3, p.177-208, July 1998 [doi>10.1145/285857.285860]
• 28: J. Thomas Ngo , Joe Marks, Spacetime constraints revisited, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.343-350, September 1993 [doi>10.1145/166117.166160]
• 29: Mark H. Overmars, Point location in fat subdivisions, Information Processing Letters, v.44 n.5, p.261-265, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90211-D]
• 30: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 31: Edward J. Routh. Elementary Rigid Dynamics. Macmillan, London, 1905.
• 32: Karl Sims, Evolving virtual creatures, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.15-22, July 1994 [doi>10.1145/192161.192167]
• 33: John M. Snyder , Adam R. Woodbury , Kurt Fleischer , Bena Currin , Alan H. Barr, Interval methods for multi-point collisions between time-dependent curved surfaces, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.321-334, September 1993 [doi>10.1145/166117.166158]
• 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 , William Welch, Interactive dynamics, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.11-21, Mar. 1990

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation; Continuous; Discrete event

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
animation, physics based modeling