“High-Order Incremental Potential Contact for Elastodynamic Simulation on Curved Meshes” by Ferguson, Jain, Zorin, Schneider and Panozzo
Conference:
Type:
Title:
- High-Order Incremental Potential Contact for Elastodynamic Simulation on Curved Meshes
Session/Category Title: Making Contact: Simulating and Detecting Collisions
Presenter(s)/Author(s):
Moderator(s):
Abstract:
High-order bases provide major advantages over linear ones in terms of efficiency, as they provide (for the same physical model) higher accuracy for the same running time, and reliability, as they are less affected by locking artifacts and mesh quality. Thus, we introduce a high-order finite element (FE) formulation (high-order bases) for elastodynamic simulation on high-order (curved) meshes with contact handling based on the recently proposed Incremental Potential Contact (IPC) model. Our approach is based on the observation that each IPC optimization step used to minimize the elasticity, contact, and friction potentials leads to linear trajectories even in the presence of nonlinear meshes or nonlinear FE bases. It is thus possible to retain the strong non-penetration guarantees and large time steps of the original formulation while benefiting from the high-order bases and high-order geometry. We accomplish this by mapping displacements and resulting contact forces between a linear collision proxy and the underlying high-order representation. We demonstrate the effectiveness of our approach in a selection of problems from graphics, computational fabrication, and scientific computing.
References:
1. Christie Alappat, Achim Basermann, Alan R. Bishop, Holger Fehske, Georg Hager, Olaf Schenk, Jonas Thies, and Gerhard Wellein. 2020. A Recursive Algebraic Coloring Technique for Hardware-Efficient Symmetric Sparse Matrix-Vector Multiplication. ACM Transactions on Parallel Computing 7, 3, Article 19 (June 2020), 37 pages.
2. Fadi Aldakheel, Blaž Hudobivnik, Edoardo Artioli, Lourenço Beirão da Veiga, and Peter Wriggers. 2020. Curvilinear virtual elements for contact mechanics. Computer Methods in Applied Mechanics and Engineering 372 (2020), 113394.
3. I. Babuska and B. Q. Guo. 1988. The h-p Version of the Finite Element Method for Domains with Curved Boundaries. SIAM J. Numer. Anal. 25, 4 (1988), 837–861.
4. I. Babuška and B.Q. Guo. 1992. The h, p and h-p version of the finite element method; basis theory and applications. Advances in Engineering Software 15, 3 (1992), 159–174.
5. Adam Bargteil and Tamar Shinar. 2018. An Introduction to Physics-Based Animation. In ACM SIGGRAPH 2018 Courses (Vancouver, British Columbia, Canada). ACM, New York, NY, Article 6, 1 pages.
6. Adam W Bargteil and Elaine Cohen. 2014. Animation of deformable bodies with quadratic Bézier finite elements. ACM Transactions on Graphics 33, 3 (2014), 27.
7. F. Bassi and S. Rebay. 1997. High-Order Accurate Discontinuous Finite Element Solution of the 2D Euler Equations. J. Comput. Phys. 138, 2 (1997), 251–285.
8. F.B. Belgacem, P. Hild, and P. Laborde. 1998. The mortar finite element method for contact problems. Mathematical and Computer Modelling 28, 4 (1998), 263–271. Recent Advances in Contact Mechanics.
9. Tino Bog, Nils Zander, Stefan Kollmannsberger, and Ernst Rank. 2015. Normal contact with high order finite elements and a fictitious contact material. Computers & Mathematics with Applications 70, 7 (2015), 1370–1390. High-Order Finite Element and Isogeometric Methods.
10. Matthias Bollhöfer, Aryan Eftekhari, Simon Scheidegger, and Olaf Schenk. 2019. Large-scale Sparse Inverse Covariance Matrix Estimation. SIAM Journal on Scientific Computing 41, 1 (2019), 380–401.
11. Matthias Bollhöfer, Olaf Schenk, Radim Janalik, Steve Hamm, and Kiran Gullapalli. 2020. State-of-the-Art Sparse Direct Solvers. Parallel Algorithms in Computational Science and Engineering (2020), 3–33.
12. Bernard Brogliato. 1999. Nonsmooth Mechanics. Springer-Verlag.
13. R. P. R. Cardoso and O. B. Adetoro. 2017. On contact modelling in isogeometric analysis. European Journal of Computational Mechanics 26, 5-6 (2017), 443–472.
14. HeeSun Choi, Cindy Crump, Christian Duriez, Asher Elmquist, Gregory Hager, David Han, Frank Hearl, Jessica Hodgins, Abhinandan Jain, Frederick Leve, Chen Li, Franziska Meier, Dan Negrut, Ludovic Righetti, Alberto Rodriguez, Jie Tan, and Jeff Trinkle. 2021. On the use of simulation in robotics: Opportunities, challenges, and suggestions for moving forward. Proceedings of the National Academy of Sciences 118, 1 (2021).
15. Franz Chouly, Patrick Hild, Vanessa Lleras, and Yves Renard. 2022. Nitsche method for contact with Coulomb friction: Existence results for the static and dynamic finite element formulations. J. Comput. Appl. Math. 416 (2022), 114557.
16. François Faure, Benjamin Gilles, Guillaume Bousquet, and Dinesh K. Pai. 2011. Sparse Meshless Models of Complex Deformable Solids. ACM Transactions on Graphics 30, 4, Article 73 (July 2011), 10 pages.
17. Zachary Ferguson 2020. IPC Toolkit. https://ipc-sim.github.io/ipc-toolkit/. https://ipc-sim.github.io/ipc-toolkit/
18. Zachary Ferguson, Minchen Li, Teseo Schneider, Francisca Gil-Ureta, Timothy Langlois, Chenfanfu Jiang, Denis Zorin, Danny M. Kaufman, and Daniele Panozzo. 2021. Intersection-Free Rigid Body Dynamics. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 40, 4, Article 183 (July 2021), 16 pages.
19. David Franke, A. Düster, V. Nübel, and E. Rank. 2010. A comparison of the h-, p-, hp-, and rp-version of the FEM for the solution of the 2D Hertzian contact problem. Computational Mechanics 45, 5 (April 2010), 513–522.
20. David Franke, Alexander Düster, and Ernst Rank. 2008. The p-version of the FEM for computational contact mechanics. Pamm 8, 1 (2008), 10271–10272.
21. Tom Gustafsson, Rolf Stenberg, and Juha Videman. 2020. On Nitsche’s Method for Elastic Contact Problems. SIAM Journal on Scientific Computing 42, 2 (2020), B425–B446.
22. Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2020. Fast Tetrahedral Meshing in the Wild. ACM Transactions on Graphics 39, 4, Article 117 (July 2020), 18 pages.
23. S. Hüeber and B.I. Wohlmuth. 2006. Mortar methods for contact problems. Springer Berlin Heidelberg, Berlin, Heidelberg, 39–47.
24. T.J.R. Hughes, J.A. Cottrell, and Y. Bazilevs. 2005. Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement. Computer Methods in Applied Mechanics and Engineering 194, 39 (2005), 4135–4195.
25. Alec Jacobson, Ilya Baran, Jovan Popović, and Olga Sorkine. 2011. Bounded Biharmonic Weights for Real-Time Deformation. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 30, 4 (2011), 78:1–78:8.
26. A. Jameson, J. Alonso, and M. McMullen. 2002. Application of a non-linear frequency domain solver to the Euler and Navier-Stokes equations. In 40th AIAA Aerospace Sciences Meeting & Exhibit.
27. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Transactions on Graphics 36, 6, Article 186 (Nov. 2017), 9 pages.
28. Zhongshi Jiang, Teseo Schneider, Denis Zorin, and Daniele Panozzo. 2020. Bijective Projection in a Shell. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 39, 6, Article 247 (Nov. 2020), 18 pages.
29. Zhongshi Jiang, Ziyi Zhang, Yixin Hu, Teseo Schneider, Denis Zorin, and Daniele Panozzo. 2021. Bijective and Coarse High-Order Tetrahedral Meshes. ACM Transactions on Graphics 40, 4, Article 157 (July 2021), 16 pages.
30. Amaury Johnen, J-F Remacle, and Christophe Geuzaine. 2013. Geometrical validity of curvilinear finite elements. J. Comput. Phys. 233 (2013), 359–372.
31. Couro Kane, Jerrold E Marsden, Michael Ortiz, and Matthew West. 2000. Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. Internat. J. Numer. Methods Engrg. 49, 10 (Dec. 2000), 1295–1325.
32. Noboru Kikuchi and John Tinsley Oden. 1988. Contact Problems in Elasticity: A Study of Variational Inequalities and Finite Element Methods. SIAM Studies in App. and Numer. Math., Vol. 8. Society for Industrial and Applied Mathematics.
33. Theodore Kim and David Eberle. 2022. Dynamic Deformables: Implementation and Production Practicalities (Now with Code!). In ACM SIGGRAPH 2022 Courses (Vancouver, British Columbia, Canada). ACM, New York, NY, Article 7, 259 pages.
34. Alexander Konyukhov and Karl Schweizerhof. 2009. Incorporation of contact for high-order finite elements in covariant form. Computer Methods in Applied Mechanics and Engineering 198, 13 (2009), 1213–1223.
35. Rolf. Krause and Patrick. Zulian. 2016. A Parallel Approach to the Variational Transfer of Discrete Fields between Arbitrarily Distributed Unstructured Finite Element Meshes. SIAM Journal on Scientific Computing 38, 3 (2016).
36. Paul G Kry and Dinesh K Pai. 2003. Continuous contact simulation for smooth surfaces. ACM Transactions on Graphics 22, 1 (2003), 106–129.
37. Lei Lan, Danny M. Kaufman, Minchen Li, Chenfanfu Jiang, and Yin Yang. 2022. Affine Body Dynamics: Fast, Stable and Intersection-Free Simulation of Stiff Materials. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 41, 4, Article 67 (July 2022), 14 pages.
38. Lei Lan, Ran Luo, Marco Fratarcangeli, Weiwei Xu, Huamin Wang, Xiaohu Guo, Junfeng Yao, and Yin Yang. 2020. Medial Elastics: Efficient and Collision-Ready Deformation via Medial Axis Transform. ACM Transactions on Graphics 39, 3, Article 20 (April 2020), 17 pages.
39. Lei Lan, Yin Yang, Danny Kaufman, Junfeng Yao, Minchen Li, and Chenfanfu Jiang. 2021. Medial IPC: Accelerated Incremental Potential Contact with Medial Elastics. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 40, 4, Article 158 (July 2021), 16 pages.
40. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection- and Inversion-free Large Deformation Dynamics. ACM Transactions on Graphics 39, 4, Article 49 (July 2020), 20 pages.
41. Minchen Li, Danny M. Kaufman, and Chenfanfu Jiang. 2021. Codimensional Incremental Potential Contact. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 40, 4, Article 170 (2021).
42. Andreas Longva, Fabian Löschner, Tassilo Kugelstadt, José Antonio Fernández-Fernández, and Jan Bender. 2020. Higher-Order Finite Elements for Embedded Simulation. ACM Transactions on Graphics 39, 6, Article 181 (Nov. 2020), 14 pages.
43. Xiaojuan Luo, Mark S Shephard, and Jean-Francois Remacle. 2001. The influence of geometric approximation on the accuracy of high order methods. Rensselaer SCOREC report 1 (2001).
44. Steve A. Maas, Benjamin J. Ellis, Gerard A. Ateshian, and Jeffrey A. Weiss. 2012. FEBio: Finite Elements for Biomechanics. Journal of Biomechanical Engineering 134, 1 (Feb. 2012).
45. Sebastian Martin, Peter Kaufmann, Mario Botsch, Eitan Grinspun, and Markus Gross. 2010. Unified Simulation of Elastic Rods, Shells, and Solids. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 29, 3 (2010), 39:1–39:10.
46. Johannes Mezger, Bernhard Thomaszewski, Simon Pabst, and Wolfgang Straer. 2009. Interactive physically-based shape editing. Computer Aided Geometric Design 26, 6 (2009), 680–694. Solid and Physical Modeling 2008.
47. Matthew Moore and Jane Wilhelms. 1988. Collision Detection and Response for Computer Animation. Computer Graphics (Proceedings of SIGGRAPH) 22, 4 (June 1988), 289–298.
48. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2015. Air Meshes for Robust Collision Handling. ACM Transactions on Graphics 34, 4, Article 133 (July 2015), 9 pages.
49. Donald D Nelson and Elaine Cohen. 1998. User interaction with CAD models with nonholonomic parametric surface constraints. In ASME International Mechanical Engineering Congress and Exposition, Vol. 15861. American Society of Mechanical Engineers, 235–242.
50. Donald D. Nelson, David E. Johnson, and Elaine Cohen. 2005. Haptic Rendering of Surface-to-Surface Sculpted Model Interaction. In ACM SIGGRAPH 2005 Courses (Los Angeles, California). ACM, New York, NY, 97–es.
51. Johannes C. C. 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.
52. J. Tinsley Oden. 1994. Optimal h-p finite element methods. Computer Methods in Applied Mechanics and Engineering 112, 1 (1994), 309–331.
53. Julian Panetta, Qingnan Zhou, Luigi Malomo, Nico Pietroni, Paolo Cignoni, and Denis Zorin. 2015. Elastic Textures for Additive Fabrication. ACM Transactions on Graphics 34, 4, Article 135 (July 2015), 12 pages.
54. Roman Poya, Antonio J. Gil, Rogelio Ortigosa, Ruben Sevilla, Javier Bonet, and Wolfgang A. Wall. 2018. A curvilinear high order finite element framework for electromechanics: From linearised electro-elasticity to massively deformable dielectric elastomers. Computer Methods in Applied Mechanics and Engineering 329 (2018), 75–117.
55. Romain Prévost, Emily Whiting, Sylvain Lefebvre, and Olga Sorkine-Hornung. 2013. Make It Stand: Balancing Shapes for 3D Fabrication. ACM Transactions on Graphics (Proceedings of SIGGRAPH) 32, 4 (2013), 81:1–81:10.
56. Xavier Provot. 1997. Collision and Self-Collision Handling in Cloth Model Dedicated to Design Garments. In Computer Animation and Simulation. Springer, 177–189.
57. Michael A Puso and Tod A Laursen. 2004. A mortar segment-to-segment contact method for large deformation solid mechanics. Computer Methods in Applied Mechanics and Engineering 193, 6-8 (2004), 601–629.
58. Teseo Schneider, Jérémie Dumas, Xifeng Gao, Mario Botsch, Daniele Panozzo, and Denis Zorin. 2019a. Poly-Spline Finite-Element Method. ACM Transactions on Graphics 38, 3, Article 19 (March 2019), 16 pages.
59. Teseo Schneider, Jérémie Dumas, Xifeng Gao, Denis Zorin, and Daniele Panozzo. 2019b. PolyFEM. https://polyfem.github.io/.
60. Teseo Schneider, Yixin Hu, Jérémie Dumas, Xifeng Gao, Daniele Panozzo, and Denis Zorin. 2018. Decoupling Simulation Accuracy from Mesh Quality. ACM Transactions on Graphics 37, 6 (Oct. 2018).
61. Teseo Schneider, Yixin Hu, Xifeng Gao, Jérémie Dumas, Denis Zorin, and Daniele Panozzo. 2022. A Large-Scale Comparison of Tetrahedral and Hexahedral Elements for Solving Elliptic PDEs with the Finite Element Method. ACM Transactions on Graphics 41, 3, Article 23 (March 2022), 14 pages.
62. Teseo Schneider, Daniele Panozzo, and Xianlian Zhou. 2021. Isogeometric high order mesh generation. Computer Methods in Applied Mechanics and Engineering 386 (2021), 114104.
63. Alexander Seitz, Philipp Farah, Johannes Kremheller, Barbara I. Wohlmuth, Wolfgang A. Wall, and Alexander Popp. 2016. Isogeometric dual mortar methods for computational contact mechanics. Computer Methods in Applied Mechanics and Engineering 301 (2016), 259–280.
64. Ruben Sevilla, Sonia Fernández-Méndez, and Antonio Huerta. 2011. Comparison of high-order curved finite elements. Internat. J. Numer. Methods Engrg. 87, 8 (2011), 719–734.
65. John M. Snyder, Adam R. Woodbury, Kurt Fleischer, Bena Currin, and Alan H. Barr. 1993. Interval Methods for Multi-Point Collisions between Time-Dependent Curved Surfaces, In Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques (Anaheim, CA). Annual Conference Series (Proceedings of SIGGRAPH), 321–334.
66. Rolf Stenberg. 1998. Mortaring by a method of J. A. Nitsche. Computational Mechanics (Jan. 1998).
67. David E Stewart. 2001. Finite-dimensional contact mechanics. Philosophical Transactions of the Royal Society A 359 (2001), 2467–2482.
68. Stefan Suwelack, Dimitar Lukarski, Vincent Heuveline, Rüdiger Dillmann, and Stefanie Speidel. 2013. Accurate Surface Embedding for Higher Order Finite Elements. In Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Anaheim, California) (SCA ’13). ACM, New York, NY, 187–192.
69. I. Temizer, P. Wriggers, and T.J.R. Hughes. 2011. Contact treatment in isogeometric analysis with NURBS. Computer Methods in Applied Mechanics and Engineering 200, 9 (2011), 1100–1112.
70. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically Deformable Models. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques(SIGGRAPH ’87). ACM, New York, NY, 205–214.
71. Mickeal Verschoor and Andrei C Jalba. 2019. Efficient and accurate collision response for elastically deformable models. ACM Transactions on Graphics 38, 2, Article 17 (March 2019), 20 pages.
72. Brian Von Herzen, Alan H. Barr, and Harold R. Zatz. 1990. Geometric Collisions for Time-Dependent Parametric Surfaces. Computer Graphics (Proceedings of SIGGRAPH) 24, 4 (Sept. 1990), 39–48.
73. Bolun Wang, Zachary Ferguson, Teseo Schneider, Xin Jiang, Marco Attene, and Daniele Panozzo. 2021. A Large Scale Benchmark and an Inclusion-Based Algorithm for Continuous Collision Detection. ACM Transactions on Graphics 40, 5, Article 188 (Oct. 2021), 16 pages.
74. Peter Wriggers. 1995. Finite Element Algorithms for Contact Problems. Archives of Computational Methods in Engineering 2 (Dec. 1995), 1–49.
75. P. Wriggers, J. Schröder, and A. Schwarz. 2013. A finite element method for contact using a third medium. Computational Mechanics 52, 4 (Oct. 2013), 837–847.
