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

  • ©Yufeng Zhu, Robert Bridson, and Chen Greif




    Simulating rigid body fracture with surface meshes



    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

ACM Digital Library Publication: