“Dynamic local remeshing for elastoplastic simulation” by Wicke, Ritchie, Klingner, Burke, Shewchuk, et al. …

  • ©Martin Wicke, Daniel Ritchie, Bryan M. Klingner, Sebastian Burke, Jonathan R. Shewchuk, and James F. O'Brien




    Dynamic local remeshing for elastoplastic simulation



    We propose a finite element simulation method that addresses the full range of material behavior, from purely elastic to highly plastic, for physical domains that are substantially reshaped by plastic flow, fracture, or large elastic deformations. To mitigate artificial plasticity, we maintain a simulation mesh in both the current state and the rest shape, and store plastic offsets only to represent the non-embeddable portion of the plastic deformation. To maintain high element quality in a tetrahedral mesh undergoing gross changes, we use a dynamic meshing algorithm that attempts to replace as few tetrahedra as possible, and thereby limits the visual artifacts and artificial diffusion that would otherwise be introduced by repeatedly remeshing the domain from scratch. Our dynamic mesher also locally refines and coarsens a mesh, and even creates anisotropic tetrahedra, wherever a simulation requests it. We illustrate these features with animations of elastic and plastic behavior, extreme deformations, and fracture.


    1. Bargteil, A. W., Wojtan, C., Hodgins, J. K., and Turk, G. 2007. A finite element method for animating large viscoplastic flow. ACM Transactions on Graphics 26, 3, 16:1–16:8. Google ScholarDigital Library
    2. Bielser, D., Maiwald, V. A., and Gross, M. H. 1999. Interactive cuts through 3-dimensional soft tissue. Computer Graphics Forum 18, 3, 31–38.Google ScholarCross Ref
    3. Briere de l’Isle, E., and George, P.-L. 1995. Optimization of tetrahedral meshes. In Modeling, Mesh Generation, and Adaptive Numerical Methods for Partial Differential Equations, vol. 75 of IMA Volumes in Mathematics and its Applications. 97–128.Google Scholar
    4. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM Journal on Scientific Computing 31, 4, 2472–2493. Google ScholarDigital Library
    5. Budd, C. J., Huang, W., and Russell, R. D. 2009. Adaptivity with moving grids. In Acta Numerica 2009, vol. 18. 1–131.Google Scholar
    6. Canann, S. A., Stephenson, M., and Blacker, T. 1993. Optismoothing: An optimization-driven approach to mesh smoothing. Finite Elements in Analysis and Design 13, 185–190. Google ScholarDigital Library
    7. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. A multiresolution framework for dynamic deformations. In Proc. Symposium on Computer Animation, 41–48. Google ScholarDigital Library
    8. Cardoze, D., Cunha, A., Miller, G. L., Phillips, T., and Walkington, N. 2004. A Bézier-based approach to unstructured moving meshes. In Proc. Symposium on Computational Geometry, 310–319. Google ScholarDigital Library
    9. Carlson, M., Mucha, P. J., Van Horn III, R. B., and Turk, G. 2002. Melting and flowing. In Proc. Symposium on Computer Animation, 167–174. Google ScholarDigital Library
    10. Carlson, M., Mucha, P. J., and Turk, G. 2004. Rigid fluid: Animating the interplay between rigid bodies and fluid. ACM Transactions on Graphics 23, 3, 377–384. Google ScholarDigital Library
    11. Cheng, S.-W., Dey, T. K., Edelsbrunner, H., Facello, M. A., and Teng, S.-H. 2000. Sliver exudation. Journal of the Association for Computing Machinery 47, 5, 883–904. Google ScholarDigital Library
    12. Chentanez, N., Feldman, B. E., Labelle, F., O’Brien, J. F., and Shewchuk, J. R. 2007. Liquid simulation on lattice-based tetrahedral meshes. In Proc. Symposium on Computer Animation, 219–228. Google ScholarDigital Library
    13. Chentanez, N., Alterovitz, R., Ritchie, D., Cho, L., Hauser, K. K., Goldberg, K., Shewchuk, J. R., and O’Brien, J. F. 2009. Interactive simulation of surgical needle insertion and steering. ACM Transactions on Graphics 28, 3, 88:1–88:10. Google ScholarDigital Library
    14. Cook, R. D., Malkus, D. S., Plesha, M. E., and Witt, R. J. 2001. Concepts and Applications of Finite Element Analysis, fourth ed. John Wiley & Sons, New York. Google ScholarDigital Library
    15. de Cougny, H. L., and Shephard, M. S. 1995. Refinement, derefinement, and optimization of tetrahedral geometric triangulations in three dimensions. Manuscript.Google Scholar
    16. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic real-time deformations using space & time adaptive sampling. In Proc. SIGGRAPH ’01, 31–36. Google ScholarDigital Library
    17. Edelsbrunner, H., and Guoy, D. 2001. An experimental study of sliver exudation. In Proc. Tenth International Meshing Roundtable, 307–316.Google Scholar
    18. Enright, D., Fedkiw, R., Ferziger, J., and Mitchell, I. 2002. A hybrid particle level set method for improved interface capturing. Journal of Computational Physics 183, 1, 83–116. Google ScholarDigital Library
    19. Freitag, L. A., and Ollivier-Gooch, C. 1997. Tetrahedral mesh improvement using swapping and smoothing. International Journal for Numerical Methods in Engineering 40, 21, 3979–4002.Google ScholarCross Ref
    20. Freitag, L. A., Jones, M., and Plassmann, P. 1995. An efficient parallel algorithm for mesh smoothing. In Proc. Fourth International Meshing Roundtable, 47–58.Google Scholar
    21. Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proc. SIGGRAPH ’00, 249–254. Google ScholarDigital Library
    22. Ganovelli, F., Cignoni, P., Montani, C., and Scopigno, R. 2001. Enabling cuts on multiresolution representation. The Visual Computer 17, 5, 274–286.Google ScholarCross Ref
    23. Garland, M., and Heckbert, P. 1997. Surface simplification using quadric error metrics. In Proc. SIGGRAPH ’97, 209–216. Google ScholarDigital Library
    24. Gibson, S. F. F., and Mirtich, B. 1997. A survey of deformable modeling in computer graphics. Tech. Rep. TR97-17, Mitsubishi Electric Research Laboratories.Google Scholar
    25. Goktekin, T. G., Bargteil, A. W., and O’Brien, J. F. 2004. A method for animating viscoelastic fluids. ACM Transactions on Graphics 23, 3, 463–468. Google ScholarDigital Library
    26. Grinspun, E., Krysl, P., and Schröder, P. 2002. CHARMS: A simple framework for adaptive simulation. ACM Transactions on Graphics 21, 3, 281–290. Google ScholarDigital Library
    27. Hermann, L. R. 1976. Laplacian-isoparametric grid generation scheme. Journal of the Engineering Mechanics Division of the American Society of Civil Engineers 102, 749–756.Google Scholar
    28. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proc. Symposium on Computer Animation, 131–140. Google ScholarDigital Library
    29. Jiao, X. 2007. Face offsetting: A unified approach for explicit moving interfaces. Journal of Computational Physics 31, 4, 2472–2493. Google ScholarDigital Library
    30. Joe, B. 1995. Construction of three-dimensional improved-quality triangulations using local transformations. SIAM Journal on Scientific Computing 16, 6, 1292–1307. Google ScholarDigital Library
    31. Jones, M. T., and Plassmann, P. E. 1997. Adaptive refinement of unstructured finite-element meshes. Finite Elements in Analysis and Design 25, 41–60. Google ScholarDigital Library
    32. Klincsek, G. T. 1980. Minimal triangulations of polygonal domains. Annals of Discrete Mathematics 9, 121–123.Google ScholarCross Ref
    33. Klingner, B. M., and Shewchuk, J. R. 2007. Aggressive tetrahedral mesh improvement. In Proc. 16th International Meshing Roundtable, 3–23.Google Scholar
    34. Klingner, B. M., Feldman, B. E., Chentanez, N., and O’Brien, J. F. 2006. Fluid animation with dynamic meshes. ACM Transactions on Graphics 25, 3, 820–825. Google ScholarDigital Library
    35. Klingner, B. M. 2009. Tetrahedral Mesh Improvement. PhD thesis, Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, California.Google Scholar
    36. Kucharik, M., Garimella, R. V., Schofield, S. P., and Shashkov, M. J. 2010. A comparative study of interface reconstruction methods for multi-material ALE simulations. Journal of Computational Physics 229, 7, 2432–2452. Google ScholarDigital Library
    37. Mauch, S., Noels, L., Zhao, Z., and Radovitzky, R. A. 2006. Lagrangian simulation of penetration environments via mesh healing and adaptive optimization. In Proc. 25th Army Science Conference.Google Scholar
    38. Molino, N., Bao, Z., and Fedkiw, R. 2004. A virtual node algorithm for changing mesh topology during simulation. ACM Transactions on Graphics 23, 3, 385–392. Google ScholarDigital Library
    39. Müller, M., and Gross, M. H. 2004. Interactive virtual materials. In Proc. Graphics Interface, 239–246. Google ScholarDigital Library
    40. Müller, M., Teschner, M., and Gross, M. 2004. Physically-based simulation of objects represented by surface meshes. In Proc. Computer Graphics International, 26–33. Google ScholarDigital Library
    41. Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically based deformable models in computer graphics. Computer Graphics Forum 25, 4, 809–836.Google ScholarCross Ref
    42. O’Brien, J. F., and Hodgins, J. K. 1999. Graphical modeling and animation of brittle fracture. In Proc. SIGGRAPH ’99, 137–146. Google ScholarDigital Library
    43. O’Brien, J. F., Bargteil, A. W., and Hodgins, J. K. 2002. Graphical modeling and animation of ductile fracture. ACM Transactions on Graphics 21, 3, 291–294. Google ScholarDigital Library
    44. Oden, J. T., and Demkowicz, L. F. 1989. Advances in adaptive improvements: A survey of adaptive finite element methods in computational mechanics. In State-of-the-Art Surveys on Computational Mechanics. The American Society of Mechanical Engineers, 441–467.Google Scholar
    45. Parthasarathy, V. N., and Kodiyalam, S. 1991. A constrained optimization approach to finite element mesh smoothing. Finite Elements in Analysis and Design 9, 4, 309–320. Google ScholarDigital Library
    46. Parthasarathy, V. N., Graichen, C. M., and Hathaway, A. F. 1994. A comparison of tetrahedron quality measures. Finite Elements in Analysis and Design 15, 3, 255–261. Google ScholarDigital Library
    47. Shamir, A., Pascucci, V., and Bajaj, C. 2000. Multiresolution dynamic meshes with arbitrary deformations. In Proc. IEEE Visualization, 423–430. Google ScholarDigital Library
    48. Shewchuk, J. R. 2002. Two discrete optimization algorithms for the topological improvement of tetrahedral meshes. Manuscript.Google Scholar
    49. Sifakis, E., Shinar, T., Irving, G., and Fedkiw, R. 2007. Hybrid simulation of deformable solids. In Proc. Symposium on Computer Animation, 81–90. Google ScholarDigital Library
    50. Steinemann, D., Harders, M., Gross, M., and Szekely, G. 2006. Hybrid cutting of deformable solids. In Proc. IEEE Virtual Reality. Google ScholarDigital Library
    51. Steinemann, D., Otaduy, M. A., and Gross, M. 2006. Fast arbitrary splitting of deforming objects. In Proc. Symposium on Computer Animation, 63–72. Google ScholarDigital Library
    52. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Proc. SIGGRAPH ’87, 205–214. Google ScholarDigital Library
    53. Wojtan, C., and Turk, G. 2008. Fast viscoelastic behavior with thin features. ACM Transactions on Graphics 27, 3, 47:1–47:8. Google ScholarDigital Library
    54. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2009. Deforming meshes that split and merge. ACM Transactions on Graphics 28, 3, 76:1–76:10. Google ScholarDigital Library

ACM Digital Library Publication: