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

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