“RedMax: efficient & flexible approach for articulated dynamics” by Wang, Weidner, Baxter, Hwang, Kaufman, et al. …

  • ©Ying Wang, Nicholas J. Weidner, Margaret A. Baxter, Yura Hwang, Danny M. Kaufman, and Shinjiro Sueda




    RedMax: efficient & flexible approach for articulated dynamics

Session/Category Title: Motion is in Control



    It is well known that the dynamics of articulated rigid bodies can be solved in O(n) time using a recursive method, where n is the number of joints. However, when elasticity is added between the bodies (e.g., damped springs), with linearly implicit integration, the stiffness matrix in the equations of motion breaks the tree topology of the system, making the recursive O(n) method inapplicable. In such cases, the only alternative has been to form and solve the system matrix, which takes O(n3) time. We propose a new approach that is capable of solving the linearly implicit equations of motion in near linear time. Our method, which we call RedMax, is built using a combined reduced/maximal coordinate formulation. This hybrid model enables direct flexibility to apply arbitrary combinations of constraints and contact modeling in both reduced and maximal coordinates, as well as mixtures of implicit and explicit forces in either coordinate representation. We highlight RedMax’s flexibility with seamless integration of deformable objects with two-way coupling, at a standard additional cost. We further highlight its flexibility by constructing an efficient internal (joint) and external (environment) frictional contact solver that can leverage bilateral joint constraints for rapid evaluation of frictional articulated dynamics.


    1. V. Acary and B. Brogliato. 2008. Numerical Methods for Nonsmooth Dynamical Systems: Applications in Mechanics and Electronics. Springer Science & Business Media.Google Scholar
    2. M. Anitescu and G. D. Hart. 2004. A Fixed-point Iteration Approach for Multibody Dynamics with Contact and Small Friction. MATH. PROG. 101, 1 (2004), 3–32. Google ScholarDigital Library
    3. A. Avello, J. M. Jiménez, E. Bayo, and J. G. de Jalón. 1993. A Simple and Highly Parallelizable Method for Real-time Dynamic Simulation Based on Velocity Transformations. Comput. Methods in Appl. Mech. Eng. 107, 3 (1993), 313–339.Google ScholarCross Ref
    4. D.-S. Bae and E. J. Haug. 1987a. A Recursive Formulation for Constrained Mechanical System Dynamics: Part I. Open Loop Systems. J STRUCT MECH 15, 3 (1987), 359–382.Google Scholar
    5. D.-S. Bae and E. J. Haug. 1987b. A Recursive Formulation for Constrained Mechanical System Dynamics: Part II. Closed Loop Systems. J STRUCT MECH 15, 4 (1987), 481–506.Google Scholar
    6. D. Baraff. 1996. Linear-time Dynamics Using Lagrange Multipliers. In Annual Conference Series (Proc. SIGGRAPH). 137–146. Google ScholarDigital Library
    7. D. Baraff and A. Witkin. 1998. Large Steps in Cloth Simulation. In Annual Conference Series (Proc. SIGGRAPH). 43–54. Google ScholarDigital Library
    8. J. Baumgarte. 1972. Stabilization of Constraints and Integrals of Motion in Dynamical Systems. Comput. Methods in Appl. Mech. Eng. 1 (Jun 1972), 1–16.Google Scholar
    9. F. Bertails. 2009. Linear Time Super-Helices. Computer Graphics Forum (Proc. Eurographics) 28, 2 (May 2009), 417–426.Google ScholarCross Ref
    10. S. Bouaziz, S. Martin, T. Liu, L. Kavan, and M. Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Trans. Graph. 33, 4, Article 154 (July 2014). Google ScholarDigital Library
    11. S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press. Google ScholarDigital Library
    12. M. B. Cline and D. K. Pai. 2003. Post-stabilization for Rigid Body Simulation with Contact and Constraints. In IEEE Int. Conf. Robot. Autom., Vol. 3. 3744–3751.Google Scholar
    13. J. G. De Jalon and E. Bayo. 2012. Kinematic and Dynamic Simulation of Multibody Systems: The Real-Time Challenge. Springer Science & Business Media.Google Scholar
    14. S. L. Delp, F. C. Anderson, A. S. Arnold, P. Loan, A. Habib, C. T. John, E. Guendelman, and D. G. Thelen. 2007. OpenSim: Open-source Software to Create and Analyze Dynamic Simulations of Movement. IEEE T BIO-MED ENG 54, 11 (2007), 1940–1950.Google ScholarCross Ref
    15. E. D. Demaine and J. O’Rourke. 2008. Geometric Folding Algorithms: Linkages, Origami, Polyhedra (reprint ed.). Cambridge University Press. Google ScholarDigital Library
    16. M. Deuss, D. Panozzo, E. Whiting, Y. Liu, P. Block, O. Sorkine-Hornung, and M. Pauly.Google Scholar
    17. 2014 Assembling Self-supporting Structures. ACM Trans. Graph. 33, 6, Article 214 (Nov. 2014). Google ScholarDigital Library
    18. E. Drumwright. 2012. Fast Dynamic Simulation of Highly Articulated Robots with Contact Via θ(n2) Time Dense Generalized Inertia Matrix Inversion. In Int. Conf. on Sim., Model., & Prog. for Auton. Robots. Springer, 65–76. Google ScholarDigital Library
    19. E. Drumwright and D. A. Shell. 2010. Modeling Contact Friction and Joint Friction in Dynamic Robotic Simulation Using the Principle of Maximum Dissipation. In Algorithmic Foundations of Robotics IX. Springer, 249–266.Google Scholar
    20. E. Evans, Y. Hwang, S. Sueda, and T. A. Uyeno. 2018. Estimating Whole Body Flexibility in Pacific Hagfish. In The Society for Integrative & Comparative Biology.Google Scholar
    21. R. Featherstone. 1983. The Calculation of Robot Dynamics Using Articulated-body Inertias. INT J ROBOT RES 2, 1 (1983), 13–30.Google ScholarCross Ref
    22. S. Hadap. 2006. Oriented Strands: Dynamics of Stiff Multi-body System. In Proc. ACM SIGGRAPH / Eurographics Symp. Comput. Anim. (SCA ’06). 91–100. Google ScholarDigital Library
    23. F. Hernandez, C. Garre, R. Casillas, and M. A. Otaduy. 2011. Linear-Time Dynamics of Characters with Stiff Joints. In V Ibero-American Symposium on Computer Graphics (SIACG 2011). The Eurographics Association and Blackwell Publishing Ltd.Google Scholar
    24. S. Jain and C. K. Liu. 2011. Controlling Physics-based Characters Using Soft Contacts. ACM Trans. Graph. 30, 6, Article 163 (Dec. 2011). Google ScholarDigital Library
    25. D. M. Kaufman, S. Sueda, D. L. James, and D. K. Pai. 2008. Staggered Projections for Frictional Contact in Multibody Systems. ACM Trans. Graph. 27, 5, Article 164 (Dec 2008). Google ScholarDigital Library
    26. J. Kim. 2012. Lie Group Formulation of Articulated Rigid Body Dynamics. Technical Report. Carnegie Mellon University.Google Scholar
    27. J. Kim and N. S. Pollard. 2011. Fast Simulation of Skeleton-driven Deformable Body Characters. ACM Trans. Graph. 30, 5, Article 121 (Oct. 2011). Google ScholarDigital Library
    28. C. Lanczos. 2012. The Variational Principles of Mechanics (4 ed.). Dover Publications.Google Scholar
    29. J. Leijnse, P. Quesada, and C. Spoor. 2010. Kinematic Evaluation of the Finger’s Interphalangeal Joints Coupling Mechanism—variability, Flexion-extension Differences, Triggers, Locking Swanneck Deformities, Anthropometric Correlations. Journal of Biomechanics 43, 12 (2010), 2381–2393.Google ScholarCross Ref
    30. J. Li, G. Daviet, R. Narain, F. Bertails-Descoubes, M. Overby, G. E. Brown, and L. Boissieux. 2018. An Implicit Frictional Contact Solver for Adaptive Cloth Simulation. ACM Trans. Graph. 37, 4, Article 52 (July 2018). Google ScholarDigital Library
    31. L. Liu, K. Yin, B. Wang, and B. Guo. 2013. Simulation and Control of Skeleton-driven Soft Body Characters. ACM Trans. Graph. 32, 6, Article 215 (Nov. 2013). Google ScholarDigital Library
    32. M. Müller, B. Heidelberger, M. Hennix, and J. Ratcliff. 2007. Position Based Dynamics. J VIS COMMUN IMAGE R 18, 2 (2007), 109–118. Google ScholarDigital Library
    33. D. Negrut, R. Serban, and F. A. Potra. 1997. A Topology-based Approach to Exploiting Sparsity in Multibody Dynamics: Joint Formulation. J STRUCT MECH 25, 2 (1997), 221–241.Google Scholar
    34. E. P. Popov, A. F. Vereshchagin, and S. L. Zenkevich. 1978. Robot Manipulators: Dynamics and Algorithms.Google Scholar
    35. E. Quigley, Y. Yu, J. Huang, W. Lin, and R. Fedkiw. 2018. Real-Time Interactive Tree Animation. IEEE TVCG 24, 5 (May 2018), 1717–1727.Google Scholar
    36. S. Redon, N. Galoppo, and M. C. Lin. 2005. Adaptive Dynamics of Articulated Bodies. ACM Trans. Graph. 24, 3 (July 2005), 936–945. Google ScholarDigital Library
    37. R. E. Roberson. 1966. A Dynamical Formalism for an Arbitrary Number of Interconnected Rigid Bodies with Reference to the Problem of Satellite Attitude Control.Google Scholar
    38. Proc. 3rd Congr. of Int. Fed. Automatic Control 1 (1966), 46D1–46D8.Google Scholar
    39. P. Sachdeva, S. Sueda, S. Bradley, M. Fain, and D. K. Pai. 2015. Biomechanical Simulation and Control of Hands and Tendinous Systems. ACM Trans. Graph. 34, 4, Article 42 (July 2015). Google ScholarDigital Library
    40. L. Sciavicco and B. Siciliano. 2012. Modelling and Control of Robot Manipulators. Springer Science & Business Media.Google Scholar
    41. R. Serban, D. Negrut, E. J. Haug, and F. A. Potra. 1997. A Topology-based Approach for Exploiting Sparsity in Multibody Dynamics in Cartesian Formulation. J STRUCT MECH 25, 3 (1997), 379–396.Google Scholar
    42. A. A. Shabana. 2013. Dynamics of Multibody Systems. Cambridge University press.Google Scholar
    43. H. V. Shin, C. F. Porst, E. Vouga, J. Ochsendorf, and F. Durand. 2016. Reconciling Elastic and Equilibrium Methods for Static Analysis. ACM Trans. Graph. 35, 2, Article 13 (Feb. 2016). Google ScholarDigital Library
    44. T. Shinar, C. Schroeder, and R. Fedkiw. 2008. Two-way Coupling of Rigid and Deformable Bodies. In Proc. ACM SIGGRAPH / Eurographics Symp. Comput. Anim. 95–103. Google ScholarDigital Library
    45. E. Sifakis and J. Barbic. 2012. FEM Simulation of 3D Deformable Solids: A Practitioner’s Guide to Theory, Discretization and Model Reduction. In ACM SIGGRAPH 2012 Courses. Google ScholarDigital Library
    46. D. E. Stewart. 2000. Rigid-Body Dynamics with Friction and Impact. SIAM Rev. 42, 1 (March 2000), 3–39. Google ScholarDigital Library
    47. S. Sueda, A. Kaufman, and D. K. Pai. 2008. Musculotendon Simulation for Hand Animation. ACM Trans. Graph. 27, 3, Article 83 (Aug. 2008). Google ScholarDigital Library
    48. M. Tournier, M. Nesme, B. Gilles, and F. Faure. 2015. Stable Constrained Dynamics. ACM Trans. Graph. 34, 4, Article 132 (July 2015). Google ScholarDigital Library
    49. M. W. Walker and D. E. Orin. 1982. Efficient Dynamic Computer Simulation of Robotic Mechanisms. J DYN SYST-T ASME 104, 3 (1982), 205–211.Google ScholarCross Ref
    50. J. M. Wang, S. R. Hamner, S. L. Delp, and V. Koltun. 2012. Optimizing Locomotion Controllers Using Biologically-based Actuators and Objectives. ACM Trans. Graph. 31, 4, Article 25 (July 2012). Google ScholarDigital Library
    51. T. M. Wasfy and A. K. Noor. 2003. Computational Strategies for Flexible Multibody Systems. APPL MECH REV 56, 6 (2003), 553–613.Google ScholarCross Ref
    52. E. Whiting, H. Shin, R. Wang, J. Ochsendorf, and F. Durand. 2012. Structural Optimization of 3D Masonry Buildings. ACM Trans. Graph. 31, 6, Article 159 (Nov. 2012). Google ScholarDigital Library
    53. Y. Zhou, S. Sueda, W. Matusik, and A. Shamir. 2014. Boxelization: Folding 3D Objects into Boxes. ACM Trans. Graph. 33, 4, Article 71 (July 2014). Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: