“A Nonsmooth Newton Solver for Capturing Exact Coulomb Friction in Fiber Assemblies” by Bertails, Cadoux, Daviet and Acary

We focus on the challenging problem of simulating thin elastic rods in contact, in the presence of friction. Most previous approaches in computer graphics rely on a linear complementarity formulation for handling contact in a stable way, and approximate Coulombs’s friction law for making the problem tractable. In contrast, following the seminal work by Alart and Curnier in contact mechanics, we simultaneously model contact and exact Coulomb friction as a zero finding problem of a nonsmooth function. A semi-implicit time-stepping scheme is then employed to discretize the dynamics of rods constrained by frictional contact: this leads to a set of linear equations subject to an equality constraint involving a nondifferentiable function. To solve this one-step problem we introduce a simple and practical nonsmooth Newton algorithm which proves to be reasonably efficient and robust for systems that are not overconstrained. We show that our method is able to finely capture the subtle effects that occur when thin elastic rods with various geometries enter into contact, such as stick-slip instabilities in free configurations, entangling curls, resting contacts in braid-like structures, or the formation of tight knots under large constraints. Our method can be viewed as a first step towards the accurate modeling of dynamic fibrous materials.

1. Acary, V. and Brogliato, B. 2008. Numerical Methods for Nonsmooth Dynamical Systems. Lecture Notes in Computational and Applied Mechanics, vol. 35. Springer.
2. Acary, V., Cadoux, F., Lemarechal, C., and Malick, J. 2010. A formulation of the linear discrete Coulomb friction problem via convex optimization. ZAMM/Z angew Math Mech; Zeitschrift für Angewandte Mathematik und Mechanik.
3. Alart, P. and Curnier, A. 1991. A mixed formulation for frictional contact problems prone to Newton like solution methods. Comput. Methods Appl. Mech. Engin. 92, 3, 353–375.
4. Baraff, D. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Proceedings of the ACM SIGGRAPH’ Conference. ACM, New York, 223–232.
5. Baraff, D. 1993. Issues in computing contact forces for non-penetrating rigid bodies. Algorithmica 10, 292–352.
6. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of the ACM SIGGRAPH’ Conference. ACM, New York, 23–34.
7. Baraff, D. and Witkin, A. 1992. Dynamic simulation of non-penetrating flexible bodies. In Proceedings of the ACM SIGGRAPH’ Conference. 303–308.
8. Baraff, D. and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of the ACM SIGGRAPH’ Conference. 43–54.
9. Barbič, J. and James, D. 2007. Time-Critical distributed contact for 6-dof haptic rendering of adaptively sampled reduced deformable models. In Proceedings of the ACM SIGGRAPH – EG Symposium on Computer Animation (SCA’07). Eurographics Association, 171–180.
10. Bergou, M., Wardetzky, M., Robinson, S., Audoly, B., and Grinspun, E. 2008. Discrete elastic rods. ACM Trans. Graph. 27, 3, 1–12.
11. Bertails, F. 2009. Linear time super-helices. Comput. Graph. Forum 28, 2.
12. 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. In Proceedings of the ACM SIGGRAPH. ACM, 1180–1187.
13. Blinn, J. 1998. Ten more unsolved problems in computer graphics. IEEE Comput. Graph. Appl. 18, 5, 86–89.
14. Bonnans, J. F., Gilbert, J. C., Lemaréchal, C., and Sagastizábal, C. A. 2003. Numerical Optimization. Springer, Berlin.
15. Bridson, R., Fedkiw, R., and Anderson, R. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3, 594–603.
16. Cadoux, F. 2009. Méthodes d’optimisation pour la dynamique non-régulière. Ph.D. thesis, Université Joseph Fourier.
17. Choe, B., Choi, M., and Ko, H.-S. 2005. Simulating complex hair with robust collision handling. In Proceedings of the ACM SIGGRAPH – EG Symposium on Computer Animation (SCA’05). 153–160.
18. Christensen, P., Klarbring, A., Pang, J., and Stromberg, N. 1998. Formulation and comparison of algorithms for frictional contact problems. Int. J. Numer. Methods Engin. 42, 1, 145–173.
19. Duriez, C., Dubois, F., Kheddar, A., and Andriot, C. 2006. Realistic haptic rendering of interacting deformable objects in virtual environments. IEEE Trans. Visualiz. Comput. Graph. 1, 12, 36–47.
20. Durville, D. 2004. Modelling of contact-friction interactions in entangled fibrous materials. In Proceedings of the 6th World Congress on Computational Mechanics (WCCM VI).
21. Erleben, K. 2007. Velocity-Based shock propagation for multibody dynamics animation. ACM Trans. Graph. 26, 2.
22. Frémond, M. 2002. Non-Smooth Thermo-Mechanics. Springer, Berlin.
23. Hadap, S. 2006. Oriented strands – Dynamics of stiff multi-body system. In Proceedings of the ACM SIGGRAPH – EG Symposium on Computer Animation (SCA’06). ACM, 91–100.
24. Hadap, S. and Magnenat-Thalmann, N. 2001. Modeling dynamic hair as a continuum. Comput. Graph. Forum 20, 3, 329–338.
25. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Trans. Graph. Conference.
26. Jean, M. 1999. The non smooth contact dynamics method. Comput. Methods Appl. Mechan. Engn. 177, 235–257.
27. Kaldor, J., James, D., and Marschner, S. 2008. Simulating knitted cloth at the yarn level. ACM Trans. Graph. Conference. 1–9.
28. Kaufman, D., Edmunds, T., and Pai, D. 2005. Fast frictional dynamics for rigid bodies. ACM Trans. Graph. 24, 3, 946–956.
29. Kaufman, D., Sueda, S., James, D., and Pai, D. 2008. Staggered projections for frictional contact in multibody systems. ACM Trans. Graph. 27, 5, 164:1–164:11.
30. Lenoir, J., Meseure, P., Grisoni, L., and Chaillou, C. 2004. A suture model for surgical simulation. In Proceedings of the 2nd International Symposium on Medical Simulation (ISMS’04). 105–113.
31. Lötstedt, P. 1984. Numerical simulation of time-dependent contact friction problems in rigid body mechanics. SIAM J. Sci. Stat. Comput. 5, 2, 370–393.
32. MapleSoft. 2010. Maple 14. http://www.maplesoft.com/.
33. Marques, M. M. 1993. Differential Inclusions in Nonsmooth Mechanical Problems. Shocks and Dry Friction. Progress in Nonlinear Differential Equations and their Applications. 9. Birkhäuser, Basel.
34. McAdams, A., Selle, A., Ward, K., Sifakis, E., and Teran, J. 2009. Detail preserving continuum simulation of straight hair. ACM Trans. Graph. Conference 28, 3, 1–6.
35. Milenkovic, V. and Schmidl, H. 2001. Optimization-Based animation. In Proceedings of the ACM SIGGRAPH’ Conference. ACM, New York, 37–46.
36. Moore, M. and Wilhelms, J. 1988. Collision detection and response for computer animationr3. In Proceedings of the ACM SIGGRAPH’ Conference. 289–298.
37. Moreau, J. 1994. Some numerical methods in multibody dynamics: Application to granular materials. Euro. J. Mechan. A/Solids supp., 4, 93–114.
38. Moreau, J.-J. 1988. Unilateral contact and dry friction in finite freedom dynamics. Nonsmooth Mechanics and Applications, CISM Courses Lectures 302, 1-82 (1988).
39. Müller, M., Heidelberger, B., Hennix, M., and Ratcliff, J. 2007. Position based dynamics. J. Vis. Comm. Image Represent. 18, 2, 109–118.
40. Otaduy, M., Tamstorf, R., Steinemann, D., and Gross, M. 2009. Implicit contact handling for deformable objects. Comput. Graph. Forum 28, 2.
41. Plante, E., Cani, M.-P., and Poulin, P. 2001. A layered wisp model for simulating interactions inside long hair. In Proceedings of the EG Workshop on Computer Animation and Simulation (EGCAS’01). Springer, 139–148. 
42. Qi, L. and Sun, J. 1993. A nonsmooth version of Newton’s method. Math. Program. 58, 353–367.
43. Redon, S., Kheddar, A., and Coquillart, S. 2002. Fast continuous collision detection between rigid bodies. Comput. Graph. Forum. 21, 279–288.
44. Rosenblum, R., Carlson, W., and Tripp, E. 1991. Simulating the structure and dynamics of human hair: Modeling, rendering, and animation. J. Visualiz. Comput. Anim. 2, 4, 141–148.
45. Selle, A., Lentine, M., and Fedkiw, R. 2008. A mass spring model for hair simulation. ACM Trans. Graph. 27, 3, 1–11.
46. Spillmann, J., Becker, M., and Teschner, M. 2007. Non-Iterative computation of contact forces for deformable objects. J. WSCG 15, 33–40.
47. Spillmann, J. and Teschner, M. 2007. Corde: Cosserat rod elements for the dynamic simulation of one-dimensional elastic objects. In Proceedings of the ACM SIGGRAPH – EG Symposium on Computer Animation (SCA’07). ACM, 63–72.
48. Spillmann, J. and Teschner, M. 2008. An adaptive contact model for the robust simulation of knots. Comput. Graph. Forum 27, 2.
49. Stewart, D. and Trinkle, J. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and Coulomb friction. ijnme 39, 15.
50. Stewart, D. E. 2000. Rigid-body dynamics with friction and impact. SIAM Rev. 42, 1, 3–39.
51. Teschner, M., Heidelberger, B., Müller, M., Pomeranerts, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of the Conference on Vision, Modeling, Visualization (VMV’03). 47–54.
52. Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Comput. Graph. Forum 24, 1, 61–81.
53. Theetten, A., Grisoni, L., Andriot, C., and Barsky, B. 2008. Geometrically exact splines. J. Comput. Aid. Des. 40, 1, 35–48.