Enrichment textures for detailed cutting of shells

ABSTRACT

We present a method for simulating highly detailed cutting and fracturing of thin shells using low-resolution simulation meshes. Instead of refining or remeshing the underlying simulation domain to resolve complex cut paths, we adapt the extended finite element method (XFEM) and enrich our approximation by customdesigned basis functions, while keeping the simulation mesh unchanged. The enrichment functions are stored in enrichment textures, which allows for fracture and cutting discontinuities at a resolution much finer than the underlying mesh, similar to image textures for increased visual resolution. Furthermore, we propose harmonic enrichment functions to handle multiple, intersecting, arbitrarily shaped, progressive cuts per element in a simple and unified framework. Our underlying shell simulation is based on discontinuous Galerkin (DG) FEM, which relaxes the restrictive requirement of C¹ continuous basis functions and thus allows for simpler, C⁰ continuous XFEM enrichment functions.

REFERENCES

• 1: Yazid Abdelaziz , Abdelmadjid Hamouine, Review: A survey of the extended finite element, Computers and Structures, v.86 n.11-12, p.1141-1151, June, 2008 [doi>10.1016/j.compstruc.2007.11.001]
• 2: Douglas N. Arnold , Franco Brezzi , Bernardo Cockburn , L. Donatella Marini, Unified Analysis of Discontinuous Galerkin Methods for Elliptic Problems, SIAM Journal on Numerical Analysis, v.39 n.5, p.1749-1779, 2001 [doi>10.1137/S0036142901384162]
• 3: Babuska, I., and Melenk, J. M. 1996. The partition of unity finite element method: Basic theory and applications. Comput. Meth. Appl. Mech. Eng., Special Issue on Meshless Methods 139, 289--314.
• 4: Zhaosheng Bao , Jeong-Mo Hong , Joseph Teran , Ronald Fedkiw, Fracturing Rigid Materials, IEEE Transactions on Visualization and Computer Graphics, v.13 n.2, p.370-378, March 2007 [doi>10.1109/TVCG.2007.39]
• 5: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 6: Belytschko, T., and Black, T. 1999. Elastic crack growth in finite elements with minimal remeshing. Int. J. Numer. Methods Eng. 45, 5, 601--620.
• 7: Bielser, D., Maiwald, V., and Gross, M. 1999. Interactive cuts through 3-dimensional soft tissue. Computer Graphics Forum (Proc. Eurographics) 18, 3, 31--38.
• 8: Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 9: R. Bridson , S. Marino , R. Fedkiw, Simulation of clothing with folds and wrinkles, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 10: Kwang-Jin Choi , Hyeong-Seok Ko, Stable but responsive cloth, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 11: Cirak, F., Ortiz, M., and Schröder, P. 2000. Subdivision surfaces: A new paradigm for thin-shell finite-element analysis. Int. J. Numer. Methods Eng. 47, 12, 2039--2072.
• 12: Cockburn, B. 2003. Discontinuous Galerkin methods. Z. Angew. Math. Mech. 83, 11, 731--754.
• 13: François Boux de Casson , Christian Laugier, Simulating 2D Tearing Phenomena for Interactive Medical Surgery Simulators, Proceedings of the Computer Animation, p.9, May 03-05, 2000
• 14: Desbenoit, B., Galin, E., and Akkouche, S. 2005. Modeling cracks and fractures. The Visual Computer 21, 8--10, 717--726.
• 15: Elliot English , Robert Bridson, Animating developable surfaces using nonconforming elements, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 16: Clement Forest , Herve Delingette , Nicholas Ayache, Removing Tetrahedra from a Manifold Mesh, Proceedings of the Computer Animation, p.225, June 19-21, 2002
• 17: Gingold, Y., Secord, A., Han, J. Y., Grinspun, E., and Zorin, D. 2004. A discrete model for inelastic deformation of thin shells. Tech. rep., Courant Institute of Mathematical Sciences, New York University.
• 18: Rony Goldenthal , David Harmon , Raanan Fattal , Michel Bercovier , Eitan Grinspun, Efficient simulation of inextensible cloth, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 19: Gracie, R., Wang, H., and Belytschko, T. 2008. Blending in the extended finite element method by discontinuous Galerkin and assumed strain methods. Int. J. Numer. Methods Eng. 74, 11, 1645--1669.
• 20: Eitan Grinspun , Petr Krysl , Peter Schröder, CHARMS: a simple framework for adaptive simulation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 21: Eitan Grinspun , Anil N. Hirani , Mathieu Desbrun , Peter Schröder, Discrete shells, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 22: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 23: Xiaohu Guo , Xin Li , Yunfan Bao , Xianfeng Gu , Hong Qin, Meshless Thin-Shell Simulation Based on Global Conformal Parameterization, IEEE Transactions on Visualization and Computer Graphics, v.12 n.3, p.375-385, May 2006 [doi>10.1109/TVCG.2006.52]
• 24: Huang, R., Sukumar, N., and Prévost, J. 2003. Modeling quasi-static crack growth with the extended finite element method -- Part II. Int. J. of Solids and Structures 40, 26, 7539--7552.
• 25: Hughes, T. J. R. 2000. The Finite Element Method. Linear Static and Dynamic Finite Element Analysis. Dover Publications.
• 26: Lenka Jeřábková , Torsten Kuhlen, Stable Cutting of Deformable Objects in Virtual Environments Using XFEM, IEEE Computer Graphics and Applications, v.29 n.2, p.61-71, March 2009 [doi>10.1109/MCG.2009.32]
• 27: Kaufmann, P., Martin, S., Botsch, M., and Gross, M. 2008. Flexible simulation of deformable models using discontinuous Galerkin FEM. In Proc. of Symp. on Computer Animation, 105--115.
• 28: Kaufmann, P., Martin, S., Botsch, M., and Gross, M. 2009. Implementation of discontinuous Galerkin Kirchhoff-Love shells. Tech. Rep. no. 622, Department of Computer Science, ETH Zurich.
• 29: Martin, S., Kaufmann, P., Botsch, M., Wicke, M., and Gross, M. 2008. Polyhedral finite elements using harmonic basis functions. Computer Graphics Forum (Proc. of Symp. on Geometry Processing) 27, 5, 1521--1529.
• 30: Moës, N., Dolbow, J., and Belytschko, T. 1999. A finite element method for crack growth without remeshing. Int. J. Numer. Methods Eng. 46, 1, 131--150.
• 31: Moës, N., Gravouil, A., and Belytschko, T. 2002. Nonplanar 3d crack growth by the extended finite element and level sets - Part I. Int. J. Numer. Methods Eng. 53, 11, 2549--2568.
• 32: Neil Molino , Zhaosheng Bao , Ron Fedkiw, A virtual node algorithm for changing mesh topology during simulation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 33: Müller, M. 2008. Hierarchical position based dynamics. In Proc. of Virtual Reality Interactions and Physical Simulations.
• 34: Noels, L., and Radovitzky, R. 2008. A new discontinuous Galerkin method for Kirchhoff-Love shells. Computer Methods in Applied Mechanics and Engineering 197, 2901--2929.
• 35: Noels, L. 2009. A discontinuous Galerkin formulation of nonlinear Kirchhoff-Love shells. Int. J. Numer. Methods Eng. 78, 3, 296--323.
• 36: James F. O'Brien , Jessica K. Hodgins, Graphical modeling and animation of brittle fracture, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.137-146, July 1999 [doi>10.1145/311535.311550]
• 37: James F. O'Brien , Adam W. Bargteil , Jessica K. Hodgins, Graphical modeling and animation of ductile fracture, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 38: Mark Pauly , Richard Keiser , Bart Adams , Philip Dutré , Markus Gross , Leonidas J. Guibas, Meshless animation of fracturing solids, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 39: Réthoré, J., Gravouil, A., and Combescure, A. 2005. An energy-conserving scheme for dynamic crack growth using the extended finite element method. Int. J. Numer. Methods Eng. 63, 5, 631--659.
• 40: Sethian, J. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press.
• 41: Eftychios Sifakis , Kevin G. Der , Ronald Fedkiw, Arbitrary cutting of deformable tetrahedralized objects, Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 02-04, 2007, San Diego, California
• 42: Stazi, F. L., Budyn, E., Chessa, J., and Belytschko, T. 2003. An extended finite element method with higher-order elements for curved cracks. Comput. Mech. 31, 1, 38--48.
• 43: Denis Steinemann , Miguel A. Otaduy , Markus Gross, Fast arbitrary splitting of deforming objects, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 44: Demetri Terzopoulos , Kurt Fleischer, Modeling inelastic deformation: viscolelasticity, plasticity, fracture, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.269-278, June 1988
• 45: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.205-214, August 1987
• 46: Bernhard Thomaszewski , Markus Wacker , Wolfgang Straßer, A consistent bending model for cloth simulation with corotational subdivision finite elements, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 47: Toledo, S., Chen, D., and Rotkin, V., 2003. Taucs: A library of sparse linear solvers. http://www.tau.ac.il/~stoledo/taucs.
• 48: Wempner, G., and Talaslidis, D. 2003. Mechanics of solids and shells: theories and approximations. CRC Press.
• 49: Wicke, M., Steinemann, D., and Gross, M. 2005. Efficient animation of point-sampled thin shells. Computer Graphics Forum (Proc. Eurographics) 24, 667--676.
• 50: Wicke, M., Botsch, M., and Gross, M. 2007. A finite element method on convex polyhedra. Computer Graphics Forum (Proc. Eurographics) 26, 3, 355--364.
• 51: Zi, G., and Belytschko, T. 2003. New crack-tip elements for XFEM and applications to cohesive cracks. Int. J. Numer. Methods Eng. 57, 15, 2221--2240.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation