“Efficient yarn-based cloth with adaptive contact linearization” by Kaldor, James and Marschner

Yarn-based cloth simulation can improve visual quality but at high computational costs due to the reliance on numerous persistent yarn-yarn contacts to generate material behavior. Finding so many contacts in densely interlinked geometry is a pathological case for traditional collision detection, and the sheer number of contact interactions makes contact processing the simulation bottleneck. In this paper, we propose a method for approximating penalty-based contact forces in yarn-yarn collisions by computing the exact contact response at one time step, then using a rotated linear force model to approximate forces in nearby deformed configurations. Because contacts internal to the cloth exhibit good temporal coherence, sufficient accuracy can be obtained with infrequent updates to the approximation, which are done adaptively in space and time. Furthermore, by tracking contact models we reduce the time to detect new contacts. The end result is a 7- to 9-fold speedup in contact processing and a 4- to 5-fold overall speedup, enabling simulation of character-scale garments.

1. An, S. S., Kim, T., and James, D. L. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM SIGGRAPH Asia 27, 5, 164:1–11. Google ScholarDigital Library
2. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. ACM SIGGRAPH, 43–54. Google ScholarDigital Library
3. Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. ACM Trans. Graph. 22, 3, 862–870. Google ScholarDigital Library
4. Barbič, J., and James, D. 2005. Real-Time subspace integration for St. Venant-Kirchhoff deformable models. ACM Transactions on Graphics 24, 3 (Aug.), 982–990. Google ScholarDigital Library
5. Bergou, M., Wardetzky, M., Harmon, D., Zorin, D., and Grinspun, E. 2006. A quadratic bending model for inextensible surfaces. In Fourth Eurographics Symposium on Geometry Processing, 227–230. Google ScholarDigital Library
6. Bergou, M., Wardetzky, M., Robinson, S., Audoly, B., and Grinspun, E. 2008. Discrete elastic rods. ACM SIGGRAPH. Google ScholarDigital Library
7. Bergou, M., Audoly, B., Vouga, E., Wardetzky, M., and Grinspun, E. 2010. Discrete viscous threads. ACM SIGGRAPH. Google ScholarDigital Library
8. 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 Trans. Graph. 25, 3 (August), 1180–1187. Google ScholarDigital Library
9. Bridson, R., Fedkiw, R., and john Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM SIGGRAPH, 594–603. Google ScholarDigital Library
10. Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. Symposium on Computer Animation 32, 28–36. Google ScholarDigital Library
11. Chadwick, J. N., An, S. S., and James, D. L. 2009. Harmonic shells: A practical nonlinear sound model for near-rigid thin shells. ACM Transactions on Graphics 28, 5 (Dec.), 119:1–119:10. Google ScholarDigital Library
12. Choi, K., and Ko, H. 2002. Stable but responsive cloth. ACM SIGGRAPH, 604–611. Google ScholarDigital Library
13. Chu, L. 2005. A Framework for Extracting Cloth Descriptors from the Underlying yarn Structure. PhD thesis, University of California, Berkeley.Google Scholar
14. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic real-time deformations using space and time adaptive sampling. ACM SIGGRAPH. Google ScholarDigital Library
15. English, E., and Bridson, R. 2008. Animating developable surfaces using nonconforming elements. ACM SIGGRAPH. Google ScholarDigital Library
16. Etzmuss, O., Keckeisen, M., and Strasser, W. 2003. A fast finite element solution for cloth modelling. In Computer Graphics and Applications, 2003. Proceedings. 11th Pacific Conference on, 244–251. Google ScholarDigital Library
17. Felippa, C. 2000. A systematic approach to the element-independent corotational dynamics of finite elements. Center for Aerospace Structures Document Number CU-CAS-00-03, College of Engineering, University of Colorado.Google Scholar
18. Gao, J., Guibas, L. J., and Nguyen, A. 2004. Deformable spanners and applications. Proc. 20th ACM Symp. on Comp. Geom., 179–199. Google ScholarDigital Library
19. Garg, A., Grinspun, E., Wardetzky, M., and Zorin, D. 2007. Cubic Shells. In 2007 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 91–98. Google ScholarDigital Library
20. Goldenthal, R., Harmon, D., Fattal, R., Bercovier, M., and Grinspun, E. 2007. Efficient simulation of inextensible cloth. ACM SIGGRAPH 26, 3. Google ScholarDigital Library
21. Govindaraju, N. K., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M. C., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. ACM Trans. Graph. 24, 3, 991–999. Google ScholarDigital Library
22. Grinspun, E., Krysl, P., and Schröder, P. 2002. CHARMS: A simple framework for adaptive simulation. ACM Transactions on Graphics 21, 281–290. Google ScholarDigital Library
23. Grinspun, E., Hirani, A., Desbrun, M., and Schröder, P. 2003. Discrete shells. Symposium on Computer Animation, 62–67. Google ScholarDigital Library
24. Guibas, L. 2004. Kinetic Data Structures. In Handbook of Data Structures and Applications, D. Mehta and S. Sahni, Eds. Chapman and Hall/CRC.Google Scholar
25. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM SIGGRAPH. Google ScholarDigital Library
26. Hubbard, P. 1995. Collision detection for interactive graphics applications. IEEE Trans. Visualization and Computer Graphics 1, 3, 218–230. Google ScholarDigital Library
27. Hutchinson, D., Preston, M., and Hewitt, T. 1996. Adaptive refinement for mass/spring simulations. In Proceedings of the Eurographics workshop on Computer animation and simulation’96, Springer-Verlag New York, Inc., 45. Google ScholarDigital Library
28. Kaldor, J., James, D. L., and Marschner, S. 2008. Simulating knitted cloth at the yarn level. ACM SIGGRAPH. Google ScholarDigital Library
29. Kawabata, S., Niwa, M., and Kawai, H. 1973. The finite deformation theory of plain-weave fabrics part I: The biaxial-deformation theory. Journal of the Textile Institute 64, 21–46.Google ScholarCross Ref
30. Kharevych, L., Mullen, P., Owhadi, H., and Desbrun, M. 2009. Numerical coarsening of inhomogeneous elastic materials. ACM Trans. Graph. 28, 3, 1–8. Google ScholarDigital Library
31. Kim, T., and James, D. L. 2009. Skipping steps in deformable simulation with online model reduction. ACM Trans. Graph. 28, 5, 1–9. Google ScholarDigital Library
32. King, M., Jearanaisilawong, P., and Scorate, S. 2005. A continuum constitutive model for the mechanical behavior of woven fabrics. International Journal of Solids and Structures 42, 3867–3896.Google ScholarCross Ref
33. Mirtich, B. 2000. Timewarp rigid body simulation. In Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, 193–200. Google ScholarDigital Library
34. Müller, M., and Gross, M. 2004. Interactive virtual materials. In Proceedings of Graphics Interface 2004, 239–246. Google ScholarDigital Library
35. Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. In ACM SIGGRAPH Symposium on Computer Animation, 49–54. Google ScholarDigital Library
36. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM SIGGRAPH 24, 3, 471–478. Google ScholarDigital Library
37. Nesme, M., Kry, P. G., Jeřábková, L., and Faure, F. 2009. Preserving topology and elasticity for embedded deformable models. ACM Trans. Graph. 28, 3, 1–9. Google ScholarDigital Library
38. Pai, D. 2002. STRANDS: Interactive simulation of thin solids using Cosserat models. Eurographics 21, 347–352.Google ScholarCross Ref
39. Provot, X. 1995. Deformation constraints in a mass-spring model to describe rigid cloth behavior. Proc. Graphics Interface ’95, 147–154.Google Scholar
40. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation ’97: Proceedings of the Eurographics Workshop in Budapest, Hungary, September 2–3, 1997, Springer, 177.Google ScholarCross Ref
41. Rivers, A. R., and James, D. L. 2007. FastLSM: Fast lattice shape matching for robust real-time deformation. ACM Trans. Graph. 26, 3, 82. Google ScholarDigital Library
42. Spillmann, J., and Teschner, M. 2008. An adaptive contact model for the robust simulation of knots. Eurographics 27, 497–506.Google ScholarCross Ref
43. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. Computer Graphics 21, 205–214. Google ScholarDigital Library
44. Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. In Computer Graphics Forum, vol. 24, Blackwell Publishing, 61–81.Google Scholar
45. Theetten, A., Grisoni, L., Duriez, C., and Merlhiot, X. 2007. Quasi-dynamic splines. In Proc. ACM Symposium on Solid and Physical Modeling ’07. Google ScholarDigital Library
46. Villard, J., and Borouchaki, H. 2005. Adaptive meshing for cloth animation. Engineering with Computers 20, 4, 333–341. Google ScholarDigital Library
47. Volino, P., and Thalmann, N. M. 2000. Implementing fast cloth simulation with collision response. In Proc. Computer Graphics International, 257–266. Google ScholarDigital Library
48. Volino, P., martin Courchesne, and Magnenat-Thalmann, N. 1995. Versatile and efficient techniques for simulating cloth and other deformable objects. In Proc. SIGGRAPH ’95. Google ScholarDigital Library
49. Zeng, X., Tan, V. B. C., and Shin, V. P. W. 2006. Modelling inter-yarn friction in woven fabric armor. International Journal for Numerical Methods in Engineering 66, 1309–1330.Google ScholarCross Ref