Real-time Eulerian water simulation using a restricted tall cell grid

Abstract

We present a new Eulerian fluid simulation method, which allows real-time simulations of large scale three dimensional liquids. Such scenarios have hitherto been restricted to the domain of off-line computation. To reduce computation time we use a hybrid grid representation composed of regular cubic cells on top of a layer of tall cells. With this layout water above an arbitrary terrain can be represented without consuming an excessive amount of memory and compute power, while focusing effort on the area near the surface where it most matters. Additionally, we optimized the grid representation for a GPU implementation of the fluid solver. To further accelerate the simulation, we introduce a specialized multi-grid algorithm for solving the Poisson equation and propose solver modifications to keep the simulation stable for large time steps. We demonstrate the efficiency of our approach in several real-world scenarios, all running above 30 frames per second on a modern GPU. Some scenes include additional features such as two-way rigid body coupling as well as particle representations of sub-grid detail.

References

1. Adalsteinsson, D., and Sethian, J. A. 1997. The fast construction of extension velocities in level set methods. Journal of Computational Physics 148, 2--22.
2. Adams, B., Pauly, M., Keiser, R., and Guibas, L. J. 2007. Adaptively sampled particle fluids. In Proc. SIGGRAPH, 48.
3. Bargteil, A. W., Goktekin, T. G., O'Brien, J. F., and Strain, J. A. 2005. A semi-lagrangian contouring method for fluid simulation. ACM Transactions on Graphics.
4. Batty, C., Bertails, F., and Bridson, R. 2007. A fast variational framework for accurate solid-fluid coupling. In Proc. SIGGRAPH, 100.
5. Batty, C., Xenos, S., and Houston, B. 2010. Tetrahedral embedded boundary methods for accurate and flexible adaptive fluids. In Proc. Eurographics.
6. Bridson, R. 2008. Fluid Simulation for Computer Graphics. A K Peters.
7. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM Journal on Scientific Computing 31, 4, 2472--2493.
8. Brochu, T., Batty, C., and Bridson, R. 2010. Matching fluid simulation elements to surface geometry and topology. In Proc. SIGGRAPH, 1--9.
9. Carlson, M., Mucha, P. J., and Turk, G. 2004. Rigid fluid: animating the interplay between rigid bodies and fluid. In Proc. SIGGRAPH, 377--384.
10. Chentanez, N., and Müller-Fischer, M. 2010. Real-time simulation of large bodies of water with small scale details. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation.
11. Chentanez, N., Goktekin, T. G., Feldman, B. E., and O'Brien, J. F. 2006. Simultaneous coupling of fluids and deformable bodies. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 83--89.
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. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 219--228.
13. Cohen, J. M., Tariq, S., and Green, S. 2010. Interactive fluid-particle simulation using translating eulerian grids. In Proc. ACM SIGGRAPH symposium on Interactive 3D Graphics and Games, 15--22.
14. Crane, K., Llamas, I., and Tariq, S. 2007. Real-time simulation and rendering of 3d fluids. In GPU Gems 3, H. Nguyen, Ed. Addison Wesley Professional, August, ch. 30.
15. Enright, D., and Fedkiw, R. 2002. Robust treatment of interfaces for fluid flows and computer graphics. In Computer Graphics, 9th Int. Conf. on Hyperbolic Problems Theory, Numerics, Applications.
16. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. In Proc. SIGGRAPH, 736--744.
17. 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 In Proc. 4th ASME-JSME Joint Fluids Eng. Conf., number FEDSM200345144. ASME, 2003--45144.
18. Feldman, B. E., O'Brien, J. F., and Klingner, B. M. 2005. Animating gases with hybrid meshes. In Proc. SIGGRAPH, 904--909.
19. Foster, N., and Fedkiw, R. 2001. Practical animation of liquids. In Proc. SIGGRAPH, 23--30.
20. Foster, N., and Metaxas, D. 1996. Realistic animation of liquids. Graph. Models Image Process. 58, 5, 471--483.
21. Guendelman, E., Selle, A., Losasso, F., and Fedkiw, R. 2005. Coupling water and smoke to thin deformable and rigid shells. In Proc. SIGGRAPH, 973--981.
22. Holmberg, N., and Wünsche, B. C. 2004. Efficient modeling and rendering of turbulent water over natural terrain. In Proc. GRAPHITE, 15--22.
23. Irving, G., Guendelman, E., Losasso, F., and Fedkiw, R. 2006. Efficient simulation of large bodies of water by coupling two- and three-dimensional techniques. In Proc. SIGGRAPH, 805--811.
24. Jeong, W.-K., Ross, and Whitaker, T. 2007. A fast eikonal equation solver for parallel systems. In SIAM conference on Computational Science and Engineering.
25. Kim, D., Song, O.-Y., and Ko, H.-S. 2008. A semi-lagrangian cip fluid solver without dimensional splitting. Computer Graphics Forum 27, 2 (April), 467--475.
26. Klingner, B. M., Feldman, B. E., Chentanez, N., and O'Brien, J. F. 2006. Fluid animation with dynamic meshes. In Proc. SIGGRAPH, 820--825.
27. Lentine, M., Zheng, W., and Fedkiw, R. 2010. A novel algorithm for incompressible flow using only a coarse grid projection. In Proc. SIGGRAPH, 114:1--114:9.
28. Long, B., and Reinhard, E. 2009. Real-time fluid simulation using discrete sine/cosine transforms. In Proc. ACM SIGGRAPH symposium on Interactive 3D Graphics and Games, 99--106.
29. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. In Proc. SIGGRAPH, 457--462.
30. Losasso, F., Talton, J., Kwatra, N., and Fedkiw, R. 2008. Two-way coupled sph and particle level set fluid simulation. IEEE Transactions on Visualization and Computer Graphics 14, 4, 797--804.
31. McAdams, A., Sifakis, E., and Teran, J. 2010. A parallel multigrid poisson solver for fluids simulation on large grids. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation.
32. Molemaker, J., Cohen, J. M., Patel, S., and Noh, J. 2008. Low viscosity flow simulations for animation. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 9--18.
33. Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 154--159.
34. Müller, M. 2009. Fast and robust tracking of fluid surfaces. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation.
35. Neyret, F. 2003. Advected textures. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 147--153.
36. Premoze, S., Tasdizen, T., Bigler, J., Lefohn, A. E., and Whitaker, R. T. 2003. Particle-based simulation of fluids. Comput. Graph. Forum 22, 3, 401--410.
37. Rasmussen, N., Enright, D., Nguyen, D., Marino, S., Sumner, N., Geiger, W., Hoon, S., and Fedkiw, R. 2004. Directable photorealistic liquids. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 193--202.
38. Robinson-Mosher, A., Shinar, T., Gretarsson, J., Su, J., and Fedkiw, R. 2008. Two-way coupling of fluids to rigid and deformable solids and shells. ACM Trans. Graph. 27 (August), 46:1--46:9.
39. Sanders, J., and Kandrot, E. 2010. CUDA by Example: An Introduction to General-Purpose GPU Programming. Addison-Wesley Professional.
40. Selle, A., Fedkiw, R., Kim, B., Liu, Y., and Rossignac, J. 2008. An unconditionally stable MacCormack method. J. Sci. Comput. 35, 2-3, 350--371.
41. Sin, F., Bargteil, A. W., and Hodgins, J. K. 2009. A point-based method for animating incompressible flow. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 247--255.
42. Solenthaler, B., and Pajarola, R. 2009. Predictive-corrective incompressible sph. In Proc. SIGGRAPH, 1--6.
43. Stam, J. 1999. Stable fluids. In Proc. SIGGRAPH, 121--128.
44. Takahashi, T., Ueki, H., Kunimatsu, A., and Fujii, H. 2002. The simulation of fluid-rigid body interaction. In ACM SIGGRAPH conference abstracts and applications, 266--266.
45. Thürey, N., and Rüde, U. 2004. Free Surface Lattice-Boltzmann fluid simulations with and without level sets. Proc. of Vision, Modelling, and Visualization VMV, 199--207.
46. Thürey, N., and Rüde, U. 2009. Stable free surface flows with the lattice Boltzmann method on adaptively coarsened grids. Computing and Visualization in Science 12 (5).
47. Thurey, N., Muller-Fischer, M., Schirm, S., and Gross, M. 2007. Real-time breakingwaves for shallow water simulations. In Proc. Pacific Conf. on CG and App., 39--46.
48. Štava, O., Beneš, B., Brisbin, M., and Křivánek, J. 2008. Interactive terrain modeling using hydraulic erosion. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 201--210.
49. Wojtan, C., Thürey, N., Gross, M., and Turk, G. 2010. Physics-inspired topology changes for thin fluid features. In Proc. SIGGRAPH, no. 4, 1--8.
50. Yu, J., and Turk, G. 2010. Enhancing fluid animation with adaptive, controllable and intermittent turbulence. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation.
51. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. In Proc. SIGGRAPH, 965--972.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

      • Physical simulation

    • Graphics systems and interfaces

      • Virtual reality

    • Shape modeling

• Mathematics of computing

  • Continuous mathematics

    • Topology

      • Geometric topology