Adaptive dynamics of articulated bodies

Abstract

Forward dynamics is central to physically-based simulation and control of articulated bodies. We present an adaptive algorithm for computing forward dynamics of articulated bodies: using novel motion error metrics, our algorithm can automatically simplify the dynamics of a multi-body system, based on the desired number of degrees of freedom and the location of external forces and active joint forces. We demonstrate this method in plausible animation of articulated bodies, including a large-scale simulation of 200 animated humanoids and multi-body dynamics systems with many degrees of freedom. The graceful simplification allows us to achieve up to two orders of magnitude performance improvement in several complex benchmarks.

References

1. Anderson, K. S., and Duan, S. 2000. Highly parallelizable low-order dynamics simulation algorithm for multi-rigid-body systems. AIAA Journal on Guidance, Control, and Dynamics 23, 2, 355--364.
2. Ascher, U. M., Pai, D. K., and Cloutier, B. P. 1997. Forward dynamics, elimination methods, and formulation stiffness in robot simulation. In International Journal of Robotics Research, vol. 16. no. 6. pp. 749--758.
3. Bae, D., and Haug, E. 1987. A recursive formulation for constrained mechanical systems dynamics: Part i. open-loop systems. Mechanical Structures and Machines, Vol. 15, No. 3, pp. 359--382.
4. Baraff, D., and Witkin, A. 1997. Partitioned dynamics. Technical Report CMURI-TR-97-33, Robotics Institute. Carnegie Mellon University.
5. Baraff, D. 1996. Linear-Time simulation using lagrange multipliers. In SIGGRAPH 96 Conference Proceedings, Addison Wesley, H. Rushmeier, Ed., Annual Conference Series, ACM SIGGRAPH, 137--146. held in New Orleans, Louisiana, 04-09 August 1996.
6. Barzel, R., Hughes, J., and Wood, D. 1996. Plausible motion simulation for computer graphics animation. Proc. of Eurographics Workshop on Computer Animation and Simulation, pp. 183--197.
7. Beaudoin, J., and Keyser, J. 2004. Simulation levels of detail for plant motion. Proc. of ACM SIGGRAPH/Eurographics Symposium on Computer Animation.
8. Bertails, F., Kim, T.-Y., Cani, M.-P., and Neumann, U. 2003. Adaptive wisp tree - a multiresolution control structure for simulating dynamic clustering in hair motion. Proc. of ACM SIGGRAPH / Eurographics Symposium on Computer Animation.
9. Brandl, H., Johanni, R., and Otter, M. 1986. A very efficient algorithm for the simulation of robots and similar multibody systems without inversion of the mass matrix. IFAC/IFIP/IMACS Symposium, pp. 95--100.
10. Bruderlin, A., and Calvert, T. 1989. Goal-directed, dynamic animation of human walking. In Computer Graphics (Proc. of SIGGRAPH'89), 233--242.
11. Bruderlin, A., and Calvert, T. 1996. Knowledge-driven, interactive animation of human running. In Proc. of Graphics Interface, 213--221.
12. Carlson, D., and Hodgins, J. 1997. Simulation levels of detail for real-time animation. In Proc. of Graphics Interface 1997.
13. Chenney, S., and Forsyth, D. 1997. View-dependent culling of dynamic systems in virtual environments. In Proc. of ACM Symposium on Interactive 3D Graphics.
14. Chenney, S., Ichnowski, J., and Forsyth, D. 1999. Dynamics modeling and culling. IEEE Computer Graphics and Applications March/April, pp. 79--87.
15. Chenney, S., Arikan, and Forsyth, D. 2001. Proxy simulations for efficient dynamics. Proc. of Eurographics 2001, Short Presentations.
16. Faure, F. 1999. Fast iterative refinement of articulated solid dynamics. IEEE Trans. on Visualization and Computer Graphics 5, 3, 268--276.
17. Featherstone, R., and Orin, D. E. 2000. Robot dynamics: Equations and algorithms. IEEE Int. Conf. Robotics and Automation, pp. 826--834.
18. Featherstone, R. 1987. Robot Dynamics Algorithms. Kluwer, Boston, MA.
19. Featherstone, R. 1999. A divide-and-conquer articulated body algorithm for parallel o(log(n)) calculation of rigid body dynamics. part 1: Basic algorithm. International Journal of Robotics Research 18(9):867--875.
20. Featherstone, R. 1999. A divide-and-conquer articulated body algorithm for parallel o(log(n)) calculation of rigid body dynamics. part 2: Trees, loops, and accuracy. International Journal of Robotics Research 18(9):876--892.
21. Featherstone, R. 2004. An empirical study of the joint space inertia matrix. In International Journal of Robotics Research, vol. 23, no. 9, pp. 859--871.
22. Fijany, A., Sharf, I., and D'Eleuterio, G. 1995. Parallel o(log n) algorithms for computation of manipulator forward dynamics. IEEE Trans. Robotics and Automation 11(3):389400.
23. Gillespie, R. B., and Colgate, J. E. 1997. A survey of multibody dynamics for virtual environments. Proc. of ASME Int. Mech, Engr. Conf. and Expo.
24. Girard, M., and Maciejewski, A. 1985. Computational modeling for computer animation of legged figures. In Computer Graphics (Proc. of SIGGRAPH), vol, 19. 263--270.
25. Granieri, J., Crabtree, J., and Badler, N. 1995. Production and playback of human figure motion for 3d virtual environments. In Proc. of VRAIS, 127--135.
26. Hollerbach, J. 1980. A recursive lagrangian formulation of manipulator dynamics and a comparative study of dynamics formulation complexity. IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-10, No. 11.
27. Ko, H., and Badler, N. 1993. Straight-line walking animation based on kinematic generalization that preserves the original characteristics. In Proc. of Graphics Interfaces.
28. Kokkevis, E., Metaxas, D., and Badler, N. 1996. User-controlled physics-based animation for articulated figures. Proc. of Computer Animation, 16--26.
29. McMillan, S., and Orin, D. E. 1995. Efficient computation of articulated-body inertias using successive axial screws. IEEE Trans. on Robotics and Automation, vol. 11, pp. 606--611.
30. Mueller, A., and Maisser, P. 2003. A lie-group formulation of kinematics and dynamics of constrained mbs and its application to analytical mechanics. Multibody System Dynamics, vol. 9, no. 4, pp. 311--352(42).
31. Multon, F., Valton, B., Jouin, B., and Cozor, R. 1999. Motion levels of detail for real-time virtual worlds. Proc. of ASTC-VR'99.
32. O'BRIEN, D., FISHER, S., AND LIN, M. 2001. Simulation level of detail for automatic simplification of particle system dynamics. Proc. of Computer Animation, 210--219.
33. Perbet, F., and Cani, M. 2001. Animating prairies in real-time. Proc. of ACM Symposium on Interactive 3D graphics.
34. Perlin, K. 1995. Real time responsive animation with personality. IEEE Transactions on Visualization and Computer Graphics 1, 1, 5--15.
35. Popovic, Z., and Witkin, A. 1999. Physically based motion transformation. In Proc. of SIGGRAPH 1999, 11--20.
36. Redon, S., and Lin, M. C. 2005. An efficient, error-bounded approximation algorithm for simulating quasi-statics of complex linkages. In Proceedings of ACM Symposium on Solid and Physical Modeling.
37. Reitsma, P. S. A., and Pollard, N. S. 2003. Perceptual metrics for character animation: Sensitivity to errors in ballistic motion. In ACM Transactions on Graphics 22(3) 537--542, SIGGRAPH 2003 Proceedings.
38. Rodriguez, G., Jain, A., and Kreutz-Delgado, K. 1991. Spatial operator algebra for manipulator modelling and control. Int. J. Robotics Research, vol. 10, no. 4, pp. 371--381.
39. Ward, K., and Lin, M. 2003. Proc. of pacific graphics. Adaptive Grouping and Subdivision for Simulating Hair Dynamics.
40. Ward, K., Lin, M., Lee, J., Fisher, S., and Macri, D., 2003. Modeling hair using level-of-detail representations. http://gamma.cs.unc.edu/HSLOD.
41. Yamane, K., and Nakamura, Y. 2002. Efficient parallel dynamics computation of human figures. Proc. of IEEE Int. Conf. on Robotics and Automation, pp. 530--537.
42. Yamane, K., Kuffner, J., and Hodgins, J. 2004. Synthesizing animations of human manipulation tasks. ACM Trans. on Graphics (Proc. SIGGRAPH 2004).

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

      • Physical simulation

    • Shape modeling

  • Modeling and simulation

    • Simulation types and techniques

      • Simulation by animation

• Mathematics of computing

  • Continuous mathematics

    • Topology

      • Geometric topology

• Software and its engineering

  • Software notations and tools

    • Development frameworks and environments

      • Application specific development environments