“Adaptive dynamics of articulated bodies” by Redon, Galoppo and Lin

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.

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.Google ScholarCross Ref
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. Google ScholarDigital Library
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.Google ScholarCross Ref
4. Baraff, D., and Witkin, A. 1997. Partitioned dynamics. Technical Report CMURI-TR-97-33, Robotics Institute. Carnegie Mellon University.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarDigital Library
7. Beaudoin, J., and Keyser, J. 2004. Simulation levels of detail for plant motion. Proc. of ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
10. Bruderlin, A., and Calvert, T. 1989. Goal-directed, dynamic animation of human walking. In Computer Graphics (Proc. of SIGGRAPH’89), 233–242. Google ScholarDigital Library
11. Bruderlin, A., and Calvert, T. 1996. Knowledge-driven, interactive animation of human running. In Proc. of Graphics Interface, 213–221. Google ScholarDigital Library
12. Carlson, D., and Hodgins, J. 1997. Simulation levels of detail for real-time animation. In Proc. of Graphics Interface 1997. Google ScholarDigital Library
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. Google ScholarDigital Library
14. Chenney, S., Ichnowski, J., and Forsyth, D. 1999. Dynamics modeling and culling. IEEE Computer Graphics and Applications March/April, pp. 79–87. Google ScholarDigital Library
15. Chenney, S., Arikan, and Forsyth, D. 2001. Proxy simulations for efficient dynamics. Proc. of Eurographics 2001, Short Presentations.Google Scholar
16. Faure, F. 1999. Fast iterative refinement of articulated solid dynamics. IEEE Trans. on Visualization and Computer Graphics 5, 3, 268–276. Google ScholarDigital Library
17. Featherstone, R., and Orin, D. E. 2000. Robot dynamics: Equations and algorithms. IEEE Int. Conf. Robotics and Automation, pp. 826–834.Google Scholar
18. Featherstone, R. 1987. Robot Dynamics Algorithms. Kluwer, Boston, MA. Google ScholarDigital Library
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.Google ScholarCross Ref
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.Google ScholarCross Ref
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.Google ScholarCross Ref
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.Google ScholarCross Ref
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.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
28. Kokkevis, E., Metaxas, D., and Badler, N. 1996. User-controlled physics-based animation for articulated figures. Proc. of Computer Animation, 16–26. Google ScholarDigital Library
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.Google ScholarCross Ref
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).Google ScholarCross Ref
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.Google Scholar
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.Google Scholar
33. Perbet, F., and Cani, M. 2001. Animating prairies in real-time. Proc. of ACM Symposium on Interactive 3D graphics. Google ScholarDigital Library
34. Perlin, K. 1995. Real time responsive animation with personality. IEEE Transactions on Visualization and Computer Graphics 1, 1, 5–15. Google ScholarDigital Library
35. Popovic, Z., and Witkin, A. 1999. Physically based motion transformation. In Proc. of SIGGRAPH 1999, 11–20. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
39. Ward, K., and Lin, M. 2003. Proc. of pacific graphics. Adaptive Grouping and Subdivision for Simulating Hair Dynamics. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
42. Yamane, K., Kuffner, J., and Hodgins, J. 2004. Synthesizing animations of human manipulation tasks. ACM Trans. on Graphics (Proc. SIGGRAPH 2004). Google ScholarDigital Library