“Robust eXtended finite elements for complex cutting of deformables” by Koschier, Bender and Thuerey
Conference:
Type:
Title:
- Robust eXtended finite elements for complex cutting of deformables
Session/Category Title: Clever Solids
Presenter(s)/Author(s):
Moderator(s):
Abstract:
In this paper we present a robust remeshing-free cutting algorithm on the basis of the eXtended Finite Element Method (XFEM) and fully implicit time integration. One of the most crucial points of the XFEM is that integrals over discontinuous polynomials have to be computed on subdomains of the polyhedral elements. Most existing approaches construct a cut-aligned auxiliary mesh for integration. In contrast, we propose a cutting algorithm that includes the construction of specialized quadrature rules for each dissected element without the requirement to explicitly represent the arising subdomains. Moreover, we solve the problem of ill-conditioned or even numerically singular solver matrices during time integration using a novel algorithm that constrains non-contributing degrees of freedom (DOFs) and introduce a preconditioner that efficiently reuses the constructed quadrature weights.Our method is particularly suitable for fine structural cutting as it decouples the added number of DOFs from the cut’s geometry and correctly preserves geometry and physical properties by accurate integration. Due to the implicit time integration these fine features can still be simulated robustly using large time steps. As opposed to this, the vast majority of existing approaches either use remeshing or element duplication. Remeshing based methods are able to correctly preserve physical quantities but strongly couple cut geometry and mesh resolution leading to an unnecessary large number of additional DOFs. Element duplication based approaches keep the number of additional DOFs small but fail at correct conservation of mass and stiffness properties. We verify consistency and robustness of our approach on simple and reproducible academic examples while stability and applicability are demonstrated in large scenarios with complex and fine structural cutting.
References:
1. P. Areias and T. Belytschko. 2006. A comment on the article “A finite element method for simulation of strong and weak discontinuities in solid mechanics” by A. Hansbo and P. Hansbo [Comput. Methods Appl. Mech. Engrg. 193 (2004) 3523–3540]. Computer Methods in Applied Mechanics and Engineering 195, 9–12 (2006), 1275–1276.Google Scholar
2. Z. Bao, J. Hong, J. Teran, and R. Fedkiw. 2007. Fracturing Rigid Materials. IEEE Transactions on Visualization and Computer Graphics 13, 2 (2007), 370–378. Google ScholarDigital Library
3. D. Baraff, A. Witkin, and M. Kass. 2003. Untangling Cloth. ACM Transactions on Graphics 22, 3 (2003), 862–870. Google ScholarDigital Library
4. J. Bedrossian, J. von Brecht, S. Zhu, E. Sifakis, and J. Teran. 2010. A second order virtual node method for elliptic problems with interfaces and irregular domains. J. Comput. Phys. 229, 18 (2010), 6405–6426. Google ScholarDigital Library
5. T. Belytschko and T. Black. 1999. Elastic crack growth in finite elements with minimal remeshing. Internat. J. Numer. Methods Engrg. 45, 5 (1999), 601–620. Google ScholarCross Ref
6. D. Bielser, P. Glardon, M. Teschner, and M. Gross. 2004. A State Machine for Real-Time Cutting of Tetrahedral Meshes. Graphical Models 66, 6 (2004), 398–417. Google ScholarDigital Library
7. D. Bielser and M. H. Gross. 2000. Interactive Simulation of Surgical Cuts. In Pacific Graphics. 116–126. Google ScholarCross Ref
8. D. Bielser, V. Maiwald, and M. Gross. 1999. Interactive Cuts through 3-Dimensional Soft Tissue. Computer Graphics Forum 18, 3 (1999), 31–38. Google ScholarCross Ref
9. O. Busaryev, T. Dey, and H. Wang. 2013. Adaptive Fracture Simulation of Multi-Layered Thin Plates. ACM Transactions on Graphics 32, 4 (2013), 1.Google ScholarDigital Library
10. C. Daux, N. Moes, J. Dolbow, N. Sukumar, and T. Belytschko. 2000. Arbitrary branched and intersecting cracks with the extended finite element method. Internat. J. Numer. Methods Engrg. 48, 12 (2000), 1741–1760. Google ScholarCross Ref
11. C. Dick, J. Georgii, and R. Westermann. 2010. A Hexahedral Multigrid Approach for Simulating Cuts in Deformable Objects. IEEE Transactions on Visualization and Computer Graphics 17, 11 (2010), 1663–1675. Google ScholarDigital Library
12. T.P. Fries and T. Belytschko. 2010. The extended/generalized finite element method: An overview of the method and its applications. Internat. J. Numer. Methods Engrg. 84, 3 (2010), 253–304. Google ScholarCross Ref
13. A. Hansbo and P. Hansbo. 2004. A finite element method for the simulation of strong and weak discontinuities in solid mechanics. Computer Methods in Applied Mechanics and Engineering 193 (2004), 3523–3540. Google ScholarCross Ref
14. J. Hegemann, C. Jiang, C. Schroeder, and J. Teran. 2013. A Level-Set Method for Ductile Fracture. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 193–201. Google ScholarDigital Library
15. J. Hellrung, L. Wang, E. Sifakis, and J. Teran. 2012. A second order virtual node method for elliptic problems with interfaces and irregular domains in three dimensions. J. Comput. Phys. 231, 4 (2012), 2015–2048. Google ScholarDigital Library
16. D. Holdych, D. Noble, and R. Secor. 2008. Quadrature rules for triangular and tetrahedral elements with generalized functions. Internat. J. Numer. Methods Engrg. 73, 9 (2008), 1310–1327. Google ScholarCross Ref
17. L. Jerábková and T. Kuhlen. 2009. Stable Cutting of Deformable Objects in Virtual Environments Using XFEM. IEEE Computer Graphics and Applications 29, 2 (2009), 61–71. Google ScholarDigital Library
18. P. Kaufmann, S. Martin, M. Botsch, E. Grinspun, and M. Gross. 2009. Enrichment Textures for Detailed Cutting of Shells. ACM Transactions on Graphics 28, 3 (2009), 50:1–50:10.Google ScholarDigital Library
19. P. Kaufmann, S. Martin, M. Botsch, and M. Gross. 2008. Flexible Simulation of Deformable Models Using Discontinuous Galerkin FEM. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 105–115.Google Scholar
20. J. Kim and N. Pollard. 2011. Fast simulation of skeleton-driven deformable body characters. ACM Transactions on Graphics 30, 5 (2011), 1–19. Google ScholarDigital Library
21. D. Koschier, S. Lipponer, and J. Bender. 2014. Adaptive Tetrahedral Meshes for Brittle Fracture Simulation. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 1–10.Google Scholar
22. S. Martin, P. Kaufmann, M. Botsch, M. Wicke, and M. Gross. 2008. Polyhedral Finite Elements Using Harmonic Basis Functions. Computer Graphics Forum 27, 5 (2008), 1521–1529. Google ScholarCross Ref
23. N. Mitchell, C. Cutting, and E. Sifakis. 2015. GRIDiron: An Interactive Authoring and Cognitive Training Foundation for Reconstructive Plastic Surgery Procedures. ACM Transactions on Graphics 34, 4 (2015), 43:1–43:12.Google ScholarDigital Library
24. N. Moës, J. Dolbow, and T. Belytschko. 1999. A Finite Element Method for Crack Growth without Remeshing. Internat. J. Numer. Methods Engrg. 46, 1 (1999), 131–150. Google ScholarCross Ref
25. N. Molino, Z. Bao, and R. Fedkiw. 2004. A Virtual Node Algorithm for Changing Mesh Topology During Simulation. ACM Transactions on Graphics 23, 3 (2004), 385–392. Google ScholarDigital Library
26. S. Mousavi, E. Grinspun, and N. Sukumar. 2011a. Harmonic enrichment functions: A unified treatment of multiple, intersecting and branched cracks in the extended finite element method. Internat. J. Numer. Methods Engrg. 85, 10 (2011), 1306–1322.Google Scholar
27. S. Mousavi, E. Grinspun, and N. Sukumar. 2011b. Higher-order extended finite elements with harmonic enrichment functions for complex crack problems. Internat. J. Numer. Methods Engrg. 86, 4–5 (2011), 560–574.Google ScholarCross Ref
28. B. Müller, S. Krämer-Eis, F. Kummer, and M. Oberlack. 2017. A high-order discontinuous Galerkin method for compressible flows with immersed boundaries. Internat. J. Numer. Methods Engrg. 110, 1 (2017), 3–30. Google ScholarCross Ref
29. B. Müller, F. Kummer, and M. Oberlack. 2013. Highly accurate surface and volume integration on implicit domains by means of moment-fitting. Internat. J. Numer. Methods Engrg. 96, 8 (2013), 512–528. Google ScholarCross Ref
30. B. Müller, F. Kummer, M. Oberlack, and Y. Wang. 2012. Simple multidimensional integration of discontinuous functions with application to level set methods. Internat. J. Numer. Methods Engrg. 92, 7 (2012), 637–651. Google ScholarCross Ref
31. A. Nealen, M. Müller, R. Keiser, E. Boxerman, and M. Carlson. 2006. Physically Based Deformable Models in Computer Graphics. Computer Graphics Forum 25, 4 (2006), 809–836. Google ScholarCross Ref
32. J. O’Brien, A. Bargteil, and J. Hodgins. 2002. Graphical Modeling and Animation of Ductile Fracture. ACM Transactions on Graphics 21, 3 (2002), 291–294. Google ScholarDigital Library
33. J. O’Brien and J. Hodgins. 1999. Graphical Modeling and Animation of Brittle Fracture. In Conference on Computer Graphics and Interactive Techniques. 137–146. Google ScholarDigital Library
34. M. Pauly, R. Keiser, B. Adams, P. Dutré, M. Gross, and L. Guibas. 2005. Meshless Animation of Fracturing Solids. ACM Transactions on Graphics 24, 3 (2005), 957–964. Google ScholarDigital Library
35. T. Pfaff, R. Narain, J. de Joya, and J. O’Brien. 2014. Adaptive Tearing and Cracking of Thin Sheets. ACM Transactions on Graphics 33 (2014), 1–9. Google ScholarDigital Library
36. C. Richardson, J. Hegemann, E. Sifakis, J. Hellrung, and J. Teran. 2011. An XFEM method for modeling geometrically elaborate crack propagation in brittle materials. Internat. J. Numer. Methods Engrg. 88, 10 (2011), 1042–1065. Google ScholarCross Ref
37. C. Schroeder, A. Stomakhin, R. Howes, and J. Teran. 2014. A second order virtual node algorithm for Navier-Stokes flow problems with interfacial forces and discontinuous material properties. J. Comput. Phys. 265 (2014), 221–245. Google ScholarDigital Library
38. J. Shewchuk. 1994. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Technical Report.Google ScholarDigital Library
39. J. Shewchuk. 2002. What Is a Good Linear Finite Element? Interpolation, Conditioning, Anisotropy, and Quality Measures. Technical Report.Google Scholar
40. E. Sifakis and J. Barbic. 2012. FEM Simulation of 3D Deformable Solids. In ACM SIGGRAPH Courses. 1–50.Google Scholar
41. E. Sifakis, K. Der, and R. Fedkiw. 2007. Arbitrary Cutting of Deformable Tetrahedralized Objects. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 73–80.Google Scholar
42. F. Sin, D. Schroeder, and J. Barbič. 2013. Vega: Non-linear FEM deformable object simulator. Computer Graphics Forum 32, 1 (2013), 36–48. Google ScholarCross Ref
43. P. Sonneveld. 1989. CGS, a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 10, 1 (1989), 36–52. Google ScholarDigital Library
44. D. Steinemann, M. Harders, M. Gross, and G. Szekely. 2006. Hybrid Cutting of Deformable Solids. In IEEE Virtual Reality. 35–42. Google ScholarDigital Library
45. G. Ventura. 2006. On the elimination of quadrature subcells for discontinuous functions in the eXtended Finite-Element Method. Internat. J. Numer. Methods Engrg. 66, 5 (2006), 761–795. Google ScholarCross Ref
46. Y. Wang, C. Jiang, C. Schroeder, and J. Teran. 2014. An Adaptive Virtual Node Algorithm with Robust Mesh Cutting. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 1–9.Google Scholar
47. M. Wicke, D. Ritchie, B. Klingner, S. Burke, J. Shewchuk, and J. O’Brien. 2010. Dynamic local remeshing for elastoplastic simulation. In ACM Transactions on Graphics. Google ScholarDigital Library
48. B. Wu, Z. Xu, and Z. Li. 2008. A note on imposing displacement boundary conditions in finite element analysis. Communications in Numerical Methods in Engineering 24, 9 (2008), 777–784. Google ScholarCross Ref
49. J. Wu, C. Dick, and R. Westermann. 2011. Interactive High-Resolution Boundary Surfaces for Deformable Bodies with Changing Topology. In Virtual Reality Interactions and Physical Simulations. 29–38.Google Scholar
50. J. Wu, R. Westermann, and C. Dick. 2015. A Survey of Physically Based Simulation of Cuts in Deformable Bodies. Computer Graphics Forum 34, 6 (2015), 1–27. Google ScholarDigital Library
51. Y.-H. Yeung, J. Crouch, and A. Pothen. 2016. Interactively Cutting and Constraining Vertices in Meshes Using Augmented Matrices. ACM Transactions on Graphics 35, 2 (2016), 18:1–18:17.Google ScholarDigital Library
52. L. Zhang, T. Cui, and H. Liu. 2009. A Set of Symmetric Quadrature Rules on Triangles and Tetrahedra. Journal of Computational Mathematics 27, 1 (2009), 89–96.Google Scholar
53. Y. Zhu, Y. Wang, J. Hellrung, A. Cantarero, E. Sifakis, and J. Teran. 2012. A second-order virtual node algorithm for nearly incompressible linear elasticity in irregular domains. J. Comput. Phys. 231, 21 (2012), 7092–7117. Google ScholarDigital Library
