“In-Timestep Remeshing for Contacting Elastodynamics” by Ferguson, Schneider, Kaufman and Panozzo
Conference:
Type:
Title:
- In-Timestep Remeshing for Contacting Elastodynamics
Session/Category Title: Making Contact: Simulating and Detecting Collisions
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We propose In-Timestep Remeshing, a fully coupled, adaptive meshing algorithm for contacting elastodynamics where remeshing steps are tightly integrated, implicitly, within the timestep solve. Our algorithm refines and coarsens the domain automatically by measuring physical energy changes within each ongoing timestep solve. This provides consistent, degree-of-freedom-efficient, productive remeshing that, by construction, is physics-aware and so avoids the errors, over-refinements, artifacts, per-example hand-tuning, and instabilities commonly encountered when remeshing with timestepping methods. Our in-timestep computation then ensures that each simulation step’s output is both a converged stable solution on the updated mesh and a temporally consistent trajectory with respect to the model and solution of the last timestep. At the same time, the output is guaranteed safe (intersection- and inversion-free) across all operations. We demonstrate applications across a wide range of extreme stress tests with challenging contacts, sharp geometries, extreme compressions, large timesteps, and wide material stiffness ranges – all scenarios well-appreciated to challenge existing remeshing methods.
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 Trans. Parallel Comput. 7, 3, Article 19 (June 2020), 37 pages.
2. Adam W. Bargteil, Chris Wojtan, Jessica K. Hodgins, and Greg Turk. 2007. A Finite Element Method for Animating Large Viscoplastic Flow. In ACM SIGGRAPH 2007 Papers (San Diego, California) (SIGGRAPH ’07). Association for Computing Machinery, New York, NY, USA, 16–es.
3. Jan Bender and Crispin Deul. 2013. Adaptive cloth simulation using corotational finite elements. Computers & Graphics 37, 7 (2013), 820–829.
4. 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), A380–A401.
5. Matthias Bollhöfer, Olaf Schenk, Radim Janalik, Steve Hamm, and Kiran Gullapalli. 2020. State-of-the-Art Sparse Direct Solvers. (2020), 3–33.
6. Tyson Brochu and Robert Bridson. 2009. Robust Topological Operations for Dynamic Explicit Surfaces. SIAM Journal on Scientific Computing 31, 4 (2009), 2472–2493.
7. Chris J Budd, Weizhang Huang, and Robert D Russell. 2009. Adaptivity with moving grids. Acta Numerica 18 (2009), 111–241.
8. Nuttapong Chentanez, Ron Alterovitz, Daniel Ritchie, Lita Cho, Kris K. Hauser, Ken Goldberg, Jonathan R. Shewchuk, and James F. O’Brien. 2009. Interactive Simulation of Surgical Needle Insertion and Steering. ACM Trans. Graph. 28, 3, Article 88 (July 2009), 10 pages.
9. Fang Da, Christopher Batty, and Eitan Grinspun. 2014. Multimaterial Mesh-Based Surface Tracking. ACM Trans. on Graphics (SIGGRAPH North America 2014) (2014).
10. Gilles Debunne, Mathieu Desbrun, Marie-Paule Cani, and Alan H. Barr. 2001. Dynamic Real-Time Deformations Using Space and Time Adaptive Sampling. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). Association for Computing Machinery, New York, NY, USA, 31–36.
11. Leszek Demkowicz. 2006. Computing with hp-ADAPTIVE FINITE ELEMENTS. Chapman and Hall/CRC.
12. Marion Dunyach, David Vanderhaeghe, Loïc Barthe, and Mario Botsch. 2013. Adaptive Remeshing for Real-Time Mesh Deformation. In Eurographics 2013 – Short Papers, M.-A. Otaduy and O. Sorkine (Eds.). The Eurographics Association.
13. Tobias Erhart, Wolfgang A. Wall, and Ekkehard Ramm. 2006. Robust adaptive remeshing strategy for large deformation, transient impact simulations. Internat. J. Numer. Methods Engrg. 65, 13 (2006), 2139–2166.
14. Zachary Ferguson et al. 2020. IPC Toolkit. https://ipc-sim.github.io/ipc-toolkit/
15. Eitan Grinspun, Petr Krysl, and Peter Schröder. 2002. CHARMS: A Simple Framework for Adaptive Simulation. ACM Trans. Graph. 21, 3 (July 2002), 281–290.
16. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.
17. David Hahn and Chris Wojtan. 2015. High-Resolution Brittle Fracture Simulation with Boundary Elements. ACM Trans. Graph. 34, 4, Article 151 (July 2015), 12 pages.
18. Kai Hormann, Günther Greiner, and Swen Campagna. 1998. Hierarchical Parametrization of Triangulated Surfaces. Proceedings of Vision, Modeling and Visualization (Jan. 1998).
19. 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.
20. Dave Hutchinson, Martin Preston, and Terry Hewitt. 1996. Adaptive Refinement for Mass/Spring Simulations. In Proceedings of the Eurographics Workshop on Computer Animation and Simulation ’96 (Poitiers, France). Springer-Verlag, Berlin, Heidelberg, 31–45.
21. Zhongshi Jiang, Jiacheng Dai, Yixin Hu, Yunfan Zhou, Jeremie Dumas, Qingnan Zhou, Gurkirat Singh Bajwa, Denis Zorin, Daniele Panozzo, and Teseo Schneider. 2022. Declarative Specification for Unstructured Mesh Editing Algorithms. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) 41, 6, Article 251 (Nov. 2022), 14 pages.
22. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Trans. Graph. 36, 6, Article 186 (Nov. 2017), 9 pages.
23. Bryan M. Klingner, Bryan E. Feldman, Nuttapong Chentanez, and James F. O’Brien. 2006. Fluid Animation with Dynamic Meshes. In ACM SIGGRAPH 2006 Papers (Boston, Massachusetts) (SIGGRAPH ’06). Association for Computing Machinery, New York, NY, USA, 820–825.
24. Woojong Koh, Rahul Narain, and James F. O’Brien. 2015. View-Dependent Adaptive Cloth Simulation with Buckling Compensation. IEEE Transactions on Visualization and Computer Graphics 21, 10 (Oct. 2015), 1138–1145.
25. Dan Koschier, Sebastian Lipponer, and Jan Bender. 2015. Adaptive Tetrahedral Meshes for Brittle Fracture Simulation. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Copenhagen, Denmark) (SCA ’14). Eurographics Association, Goslar, DEU, 57–66.
26. 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), C307–C333.
27. Jie Li, Gilles Daviet, Rahul Narain, Florence Bertails-Descoubes, Matthew Overby, George E. Brown, and Laurence Boissieux. 2018. An Implicit Frictional Contact Solver for Adaptive Cloth Simulation. ACM Trans. Graph. 37, 4, Article 52 (July 2018), 15 pages.
28. Ling Li and Vasily Volkov. 2005. Cloth Animation with Adaptively Refined Meshes. In Proceedings of the Twenty-Eighth Australasian Conference on Computer Science – Volume 38 (Newcastle, Australia) (ACSC ’05). Australian Computer Society, Inc., AUS, 107–113.
29. Minchen Li, Zachary Ferguson, Teseo Schneider, Chenfanfu Jiang, Denis Zorin, Daniele Panozzo, and Danny M. Kaufman. 2023. Convergent Incremental Potential Contact. arXiv.
30. 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 (Proceedings of SIGGRAPH) 39, 4, Article 49 (Aug. 2020), 20 pages.
31. Richard Lipton, Donald Rose, and Robert Targan. 1979. Generalized Nested Dissection. SIAM J. Numer. Anal. 16, 2 (1979), 346–358.
32. S. Léger, A. Fortin, C. Tibirna, and M. Fortin. 2014. An updated Lagrangian method with error estimation and adaptive remeshing for very large deformation elasticity problems. Internat. J. Numer. Methods Engrg. 100, 13 (2014), 1006–1030.
33. Pierre-Luc Manteaux, Wei-Lun Sun, Francois Faure, Marie-Paule Cani, and James F. O’Brien. 2015. Interactive Detailed Cutting of Thin Sheets. In Proceedings of ACM SIGGRAPH Motion in Games. 1–8.
34. P.-L. Manteaux, C. Wojtan, R. Narain, S. Redon, F. Faure, and M.-P. Cani. 2017. Adaptive Physically Based Models in Computer Graphics. Computer Graphics Forum 36, 6 (2017), 312–337.
35. Sandeep Menon, Kyle G. Mooney, K.G. Stapf, and David P. Schmidt. 2015. Parallel adaptive simplical re-meshing for deforming domain CFD computations. J. Comput. Phys. 298 (2015), 62–78.
36. Marek Krzysztof Misztal, Kenny Erleben, Adam Bargteil, Jens Fursund, Brian Bunch Christensen, Jakob Andreas Bærentzen, and Robert Bridson. 2014. Multiphase flow of immiscible fluids on unstructured moving meshes. IEEE Transactions on Visualization and Computer Graphics 20, 1 (2014), 4–16.
37. Marek Krzysztof Misztal and Jakob Andreas Bærentzen. 2012. Topology-Adaptive Interface Tracking Using the Deformable Simplicial Complex. ACM Trans. Graph. 31, 3, Article 24 (jun 2012), 12 pages.
38. William F. Mitchell. 1991. Adaptive refinement for arbitrary finite-element spaces with hierarchical bases. J. Comput. Appl. Math. 36, 1 (1991), 65–78. Special Issue on Adaptive Methods.
39. William F. Mitchell and Marjorie A. McClain. 2014. A Comparison of Hp-Adaptive Strategies for Elliptic Partial Differential Equations. ACM Trans. Math. Softw. 41, 1, Article 2 (Oct. 2014), 39 pages.
40. J. F. Molinari and M. Ortiz. 2002. Three-dimensional adaptive meshing by subdivision and edge-collapse in finite-deformation dynamic-plasticity problems with application to adiabatic shear banding. Internat. J. Numer. Methods Engrg. 53, 5 (2002), 1101–1126.
41. J. Mosler and M. Ortiz. 2007. Variational h-adaption in finite deformation elasticity and plasticity. Internat. J. Numer. Methods Engrg. 72, 5 (2007), 505–523.
42. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2015. Air Meshes for Robust Collision Handling. ACM Trans. Graph. 34, 4, Article 133 (July 2015), 9 pages.
43. Rahul Narain, Tobias Pfaff, and James F. O’Brien. 2013. Folding and Crumpling Adaptive Sheets. ACM Trans. Graph. 32, 4, Article 51 (July 2013), 8 pages.
44. Rahul Narain, Armin Samii, and James F. O’Brien. 2012. Adaptive Anisotropic Remeshing for Cloth Simulation. ACM Trans. Graph. 31, 6, Article 152 (Nov. 2012), 10 pages.
45. James F. O’Brien, Adam W. Bargteil, and Jessica K. Hodgins. 2002. Graphical Modeling and Animation of Ductile Fracture. ACM Trans. Graph. 21, 3 (July 2002), 291–294.
46. James F. O’Brien and Jessica K. Hodgins. 1999. Graphical Modeling and Animation of Brittle Fracture. In Proceedings of ACM SIGGRAPH 1999. ACM Press/Addison-Wesley Publishing Co., 137–146.
47. Maria Elizabeth G. Ong. 1994. Uniform Refinement of a Tetrahedron. SIAM Journal on Scientific Computing 15, 5 (1994), 1134–1144.
48. Jean-Paul Pelteret. 2016. The ‘Quasi-Static Finite-Strain Compressible Elasticity’ code gallery program. https://dealii.org/developer/doxygen/deal.II/code_gallery_Quasi_static_Finite_strain_Compressible_Elasticity.html. Accessed: 2023-04-24.
49. Tobias Pfaff, Rahul Narain, Juan Miguel de Joya, and James F. O’Brien. 2014. Adaptive Tearing and Cracking of Thin Sheets. ACM Trans. Graph. 33, 4, Article 110 (July 2014), 9 pages.
50. Devon Powell. 2021. PolyClipper. https://github.com/LLNL/PolyClipper.
51. Alfred Schmidt and Kunibert G. Siebert. 2000. A posteriori estimators for the h – p version of the finite element method in 1D. Applied Numerical Mathematics 35, 1 (2000), 43–66.
52. Teseo Schneider, Jérémie Dumas, Xifeng Gao, Denis Zorin, and Daniele Panozzo. 2019. PolyFEM. https://polyfem.github.io/
53. Timothy J. R. Simnett, Stephen D. Laycock, and Andy M. Day. 2009. An Edge-based Approach to Adaptively Refining a Mesh for Cloth Deformation. In Theory and Practice of Computer Graphics, Wen Tang and John Collomosse (Eds.). The Eurographics Association.
54. Mélina Skouras, Bernhard Thomaszewski, Peter Kaufmann, Akash Garg, Bernd Bickel, Eitan Grinspun, and Markus Gross. 2014. Designing Inflatable Structures. ACM Trans. Graph. 33, 4, Article 63 (July 2014), 10 pages.
55. Jonas Spillmann and Matthias Teschner. 2008. An Adaptive Contact Model for the Robust Simulation of Knots. Computer Graphics Forum 27, 2 (2008), 497–506.
56. Keith Stein, Tayfun E. Tezduyar, and Richard Benney. 2004. Automatic mesh update with the solid-extension mesh moving technique. Computer Methods in Applied Mechanics and Engineering 193, 21 (2004), 2019–2032. Flow Simulation and Modeling.
57. Vasileios Vavourakis, Dimitrios Loukidis, Dimos C. Charmpis, and Panos Papanastasiou. 2013. Assessment of Remeshing and Remapping Strategies for Large Deformation Elastoplastic Finite Element Analysis. Comput. Struct. 114–115 (Jan. 2013), 133–146.
58. J. Villard and H. Borouchaki. 2005. Adaptive Meshing for Cloth Animation. Eng. with Comput. 20, 4 (Aug. 2005), 333–341.
59. Martin Wicke, Daniel Ritchie, Bryan M. Klingner, Sebastian Burke, Jonathan R. Shewchuk, and James F. O’Brien. 2010. Dynamic Local Remeshing for Elastoplastic Simulation. ACM Trans. Graph. 29, 4, Article 49 (July 2010), 11 pages.
60. Chris Wojtan, Nils Thürey, Markus Gross, and Greg Turk. 2009. Deforming Meshes That Split and Merge. In ACM SIGGRAPH 2009 Papers (New Orleans, Louisiana) (SIGGRAPH ’09). Association for Computing Machinery, New York, NY, USA, Article 76, 10 pages.
61. Jiayi Eris Zhang, Jèrèmie Dumas, Yun (Raymond) Fei, Alec Jacobson, Doug L. James, and Danny M. Kaufman. 2022. Progressive Simulation for Cloth Quasistatics. ACM Trans. Graph. 41, 6, Article 218 (2022).
62. M. G. Zielonka, M. Ortiz, and J. E. Marsden. 2008. Variational r-adaption in elastodynamics. Internat. J. Numer. Methods Engrg. 74, 7 (2008), 1162–1197.
