Animation
Parallel Multigrid for Nonlinear Cloth Simulation
Zhendong Wang,
Longhua Wu, Marco Fratarcangeli, Min Tang, Huamin Wang,
Zhendong Wang
Zhejiang University, China
The Ohio State University, USA
Search for more papers by this authorZhendong Wang,
Longhua Wu, Marco Fratarcangeli, Min Tang, Huamin Wang,
Zhendong Wang
Zhejiang University, China
The Ohio State University, USA
Search for more papers by this authorAbstract
Accurate high-resolution simulation of cloth is a highly desired computational tool in graphics applications. As single-resolution simulation starts to reach the limit of computational power, we believe the future of cloth simulation is in multi-resolution simulation. In this paper, we explore nonlinearity, adaptive smoothing, and parallelization under a full multigrid (FMG) framework. The foundation of this research is a novel nonlinear FMG method for unstructured meshes. To introduce nonlinearity into FMG, we propose to formulate the smoothing process at each resolution level as the computation of a search direction for the original high-resolution nonlinear optimization problem. We prove that our nonlinear FMG is guaranteed to converge under various conditions and we investigate the improvements to its performance. We present an adaptive smoother which is used to reduce the computational cost in the regions with low residuals already. Compared to normal iterative solvers, our nonlinear FMG method provides faster convergence and better performance for both Newton's method and Projective Dynamics. Our experiment shows our method is efficient, accurate, stable against large time steps, and friendly with GPU parallelization. The performance of the method has a good scalability to the mesh resolution, and the method has good potential to be combined with multi-resolution collision handling for real-time simulation in the future.
Supporting Information
| Filename | Description |
|---|---|
| cgf13554-sup-0001-S1.mp473.2 MB | Supplement Material |
Please note: The publisher is not responsible for the content or functionality of any supporting information supplied by the authors. Any queries (other than missing content) should be directed to the corresponding author for the article.
References
- Aksoylu B., Khodakovsky A., Schröder P.: Multilevel solvers for unstructured surface meshes. SIAM J. Sci. Comput. 26, 4 (Apr. 2005), 1146–1165. 3
- Bender J., Deul C.: Efficient Cloth Simulation Using an Adaptive Finite Element Method. In Workshop on Virtual Reality Interaction and Physical Simulation (2012), The Eurographics Association, pp. 21–30. 2
- Bridson R., Fedkiw R., Anderson J.: Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. (SIGGRAPH) 21, 3 (July 2002), 594–603. 2
- Bridson R., Marino S., Fedkiw R.: Simulation of clothing with folds and wrinkles. In Proceedings of SCA (2003), pp. 28–36. 2
- Bouaziz S., Martin S., Liu T., Kavan L., Pauly M.: Projective dynamics: Fusing constraint projections for fast simulation. ACM Trans. Graph. (SIGGRAPH) 33, 4 (July 2014), 154: 1–154:11. 2, 4
- Brandt A.: Multi-level adaptive solutions to boundary-value problems. Mathematics of Computation 31, 138 (1977), 333–390. 3
- Baraff D., Witkin A.: Large steps in cloth simulation. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques (New York, NY, USA, 1998), SIGGRAPH ‘98, ACM, pp. 43–54. 2
- Chen Z., Feng R., Wang H.: Modeling friction and air effects between cloth and deformable bodies. ACM Trans. Graph. (SIGGRAPH) 32, 4 (July 2013), 88: 1–88:8. 2
- Choi K.-J., Ko H.-S.: Stable but responsive cloth. ACM Trans. Graph. (SIGGRAPH) 21, 3 (July 2002), 604–611. 2, 5
- Cirio G., Lopez-Moreno J., Miraut D., Otaduy M. A.: Yarn-level simulation of woven cloth. ACM Trans. Graph. (SIGGRAPH Asia) 33, 6 (Nov. 2014), 207: 1–207:11. 2
- Clausen P., Wicke M., Shewchuk J. R., O'Brien J. F.: Simulating liquids and solid-liquid interactions with lagrangian meshes. ACM Trans. Graph. 32, 2 (Apr. 2013), 17: 1–15. 2
- Debunne G., Desbrun M., Cani M.-P., Barr A. H.: Dynamic real-time deformations using space & time adaptive sampling. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (2001), SIGGRAPH ‘01, pp. 31–36. 2
- Fratarcangeli M., Tibaldo V., Pellacini F.: Vivace: A practical Gauss-Seidel method for stable soft body dynamics. ACM Trans. Graph. (SIGGRAPH Asia) 35, 6 (Nov. 2016), 214: 1–214:9. 2, 3, 6, 8
- Green S., Turkiyyah G., Storti D.: Subdivision-based multilevel methods for large scale engineering simulation of thin shells. In Proceedings of SMA (2002), pp. 265–272. 3
- Golub G. H., Van Loan C. F.: Matrix computations ( 3rd Ed.). Johns Hopkins University Press, Baltimore, MD, USA, 1996. 5
- Georgii J., Westermann R.: A multigrid framework for real-time simulation of deformable bodies. Comput. Graph. 30, 3 (June 2006), 408–415. 3
- Jeon I., Choi K.-J., Kim T.-Y., Choi B.-O., Ko H.-S.: Constrainable multigrid for cloth. Computer Graphics Forum (Pacific Graphics) 32, 7 (2013), 31–39. 3
- Kaldor J. M., James D. L., Marschner S.: Efficient yarn-based cloth with adaptive contact linearization. ACM Trans. Graph. (SIGGRAPH) 29, 4 (July 2010), 105: 1–105:10. 2
- Liu T., Bargteil A. W., O'Brien J. F., Kavan L.: Fast simulation of mass-spring systems. ACM Trans. Graph. (SIGGRAPH Asia) 32, 6 (Nov. 2013), 214: 1–214:7. 2, 4
- Li L., Volkov V.: Cloth animation with adaptively refined meshes. In Proceedings of the Twenty-eighth Australasian Conference on Computer Science - Volume 38 (2005), pp. 107–113. 2
- Müller M.: Hierarchical position based dynamics. In Proceedings of VRIPHYS (2008), pp. 1–10. 3
- Miguel E., Bradley D., Thomaszewski B., Bickel B., Matusik W., Otaduy M. A., Marschner S.: Data-driven estimation of cloth simulation models. Comput. Graph. Forum (Eurographics) 31, 2 (May 2012), 519–528. 2
- Miguel E., Tamstorf R., Bradley D., Schvartzman S. C., Thomaszewski B., Bickel B., Matusik W., Marschner S., Otaduy M. A.: Modeling and estimation of internal friction in cloth. ACM Trans. Graph. (SIGGRAPH Asia) 32, 6 (Nov. 2013), 212: 1–212:10. 2
- Manteaux P.-L., Wojtan C., Narain R., Redon S., Faure F., Cani M.-P.: Adaptive physically based models in computer graphics. Computer Graphics Forum 36, 6 (2017), 312–337. 2
- Narain R., Overby M., Brown G. E.: ADMM ⊇ projective dynamics: Fast simulation of general constitutive models. In Proceedings of SCA (2016), pp. 21–28. 2
- Narain R., Samii A., O'Brien J. F.: Adaptive anisotropic remeshing for cloth simulation. ACM Trans. Graph. (SIGGRAPH Asia) 31, 6 (Nov. 2012), 152: 1–152:10. 2
- Otaduy M. A., Germann D., Redon S., Gross M.: Adaptive deformations with fast tight bounds. In Proceedings of SCA (2007), pp. 181–190. 3, 4, 6
- Oh S., Noh J., Wohn K.: A physically faithful multigrid method for fast cloth simulation. Computer Animation and Virtual Worlds 19, 3 (2008). 3
- Simnett T. J. R., Laycock S. D., Day A. M.: An Edge-based Approach to Adaptively Refining a Mesh for Cloth Deformation. In Theory and Practice of Computer Graphics (2009), The Eurographics Association, pp. 77–84. 2
- Tamstorf R., Jones T., McCormick S. F.: Smoothed aggregation multigrid for cloth simulation. ACM Trans. Graph. (SIGGRAPH Asia) 34, 6 (Oct. 2015), 245: 1–245:13. 2, 4
- Teran J., Sifakis E., Irving G., Fedkiw R.: Robust quasistatic finite elements and flesh simulation. In Proceedings of SCA (2005), pp. 181–190. 5
- Tang M., Wang H., Tang L., Tong R., Manocha D.: CAMA: Contact-aware matrix assembly with unified collision handling for GPU-based cloth simulation. Computer Graphics Forum (Eurographics) 35, 2 (2016), 511–521. 2
- Volino P., Magnenat-Thalmann N.: Resolving surface collisions through intersection contour minimization. ACM Trans. Graph. (SIGGRAPH) 25, 3 (July 2006), 1154–1159. 7
- Volino P., Magnenat-Thalmann N., Faure F.: A simple approach to nonlinear tensile stiffness for accurate cloth simulation. ACM Trans. Graph. 28, 4 (Sept. 2009), 105: 1–105:16. 2
- Wang H.: A Chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Trans. Graph. (SIGGRAPH Asia) 34, 6 (Oct. 2015), 246: 1–246:9. 2, 4, 6
- Wu X., Downes M. S., Goktekin T., Tendick F.: Adaptive nonlinear finite elements for deformable body simulation using dynamic progressive meshes. Computer Graphics Forum (Eurographics) 20, 3 (2001), 349–ĺC358. 2
- Wang H., O'Brien J., Ramamoorthi R.: Multi-resolution isotropic strain limiting. ACM Trans. Graph. (SIGGRAPH Asia) 29, 6 (Dec. 2010), 156: 1–156:10. 3
- Wang H., O'Brien J. F., Ramamoorthi R.: Data-driven elastic models for cloth: Modeling and measurement. ACM Trans. Graph. (SIGGRAPH) 30, 4 (July 2011), 71: 1–71:12. 2
- Wicke M., Ritchie D., Klingner B. M., Burke S., Shewchuk J. R., O'Brien J. F.: Dynamic local remeshing for elastoplastic simulation. ACM Trans. Graph. 29 (July 2010), 49: 1–49:11. 2
- Wang Z., Tang M., Tong R., Manocha D.: Tightccd: Efficient and robust continuous collision detection using tight error bounds. Comput. Graph. Forum 34, 7 (Oct. 2015), 289–298. 2
- Wang H., Yang Y.: Descent methods for elastic body simulation on the GPU. ACM Trans. Graph. (SIGGRAPH Asia) 35, 6 (Nov. 2016), 212: 1–212:10. 2, 4, 8
- Zhu Y., Sifakis E., Teran J., Brandt A.: An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2 (Apr. 2010), 16: 1–16:18. 3
