“The shape matching element method: direct animation of curved surface models” by Trusty, Chen and Levin

We introduce a new method for direct physics-based animation of volumetric curved models, represented using NURBS surfaces. Our technical contribution is the Shape Matching Element Method (SEM). SEM is a completely meshless algorithm, the first to simultaneously be robust to gaps and overlaps in geometry, be compatible with standard constitutive models and time integration schemes, support contact and frictional interactions and to preserve feature correspondence during simulation which enables editable simulated output. We demonstrate the efficacy of our algorithm by producing compelling physics-based animations from a variety of curved input models.

1. Martin Aigner, Christoph Heinrich, Bert Jüttler, Elisabeth Pilgerstorfer, Bernd Simeon, and Anh-Vu Vuong. 2009. Swept Volume Parameterization for Isogeometric Analysis. 19–44.Google Scholar
2. Sheldon Andrews, Marek Teichmann, and Paul G. Kry. 2016. Blended Linear Models for Reduced Compliant Mechanical Systems. IEEE Tran. on Visualization and Computer Graphics (TVCG) 22, 3 (2016), 1209–1222.Google ScholarDigital Library
3. Autodesk. 2021. Autodesk Fusion 360. https://www.autodesk.ca/en/products/fusion-360/Google Scholar
4. L. Beirão da Veiga, F. Brezzi, L. D. Marini, and A. Russo. 2014. The Hitchhiker’s Guide to the Virtual Element Method. Mathematical Models and Methods in Applied Sciences 24, 08 (2014), 1541–1573.Google ScholarCross Ref
5. Online Blender. 2020. Blender – a 3D modelling and rendering package. http://www.blender.orgGoogle Scholar
6. Sofien Bouaziz, Mario Deuss, Yuliy Schwartzburg, Thibaut Weise, and Mark Pauly. 2012. Shape-Up: Shaping Discrete Geometry with Projections. Comput. Graph. Forum 31, 5 (Aug. 2012), 1657–1667.Google ScholarDigital Library
7. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Trans. Graph. 33, 4, Article 154 (July 2014), 11 pages.Google ScholarDigital Library
8. Franco Brezzi, Konstantin Lipnikov, and Valeria Simoncini. 2005. A family of mimetic finite difference methods on polygonal and polyhedral meshes. Mathematical Models and Methods in Applied Sciences 15 (04 2005).Google Scholar
9. Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust Treatment of Collisions, Contact and Friction for Cloth Animation. ACM Trans. Graph. 21, 3 (July 2002), 594–603.Google ScholarDigital Library
10. Thomas Buffet, Damien Rohmer, Loïc Barthe, Laurence Boissieux, and Marie-Paule Cani. 2019. Implicit Untangling: A Robust Solution for Modeling Layered Clothing. ACM Trans. Graph. 38, 4, Article 120 (July 2019), 12 pages. Google ScholarDigital Library
11. J. Cottrell, Thomas Hughes, and Yuri Bazilevs. 2009. Isogeometric Analysis: Toward integration of CAD and FEA.Google ScholarDigital Library
12. Fernando De Goes, Andrew Butts, and Mathieu Desbrun. 2020. Discrete Differential Operators on Polygonal Meshes. ACM Trans. Graph. 39, 4, Article 110 (July 2020), 14 pages.Google Scholar
13. R. Diziol, J. Bender, and D. Bayer. 2011. Robust Real-Time Deformation of Incompressible Surface Meshes. In Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’11). ACM, New York, NY, USA, 237–246.Google Scholar
14. François Faure, Benjamin Gilles, Guillaume Bousquet, and Dinesh K. Pai. 2011. Sparse Meshless Models of Complex Deformable Solids. ACM Trans. Graph. 30, 4, Article 73 (July 2011), 10 pages.Google ScholarDigital Library
15. Jun Gao, Wenzheng Chen, Tommy Xiang, Clement Fuji Tsang, Alec Jacobson, Morgan McGuire, and Sanja Fidler. 2020. Learning Deformable Tetrahedral Meshes for 3D Reconstruction. In Advances In Neural Information Processing Systems.Google Scholar
16. Benjamin Gilles, Guillaume Bousquet, Francois Faure, and Dinesh K. Pai. 2011. Frame-Based Elastic Models. ACM Trans. Graph. 30, 2, Article 15 (April 2011), 12 pages.Google ScholarDigital Library
17. G. Haasemann, M. Kästner, S. Prüger, and V. Ulbricht. 2011. Development of a quadratic finite element formulation based on the XFEM and NURBS. Internat. J. Numer. Methods Engrg. 86, 4–5 (2011), 598–617.Google ScholarCross Ref
18. Christian Hafner, Christian Schumacher, Espen Knoop, Thomas Auzinger, Bernd Bickel, and Moritz Bächer. 2019. X-CAD: Optimizing CAD Models with Extended Finite Elements. ACM Trans. Graph. 38, 6, Article 157 (Nov. 2019), 15 pages.Google ScholarDigital Library
19. Ch. Heinrich, B. Simeon, and St. Boschert. 2012. A finite volume method on NURBS geometries and its application in isogeometric fluid-structure interaction. Mathematics and Computers in Simulation 82, 9 (2012), 1645 — 1666.Google ScholarDigital Library
20. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4, Article 60 (July 2018), 14 pages.Google ScholarDigital Library
21. Alec Jacobson et al. 2018. gptoolbox: Geometry Processing Toolbox. http://github.com/alecjacobson/gptoolbox.Google Scholar
22. Alec Jacobson, Ilya Baran, Jovan Popović, and Olga Sorkine. 2011. Bounded Biharmonic Weights for Real-Time Deformation. ACM Trans. Graph. (proceedings of ACM SIGGRAPH) 30, 4 (2011), 78:1–78:8.Google Scholar
23. Alec Jacobson, Zhigang Deng, Ladislav Kavan, and JP Lewis. 2014a. Skinning: Real-time Shape Deformation. In ACM SIGGRAPH 2014 Courses.Google Scholar
24. Alec Jacobson, Zhigang Deng, Ladislav Kavan, and J. P. Lewis. 2014b. Skinning: Real-Time Shape Deformation (Full Text Not Available) (SIGGRAPH ’14). ACM, 1 pages.Google Scholar
25. Alec Jacobson and Olga Sorkine. 2011. Stretchable and Twistable Bones for Skeletal Shape Deformation. ACM Trans. Graph. (proceedings of ACM SIGGRAPH ASIA) 30, 6 (2011), 165:1–165:8.Google Scholar
26. Doug L. James and Dinesh K. Pai. 1999. ArtDefo: Accurate Real Time Deformable Objects. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’99). 65–72.Google Scholar
27. Peter Kaufmann, Sebastian Martin, Mario Botsch, and Markus Gross. 2009. Flexible simulation of deformable models using discontinuous galerkin fem. Graphical Models 71, 4 (2009), 153–167.Google ScholarDigital Library
28. Amir Khosravifard and Mohammad Rahim Hematiyan. 2010. A new method for meshless integration in 2D and 3D Galerkin meshfree methods. Engineering Analysis with Boundary Elements 34, 1 (2010), 30 — 40.Google ScholarCross Ref
29. Cornelius Lanczos. 2012. The variational principles of mechanics. Courier Corporation.Google Scholar
30. Grégory Legrain. 2013. A NURBS enhanced extended finite element approach for unfitted CAD analysis. Computational Mechanics 52 (04 2013).Google Scholar
31. David I.W. Levin. 2020. Bartels: A lightweight collection of routines for physics simulation. https://github.com/dilevin/Bartels.Google Scholar
32. Xiang Li, Nandan Sudarsanam, and Daniel D Frey. 2006. Regularities in data from factorial experiments. Complexity 11, 5 (2006), 32–45.Google ScholarDigital Library
33. Konstantin Lipnikov, Gianmarco Manzini, and Mikhail Shashkov. 2014. Mimetic Finite Difference Method. J. Comput. Phys. 257 (Jan. 2014), 1163–1227.Google ScholarDigital Library
34. Wing Kam Liu, Sukky Jun, and Yi Fei Zhang. 1995. Reproducing kernel particle methods. International Journal for Numerical Methods in Fluids 20, 8–9 (1995), 1081–1106.Google ScholarCross Ref
35. Sebastian Martin, Peter Kaufmann, Mario Botsch, Eitan Grinspun, and Markus Gross. 2010. Unified Simulation of Elastic Rods, Shells, and Solids. ACM Trans. Graph. 29, 4, Article 39 (July 2010), 10 pages.Google ScholarDigital Library
36. Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011a. Efficient Elasticity for Character Skinning with Contact and Collisions. ACM, New York, NY, USA.Google Scholar
37. Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011b. Efficient Elasticity for Character Skinning with Contact and Collisions. ACM Trans. Graph. 30, 4, Article 37 (2011), 12 pages.Google ScholarDigital Library
38. Robert McNeel and Associates. 2021. Rhinoceros 3D. https://www.rhino3d.com/Google Scholar
39. Matthias Müller and Nuttapong Chentanez. 2011. Solid Simulation with Oriented Particles. In ACM SIGGRAPH 2011 Papers (SIGGRAPH ’11). ACM, New York, NY, USA, Article 92, 10 pages.Google Scholar
40. Matthias Müller, Nuttapong Chentanez, and Miles Macklin. 2016. Simulating Visual Geometry. In MIG. ACM, 31–38.Google Scholar
41. Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position based dynamics. J Vis Commun Image R 18, 2 (2007), 109–118.Google ScholarDigital Library
42. Matthias Müller, Bruno Heidelberger, Matthias Teschner, and Markus Gross. 2005. Meshless Deformations Based on Shape Matching. ACM Trans. Graph. 24, 3 (July 2005), 471–478.Google ScholarDigital Library
43. M. Müller, R. Keiser, A. Nealen, M. Pauly, M. Gross, and M. Alexa. 2004. Point Based Animation of Elastic, Plastic and Melting Objects. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Eurographics Association, 141–151.Google Scholar
44. Matthias Müller, Matthias Teschner, and Markus Gross. 2004. Physically-Based Simulation of Objects Represented by Surface Meshes. In Proceedings of the Computer Graphics International (CGI ’04). IEEE Computer Society, USA, 26–33.Google ScholarCross Ref
45. Matthieu Nesme, Paul G. Kry, Lenka Jeřábková, and François Faure. 2009. Preserving Topology and Elasticity for Embedded Deformable Models. ACM Trans. Graph. 28, 3, Article 52 (2009), 9 pages.Google ScholarDigital Library
46. Joachim Nitsche. 1971. Über ein Variationsprinzip zur Lösung von Dirichlet-Problemen bei Verwendung von Teilräumen, die keinen Randbedingungen unterworfen sind. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 36 (1971), 9–15.Google Scholar
47. Alec R. Rivers and Doug L. James. 2007. FastLSM: Fast Lattice Shape Matching for Robust Real-Time Deformation. In ACM SIGGRAPH 2007 Papers (SIGGRAPH ’07). ACM, New York, NY, USA, 82–es.Google Scholar
48. Scott D Roth. 1982. Ray casting for modeling solids. Computer Graphics and Image Processing 18, 2 (1982), 109 — 144.Google ScholarCross Ref
49. Masoud Safdari, Ahmad R. Najafi, Nancy R. Sottos, and Philippe H. Geubelle. 2015. A NURBS-based interface-enriched generalized finite element method for problems with complex discontinuous gradient fields. Internat. J. Numer. Methods Engrg. 101, 12 (2015), 950–964.Google ScholarCross Ref
50. Masoud Safdari, Ahmad R. Najafi, Nancy R. Sottos, and Philippe H. Geubelle. 2016. A NURBS-based generalized finite element scheme for 3D simulation of heterogeneous materials. J. Comput. Phys. 318 (2016), 373 — 390.Google ScholarDigital Library
51. Rohan Sawhney and Keenan Crane. 2020. Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-Based Methods on Volumetric Domains. ACM Trans. Graph. 39, 4 (2020).Google ScholarDigital Library
52. Ruben Sevilla, Sonia Mendez, and Antonio Huerta. 2008. Nurbs-enhanced finite element method (NEFEM). Internat. J. Numer. Methods Engrg. 76 (10 2008), 56–83.Google Scholar
53. Jonathan Richard Shewchuk. 1996. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Applied Computational Geometry: Towards Geometric Engineering, Ming C. Lin and Dinesh Manocha (Eds.). Lecture Notes in Computer Science, Vol. 1148. Springer-Verlag, 203–222. From the First ACM Workshop on Applied Computational Geometry.Google ScholarDigital Library
54. Jonathan Richard Shewchuk. 2002. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry 22, 1 (2002), 21 — 74. 16th ACM Symposium on Computational Geometry.Google ScholarDigital Library
55. Eftychios Sifakis and Jernej Barbic. 2012. FEM Simulation of 3D Deformable Solids: A Practitioner’s Guide to Theory, Discretization and Model Reduction. In ACM SIGGRAPH 2012 Courses. ACM, Article 20, 50 pages.Google ScholarDigital Library
56. Denis Steinemann, Miguel A. Otaduy, and Markus Gross. 2008. Fast Adaptive Shape Matching Deformations. In ACM/Eurographics Symposium on Computer Animation. Eurographics Association, 87–94.Google Scholar
57. Thomas Stumpp, Jonas Spillmann, Markus Becker, and Matthias Teschner. 2008. A Geometric Deformation Model for Stable Cloth Simulation. VRIPHYS 2008, 39–46.Google Scholar
58. Michael Tao, Christopher Batty, Eugene Fiume, and David Levin. 2019. Mandoline: Robust Cut-Cell Generation for Arbitrary Triangle Meshes. ACM Trans. Graph. (2019).Google ScholarDigital Library
59. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically Deformable Models. 21, 4 (1987), 205–214.Google Scholar
60. Demetri Terzopoulos and Hong Qin. 1994. Dynamic NURBS with Geometric Constraints for Interactive Sculpting. ACM Trans. Graph. 13, 2 (April 1994), 103–136.Google ScholarDigital Library
61. L. Veiga, Franco Brezzi, Andrea Cangiani, G. Manzini, L. Marini, and Alessandro Russo. 2012. Basic principles of Virtual Element Methods. Mathematical Models and Methods in Applied Sciences 23 (11 2012).Google Scholar
62. Ingo Wald, Sven Woop, Carsten Benthin, Gregory S. Johnson, and Manfred Ernst. 2014. Embree: A Kernel Framework for Efficient CPU Ray Tracing. ACM Trans. Graph. 33, 4, Article 143 (July 2014), 8 pages.Google ScholarDigital Library
63. Bin Wang, François Faure, and Dinesh K. Pai. 2012. Adaptive image-based intersection volume. ACM Trans. Graph. 31, 4 (2012), 97:1–97:9.Google ScholarDigital Library
64. Yu Wang, Alec Jacobson, Jernej Barbič, and Ladislav Kavan. 2015. Linear Subspace Design for Real-Time Shape Deformation. ACM Trans. Graph. 34, 4, Article 57 (July 2015), 11 pages.Google ScholarDigital Library
65. Andrew J. Weber and Galen Gornowicz. 2009. Collision-Free Construction of Animated Feathers Using Implicit Constraint Surfaces. ACM Trans. Graph. 28, 2, Article 12 (2009), 8 pages.Google ScholarDigital Library
66. Zangyueyang Xian, Xin Tong, and Tiantian Liu. 2019. A Scalable Galerkin Multigrid Method for Real-Time Simulation of Deformable Objects. ACM Trans. Graph. 38, 6, Article 162 (2019), 13 pages.Google ScholarDigital Library
67. Jiayi Eris Zhang, Seungbae Bang, David I.W. Levin, and Alec Jacobson. 2020. Complementary Dynamics. ACM Trans. Graph. (2020).Google Scholar