“A novel algorithm for incompressible flow using only a coarse grid projection” by Lentine, Zheng and Fedkiw

  • ©Michael Lentine, Wen Zheng, and Ronald Fedkiw




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



    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.


    1. Berger, M., and Oliger, J. 1984. Adaptive mesh refinement for hyperbolic partial differential equations. J. Comput. Phys. 53, 484–512.Google ScholarCross Ref
    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. Google ScholarDigital Library
    3. Bridson, R., Houriham, J., and Nordenstam, M. 2007. Curl-noise for procedural fluid flow. ACM Trans. Graph. 26, 3, 46. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    6. Fedkiw, R., Stam, J., and Jensen, H. 2001. Visual simulation of smoke. In Proc. of ACM SIGGRAPH 2001, 15–22. Google ScholarDigital Library
    7. Foster, N., and Metaxas, D. 1997. Controlling fluid animation. In Comput. Graph. Int., 178–188. Google ScholarDigital Library
    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.Google ScholarCross Ref
    9. Horvath, C., and Geiger, W. 2009. Directable, high-resolution simulation of fire on the gpu. ACM Trans. Graph. 28, 3, 1–8. Google ScholarDigital Library
    10. Kim, B.-M., Liu, Y., Llamas, I., and Rossignac, J. 2005. Using BFECC for fluid simulation. In Eurographics Workshop on Natural Phenomena 2005. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    13. Lamorlette, A., and Foster, N. 2002. Structural modeling of flames for a production environment. ACM Trans. Graph. (SIGGRAPH Proc.) 21, 3, 729–735. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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.Google ScholarCross Ref
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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. Google ScholarDigital Library
    28. Stam, J., and Fiume, E. 1993. Turbulent wind fields for gaseous phenomena. In Proc. of SIGGRAPH 1993, 369–376. Google ScholarDigital Library
    29. Stam, J. 1999. Stable fluids. In Proc. of SIGGRAPH 99, 121–128. Google ScholarDigital Library
    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. Google ScholarDigital Library
    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.Google ScholarCross Ref
    32. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. (SIGGRAPH Proc.) 24, 3, 965–972. Google ScholarDigital Library

ACM Digital Library Publication: