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

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