More Web Proxy on the site http://driver.im/

research-article

A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics

Authors:

Florence Bertails-Descoubes,

Laurence BoissieuxAuthors Info & Claims

SA '11: Proceedings of the 2011 SIGGRAPH Asia Conference

Article No.: 139, Pages 1 - 12

https://doi.org/10.1145/2024156.2024173

Published: 12 December 2011 Publication History

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.

Supplementary Material

Supplemental material. (a139-daviet.zip)

Download
76.94 MB

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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).

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[40]

Qi, L., and Sun, J. 1993. A nonsmooth version of Newton's method. Mathematical Programming 58, 353--367.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Cited By

Lan LLu ZLong JYuan CLi XHe XWang HJiang CYang Y(2024)Efficient GPU Cloth Simulation with Non-distance Barriers and Subspace ReuseACM Transactions on Graphics10.1145/368776043:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687760
Crespel OHohnadel EMetivet TBertails-Descoubes F(2024)Contact detection between curved fibres: high order makes a differenceACM Transactions on Graphics10.1145/365819143:4(1-23)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658191
Xun LZheng GKruszewski A(2024)Cosserat-Rod-Based Dynamic Modeling of Soft Slender Robot Interacting With EnvironmentIEEE Transactions on Robotics10.1109/TRO.2024.338639340(2811-2830)Online publication date: 2024
https://doi.org/10.1109/TRO.2024.3386393
Show More Cited By

Index Terms

A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics
1. Computing methodologies
  1. Computer graphics
    1. Animation

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

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 ...
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SA '11: Proceedings of the 2011 SIGGRAPH Asia Conference

December 2011

730 pages

ISBN:9781450308076

DOI:10.1145/2024156

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

In-Cooperation

SIGCHI: ACM Special Interest Group on Computer-Human Interaction

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 December 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SA '11

Sponsor:

SIGGRAPH

SA '11: SIGGRAPH Asia 2011

December 12 - 15, 2011

Hong Kong, China

Acceptance Rates

Overall Acceptance Rate 178 of 869 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
892
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)9

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lan LLu ZLong JYuan CLi XHe XWang HJiang CYang Y(2024)Efficient GPU Cloth Simulation with Non-distance Barriers and Subspace ReuseACM Transactions on Graphics10.1145/368776043:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687760
Crespel OHohnadel EMetivet TBertails-Descoubes F(2024)Contact detection between curved fibres: high order makes a differenceACM Transactions on Graphics10.1145/365819143:4(1-23)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658191
Xun LZheng GKruszewski A(2024)Cosserat-Rod-Based Dynamic Modeling of Soft Slender Robot Interacting With EnvironmentIEEE Transactions on Robotics10.1109/TRO.2024.338639340(2811-2830)Online publication date: 2024
https://doi.org/10.1109/TRO.2024.3386393
Xiao WLiu WWang YGhanem BLi B(2023)Automatic Animation of Hair Blowing in Still Portrait Photos2023 IEEE/CVF International Conference on Computer Vision (ICCV)10.1109/ICCV51070.2023.02099(22906-22918)Online publication date: 1-Oct-2023
https://doi.org/10.1109/ICCV51070.2023.02099
Tong DChoi AJoo JJawed M(2023)A fully implicit method for robust frictional contact handling in elastic rodsExtreme Mechanics Letters10.1016/j.eml.2022.10192458(101924)Online publication date: Jan-2023
https://doi.org/10.1016/j.eml.2022.101924
Ascher ULarionov ESheen SPai D(2022)Simulating deformable objects for computer animation: A numerical perspectiveJournal of Computational Dynamics10.3934/jcd.20210219:2(47)Online publication date: 2022
https://doi.org/10.3934/jcd.2021021
Lan LMa GYang YZheng CLi MJiang C(2022)Penetration-free projective dynamics on the GPUACM Transactions on Graphics10.1145/3528223.353006941:4(1-16)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530069
N. JDhas BSrinivasa AReddy JRoy D(2022)A novel four-field mixed FE approximation for Kirchhoff rods using Cartan’s moving framesComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2022.115094402(115094)Online publication date: Dec-2022
https://doi.org/10.1016/j.cma.2022.115094
Li MKaufman DJiang C(2021)Codimensional incremental potential contactACM Transactions on Graphics10.1145/3450626.345976740:4(1-24)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459767
Larionov EFan YPai D(2021)Frictional Contact on Smooth Elastic SolidsACM Transactions on Graphics10.1145/344666340:2(1-17)Online publication date: 21-Apr-2021
https://dl.acm.org/doi/10.1145/3446663
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents