“Adaptive nonlinearity for collisions in complex rod assemblies” by Smith, Kaufman, Tamstorf, Grinspun and Aubry

  • ©Breannan Smith, Danny M. Kaufman, Rasmus Tamstorf, Eitan Grinspun, and Jean-Marie Aubry



Session Title:

    Hair & Collisions


    Adaptive nonlinearity for collisions in complex rod assemblies




    We develop an algorithm for the efficient and stable simulation of large-scale elastic rod assemblies. We observe that the time-integration step is severely restricted by a strong nonlinearity in the response of stretching modes to transversal impact, the degree of this nonlinearity varying greatly with the shape of the rod. Building on these observations, we propose a collision response algorithm that adapts its degree of nonlinearity. We illustrate the advantages of the resulting algorithm by analyzing simulations involving elastic rod assemblies of varying density and scale, with up to 1.7 million individual contacts per time step.


    1. Alart, P., and Curnier, A. 1991. A mixed formulation for frictional contact problems prone to Newton like solution methods. Computer Methods in Applied Mechanics and Engineering 92, 3 (Nov.), 353–375. Google ScholarDigital Library
    2. Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. G. 2010. Volume Contact Constraints at Arbitrary Resolution. ACM Trans. Graph. 29, 4 (July), 82:1–82:10. Google ScholarDigital Library
    3. Baraff, D., and Witkin, A. 1998. Large Steps in Cloth Simulation. In Proceedings of SIGGRAPH 98, Annual Conference Series, 43–54. Google ScholarDigital Library
    4. Baraff, D. 1989. Analytical Methods for Dynamic Simulation of Non-penetrating Rigid Bodies. Computer Graphics 23, 223–232. Google ScholarDigital Library
    5. 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
    6. Bergou, M., Audoly, B., Vouga, E., Wardetzky, M., and Grinspun, E. 2010. Discrete Viscous Threads. ACM Trans. Graph. 29, 4 (July), 116:1–116:10. Google ScholarDigital Library
    7. Bertails-Descoubes, F., Cadoux, F., Daviet, G., and Acary, V. 2011. A Nonsmooth Newton Solver for Capturing Exact Coulomb Friction in Fiber Assemblies. ACM Trans. Graph. 30, 1 (Feb.), 6:1–6:14. Google ScholarDigital Library
    8. Bonnefon, O., and Daviet, G. 2011. Quartic formulation of Coulomb 3D frictional contact. Tech. Rep. RT-0400, INRIA, Jan.Google Scholar
    9. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust Treatment of Collisions, Contact, and Friction for Cloth Animation. ACM Trans. Graph. 21, 3 (July), 594–603. Google ScholarDigital Library
    10. Daviet, G., Bertails-Descoubes, F., and Boissieux, L. 2011. A Hybrid Iterative Solver for Robustly Capturing Coulomb Friction in Hair Dynamics. ACM Trans. Graph. 30, 6 (Dec.), 139:1–139:12. Google ScholarDigital Library
    11. Duriez, C., Andriot, C., and Kheddar, A. 2004. Signorini’s contact model for deformable objects in haptic simulations. In IEEE/RSJ IROS, vol. 4, 3232–3237.Google Scholar
    12. Duriez, C., Dubois, F., Kheddar, A., and Andriot, C. 2006. Realistic Haptic Rendering of Interacting Deformable Objects in Virtual Environments. IEEE Transactions on Visualization and Computer Graphics 12, 1 (Jan.), 36–47. Google ScholarDigital Library
    13. Goyal, S., Ruina, A., and Papadopoulos, J. 1991. Planar sliding with dry friction Part 2. Dynamics of motion. Wear 143, 2, 331–352.Google ScholarCross Ref
    14. Hadap, S., Cani, M.-P., Lin, M., Kim, T.-Y., Bertails, F., Marschner, S., Ward, K., and Kačić-Alesić, Z. 2007. Strands and Hair: Modeling, Animation, and Rendering. In ACM SIGGRAPH Courses, 1–150. Google ScholarDigital Library
    15. Hairer, E., and Wanner, G. 2004. Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, second ed. Springer.Google Scholar
    16. Iben, H., Meyer, M., Petrovic, L., Soares, O., Anderson, J., and Witkin, A. 2013. Artistic Simulation of Curly Hair. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 63–71. Google ScholarDigital Library
    17. Jean, M., and Moreau, J. J. 1992. Unilaterality and dry friction in the dynamics of rigid body collections. In Proceedings of Contact Mechanics International Symposium, vol. 1, 31–48.Google Scholar
    18. Jourdan, F., Alart, P., and Jean, M. 1998. A Gauss-Seidel like algorithm to solve frictional contact problems. Computer Methods in Applied Mechanics and Engineering 155, 1 (Mar.), 31–47.Google ScholarCross Ref
    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. Kikuchi, N., and Oden, J. T. 1988. Contact Problems in Elasticity: A Study of Variational Inequalities and Finite Element Methods, vol. 8 of SIAM Studies in Applied and Numerical Mathematics. Society for Industrial and Applied Mathematics.Google Scholar
    21. Landau, L. D., and Lifshitz, E. 1986. Theory Of Elasticity, Course of Theoretical Physics, Vol. 7. Pergamon Press, Oxford.Google Scholar
    22. McAdams, A., Selle, A., Ward, K., Sifakis, E., and Teran, J. 2009. Detail Preserving Continuum Simulation of Straight Hair. ACM Trans. Graph. 28, 3 (July), 62:1–62:6. Google ScholarDigital Library
    23. Mirtich, B., and Canny, J. 1995. Impulse-based Simulation of Rigid Bodies. In Proceedings of the 1995 Symposium on Interactive 3D Graphics, 181–ff. Google ScholarDigital Library
    24. Moreau, J. J. 1988. Unilateral Contact and Dry Friction in Finite Freedom Dynamics. Nonsmooth Mechanics and Applications, CISM Courses and Lectures, 302, 1–82.Google Scholar
    25. Otaduy, M. A., Tamstorf, R., Steinemann, D., and Gross, M. 2009. Implicit Contact Handling for Deformable Objects. Computer Graphics Forum 28, 2, 559–568.Google ScholarCross Ref
    26. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation, Eurographics, 177–189.Google Scholar
    27. Robbins, C. R. 2012. Chemical and Physical Behavior of Human Hair, fifth ed. Springer.Google Scholar
    28. 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
    29. Spillmann, J., and Teschner, M. 2007. CORDE: Cosserat Rod Elements for the Dynamic Simulation of One-Dimensional Elastic Objects. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 63–72. Google ScholarDigital Library
    30. Stewart, D. E. 2001. Finite-dimensional contact mechanics. Phil. Trans. R. Soc. Lond. A 359, 2467–2482.Google ScholarCross Ref
    31. Stewart, D. E. 2011. Dynamics with Inequalities: Impacts and Hard Constraints. Society for Industrial and Applied Mathematics. Google ScholarDigital Library
    32. Ward, K., Bertails, F., Kim, T.-Y., Marschner, S. R., Cani, M.-P., and Lin, M. C. 2007. A Survey on Hair Modeling: Styling, Simulation, and Rendering. IEEE Transactions on Visualization and Computer Graphics 13, 2 (Mar.), 213–234. Google ScholarDigital Library
    33. Zheng, C., and James, D. L. 2011. Toward High-Quality Modal Contact Sound. ACM Trans. Graph. 30, 4 (July), 38:1–38:12. Google ScholarDigital Library

ACM Digital Library Publication: