“Numerical coarsening using discontinuous shape functions” by Chen, Bao, Wang, Desbrun and Huang

  • ©Jiong Chen, Hujun Bao, Tianyu Wang, Mathieu Desbrun, and Jin Huang



Entry Number: 120


    Numerical coarsening using discontinuous shape functions

Session/Category Title: Deep Thoughts on How Things Move




    In this paper, an efficient and scalable approach for simulating inhomogeneous and non-linear elastic objects is introduced. Our numerical coarsening approach consists in optimizing non-conforming and matrix-valued shape functions to allow for predictive simulation of heterogeneous materials with non-linear constitutive laws even on coarse grids, thus saving orders of magnitude in computational time compared to traditional finite element computations. The set of local shape functions over coarse elements is carefully tailored in a preprocessing step to balance geometric continuity and local material stiffness. In particular, we do not impose continuity of our material-aware shape functions between neighboring elements to significantly reduce the fictitious numerical stiffness that conforming bases induce; however, we enforce crucial geometric and physical properties such as partition of unity and exact reproduction of representative fine displacements to eschew the use of discontinuous Galerkin methods. We demonstrate that we can simulate, with no parameter tuning, inhomogeneous and non-linear materials significantly better than previous approaches that traditionally try to homogenize the constitutive model instead.


    1. Jernej Barbič and Doug L. James. 2005. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Transactions on Graphics (TOG) 24, 3 (July 2005), 982–990. Google ScholarDigital Library
    2. Alain Bensoussan, Jacques-Louis Lions, and George Papanicolaou. 1978. Asymptotic analysis for periodic structures. Vol. 5. North-Holland Publishing Company.Google Scholar
    3. Desai Chen, David IW Levin, Wojciech Matusik, and Danny M Kaufman. 2017. Dynamics-aware numerical coarsening for fabrication design. ACM Transactions on Graphics (TOG) 36, 4, Article 84 (2017), 15 pages. Google ScholarDigital Library
    4. Desai Chen, David IW Levin, Shinjiro Sueda, and Wojciech Matusik. 2015. Data-driven finite elements for geometry and material design. ACM Transactions on Graphics (TOG) 34, 4, Article 74 (2015), 10 pages. Google ScholarDigital Library
    5. Bernardo Cockburn, George E. Karniadakis, and Chi-Wang Shu. 2011. Discontinuous Galerkin Methods: Theory, Computation and Applications. Springer. Google ScholarCross Ref
    6. Tim Davis. 2017. Suitesparse: a suite of sparse matrix software. Found at http://faculty.cse.tamu.edu/davis/suitesparse.html.Google Scholar
    7. Gilles Debunne, Mathieu Desbrun, Marie-Paule Cani, and Alan H. Barr. 2001. Dynamic Real-time Deformations Using Space & Time Adaptive Sampling. In ACM SIGGRAPH Proceedings. ACM, New York, NY, USA, 31–36. Google ScholarDigital Library
    8. Yalchin Efendiev, Juan Galvis, and Xiao-Hui Wu. 2011. Multiscale finite element methods for high-contrast problems using local spectral basis functions. J. Comput. Phys. 230, 4 (2011), 937–955. Google ScholarDigital Library
    9. Elliot English and Robert Bridson. 2008. Animating developable surfaces using non-conforming elements. ACM Transactions on Graphics (TOG) 27, 3, Article 66 (2008), 5 pages. Google ScholarDigital Library
    10. François Faure, Benjamin Gilles, Guillaume Bousquet, and Dinesh K Pai. 2011. Sparse meshless models of complex deformable solids. ACM transactions on graphics (TOG) 30, 4, Article 73 (2011), 10 pages. Google ScholarDigital Library
    11. Benjamin Gilles, Guillaume Bousquet, Francois Faure, and Dinesh K. Pai. 2011. Frame-based Elastic Models. ACM Transactions on Graphics (TOG) 30, 2, Article 15 (2011), 12 pages. Google ScholarDigital Library
    12. Eitan Grinspun, Petr Krysl, and Peter Schröder. 2002. CHARMS: A Simple Framework for Adaptive Simulation. ACM Transactions on Graphics 21, 3 (July 2002), 281–290. Google ScholarDigital Library
    13. Geoffrey Irving, Joseph Teran, and Ronald Fedkiw. 2006. Tetrahedral and hexahedral invertible finite elements. Graphical Models 68, 2 (2006), 66–89. Google ScholarDigital Library
    14. A. Johnen, J.-F. Remade, and C. Geuzaine. 2013. Geometrical validity of curvilinear finite elements. J. Comp. Phys. 233, Supplement C (2013), 359–372. Google ScholarDigital Library
    15. Lily Kharevych, Patrick Mullen, Houman Owhadi, and Mathieu Desbrun. 2009. Numerical coarsening of inhomogeneous elastic materials. ACM Transactions on Graphics (TOG) 28, 3, Article 51 (2009), 8 pages. Google ScholarDigital Library
    16. Peter. Krysl, Sanjay Lall, and Jerrold E. Marsden. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. Int. J. Num. Methods Eng. 51, 4 (2001), 479–504.Google ScholarCross Ref
    17. Siwang Li, Jin Huang, Fernando de Goes, Xiaogang Jin, Hujun Bao, and Mathieu Desbrun. 2014. Space-time Editing of Elastic Motion Through Material Optimization and Reduction. ACM Transactions on Graphics (TOG) 33, 4, Article 108 (2014), 10 pages. Google ScholarDigital Library
    18. Sebastian Martin, Peter Kaufmann, Mario Botsch, Martin Wicke, and Markus Gross. 2008. Polyhedral finite elements using harmonic basis functions. Computer Graphics Forum 27, 5 (2008), 1521–1529. Google ScholarDigital Library
    19. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based elastic materials. ACM Transactions on Graphics (TOG) 30, 4, Article 72 (2011), 8 pages. Google ScholarDigital Library
    20. Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf Joseph Teran, and Eftychios Sifakis. 2011. Efficient elasticity for character skinning with contact and collisions. ACM Transactions on Graphics (TOG) 30, 4 (2011), 37. Google ScholarDigital Library
    21. Matthias Müller and Markus Gross. 2004. Interactive Virtual Materials. In Proceedings of Graphics Interface 2004 (GI ’04). Canadian Human-Computer Communications Society, School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 239–246. Google ScholarDigital Library
    22. Rahul Narain, Armin Samii, and James F. O’Brien. 2012. Adaptive anisotropic remeshing for cloth simulation. ACM Transactions on Graphics (TOG) 31, 6, Article 152 (2012), 10 pages. Google ScholarDigital Library
    23. Matthieu Nesme, Paul G Kry Lenka Jeřábková, and François Faure. 2009. Preserving topology and elasticity for embedded deformable models. ACM Transactions on Graphics (TOG) 28, 3, Article 52 (2009), 9 pages. Google ScholarDigital Library
    24. Houman Owhadi, Lei Zhang, and Leonid Berlyand. 2014. Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization. ESAIM: Mathematical Modelling and Numerical Analysis 48, 2 (2014), 517–552.Google ScholarCross Ref
    25. Julian Panetta, Qingnan Zhou, Luigi Malomo, Nico Pietroni, Paolo Cignoni, and Denis Zorin. 2015. Elastic Textures for Additive Fabrication. ACM Transactions on Graphics (TOG) 34, 4, Article 135 (2015), 12 pages. Google ScholarDigital Library
    26. Alex Pentland and John Williams. 1989. Good Vibrations: Modal Dynamics for Graphics and Animation. SIGGRAPH Comput. Graph. 23, 3 (1989), 207–214. Google ScholarDigital Library
    27. Gangan Prathap. 1993. The Finite Element Method in Structural Mechanics. Solid Mechanics and Its Applications, Vol. 24. Springer.Google Scholar
    28. Christian Schumacher, Bernd Bickel, Jan Rys, Steve Marschner, Chiara Daraio, and Markus Gross. 2015. Microstructures to control elasticity in 3D printing. ACM Transactions on Graphics (TOG) 34, 4, Article 136 (2015), 13 pages. Google ScholarDigital Library
    29. Jonathan R. Shewchuk. 2002. What is a Good Linear Element? Interpolation, Conditioning, and Quality Measures. In Int. Meshing Roundtable. 115–126.Google Scholar
    30. Rosell Torres, Jose M. Espadero, Felipe A. Calvo, and Miguel A. Otaduy. 2014. Interactive Deformation of Heterogeneous Volume Data. Lecture Notes in Computer Science 8789 (2014).Google Scholar
    31. Rosell Torres, Alejandro Rodríiguez, José M Espadero, and Miguel A Otaduy. 2016. High-resolution interaction with corotational coarsening models. ACM Transactions on Graphics (TOG) 35, 6, Article 211 (2016), 11 pages. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: