“A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics” by Daviet, Bertails-Descoubes and Boissieux
Conference:
Type(s):
Title:
- A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics
Session/Category Title: Contact, Collision and Congestion
Presenter(s)/Author(s):
Abstract:
Dry friction between hair fibers plays a major role in the collective hair dynamic behavior as it accounts for typical nonsmooth features such as stick-slip instabilities. However, due the challenges posed by the modeling of nonsmooth friction, previous mechanical models for hair either neglect friction or use an approximate smooth friction model, thus losing important visual features. In this paper we present a new generic robust solver for capturing Coulomb friction in large assemblies of tightly packed fibers such as hair. Our method is based on an iterative algorithm where each single contact problem is efficiently and robustly solved by introducing a hybrid strategy that combines a new zero-finding formulation of (exact) Coulomb friction together with an analytical solver as a fail-safe. Our global solver turns out to be very robust and highly scalable as it can handle up to a few thousand densely packed fibers subject to tens of thousands frictional contacts at a reasonable computational cost. It can be conveniently combined to any fiber model with various rest shapes, from smooth to curly. Our results, visually validated against real hair motions, depict typical hair collective effects and greatly enhance the realism of standard hair simulators.
References:
1. Acary, V., and Brogliato, B. 2008. Numerical methods for nonsmooth dynamical systems, vol. 35 of Lecture Notes in Computational and Applied Mechanics. Springer.
2. Acary, V., Cadoux, F., Lemarechal, C., and Malick, J. 2011. A formulation of the linear discrete Coulomb friction problem via convex optimization. ZAMM/Zangew Math Mech; Zeitschrift für Angewandte Mathematik und Mechanik 91 (02), 155–175.
3. Alart, P., and Curnier, A. 1991. A mixed formulation for frictional contact problems prone to Newton like solution methods. Comput. Methods Appl. Mech. Eng. 92, 3, 353–375.
4. Anitescu, M., and Tasora, A., 2008. An iterative approach for cone complementarity problems for nonsmooth dynamics.
5. Anjyo, K., Usami, Y., and Kurihara, T. 1992. A simple method for extracting the natural beauty of hair. In Computer Graphics Proceedings (Proceedings of the ACM SIGGRAPH’92 conference), 111–120.
6. Autodesk, 2009. 3ds Max Hair & Fur. http://usa.autodesk.com/.
7. Baraff, D. 1991. Coping with friction for non-penetrating rigid body simulation. In Computer Graphics Proceedings (Proceedings of the ACM SIGGRAPH’91 conference), ACM, 31–40.
8. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Computer Graphics Proceedings (Proceedings of the ACM SIGGRAPH’94 conference), ACM, New York, NY, USA, 23–34.
9. Bergou, M., Wardetzky, M., Robinson, S., Audoly, B., and Grinspun, E. 2008. Discrete elastic rods. ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH’08 conference) 27, 3, 1–12.
10. Bergou, M., Audoly, B., Vouga, E., Wardetzky, M., and Grinspun, E. 2010. Discrete viscous threads. ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH’10 Conference).
11. Bertails-Descoubes, F., Cadoux, F., Daviet, G., and Acary, V. 2011. A nonsmooth Newton solver for capturing exact Coulomb friction in fiber assemblies. ACM Transactions on Graphics 30 (February), 6:1–6:14.
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. ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH’06 conference) 25 (July), 1180–1187.
13. Bonnefon, O., and Daviet, G. 2011. Quartic formulation of Coulomb 3D frictional contact. Tech. rep., INRIA – Laboratoire Jean Kuntzmann.
14. Chen, J.-S., Sun, D., and Sun, J. 2008. The SC1 property of the squared norm of the SOC Fischer-Burmeister function. Operations Research Letters 36, 3, 385–392.
15. Choe, B., Choi, M., and Ko, H.-S. 2005. Simulating complex hair with robust collision handling. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, ACM, New York, NY, USA, SCA ’05, 153–160.
16. Dubois, F., and Jean, M. 2006. The non smooth contact dynamic method: recent LMGC90 software developments and application. In Analysis and Simulation of Contact Problems, P. Wriggers and U. Nackenhorst, Eds., vol. 27 of Lecture Notes in Applied and Computational Mechanics. Springer Berlin/Heidelberg, 375–378. 10.1007/3-540-31761-9-44.
17. 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 (TVCG) 1, 12, 36–47.
18. Duriez, C. 2008. Rendering of frictional contact with deformable environments. In Haptic Rendering: Foundations, Algorithms and Applications. A. K. Peters, Ltd., Natick, MA, USA, 421–442.
19. Erleben, K. 2007. Velocity-based shock propagation for multi-body dynamics animation. ACM Transaction on Graphics 26, 2.
20. Fischer, A. 1992. A special Newton-type optimization method. Optimization: A Journal of Mathematical Programming and Operations Research 24, 3, 269–284.
21. Fukushima, M., Luo, Z.-Q., and Tseng, P. 2002. Smoothing functions for second-order-cone complementarity problems. SIAM J. on Optimization 12 (February), 436–460.
22. G. De Saxcé, G., and Feng, Z.-Q. 1998. The bipotential method: a constructive approach to design the complete contact law with friction and improved numerical algorithms. Math. Comput. Modelling 28, 4–8, 225–245.
23. Goldenthal, R., Harmon, D., Fattal, R., Bercovier, M., and Grinspun, E. 2007. Efficient simulation of inextensible cloth. In ACM SIGGRAPH 2007 papers, ACM, New York, NY, USA, SIGGRAPH ’07.
24. Hadap, S., and Magnenat-Thalmann, N. 2001. Modeling dynamic hair as a continuum. Computer Graphics Forum 20, 3, 329–338. Proceedings of Eurographics’01.
25. Hadap, S. 2006. Oriented strands – dynamics of stiff multi-body system. In ACM SIGGRAPH – EG Symposium on Computer Animation (SCA’06), ACM-EG SCA, 91–100.
26. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM, New York, NY, USA.
27. 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, 31–47.
28. Kaldor, J., James, D., and Marschner, S. 2008. Simulating knitted cloth at the yarn level. In ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH’08 conference, ACM, New York, NY, USA, 1–9.
29. Kaldor, J., James, D., and Marschner, S. 2010. Efficient yarn-based cloth with adaptive contact linearization. In ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH’10 conference, ACM, New York, NY, USA, vol. 29, 105:1–105:10.
30. Kanno, Y., Martins, J. A. C., and Costa, A. P. D., 2004. Second-order cone linear complementarity formulation of quasistatic incremental frictional contact problem.
31. Kaufman, D., Edmunds, T., and Pai, D. 2005. Fast frictional dynamics for rigid bodies. ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH’05 conference) 24, 3, 946–956.
32. Kaufman, D., Sueda, S., James, D., and Pai, D. 2008. Staggered projections for frictional contact in multibody systems. ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH Asia’08 conference) 27, 5, 164:1–164:11.
33. McAdams, A., Selle, A., Ward, K., Sifakis, E., and Teran, J. 2009. Detail preserving continuum simulation of straight hair. ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH’09 conference) 28, 3, 1–6.
34. Moreau, J.-J., and Jean, M. 1996. Numerical treatment of contact and friction: the contact dynamics method. In The 1996 3rd Biennial Joint Conference on Engineering Systems Design and Analysis, ESDA, 201–208.
35. Moreau, J.-J., 1988. Unilateral contact and dry friction in finite freedom dynamics. Nonsmooth mechanics and applications, CISM Courses Lect. 302, 1–82 (1988).
36. Moreau, J. 1994. Some numerical methods in multibody dynamics: Application to granular materials. European Journal of Mechanics – A/Solids supp., 4, 93–114.
37. Otaduy, M., Tamstorf, R., Steinemann, D., and Gross, M. 2009. Implicit contact handling for deformable objects. Computer Graphics Forum (Proceedings of Eurographics’09) 28, 2 (apr).
38. Pai, D. 2002. Strands: Interactive simulation of thin solids using cosserat models. Computer Graphics Forum 21, 3, 347–352. Proceedings of Eurographics’02.
39. Plante, E., Cani, M.-P., and Poulin, P. 2001. A layered wisp model for simulating interactions inside long hair. In EG workshop on Computer Animation and Simulation (EG CAS’01), Springer, Computer Science, 139–148.
40. Qi, L., and Sun, J. 1993. A nonsmooth version of Newton’s method. Mathematical Programming 58, 353–367.
41. Radjai, F., Wolf, D., Jean, M., and Moreau, J.-J. 1998. Bimodal character of stress transmission in granular packings. Phys. Rev. Lett. 80 (Jan), 61–64.
42. Rosenblum, R., Carlson, W., and Tripp, E. 1991. Simulating the structure and dynamics of human hair: Modeling, rendering, and animation. The Journal of Visualization and Computer Animation 2, 4, 141–148.
43. Selle, A., Lentine, M., and Fedkiw, R. 2008. A mass spring model for hair simulation. ACM Transactions on Graphics (Proceedings of the ACM SIGGRAPH’08 conference) 27, 3, 1–11.
44. Silcowitz, M., Niebe, S., and Erleben, K. 2009. Nonsmooth Newton Method for Fischer function reformulation of contact force problems for interactive rigid body simulation. 105–114.
45. Spillmann, J., and Teschner, M. 2007. CoRdE: Cosserat rod elements for the dynamic simulation of one-dimensional elastic objects. In ACM SIGGRAPH – EG Symposium on Computer Animation (SCA’07), ACM-EG SC A, 63–72.
46. Teschner, M., Heidelberger, B., Müller, M., Pomeranerts, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Vision, Modeling, Visualization (VMV 2003), 47–54.
47. Ward, K., Simmons, M., Milne, A., Yosumi, H., and Zhao, X. 2010. Simulating Rapunzel’s hair in Disney’s Tangled. In ACM SIGGRAPH 2010 Talks, ACM, New York, NY, USA, SIGGRAPH ’10, 22:1–22:1.
48. Zhang, H., Li, J., and Pan, S. 2011. New second-order cone linear complementarity formulation and semi-smooth Newton algorithm for finite element analysis of 3d frictional contact problem. Computer Methods in Applied Mechanics and Engineering 200, 1–4, 77–88.
