Real-time fluid simulation using discrete sine/cosine transforms

ABSTRACT

Recent advances in fluid simulations have yielded exceptionally realistic imagery. However, most algorithms have computational requirements that are prohibitive for real-time simulations. Using Fourier based solutions mitigates this issue, although due to wraparound, boundary conditions are not naturally available, leading to inconsistencies near the boundary. We show that slip boundary conditions can be imposed by solving the mass conservation step using cosine and sine transforms instead of the Fourier transform. Further, we show that measures against density dissipation can be computed using cosine transforms and we describe a new method to compute surface tension in the same domain. This combination of related algorithms leads to real-time simulations with boundary conditions.

References

1. Anderson, J. D. 1995. Computational fluid dynamics: The basics with applications. McGraw-Hill, New York, NY.
2. Batty, C., Bertails, F., and Bridson, R. 2007. A fast variational framework for accurate solid-fluid coupling. ACM Transactions on Graphics 26, 3, 100.
3. Bessonov, O., Brailovskaya, V., Polezhaev, V., and Roux, B. 1995. Parallelization of the solution of 3d navier-stokes equations for fluid flow in a cavity with moving covers. In PaCT '95: Proc. of the 3rd International Conference on Parallel Computing Technologies, 385--399.
4. Boyd, J. 1999. Chebyshev and Fourier spectral methods, 2rd ed. Dover Publications, Mineola, NY.
5. Carlson, M., Mucha, P. J., and Turk, G. 2004. Rigid fluid: Animating the interplay between rigid bodies and fluid. ACM Transactions on Graphics 23, 3, 377--384.
6. Denis, B., Côté, J., and Laprise, R. 2001. Spectral decomposition of two-dimensional atmospheric fields on limited-area domains using the discrete cosine transform (DCT). Monthly Weather Review 130, 1812--1829.
7. Dupont, T. F., and Liu, Y. 2003. Back and forth error compensation and correction methods for removing errors introduced by uneven gradients of the level set function. Journal of Computational Physics 190, 1, 311--324.
8. Durand, F., and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. ACM Transactions on Graphics 23, 3, 257--266.
9. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Transactions on Graphics 21, 3, 736--744.
10. Fattal, R., and Lischinski, D. 2004. Target-driven smoke animation. ACM Transactions on Graphics 23, 3, 441--448.
11. Fedkiw, R., Aslam, T., Merriman, B., and Osher, S. 1999. A non-oscillatory Eulerian approach to interfaces in multimaterial flows (the ghost fluid method). Journal of Computational Physics 152, 457--492.
12. Fedkiw, R., Stam, J., and Jensen, H. 2001. Visual simulation of smoke. In Proceedings of ACM SIGGRAPH '01, 15--22.
13. Feldman, B. E., O'Brien, J. F., and Klingner, B. M. 2005. Animating gases with hybrid meshes. ACM Transactions on Graphics 24, 3, 904--909.
14. Foster, N., and Fedkiw, R. 2001. Practical animation of liquids. In Proceedings of ACM SIGGRAPH 2001, 23--30.
15. Foster, N., and Metaxas, D. 1997. Modeling the motion of a hot, turbulent gas. In Proceedings of SIGGRAPH '97, 181--188.
16. Frigo, M., and Johnson, S. G. 2005. The design and implementation of FFTW3. Proceedings of the IEEE 93, 2, 216--231.
17. Frigo, M. 1999. A fast fourier transform compiler. In ACM SIGPLAN'99 Conference on Programming Language Design and Implementation (PLDI), 169--180.
18. Géneveaux, O., Habibi, A., and Dischler, J.-M. 2003. Simulating fluid-solid interaction. In Graphics Interface, 31--38.
19. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Non-convex rigid bodies with stacking. ACM Transactions on Graphics 22, 3, 871--878.
20. Guermond, J.-L., and Quartapelle, L. 2000. A projection FEM for variable density incompressible flows. J. Comput. Phys. 165, 1, 167--188.
21. Hockney, R. W. 1965. A fast direct solution of poisson's equation using fourier analysis. J. ACM 12, 1, 95--113.
22. Ihrke, I., Ziegler, G., Tevs, A., Theobalt, C., Magnor, M., and Seidel, H.-P. 2007. Eikonal rendering: Efficient light transport in refractive optics. ACM Transactions on Graphics 26, 3, 59.
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. ACM Transactions on Graphics 25, 3, 805--811.
24. Kayija, J. T., and von Herzen, B. 1984. Ray tracing volume densities. Proc. of ACM SIGGRAPH 1984 18, 3, 165--174.
25. Kim, B. M., Liu, Y., Llamas, I., and Rosignac, J. 2005. Flowfixer: Using BFECC for fluid simulation. In Eurographics Workshop on Natural Phenomena, 51--56.
26. Klingner, B. M., Feldman, B. E., Chentanez, N., and O'Brien, J. F. 2006. Fluid animation with dynamic meshes. ACM Transactions on Graphics 25, 3, 820--825.
27. Lamorlette, A., and Foster, N. 2002. Structural modeling of natural flames. ACM Transactions on Graphics 21, 3, 729--735.
28. Losasso, F., Shinar, T., and Selle, A. 2006. Multiple interacting fluids. ACM Transactions on Graphics 25, 3, 812--819.
29. Makhoul, J. 1980. A fast cosine transform in one and two dimensions. IEEE Transactions on Acoustics, Speech, and Signal Processing ASSP-28, 1, 27--34.
30. Martucci, S. A. 1994. Symmetric convolution and the discrete sine and cosine transforms. IEEE Transactions on Signal Processing 42, 5, 1038--1051.
31. Nguyen, D., Fedkiw, R., and Jensen, H. 2002. Physically-based modeling and animation of fire. ACM Transactions on Graphics 29, 3, 721--728.
32. Reeves, R., and Kubik, K. 2006. Shift, scaling and derivative properties of the discrete cosine transform. Signal Processing 86, 1597--1603.
33. Selle, A., Rasmussen, N., and Fedkiw, R. 2005. A vortex particle method for smoke, water and explosions. ACM Transactions on Graphics 24, 3, 910--914.
34. Selle, A., Fedkiw, R., Kim, B. M., Liu, Y., and Rossignac, J. 2007. An unconditionally stable MacCormack method. Journal of Scientific Computing, in review.
35. Shao, X., and Johnson, S. G. 2008. Type-II/III DCT/DST algorithms with reduced number of arithmetic operations. Signal Processing 88, 6, 1553--1564.
36. Stam, J. 1999. Stable fluids. In Proceedings of ACM SIGGRAPH, 121--128.
37. Stam, J. 2001. A simple fluid solver based on the FFT. Journal of Graphics Tools 6, 2, 43--52.
38. Stavroudis, O. N. 1972. The Optics of Rays, Wavefronts and Caustics. Academic Press, New York.
39. Strang, G. 1988. Linear algebra and its applications, 3rd ed. Harcourt College Publishers, Fort Worth.
40. Strang, G. 1999. The discrete cosine transform. SIAM Review 41, 1, 135--147.
41. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. ACM Transactions on Graphics 25, 3, 826--834.
42. Yokokawa, M., Itakura, K., Uno, A., Ishihara, T., and Kaneda, Y. 2002. 16.4-Tflops direct numerical simulation of turbulence by a Fourier spectral method on the Earth Simulator. In Supercomputing '02: Proceedings of the 2002 ACM/IEEE Conf. on Supercomputing, 1--17.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

      • Physical simulation

    • Shape modeling

• Mathematics of computing

  • Continuous mathematics

    • Topology

      • Geometric topology