“RedMax: efficient & flexible approach for articulated dynamics” by Wang, Weidner, Baxter, Hwang, Kaufman, et al. …
Conference:
Type(s):
Title:
- RedMax: efficient & flexible approach for articulated dynamics
Session/Category Title: Motion is in Control
Presenter(s)/Author(s):
Abstract:
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.
References:
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
