“Eulerian solid simulation with contact” by Levin, Litven, Jones, Sueda and Pai

  • ©David I. W. Levin, Joshua Litven, Garrett L. Jones, Shinjiro Sueda, and Dinesh K. Pai




    Eulerian solid simulation with contact



    Simulating viscoelastic solids undergoing large, nonlinear deformations in close contact is challenging. In addition to inter-object contact, methods relying on Lagrangian discretizations must handle degenerate cases by explicitly remeshing or resampling the object. Eulerian methods, which discretize space itself, provide an interesting alternative due to the fixed nature of the discretization. In this paper we present a new Eulerian method for viscoelastic materials that features a collision detection and resolution scheme which does not require explicit surface tracking to achieve accurate collision response. Time-stepping with contact is performed by the efficient solution of large sparse quadratic programs; this avoids constraint sticking and other difficulties. Simulation and collision processing can share the same uniform grid, making the algorithm easy to parallelize. We demonstrate an implementation of all the steps of the algorithm on the GPU. The method is effective for simulation of complicated contact scenarios involving multiple highly deformable objects, and can directly simulate volumetric models obtained from medical imaging techniques such as CT and MRI.


    1. Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. 2010. Volume contact constraints at arbitrary resolution. ACM Trans. Graph. 29, 4 (July), 82:1–82:10. Google ScholarDigital Library
    2. Banks, J. W., Schwendeman, D. W., Kapila, A. K., and Henshaw, W. D. 2007. A high-resolution Godunov method for compressible multi-material flow on overlapping grids. J. Comput. Phys. 223, 1, 262–297. Google ScholarDigital Library
    3. Bargteil, A. W., Wojtan, C., Hodgins, J. K., and Turk, G. 2007. A Finite Element Method for Animating Large Viscoplastic Flow. ACM Trans. Graph. 26, 3 (July), 16:1–16:8. Google ScholarDigital Library
    4. Barton, P. T., and Drikakis, D. 2010. An Eulerian method for multi-component problems in non-linear elasticity with sliding interfaces. J. Comput. Phys. 229, 15, 5518–5540. Google ScholarDigital Library
    5. Batty, C., Bertails, F., and Bridson, R. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Trans. Graph. 26, 3 (July), 100:1–100:7. Google ScholarDigital Library
    6. Bell, N., and Garland, M., 2010. Cusp: Generic parallel algorithms for sparse matrix and graph computations. Version 0.1.0. http://cusp-library.googlecode.com.Google Scholar
    7. Brochu, T., Batty, C., and Bridson, R. 2010. Matching fluid simulation elements to surface geometry and topology. ACM Trans. Graph. 29, 4 (July), 47:1–47:9. Google ScholarDigital Library
    8. Carlson, M., Mucha, P. J., Van Horn, III, R. B., and Turk, G. 2002. Melting and flowing. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, SCA ’02, 167–174. Google Scholar
    9. Carlson, M., Mucha, P. J., and Turk, G. 2004. Rigid fluid: animating the interplay between rigid bodies and fluid. ACM Trans. Graph. 23 (August), 377–384. Google ScholarDigital Library
    10. Cline, M., and Pai, D. 2003. Post-stabilization for rigid body simulation with contact and constraints. In Proc. ICRA’03, vol. 3, 3744–3751.Google Scholar
    11. Desbrun, M., and Gascuel, M. P. 1996. Smoothed particles: a new paradigm for animating highly deformable bodies. In Proceedings of the Eurographics workshop on Computer animation and simulation, 61–76. Google ScholarDigital Library
    12. Enright, D., Fedkiw, R., Ferziger, J., and Mitchell, I. 2002. A hybrid particle level set method for improved interface capturing. J. Comput. Phys. 183, 1, 83–116. Google ScholarDigital Library
    13. Faure, F., Allard, J., and Nesme, M. 2007. Eulerian Contact for Versatile Collision Processing. Research Report RR-6203, INRIA.Google Scholar
    14. Fedkiw, R. P., Aslam, T., Merriman, B., and Osher, S. 1999. A non-oscillatory Eulerian approach to interfaces in multimaterial flows (the ghost fluid method). J. Comput. Phys. 152, 2, 457–492. Google ScholarDigital Library
    15. Foster, N., and Metaxas, D. 1996. Realistic animation of liquids. Graph. Models Image Process. 58, 5, 471–483. Google ScholarDigital Library
    16. Gilles, B., Bousquet, G., Faure, F., and Pai, D. K. 2011. Frame-based elastic models. ACM Trans. Graph. 30, 2 (April), 15:2–15:12. Google ScholarDigital Library
    17. Goktekin, T. G., Bargteil, A. W., and O’Brien, J. F. 2004. A method for animating viscoelastic fluids. ACM Trans. Graph. 23 (August), 463–468. Google ScholarDigital Library
    18. Harris, M., Sengupta, S., and Owens, J. D. 2007. Parallel prefix sum (scan) with CUDA. In GPU Gems 3, H. Nguyen, Ed. Addison Wesley.Google Scholar
    19. Humphrey, J., Price, D., Spagnoli, K., Paolini, A., and Kelmelis, E. 2010. CULA: hybrid GPU accelerated linear algebra routines. In Proc. SPIE, vol. 7705, 1.Google Scholar
    20. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, SCA ’04, 131–140. Google Scholar
    21. Kamrin, K., and Nave, J.-C. 2009. An eulerian approach to the simulation of deformable solids: Application to finite-strain elasticity. Submitted (available: http://arxiv.org/PS_cache/arxiv/pdf/0901/0901.3799v2.pdf).Google Scholar
    22. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered projections for frictional contact in multibody systems. ACM Trans. Graph. 27, 5 (December), 164:1–164:11. Google ScholarDigital Library
    23. Labelle, F., and Shewchuk, J. R. 2007. Isosurface stuffing: fast tetrahedral meshes with good dihedral angles. ACM Trans. Graph. 26, 3 (July), 57:1–57:10. Google ScholarDigital Library
    24. Le Grand, S. 2007. Broad-Phase Collision Detection with CUDA. In GPU Gems 3, H. Nguyen, Ed. Addison-Wesley.Google Scholar
    25. Lévy, B., and Liu, Y. 2010. L p Centroidal Voronoi Tessellation and its applications. ACM Trans. Graph. 29, 4 (July), 119:1–119:11. Google ScholarDigital Library
    26. Losasso, F., Shinar, T., Selle, A., and Fedkiw, R. 2006. Multiple interacting liquids. ACM Trans. Graph. 25, 3 (July), 812–819. Google ScholarDigital Library
    27. McAdams, A., Selle, A., Ward, K., Sifakis, E., and Teran, J. 2009. Detail preserving continuum simulation of straight hair. ACM Trans. Graph. 28, 3 (July), 62:1–62:6. Google ScholarDigital Library
    28. Mehrotra, S. 1992. On the Implementation of a Primal-Dual Interior Point Method. SIOPT 2, 4, 575–601.Google ScholarCross Ref
    29. Miller, G., and Colella, P. 2001. A High-Order Eulerian Godunov Method for Elastic-Plastic Flow in Solids* 1. J. Comput. Phys. 167, 1, 131–176. Google ScholarDigital Library
    30. Moreau, J. J. 1966. Quadratic programming in mechanics: One-sided constraints. Journal SIAM Control 4, 1, 153–158.Google ScholarCross Ref
    31. Müller, M., Keiser, R., Nealen, A., Pauly, M., Gross, M., and Alexa, M. 2004. Point based animation of elastic, plastic and melting objects. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, SCA ’04, 141–151. Google Scholar
    32. Müller, M., Teschner, M., and Gross, M. 2004. Physically-based simulation of objects represented by surface meshes. In Proc. CGI 2004, 26–33. Google Scholar
    33. Narain, R., Golas, A., and Lin, M. C. 2010. Free-flowing granular materials with two-way solid coupling. ACM Trans. Graph. 29 (December), 173:1–173:10. Google ScholarDigital Library
    34. Nocedal, J., and Wright, S. 1999. Numerical Optimization. Springer-Verlag.Google Scholar
    35. NVIDIA Corporation, 2010. CUDA Programming Guide.Google Scholar
    36. Osher, S., and Fedkiw, R. 2002. Level set methods and dynamic implicit surfaces. Springer-Verlag.Google Scholar
    37. Petrovic, L., Henne, M., and Anderson, J. 2005. Volumetric methods for simulation and rendering of hair. Tech. rep., Pixar Animation Studios.Google Scholar
    38. Robinson-Mosher, A., English, R. E., and Fedkiw, R. 2009. Accurate tangential velocities for solid fluid coupling. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’09, 227–236. Google Scholar
    39. Roettger, S., 2011. The volume library. http://www9.informatik.uni-erlangen.de/External/vollib/.Google Scholar
    40. Solenthaler, B., Schläfli, J., and Pajarola, R. 2007. A unified particle model for fluid-solid interactions. Computer Animation and Virtual Worlds 18, 1, 69–82. Google ScholarDigital Library
    41. Sulsky, D., Chen, Z., and Schreyer, H. 1994. A particle method for history-dependent materials. Computer Methods in Applied Mechanics and Engineering 118, 1-2, 179–196.Google ScholarCross Ref
    42. Sulsky, D., Zhou, S., and Schreyer, H. 1995. Application of a particle-in-cell method to solid mechanics. Computer Physics Communications 87, 1-2, 236–252.Google ScholarCross Ref
    43. Teran, J., Blemker, S., Hing, V. N. T., and Fedkiw, R. 2003. Finite volume methods for the simulation of skeletal muscle. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, SCA ’03, 68–74. Google ScholarDigital Library
    44. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Computer Graphics (Proceedings of SIGGRAPH 87), vol. 21, ACM, 205–214. Google Scholar
    45. Tran, L. B., and Udaykumar, H. S. 2004. A particle-level set-based sharp interface cartesian grid method for impact, penetration, and void collapse. J. Comput. Phys. 193, 2, 469–510. Google ScholarDigital Library
    46. Trangenstein, J. 1994. A second-order Godunov algorithm for two-dimensional solid mechanics. Computational Mechanics 13, 5, 343–359.Google ScholarCross Ref
    47. 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. 29 (July), 49:1–49:11. Google ScholarDigital Library
    48. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3 (July), 965–972. Google ScholarDigital Library

ACM Digital Library Publication: