“Large-scale dynamic simulation of highly constrained strands” by Sueda, Jones, Levin and Pai

  • ©Shinjiro Sueda, Garrett L. Jones, David I. W. Levin, and Dinesh K. Pai




    Large-scale dynamic simulation of highly constrained strands



    A significant challenge in applications of computer animation is the simulation of ropes, cables, and other highly constrained strandlike physical curves. Such scenarios occur frequently, for instance, when a strand wraps around rigid bodies or passes through narrow sheaths. Purely Lagrangian methods designed for less constrained applications such as hair simulation suffer from difficulties in these important cases. To overcome this, we introduce a new framework that combines Lagrangian and Eulerian approaches. The two key contributions are the reduced node, whose degrees of freedom precisely match the constraint, and the Eulerian node, which allows constraint handling that is independent of the initial discretization of the strand. The resulting system generates robust, efficient, and accurate simulations of massively constrained systems of rigid bodies and strands.


    1. Bergou, M., Wardetzky, M., Robinson, S., Audoly, B., and Grinspun, E. 2008. Discrete elastic rods. ACM Trans. Graph. 27, 3 (Aug), 63:1–63:12. Google ScholarDigital Library
    2. Bergou, M., Audoly, B., Vouga, E., Wardetzky, M., and Grinspun, E. 2010. Discrete viscous threads. ACM Trans. Graph. 29, 4 (Jul), 116:1–116:10. Google ScholarDigital Library
    3. Bertails, F., Audoly, B., Cani, M.-P., Querleux, B., Leroy, F., and Lévêque, J.-L. 2006. Super-helices for predicting the dynamics of natural hair. ACM Trans. Graph. 25, 3 (Jul), 1180–1187. Google ScholarDigital Library
    4. Bertails, F. 2009. Linear time super-helices. Computer Graphics Forum 28, 2, 417–426.Google ScholarCross Ref
    5. Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press. Google Scholar
    6. Chentanez, N., Alterovitz, R., Ritchie, D., Cho, L., Hauser, K. K., Goldberg, K., Shewchuk, J. R., and O’Brien, J. F. 2009. Interactive simulation of surgical needle insertion and steering. ACM Trans. Graph. 28, 3 (Jul), 88:1–88:10. Google ScholarDigital Library
    7. Choe, B., Choi, M. G., and Ko, H.-S. 2005. Simulating complex hair with robust collision handling. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 153–160. Google Scholar
    8. Cline, M. B., and Pai, D. K. 2003. Post-stabilization for rigid body simulation with contact and constraints. In Proc. IEEE International Conference on Robotics and Automation, vol. 3, 3744–3751.Google Scholar
    9. Coleman, P., and Singh, K. 2006. Cords: Geometric curve primitives for modeling contact. IEEE Computer Graphics and Applications 26, 3, 72–79. Google ScholarDigital Library
    10. Davis, T. A. 2006. Direct Methods for Sparse Linear Systems. SIAM Book Series on the Fundamentals of Algorithms. SIAM. Google Scholar
    11. Delp, S. L., Anderson, F. C., Arnold, A. S., Loan, P., Habib, A., John, T., Guendelman, E., and Thelen, D. G., 2007. Opensim: Open-source software to create and analyze dynamic simulations of movement.Google Scholar
    12. Donea, J., Huerta, A., Ponthot, J.-P., and Rodriguez-Ferran, A. 2004. Arbitrary lagrangian-eulerian methods. Encyclopedia of Computational Mechanics.Google Scholar
    13. Featherstone, R. 1987. Robot Dynamics Algorithms, 1st ed. Springer. Google Scholar
    14. Garćia-Fernández, I., Pla-Castells, M., and Martínez-Durá, R. J. 2008. Elevation cable modeling for interactive simulation of cranes. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 173–181. Google ScholarDigital Library
    15. Grégoire, M., and Schömer, E. 2007. Interactive simulation of one-dimensional flexible parts. Comput. Aided Des. 39 (Aug), 694–707. Google ScholarDigital Library
    16. Hadap, S. 2006. Oriented strands: dynamics of stiff multi-body system. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 91–100. Google Scholar
    17. Kaldor, J. M., James, D. L., and Marschner, S. 2008. Simulating knitted cloth at the yarn level. ACM Trans. Graph. 27, 3 (Aug), 65:1–65:9. Google ScholarDigital Library
    18. Kaldor, J. M., James, D. L., and Marschner, S. 2010. Efficient yarn-based cloth with adaptive contact linearization. ACM Trans. Graph. 29, 4 (Jul), 105:1–105:10. Google ScholarDigital Library
    19. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered projections for frictional contact in multibody systems. ACM Trans. Graph. 27, 5 (Dec), 164:1–164:11. Google ScholarDigital Library
    20. Kiss, B., Levine, J., and Mullhaupt, P. 1999. Modelling, flatness and simulation of a class of cranes. Periodica Polytechnica, Electrical Engineering, 43, 215–225.Google Scholar
    21. Kry, P. G., and Pai, D. K. 2003. Continuous contact simulation for smooth surfaces. ACM Trans. Graph. 22, 1 (Jan), 106–129. Google ScholarDigital Library
    22. Kubiak, B., Pietroni, N., Ganovelli, F., and Fratarcangeli, M. 2007. A robust method for real-time thread simulation. In Proc. ACM symposium on virtual reality software and technology, 85–88. Google Scholar
    23. Lee, S.-H., and Terzopoulos, D. 2008. Spline joints for multi-body dynamics. ACM Trans. Graph. 27, 3 (Aug), 22:1–22:8. Google ScholarDigital Library
    24. Lenoir, J., Grisoni, L., Meseure, P., Rémion, Y., and Chaillou, C. 2004. Smooth constraints for spline variational modeling. In GRAPHITE 2004, 58–64. Google ScholarDigital Library
    25. Lenoir, J., Cotin, S., Duriez, C., and Neumann, P. 2006. Interactive physically-based simulation of catheter and guidewire. Computer & Graphics 30, 3 (Jun), 417–423. Google ScholarDigital Library
    26. Martin, S., Kaufmann, P., Botsch, M., Grinspun, E., and Gross, M. 2010. Unified simulation of elastic rods, shells, and solids. ACM Trans. Graph. 29, 4 (Jul), 39:1–39:10. Google ScholarDigital Library
    27. McAdams, A., Selle, A., Ward, K., Sifakis, E., and Teran, J. 2009. Detail preserving continuum simulation of straight hair. ACM Trans. Graph. 28, 3 (Jul), 62:1–62:6. Google ScholarDigital Library
    28. Murray, R. M., Li, Z., and Sastry, S. S. 1994. A Mathematical Introduction to Robotic Manipulation. CRC Press. Google Scholar
    29. Nocent, O., and Remion, Y. 2001. Continuous deformation energy for dynamic material splines subject to finite displacements. In Proc. Eurographic workshop on Computer animation and simulation, Springer-Verlag, 88–97. Google ScholarDigital Library
    30. Pai, D. K. 2002. Strands: Interactive simulation of thin solids using cosserat models. Computer Graphics Forum 21, 3, 347–352.Google ScholarCross Ref
    31. Qin, H., and Terzopoulos, D. 1996. D-NURBS: A Physics-Based Framework for Geometric Design. IEEE Transactions on Visualization and Computer Graphics 2, 1, 85–96. Google ScholarDigital Library
    32. Remion, Y., Nourrit, J., and Gillard, D. 1999. Dynamic animation of spline like objects. In Proc. WSCG Conference, 426–432.Google Scholar
    33. Selle, A., Lentine, M., and Fedkiw, R. 2008. A mass spring model for hair simulation. ACM Trans. Graph. 27, 3 (Aug), 64:1–64:11. Google ScholarDigital Library
    34. Servin, M., and Lacoursiere, C. 2007. Massless cable for real-time simulation. Computer Graphics Forum 26, 2, 172–184.Google ScholarCross Ref
    35. Servin, M., Lacoursiere, C., and Bodin, K. 2010. Hybrid, multi-resolution wires with massless frictional contacts. IEEE Transactions on Visualization and Computer Graphics. Google Scholar
    36. Spillmann, J., and Teschner, M. 2008. An adaptive contact model for the robust simulation of knots. Computer Graphics Forum 27, 2, 497–506.Google ScholarCross Ref
    37. Spillmann, J., and Teschner, M. 2009. Cosserat nets. IEEE Trans. Vis. Comput. Graph. 15, 2, 325–338. Google ScholarDigital Library
    38. Sueda, S., Kaufman, A., and Pai, D. K. 2008. Musculotendon simulation for hand animation. ACM Trans. Graph. 27, 3 (Aug), 83:1–83:8. Google ScholarDigital Library
    39. Theetten, A., Grisoni, L., Andriot, C., and Barsky, B. 2008. Geometrically exact dynamic splines. Computer-Aided Design 40, 1, 35–48. Google ScholarDigital Library

ACM Digital Library Publication: