“Modular bases for fluid dynamics” by Wicke, Stanton and Treuille

  • ©Martin Wicke, Matt Stanton, and Adrien Treuille




    Modular bases for fluid dynamics



    We present a new approach to fluid simulation that balances the speed of model reduction with the flexibility of grid-based methods. We construct a set of composable reduced models, or tiles, which capture spatially localized fluid behavior. We then precompute coupling terms so that these models can be rearranged at runtime. To enforce consistency between tiles, we introduce constraint reduction. This technique modifies a reduced model so that a given set of linear constraints can be fulfilled. Because dynamics and constraints can be solved entirely in the reduced space, our method is extremely fast and scales to large domains.


    1. Adams, B., Pauly, M., Keiser, R., and Guibas, L. J. 2007. Adaptively sampled particle fluids. In Proc. SIGGRAPH ’07. Google ScholarDigital Library
    2. Angelidis, A., and Neyret, F. 2005. Simulation of smoke based on vortex filament primitives. In Proc. SCA ’05. Google ScholarDigital Library
    3. Angelidis, A., Neyret, F., Singh, K., and Nowrouzezahrai, D. 2006. A controllable, fast and stable basis for vortex based smoke simulation. In Proc. SCA ’06. Google ScholarDigital Library
    4. Ausseur, J., Pinier, J., Glauser, M., and Higuchi, H. 2004. Predicting the Dynamics of the Flow over a NACA 4412 using POD. APS Meeting Abstracts, D8.Google Scholar
    5. Babuška, I. 1973. The finite element method with Lagrangian multipliers. Numer. Math. 20, 3.Google Scholar
    6. Barbič, J., and James, D. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. In Proc. SIGGRAPH ’05. Google ScholarDigital Library
    7. Barbič, J., and Popović, J. 2008. Real-time control of physically based simulations using gentle forces. ACM Transactions on Graphics 27, 5. Google ScholarDigital Library
    8. Bolz, J., Farmer, I., Grinspun, E., and Schröder, P. 2003. Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid. In Proc. SIGGRAPH ’03. Google ScholarDigital Library
    9. Borggaard, J., Gugercin, S., and Iliescu, T. 2006. A domain decomposition approach to POD. IEEE Conference on Decision and Control.Google Scholar
    10. Chenney, S. 2004. Flow tiles. In Proc. SCA ’04. Google ScholarDigital Library
    11. Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. In Proc. SIGGRAPH ’03. Google ScholarDigital Library
    12. Couplet, M., Basdevant, C., and Sagaut, P. 2005. Calibrated reduced-order POD-Galerkin system for fluid flow modelling. J. Comput. Phys. 207, 1. Google ScholarDigital Library
    13. Elcott, S., Tong, Y., Kanso, E., Schröder, P., and Desbrun, M. 2005. Stable, circulation-preserving, simplicial fluids. In Discrete Differential Geometry, Chapter 9 of Course Notes. ACM SIGGRAPH. Google ScholarDigital Library
    14. Farhat, C., Tezaur, R., and Toivanen, J. 2000. A domain decomposition method for discontinuous Galerkin discretizations of Helmholtz problems with plane waves and Lagrange multipliers. Int. J. Numer. Meth. Engng.Google Scholar
    15. Farhat, C., Harari, I., and Franca, L. P. 2001. The discontinuous enrichment method. Comput. Methods Appl. Mech. Engrg. 190.Google Scholar
    16. Farhat, C., Harari, I., and Hetmaniuk, U. 2003. A discontinuous Galerkin method with Lagrange multipliers for the solution of Helmholtz problems in the mid-frequency regime. Applied Mechanics and Engineering 192, 1389–1419.Google ScholarCross Ref
    17. Feldman, B. E., O’Brien, J. F., and Klingner, B. M. 2005. Animating gases with hybrid meshes. In Proc. SIGGRAPH ’05. Google ScholarDigital Library
    18. Foster, N., and Metaxas, D. 1996. Realistic animation of liquids. Graphical Models and Image Processing 58, 5. Google ScholarDigital Library
    19. Goodnight, N., Woolley, C., Luebke, D., and Humphreys, G. A. 2003. Multigrid solver for boundary value problems using programmable graphics hardware. In Proceeding of Graphics Hardware. Google ScholarDigital Library
    20. Harris, M. J., Coombe, G., Scheuermann, T., and Lastra, A. 2002. Physically-based visual simulation on graphics hardware. In Graphics Hardware 2002, 109–118. Google ScholarDigital Library
    21. Holmes, P., Lumley, J. L., and Berkooz, G. 1996. Turbulence, Coherent Structures, Dynamical Systems and Symmetry. Cambridge University Press.Google Scholar
    22. James, D. L., and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. In Proc. SIGGRAPH ’03. Google ScholarDigital Library
    23. Keiser, R., Adams, B., Gasser, D., Bazzi, P., Dutre, P., and Gross, M. 2005. A unified lagrangian approach to solidfluid animation. In Proceedings Symposium Point-Based Graphics. Google ScholarDigital Library
    24. Krüger, J., and Westermann, R. 2003. Linear algebra operators for GPU implementation of numerical algorithms. In Proc. SIGGRAPH ’03. Google ScholarDigital Library
    25. LeGresley, P. A., and Alonso, J. J. 2003. Dynamic domain decomposition and error correction for reduced order models. 41st AIAA Aerospace Sciences Meeting and Exhibit.Google Scholar
    26. Li, W., Wei, X., and Kaufman, A. 2003. Implementing lattice Boltzmann computation on graphics hardware. The Visual Computer 19, 7–8.Google ScholarDigital Library
    27. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. In Proc. SIGGRAPH ’04. Google ScholarDigital Library
    28. Lucia, D. J., and King, P. I. 2002. Domain decomposition for reduced-order modeling of a flow with moving shocks. AIAA Journal 40, 11, 2360–2362.Google ScholarCross Ref
    29. Lumley, J. L. 1970. Stochastic Tools in Turbulence, vol. 12 of Applied Mathematics and Mechanics. Academic Press.Google Scholar
    30. Marion, M., and Temam, R. 1989. Nonlinear Galerkin methods. SIAM J. Numer. Anal. 26, 5, 1139–1157. Google ScholarDigital Library
    31. Müller, M., Charypar, D., and Gross, M. 2003. Particle-Based Fluid Simulation for Interactive Applications. In Proc. SCA ’03. Google ScholarDigital Library
    32. Park, S. I., and Kim, M. J. 2005. Vortex fluid for gaseous phenomena. In Proc. SCA ’05. Google ScholarDigital Library
    33. Rowley, C., Williams, D., Colonius, T., Murray, R., and MacMartin, D. 2006. Linear models for control of cavity flow oscillations. J. Fluid Mech. 547, 317–330.Google ScholarCross Ref
    34. Selle, A., Rasmussen, N., and Fedkiw, R. 2005. A vortex particle method for smoke, water and explosions. In Proc. SIGGRAPH ’05. Google ScholarDigital Library
    35. Shewchuk, J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Tech. Rep. CS-94-125, Carnegie Mellon University, Pittsburgh, PA, USA. Google ScholarDigital Library
    36. Sirisup, S., and Karniadakis, G. E. 2004. A spectral viscosity method for correcting the long-term behavior of POD models. J. Comput. Phys. 194, 1, 92–116. Google ScholarDigital Library
    37. Sirovich, L. 1987. Turbulence and the dynamics of coherent structures. I – Coherent structures. II – Symmetries and transformations. III – Dynamics and scaling. Quarterly of Applied Mathematics 45 (Oct.), 561–571.Google ScholarCross Ref
    38. Sloan, P.-P., Kautz, J., and Snyder, J. 2002. Precomputed radiance transfer for real-time rendering in dynamic, lowfrequency lighting environments. In Proc. SIGGRAPH ’02. Google ScholarDigital Library
    39. Stam, J. 1999. Stable Fluids. In Computer Graphics (SIGGRAPH 99). Google ScholarDigital Library
    40. Tezaur, R., and Farhat, C. 2006. Three-dimensional discontinuous Galerkin elements with plane waves and Lagrange multipliers for the solution of mid-frequency Helmholtz problems. Int. J. Numer. Meth. Engng 66.Google Scholar
    41. Tezaur, R., Zhang, L., and Farhat, C. 2008. A discontinuous enrichment method for capturing evanescent waves in multiscale fluid and fluid/solid problems. Comput. Methods Appl. Mech. Engrg. 197.Google Scholar
    42. Toselli, A., and Widlund, O. 2005. Domain Decomposition Methods – Algorithms and Theory. Springer.Google Scholar
    43. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. In Proc. SIGGRAPH ’06. Google ScholarDigital Library
    44. Wu, E., Liu, Y., and Liu, X. 2005. An improved study of realtime fluid simulation on GPU. Computer Animation and Virtual Worlds 15, 3–4. Google ScholarDigital Library
    45. Zhang, L., Tezaur, R., and Farhat, C. 2006. The discontinuous enrichment method for elastic wave propagation in the medium-frequency regime. Internat. J. Numer. Methods Engrg. 66.Google Scholar
    46. Zhu, Y., and Bridson, R. 2005. Animating sand as a fluid. In Proc. SIGGRAPH ’05. Google ScholarDigital Library

ACM Digital Library Publication: