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.
Supplemental Material
Available for Download
- Acary, V., and Brogliato, B. 2008. Numerical methods for nonsmooth dynamical systems, vol. 35 of Lecture Notes in Computational and Applied Mechanics. Springer.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Anitescu, M., and Tasora, A., 2008. An iterative approach for cone complementarity problems for nonsmooth dynamics.Google Scholar
- 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. Google ScholarDigital Library
- Autodesk, 2009. 3ds Max Hair & Fur. http://usa.autodesk.com/.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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). Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Bonnefon, O., and Daviet, G. 2011. Quartic formulation of Coulomb 3D frictional contact. Tech. rep., INRIA - Laboratoire Jean Kuntzmann.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Erleben, K. 2007. Velocity-based shock propagation for multi-body dynamics animation. ACM Transaction on Graphics 26, 2. Google ScholarDigital Library
- Fischer, A. 1992. A special Newton-type optimization method. Optimization: A Journal of Mathematical Programming and Operations Research 24, 3, 269--284.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Hadap, S., and Magnenat-Thalmann, N. 2001. Modeling dynamic hair as a continuum. Computer Graphics Forum 20, 3, 329--338. Proceedings of Eurographics'01.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM, New York, NY, USA.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Kanno, Y., Martins, J. A. C., and Costa, A. P. D., 2004. Second-order cone linear complementarity formulation of quasistatic incremental frictional contact problem.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Moreau, J.-J., 1988. Unilateral contact and dry friction in finite freedom dynamics. Nonsmooth mechanics and applications, CISM Courses Lect. 302, 1--82 (1988).Google Scholar
- Moreau, J. 1994. Some numerical methods in multibody dynamics: Application to granular materials. European Journal of Mechanics - A/Solids supp., 4, 93--114.Google Scholar
- 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).Google Scholar
- Pai, D. 2002. Strands: Interactive simulation of thin solids using cosserat models. Computer Graphics Forum 21, 3, 347--352. Proceedings of Eurographics'02.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Qi, L., and Sun, J. 1993. A nonsmooth version of Newton's method. Mathematical Programming 58, 353--367. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
Index Terms
- A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics
Recommendations
A nonsmooth Newton solver for capturing exact Coulomb friction in fiber assemblies
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 ...
A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics
SA '11: Proceedings of the 2011 SIGGRAPH Asia ConferenceDry 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 ...
Existence Results for Quasistatic Contact Problems with Coulomb Friction
Abstract.We prove the existence of a solution for an elastic frictional, quasistatic, contact problem with a Signorini non-penetration condition and a local Coulomb friction law. The problem is formulated as a time-dependent variational problem and is ...
Comments