A novel algorithm for incompressible flow using only a coarse grid projection

Abstract

Large scale fluid simulation can be difficult using existing techniques due to the high computational cost of using large grids. We present a novel technique for simulating detailed fluids quickly. Our technique coarsens the Eulerian fluid grid during the pressure solve, allowing for a fast implicit update but still maintaining the resolution obtained with a large grid. This allows our simulations to run at a fraction of the cost of existing techniques while still providing the fine scale structure and details obtained with a full projection. Our algorithm scales well to very large grids and large numbers of processors, allowing for high fidelity simulations that would otherwise be intractable.

References

1. Berger, M., and Oliger, J. 1984. Adaptive mesh refinement for hyperbolic partial differential equations. J. Comput. Phys. 53, 484--512.
2. Bolz, J., Farmer, I., Grinspun, E., and Schroder, P. 2003. Sparse matrix solvers on the gpu: Conjugate gradients and multi-grid. ACM Trans. Graph. (SIGGRAPH Proc.) 22, 3, 917--924.
3. Bridson, R., Houriham, J., and Nordenstam, M. 2007. Curl-noise for procedural fluid flow. ACM Trans. Graph. 26, 3, 46.
4. 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 Wrkshp. on Anim. and Sim.), Springer-Verlag, R. Boulic and G. Hegron, Eds., 61--76.
5. Dupont, T., and Liu, Y. 2003. Back and forth error compensation and correction methods for removing errors induced by uneven gradients of the level set function. J. Comput. Phys. 190/1, 311--324.
6. Fedkiw, R., Stam, J., and Jensen, H. 2001. Visual simulation of smoke. In Proc. of ACM SIGGRAPH 2001, 15--22.
7. Foster, N., and Metaxas, D. 1997. Controlling fluid animation. In Comput. Graph. Int., 178--188.
8. Gao, Y., Li, C.-F., Hu, S.-M., and Barsky, B. A. 2009. Simulating gaseous fluids with low and high speeds. Comput. Graph. Forum 28, 7, 1845--1852.
9. Horvath, C., and Geiger, W. 2009. Directable, high-resolution simulation of fire on the gpu. ACM Trans. Graph. 28, 3, 1--8.
10. Kim, B.-M., Liu, Y., Llamas, I., and Rossignac, J. 2005. Using BFECC for fluid simulation. In Eurographics Workshop on Natural Phenomena 2005.
11. Kim, T., Thürey, N., James, D., and Gross, M. 2008. Wavelet turbulence for fluid simulation. In SIGGRAPH '08: ACM SIGGRAPH 2008 papers, 1--6.
12. Kim, D., Song, O.-Y., and Ko, H.-S. 2009. Stretching and wiggling liquids. In SIGGRAPH Asia '09: ACM SIGGRAPH Asia 2009 papers, ACM, New York, NY, USA, 1--7.
13. Lamorlette, A., and Foster, N. 2002. Structural modeling of flames for a production environment. ACM Trans. Graph. (SIGGRAPH Proc.) 21, 3, 729--735.
14. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. (SIGGRAPH Proc.) 23, 457--462.
15. Losasso, F., Fedkiw, R., and Osher, S. 2006. Spatially adaptive techniques for level set methods and incompressible flow. Computers and Fluids 35, 995--1010.
16. Losasso, F., Talton, J., Kwatra, N., and Fedkiw, R. 2008. Two-way coupled sph and particle level set fluid simulation. IEEE Trans. on Vis. and Comput. Graph. 14, 4, 797--804.
17. Molemaker, J., Cohen, J., Patel, S., and Noh, J. 2008. Low viscosity flow simulations for animation. In SCA '08: Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, 9--18.
18. Mullen, P., Crane, K., Pavlov, D., Tong, Y., and Desbrun, M. 2009. Energy-preserving integrators for fluid animation. In SIGGRAPH '09: ACM SIGGRAPH 2009 papers, 1--8.
19. Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. In Proc. of the 2003 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim., 154--159.
20. Narain, R., Sewall, J., Carlson, M., and Lin, M. C. 2008. Fast animation of turbulence using energy transport and procedural synthesis. In SIGGRAPH Asia '08: ACM SIGGRAPH Asia 2008 papers, ACM, New York, NY, USA, 1--8.
21. Nielsen, M. B., Christensen, B. B., Zafar, N. B., Roble, D., and Museth, K. 2009. Guiding of smoke animations through variational coupling of simulations at different resolutions. In SCA '09: Proc. of the 2009 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim., 217--226.
22. Pfaff, T., Thuerey, N., Selle, A., and Gross, M. 2009. Synthetic turbulence using artificial boundary layers. In SIGGRAPH Asia '09: ACM SIGGRAPH Asia 2009 papers, 1--10.
23. Rasmussen, N., Nguyen, D., Geiger, W., and Fedkiw, R. 2003. Smoke simulation for large scale phenomena. ACM Trans. Graph. (SIGGRAPH Proc.) 22, 703--707.
24. Reeves, W. 1983. Particle systems - a technique for modeling a class of fuzzy objects. In Comput. Graph. (Proc. of SIGGRAPH 83), vol. 17, 359--376.
25. Schechter, H., and Bridson, R. 2008. Evolving sub-grid turbulence for smoke animation. In SCA '08: Proc. of the 2008 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim., 1--7.
26. Selle, A., Rasmussen, N., and Fedkiw, R. 2005. A vortex particle method for smoke, water and explosions. ACM Trans. Graph. (SIGGRAPH Proc.) 24, 3, 910--914.
27. Selle, A., Fedkiw, R., Kim, B., Liu, Y., and Rossignac, J. 2008. An unconditionally stable MacCormack method. Journal of Scientific Computing 35, 2, 350--371.
28. Stam, J., and Fiume, E. 1993. Turbulent wind fields for gaseous phenomena. In Proc. of SIGGRAPH 1993, 369--376.
29. Stam, J. 1999. Stable fluids. In Proc. of SIGGRAPH 99, 121--128.
30. Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. In SIGGRAPH '09: ACM SIGGRAPH 2009 papers, ACM, New York, NY, USA, 1--8.
31. Yoon, J.-C., Kam, H. R., Hong, J.-M., Kang, S.-J., and Kim, C.-H. 2009. Procedural synthesis using vortex particle method for fluid simulation. Comput. Graph. Forum 28, 7, 1853--1859.
32. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. (SIGGRAPH Proc.) 24, 3, 965--972.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

      • Physical simulation

    • Shape modeling

• Mathematics of computing

  • Continuous mathematics

    • Topology

      • Geometric topology