“Simulating rigid body fracture with surface meshes” by Zhu, Bridson and Greif

We present a new brittle fracture simulation method based on a boundary integral formulation of elasticity and recent explicit surface mesh evolution algorithms. Unlike prior physically-based simulations in graphics, this avoids the need for volumetric sampling and calculations, which aren’t reflected in the rendered output. We represent each quasi-rigid body by a closed triangle mesh of its boundary, on which we solve quasi-static linear elasticity via boundary integrals in response to boundary conditions and loads such as impact forces and gravity. A fracture condition based on maximum tensile stress is subsequently evaluated at mesh vertices, while crack initiation and propagation are formulated as an interface tracking procedure in material space. Existing explicit mesh tracking methods are modified to support evolving cracks directly in the triangle mesh representation, giving highly detailed fractures with sharp features, independent of any volumetric sampling (unlike tetrahedral mesh or level set approaches); the triangle mesh representation also allows simple integration into rigid body engines. We also give details on our well-conditioned integral equation treatment solved with a kernel-independent Fast Multipole Method for linear time summation. Various brittle fracture scenarios demonstrate the efficacy and robustness of our new method.

1. Alpert, B., Beylkin, G., Coifman, R., and Rokhlin, V. 1993. Wavelet-like bases for the fast solutions of second-kind integral equations. SIAM J. Sci. Comput. 14, 1 (Jan.), 159–184. Google ScholarDigital Library
2. Ang, W.-T. 2014. Hypersingular integral equations in fracture analysis. Elsevier.Google Scholar
3. Bao, Z., Hong, J.-M., Teran, J., and Fedkiw, R. 2007. Fracturing rigid materials. IEEE Trans. Vis. Comp. Graph. 13, 2, 370–378. Google ScholarDigital Library
4. Barnes, J., and Hut, P. 1986. A hierarchical o(nlogn) force-calculation algorithm. Nature 324, 446–449.Google ScholarCross Ref
5. Bender, J., Erleben, K., Trinkle, J., and Coumans, E. 2012. Interactive simulation of rigid body dynamics in computer graphics. In Eurographics 2012 State of the Art Reports. Google ScholarDigital Library
6. Blandford, G. E., Ingraffea, A. R., and Liggett, J. A. 1981. Two-dimensional stress intensity factor computations using the boundary element method. International Journal for Numerical Methods in Engineering 17, 3, 387–404.Google ScholarCross Ref
7. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM J. Sci. Comput. 31, 4, 2472–2493. Google ScholarDigital Library
8. Brochu, T., Batty, C., and Bridson, R. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph. (Proc. SIGGRAPH) 29, 4, 1–9. Google ScholarDigital Library
9. Brochu, T., Keeler, T., and Bridson, R. 2012. Linear-time smoke animation with vortex sheet meshes. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 87–95. Google ScholarDigital Library
10. Busaryev, O., Dey, T. K., and Wang, H. 2013. Adaptive fracture simulation of multi-layered thin plates. ACM Trans. Graph. (Proc. SIGGRAPH) 32, 4, 52:1–6. Google ScholarDigital Library
11. Chen, Z., Yao, M., Feng, R., and Wang, H. 2014. Physics-inspired adaptive fracture refinement. 113:1–113:7.Google Scholar
12. Chunrungsikul, S. 2001. Numerical quadrature methods for singular and nearly singular integrals. PhD thesis, Brunel University.Google Scholar
13. Da, F., Batty, C., and Grinspun, E. 2014. Multimaterial mesh-based surface tracking. ACM Trans. on Graphics (Proc. SIGGRAPH) 33, 4, 112:1–11. Google ScholarDigital Library
14. Erleben, K. 2007. Velocity-based shock propagation for multibody dynamics animation. ACM Trans. Graph. 26, 2, 12. Google ScholarDigital Library
15. Frangi, A. 2002. Fracture propagation in 3d by the symmetric galerkin boundary element method. International Journal of Fracture 116, 4, 313–330.Google ScholarCross Ref
16. Glondu, L., Marchal, M., and Dumont, G. 2013. Real-time simulation of brittle fracture using modal analysis. IEEE Trans. Vis. Comput. Graph. 19, 2, 201–209. Google ScholarDigital Library
17. Golas, A., Narain, R., Sewall, J., Krajcevski, P., Dubey, P., and Lin, M. 2012. Large-scale fluid simulation using velocity-vorticity domain decomposition. ACM Trans. Graph. 31, 6, 148:1–9. Google ScholarDigital Library
18. Greengard, L., and Rokhlin, V. 1987. A fast algorithm for particle simulations. J. Comput. Phys. 73, 2 (Dec.), 325–348. Google ScholarDigital Library
19. Hackbusch, W., and Nowak, Z. 1989. On the fast matrix multiplication in the boundary element method by panel clustering. Numerische Mathematik 54, 4, 463–491. Google ScholarDigital Library
20. Hanrahan, P., Salzman, D., and Aupperle, L. 1991. A rapid hierarchical radiosity algorithm. In Proc. ACM SIGGRAPH, 197–206. Google ScholarDigital Library
21. Hegemann, J., Jiang, C., Schroeder, C., and Teran, J. M. 2013. A level set method for ductile fracture. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 193–201. Google ScholarDigital Library
22. Hockney, R. W., and Eastwood, J. W. 1988. Computer Simulation Using Particles. Taylor & Francis, Inc., Bristol, PA, USA. Google ScholarDigital Library
23. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 131–140. Google ScholarDigital Library
24. James, D. L., and Pai, D. K. 1999. ArtDefo: Accurate real time deformable objects. In Proc. ACM SIGGRAPH, 65–72. Google ScholarDigital Library
25. James, D. L., and Pai, D. K. 2003. Multiresolution green’s function methods for interactive simulation of large-scale elastostatic objects. ACM Trans. Graph. 22, 1. Google ScholarDigital Library
26. James, D. L., Barbič, J., and Pai, D. K. 2006. Precomputed acoustic transfer: Output-sensitive, accurate sound generation for geometrically complex vibration sources. ACM Trans. Graph. (Proc. SIGGRAPH) 25, 3, 987–995. Google ScholarDigital Library
27. Kaufmann, P., Martin, S., Botsch, M., Grinspun, E., and Gross, M. 2009. Enrichment textures for detailed cutting of shells. ACM Trans. Graph. (Proc. SIGGRAPH) 28, 3. Google ScholarDigital Library
28. Köckner, A., Barnett, A., Greengard, L., and O’Neil, M. 2013. Quadrature by expansion: A new method for the evaluation of layer potentials. J. Comp. Phys. 252, 332–349. Google ScholarDigital Library
29. Keeler, T., and Bridson, R. 2014. Ocean waves animation using boundary integral equations and explicit mesh tracking. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 9. Google ScholarDigital Library
30. Kirkup, S., and Yazdani, J. 2008. A gentle introduction to the Boundary Element Method in Matlab/Freemat. In Proc. 10th WSEAS International Conference on Mathematical Methods, Computational Techniques and Intelligent Systems, MAMECTIS’ 08, 46–52. Google ScholarDigital Library
31. Koschier, D., Lipponer, S., and Bender, J. 2014. Adaptive tetrahedral meshes for brittle fracture simulation. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim.Google Scholar
32. Messner, M., and Schanz, M. 2010. An accelerated symmetric time-domain boundary element formulation for elasticity. Engineering Analysis with Boundary Elements 34, 11, 944–955.Google ScholarCross Ref
33. Messner, M. 2008. Time-dependent body forces within a boundary element formulation. PhD thesis, Technische Universität Graz.Google Scholar
34. Molino, N., Bao, Z., and Fedkiw, R. 2004. A virtual node algorithm for changing mesh topology during simulation. ACM Trans. Graph. (Proc. SIGGRAPH) 23, 3, 385–392. Google ScholarDigital Library
35. Müller, M., and Gross, M. 2004. Interactive virtual materials. In Graphics Interface 2004, 239–246. Google ScholarDigital Library
36. Müller, M., McMillan, L., Dorsey, J., and Jagnow, R. 2001. Real-time simulation of deformation and fracture of stiff materials. In Proc. Eurographics Workshop on Computer Animation and Simulation, 113–124. Google ScholarDigital Library
37. Müller, M., Chentanez, N., and Kim, T.-Y. 2013. Real time dynamic fracture with volumetric approximate convex decompositions. ACM Trans. Graph. (Proc. SIGGRAPH) 32, 4, 115:1–10. Google ScholarDigital Library
38. Norton, A., Turk, G., Bacon, B., Gerth, J., and Sweeney, P. 1991. Animation of fracture by physical modeling. The Visual Computer 7, 4, 210–219. Google ScholarDigital Library
39. O’Brien, J. F., and Hodgins, J. K. 1999. Graphical modeling and animation of brittle fracture. In Proc. ACM SIGGRAPH, 137–146. Google ScholarDigital Library
40. O’Brien, J. F., Bargteil, A. W., and Hodgins, J. K. 2002. Graphical modeling and animation of ductile fracture. In Proc. ACM SIGGRAPH, 291–294. Google ScholarDigital Library
41. Park, S. I., and Kim, M. J. 2005. Vortex fluid for gaseous phenomena. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 261–270. Google ScholarDigital Library
42. Parker, E. G., and O’Brien, J. F. 2009. Real-time deformation and fracture in a game environment. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 156–166. Google ScholarDigital Library
43. Pauly, M., Keiser, R., Adams, B., Dutré, P., Gross, M., and Guibas, L. J. 2005. Meshless animation of fracturing solids. ACM Trans. Graph. (Proc. SIGGRAPH) 24, 3, 957–964. Google ScholarDigital Library
44. Pfaff, T., Narain, R., de Joya, J. M., and O’Brien, J. F. 2014. Adaptive tearing and cracking of thin sheets. ACM Trans. Graph. (Proc. SIGGRAPH) 33, 4, 110:1–9. Google ScholarDigital Library
45. Portela, A., Aliabadi, M., and Rooke, D. 1992. The dual boundary element method: effective implementation for crack problems. International Journal for Numerical Methods in Engineering 33, 6, 1269–1287.Google ScholarCross Ref
46. Rezayat, M., Shippy, D., and Rizzo, F. 1986. On time-harmonic elastic-wave analysis by the boundary element method for moderate to high frequencies. Computer Methods in Applied Mechanics and Engineering 55, 3, 349–367. Google ScholarDigital Library
47. Sifakis, E., Der, K. G., and Fedkiw, R. 2007. Arbitrary cutting of deformable tetrahedralized objects. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 73–80. Google ScholarDigital Library
48. Sladek, J., Sladek, V., and Atluri, S. 2004. Meshless local petrov-galerkin method in anisotropic elasticity. Comput Model Eng Sci 6, 477–489.Google Scholar
49. Smith, J., Witkin, A., and Baraff, D. 2001. Fast and controllable simulation of the shattering of brittle objects. Computer Graphics Forum 20, 2 (June), 81–90.Google ScholarCross Ref
50. Steinemann, D., Otaduy, M. A., and Gross, M. 2006. Fast arbitrary splitting of deforming objects. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 63–72. Google ScholarDigital Library
51. Su, J., Schroeder, C., and Fedkiw, R. 2009. Energy stability and fracture for frame rate rigid body simulations. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 155–164. Google ScholarDigital Library
52. Sun, T., Thamjaroenporn, P., and Zheng, C. 2014. Fast multipole representation of diffusion curves and points. ACM Trans. Graph. (Proc. SIGGRAPH 2014) 33, 4. Google ScholarDigital Library
53. Terzopoulos, D., and Fleischer, K. 1988. Modeling inelastic deformation: viscolelasticity, plasticity, fracture. In Proc. ACM SIGGRAPH, vol. 22, 269–278. Google ScholarDigital Library
54. van der Vorst, H. A. 1992. Bi-cgstab: A fast and smoothly converging variant of bi-cg for the solution of nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 13, 2, 631–644. Google ScholarDigital Library
55. Weissmann, S., and Pinkall, U. 2010. Filament-based smoke with vortex shedding and variational reconnection. ACM Trans. Graph. (Proc. SIGGRAPH) 29, 3, 115:1–12. Google ScholarDigital Library
56. Wicke, M., Ritchie, D., Klingner, B. M., Burke, S., Shewchuk, J. R., and O’Brien, J. F. 2010. Dynamic local remeshing for elastoplastic simulation. ACM Trans. Graph. (Proc. SIGGRAPH) 29, 4, 49:1–11. Google ScholarDigital Library
57. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. ACM Trans. Graph. (Proc. SIGGRAPH) 28, 3, 76:1–76:10. Google ScholarDigital Library
58. Wu, J., Westermann, R., and Dick, C. 2014. Physically-based simulation of cuts in deformable bodies: A survey. In Eurographics 2014 State-of-the-Art Report, 1–19.Google Scholar
59. Ying, L., Biros, G., and Zorin, D. 2004. A kernel-independent adaptive fast multipole algorithm in two and three dimensions. J. Comput. Phys. 196, 2 (May), 591–626. Google ScholarDigital Library
60. Zheng, C., and James, D. L. 2010. Rigid-body fracture sound with precomputed soundbanks. ACM Trans. Graph. (Proc. SIGGRAPH) 29, 3. Google ScholarDigital Library