“Animating sand as a fluid” by Zhu and Bridson

We present a physics-based simulation method for animating sand. To allow for efficiently scaling up to large volumes of sand, we abstract away the individual grains and think of the sand as a continuum. In particular we show that an existing water simulator can be turned into a sand simulator with only a few small additions to account for inter-grain and boundary friction.We also propose an alternative method for simulating fluids. Our core representation is a cloud of particles, which allows for accurate and flexible surface tracking and advection, but we use an auxiliary grid to efficiently enforce boundary conditions and incompressibility. We further address the issue of reconstructing a surface from particle data to render each frame.

1. Adalsteinsson, D., and Sethian, J. 1999. The fast construction of extension velocities in level set methods. J. Comput. Phys. 148, 2–22. Google ScholarDigital Library
2. Bardenhagen, S. G., Brackbill, J. U., and Sulsky, D. 2000. The material-point method for granular materials. Comput. Methods Appl. Mech. Engrg. 187, 529–541.Google ScholarCross Ref
3. Blinn, J. 1982. A generalization of algebraic surface drawing. ACM Trans. Graph. 1, 3, 235–256. Google ScholarDigital Library
4. Brackbill, J. U., and Ruppel, H. M. 1986. FLIP: a method for adaptively zoned, particle-in-cell calculuations of fluid flows in two dimensions. J. Comp. Phys. 65, 314–343. Google ScholarDigital Library
5. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. (Proc. SIGGRAPH) 21, 594–603. Google ScholarDigital Library
6. Carlson, M., Mucha, P., Van Horn II, R., and Turk, G. 2002. Melting and flowing. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 167–174. Google ScholarDigital Library
7. Carlson, M., Mucha, P. J., and Turk, G. 2004. Rigid fluid: animating the interplay between rigid bodies and fluid. ACM Trans. Graph. (Proc. SIGGRAPH) 23, 377–384. Google ScholarDigital Library
8. Desbrun, M., and Cani, M.-P. 1996. Smoothed particles: A new paradigm for animating highly deformable bodies. In Comput. Anim. and Sim. ’96 (Proc. of EG Workshop on Anim. and Sim.), Springer-Verlag, R. Boulic and G. Hegron, Eds., 61–76. Published under the name Marie-Paule Gascuel. Google ScholarDigital Library
9. Enright, D., Fedkiw, R., Ferziger, J., and Mitchell, I. 2002. A hybrid particle level set method for improved interface capturing. J. Comp. Phys. 183, 83–116. Google ScholarDigital Library
10. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. (Proc. SIGGRAPH) 21, 3, 736–744. Google ScholarDigital Library
11. Enright, D., Nguyen, D., Gibou, F., and Fedkiw, R. 2003. Using the particle level set method and a second order accurate pressure boundary condition for free surface flows. In Proc. 4th ASME-JSME Joint Fluids Eng. Conf., no. FEDSM2003-45144, ASME.Google Scholar
12. Fedkiw, R., Stam, J., and Jensen, H. 2001. Visual simulation of smoke. In Proc. SIGGRAPH, 15–22. Google ScholarDigital Library
13. Foster, N., and Fedkiw, R. 2001. Practical animation of liquids. In Proc. SIGGRAPH, 23–30. Google ScholarDigital Library
14. Foster, N., and Metaxas, D. 1996. Realistic animation of liquids. Graph. Models and Image Processing 58, 471–483. Google ScholarDigital Library
15. Génevaux, O., Habibi, A., and Dischler, J.-M. 2003. Simulating fluid-solid interaction. In Graphics Interface, 31–38.Google Scholar
16. Goktekin, T. G., Bargteil, A. W., and O’Brien, J. F. 2004. A method for animating viscoelastic fluids. ACM Trans. Graph. (Proc. SIGGRAPH) 23, 463–468. Google ScholarDigital Library
17. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. ACM Trans. Graph. (Proc. SIGGRAPH) 22, 3, 871–878. Google ScholarDigital Library
18. Harlow, F., and Welch, J. 1965. Numerical Calculation of Time-Dependent Viscous Incompressible Flow of Fluid with Free Surface. Phys. Fluids 8, 2182–2189.Google ScholarCross Ref
19. Harlow, F. H. 1963. The particle-in-cell method for numerical solution of problems in fluid dynamics. In Experimental arithmetic, high-speed computations and mathematics.Google Scholar
20. Herrmann, H. J., and Luding, S. 1998. Modeling granular media on the computer. Continuum Mech. Therm. 10, 189–231.Google ScholarCross Ref
21. Hong, J.-M., and Kim, C.-H. 2003. Animation of bubbles in liquid. Comp. Graph. Forum (Eurographics Proc.) 22, 3, 253–262.Google ScholarCross Ref
22. 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
23. Jaeger, H. M., Nagel, S. R., and Behringer, R. P. 1996. Granular solids, liquids, and gases. Rev. Mod. Phys. 68, 4, 1259–1273.Google ScholarCross Ref
24. Konagai, K., and Johansson, J. 2001. Two dimensional Lagrangian particle finite-difference method for modeling large soil deformations. Structural Eng./Earthquake Eng., JSCE 18, 2, 105s–110s.Google Scholar
25. Kothe, D. B., and Brackbill, J. U. 1992. FLIP-INC: a particle-in-cell method for incompressible flows. Unpublished manuscript.Google Scholar
26. Lamorlette, A. 2001. Shrek effects—flames and dragon fireballs. SIGGRAPH Course Notes, Course 19, 55–66.Google Scholar
27. Li, X., and Moshell, J. M. 1993. Modeling soil: Realtime dynamic models for soil slippage and manipulation. In Proc. SIGGRAPH, 361–368. Google ScholarDigital Library
28. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. (Proc. SIGGRAPH) 23, 457–462. Google ScholarDigital Library
29. Luciani, A., Habibi, A., and Manzotti, E. 1995. A multiscale physical model of granular materials. In Graphics Interface, 136–146.Google Scholar
30. Milenkovic, V. J., and Schmidl, H. 2001. Optimization-based animation. In Proc. SIGGRAPH, 37–46. Google ScholarDigital Library
31. Milenkovic, V. J. 1996. Position-based physics: simulating the motion of many highly interacting spheres and polyhedra. In Proc. SIGGRAPH, 129–136. Google ScholarDigital Library
32. Miller, G., and Pearce, A. 1989. Globular dynamics: a connected particle system for animating viscous fluids. In Comput. & Graphics, vol. 13, 305–309.Google ScholarCross Ref
33. Monaghan, J. J. 1992. Smoothed particle hydrodynamics. Annu. Rev. Astron. Astrophys. 30, 543–574.Google ScholarCross Ref
34. Müller, M., and Gross, M. 2004. Interactive virtual materials. In Graphics Interface. Google ScholarDigital Library
35. Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 154–159. Google ScholarDigital Library
36. Nayak, G. C., and Zienkiewicz, O. C. 1972. Elasto-plastic stress analysis. A generalization for various constitutive relations including strain softening. Int. J. Num. Meth. Eng. 5, 113–135.Google ScholarCross Ref
37. O’Brien, J., Bargteil, A., and Hodgins, J. 2002. Graphical modeling of ductile fracture. ACM Trans. Graph. (Proc. SIGGRAPH) 21, 291–294. Google ScholarDigital Library
38. Onoue, K., and Nishita, T. 2003. Virtual sandbox. In Pacific Graphics, 252–262. Google ScholarDigital Library
39. Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann. Google ScholarDigital Library
40. Premoze, S., Tasdizen, T., Bigler, J., Lefohn, A., and Whitaker, R. 2003. Particle–based simulation of fluids. In Comp. Graph. Forum (Eurographics Proc.), vol. 22, 401–410.Google ScholarCross Ref
41. Rasmussen, N., Enright, D., Nguyen, D., Marino, S., Sumner, N., Geiger, W., Hoon, S., and Fedkiw, R. 2004. Directible photorealistic liquids. In Proc. ACM SIGGRAPH/Eurographics Symp. Comp. Anim., 193–202. Google ScholarDigital Library
42. Savage, S. B., and Hutter, K. 1989. The motion of a finite mass of granular material down a rough incline. J. Flui Mech. 199, 177–215.Google ScholarCross Ref
43. Shen, C., O’Brien, J. F., and Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. ACM Trans. Graph. (Proc. SIGGRAPH) 23, 896–904. Google ScholarDigital Library
44. Smith, I. M., and Griffiths, D. V. 1998. Programming the Finite Element Method. J. Wiley & Sons. Google ScholarDigital Library
45. Stam, J. 1999. Stable fluids. In Proc. SIGGRAPH, 121–128. Google ScholarDigital Library
46. Sulsky, D., Zhou, S.-J., and Schreyer, H. L. 1995. Application of particle-in-cell method to solid mechanics. Comp. Phys. Comm. 87, 236–252.Google ScholarCross Ref
47. Sumner, R. W., O’Brien, J. F., and Hodgins, J. K. 1998. Animating sand, mud, and snow. In Graphics Interface, 125–132.Google Scholar
48. Sussman, M. 2003. A second order coupled level set and volume-of-fluid method for computing growth and collapse of vapor bubbles. J. Comp. Phys. 187, 110–136. Google ScholarDigital Library
49. Takahashi, T., Fujii, H., Kunimatsu, A., Hiwada, K., Saito, T., Tanaka, K., and Ueki, H. 2003. Realistic animation of fluid with splash and foam. Comp. Graph. Forum (Eurographics Proc.) 22, 3, 391–400.Google ScholarCross Ref
50. Takeshita, D., Ota, S., Tamura, M., Fujimoto, T., and Chiba, N. 2003. Visual simulation of explosive flames. In Pacific Graphics, 482–486. Google ScholarDigital Library
51. Terzopoulos, D., and Fleischer, K. 1988. Modeling inelastic deformation: viscoelasticity, plasticity, fracture. Proc. SIGGRAPH, 269–278. Google ScholarDigital Library
52. Zhao, H. 2005. A fast sweeping method for Eikonal equations. Math. Comp. 74, 603–627.Google ScholarCross Ref