“Simulating water and smoke with an octree data structure” by Losasso, Gibou and Fedkiw

We present a method for simulating water and smoke on an unrestricted octree data structure exploiting mesh refinement techniques to capture the small scale visual detail. We propose a new technique for discretizing the Poisson equation on this octree grid. The resulting linear system is symmetric positive definite enabling the use of fast solution methods such as preconditioned conjugate gradients, whereas the standard approximation to the Poisson equation on an octree grid results in a non-symmetric linear system which is more computationally challenging to invert. The semi-Lagrangian characteristic tracing technique is used to advect the velocity, smoke density, and even the level set making implementation on an octree straightforward. In the case of smoke, we have multiple refinement criteria including object boundaries, optical depth, and vorticity concentration. In the case of water, we refine near the interface as determined by the zero isocontour of the level set function.

1. ALMGREN, A., BELL, J., COLELLA, P., HOWELL, L., AND WELCOME, M. 1998. A conservative adaptive projection method for the variable density incompressible navier-stokes equations. J. Comput. Phys. 142, 1–46. Google ScholarDigital Library
2. BERGER, M., AND COLELLA, P. 1989. Local adaptive mesh refinement for shock hydrodynamics. J. Comput. Phys. 82, 64–84. Google ScholarDigital Library
3. BERGER, M., AND OLIGER, J. 1984. Adaptive mesh refinement for hyperbolic partial differential equations. J. Comput. Phys. 53, 484–512.Google ScholarCross Ref
4. CARLSON, M., MUCHA, P., VAN HORN III, R., AND TURK, G. 2002. Melting and flowing. In ACM SIGGRAPH Symposium on Computer Animation, 167–174. Google ScholarDigital Library
5. CHEN, J., AND LOBO, N. 1994. Toward interactive-rate simulation of fluids with moving obstacles using the navier-stokes equations. Computer Graphics and Image Processing 57, 107–116. Google ScholarDigital Library
6. CHEN, S., MERRIMAN, B., OSHER, S., AND SMEREKA, P. 1997. A simple level set method for solving stefan problems. 8–29. Google ScholarDigital Library
7. DAY, M., COLELLA, P., LIJEWSKI, M., RENDLEMAN, C., AND MARCUS, D. 1998. Embedded boundary algorithms for solving the poisson equation on complex domains. Tech. rep., Lawrence Berkeley National Laboratory (LBNL-41811).Google Scholar
8. ENRIGHT, D., FEDKIW, R., FERZIGER, J., AND MITCHELL, I. 2002. A hybrid particle level set method for improved interface capturing. J. Comp. Phys. 183, 83–116. Google ScholarDigital Library
9. ENRIGHT, D., MARSCHNER, S., AND FEDKIW, R. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. (SIGGRAPH Proc.) 21, 3, 736–744. Google ScholarDigital Library
10. ENRIGHT, D., LOSASSO, F., AND FEDKIW, R. 2004. A fast and accurate semi-Lagrangian particle level set method. Computers and Structures, (in press).Google Scholar
11. FEDKIW, R., STAM, J., AND JENSEN, H. 2001. Visual simulation of smoke. In Proc. of ACM SIGGRAPH 2001, 15–22. Google ScholarDigital Library
12. FELDMAN, B. E., O’BRIEN, J. F., AND ARIKAN, O. 2003. Animating suspended particle explosions. ACM Trans. Graph. (SIGGRAPH Proc.) 22, 3, 708–715. Google ScholarDigital Library
13. FOSTER, N., AND FEDKIW, R. 2001. Practical animation of liquids. In Proc. of ACM SIGGRAPH 2001, 23–30. Google ScholarDigital Library
14. FOSTER, N., AND METAXAS, D. 1996. Realistic animation of liquids. Graph. Models and Image Processing 58, 471–483. Google ScholarDigital Library
15. FOSTER, N., AND METAXAS, D. 1997. Controlling fluid animation. In Computer Graphics International 1997, 178–188. Google ScholarDigital Library
16. FOSTER, N., AND METAXAS, D. 1997. Modeling the motion of a hot, turbulent gas. In Proc. of SIGGRAPH 97, 181–188. Google ScholarDigital Library
17. FRISKEN, S., PERRY, R., ROCKWOOD, A., AND JONES, T. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proc. SIGGRAPH 2000, 249–254. Google ScholarDigital Library
18. GIBOU, F., FEDKIW, R., CHENG, L.-T., AND KANG, M. 2002. A second–order–accurate symmetric discretization of the poisson equation on irregular domains. 205–227. Google ScholarDigital Library
19. HAM, F., LIEN, F., AND STRONG, A. 2002. A fully conservative secondorder finite difference scheme for incompressible flow on nonuniform grids. J. Comput. Phys. 117, 117–133. Google ScholarDigital Library
20. HARLOW, F., AND WELCH, J. 1965. Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface. Phys. Fluids 8, 2182–2189.Google ScholarCross Ref
21. HONG, J.-M., AND KIM, C.-H. 2003. Animation of bubbles in liquid. Comp. Graph. Forum (Eurographics Proc.) 22, 3, 253–262.Google ScholarCross Ref
22. JU, T., LOSASSO, F., SCHAEFER, S., AND WARREN, J. 2002. Dual contouring of Hermite data. ACM Trans. Graph. (SIGGRAPH Proc.) 21, 3, 339–346. Google ScholarDigital Library
23. KASS, M., AND MILLER, G. 1990. Rapid, stable fluid dynamics for computer graphics. In Computer Graphics (Proc. of SIGGRAPH 90), vol. 24, 49–57. Google ScholarDigital Library
24. LAMORLETTE, A., AND FOSTER, N. 2002. Structural modeling of natural flames. ACM Trans. Graph. (SIGGRAPH Proc.) 21, 3, 729–735. Google ScholarDigital Library
25. LEE, H., DESBRUN, M., AND SCHRODER, P. 2003. Progressive encoding of complex isosurfaces. ACM Trans. Graph. (SIGGRAPH Proc.) 22, 3, 471–476. Google ScholarDigital Library
26. MIYAZAKI, R., DOBASHI, Y., AND NISHITA, T. 2002. Simulation of cumuliform clouds based on computational fluid dynamics. Proc. Eurographics 2002 Short Presentation, 405–410.Google Scholar
27. MÜLLER, M., CHARYPAR, D., AND GROSS, M. 2003. Particle-based fluid simulation for interactive applications. In Proc. of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 154–159. Google ScholarDigital Library
28. NGUYEN, D., FEDKIW, R., AND JENSEN, H. 2002. Physically based modeling and animation of fire. In ACM Trans. Graph. (SIGGRAPH Proc.), vol. 29, 721–728. Google ScholarDigital Library
29. OHTAKE, Y., BELYAEV, A., ALEXA, M., TURK, G., AND SEIDEL, H. 2003. Multi-Level Partition of Unity Implicits. ACM Trans. Graph. (SIGGRAPH Proc.) 22, 3, 463–470. Google ScholarDigital Library
30. PERRY, R., AND FRISKEN, S. 2001. Kizamu: a system for sculpting digital characters. In Proc. SIGGRAPH 2001, vol. 20, 47–56. Google ScholarDigital Library
31. POPINET, S. 2003. Gerris: A tree-based adaptive solver for the incompressible euler equations in complex geometries. J. Comp. Phys. 190, 572–600. Google ScholarDigital Library
32. PREMOZE, S., TASDIZEN, T., BIGLER, J., LEFOHN, A., AND WHITAKER, R. 2003. Particle-based simulation of fluids. In Comp. Graph. Forum (Eurographics Proc.), vol. 22, 401–410.Google ScholarCross Ref
33. 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
34. ROUSSEL, O., SCHNEIDER, K., TSIGULIN, A., AND BOCKHORN, H. 2003. A conservative fully adaptive multiresolution algorithm for parabolic pdes. J. Comput. Phys. 188, 493–523. Google ScholarDigital Library
35. SAAD, Y. 1996. Iterative methods for sparse linear systems. PWS Publishing. New York, NY. Google ScholarDigital Library
36. SAMET, H. 1989. The Design and Analysis of Spatial Data Structures. Addison-Wesley, New York. Google ScholarDigital Library
37. SETHIAN, J. 1996. A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. 93, 1591–1595.Google ScholarCross Ref
38. SOCHNIKOV, V., AND EFRIMA, S. 2003. Level set calculations of the evolution of boundaries on a dynamically adaptive grid. Int. J. Num. Methods in Eng. 56, 1913–1929.Google ScholarCross Ref
39. STAM, J. 1999. Stable fluids. In Proc. of SIGGRAPH 99, 121–128. Google ScholarDigital Library
40. STAM, J. 2003. Flows on surfaces of arbitrary topology. ACM Trans. Graph. (SIGGRAPH Proc.) 22, 724–731. Google ScholarDigital Library
41. STRAIN, J. 1999. Fast tree-based redistancing for level set computations. J. Comput. Phys. 152, 664–686. Google ScholarDigital Library
42. STRAIN, J. 1999. Tree methods for moving interfaces. J. Comput. Phys. 151, 616–648. Google ScholarDigital Library
43. STRAIN, J. 2000. A fast modular semi-lagrangian method for moving interfaces. J. Comput. Phys. 161, 512–536. Google ScholarDigital Library
44. SUSSMAN, M., ALMGREN, A., BELL, J., COLELLA, P., HOWELL, L., AND WELCOME, M. 1999. An adaptive level set approach for incompressible two-phase flows. J. Comput. Phys. 148, 81–124. Google ScholarDigital Library
45. SUSSMAN, M. 2003. A second order coupled level set and volume-of-fluid method for computing growth and collapse of vapor bubbles. J. Comp. Phys. 187, 110–136. Google ScholarDigital Library
46. TAKAHASHI, T., FUJII, H., KUNIMATSU, A., HIWADA, K., SAITO, T., TANAKA, K., AND UEKI, H. 2003. Realistic animation of fluid with splash and foam. Comp. Graph. Forum (Eurographics Proc.) 22, 3, 391–400.Google ScholarCross Ref
47. TREUILLE, A., MCNAMARA, A., POPOVIĆ, Z., AND STAM, J. 2003. Keyframe control of smoke simulations. ACM Trans. Graph. (SIGGRAPH Proc.) 22, 3, 716–723. Google ScholarDigital Library
48. TSITSIKLIS, J. 1995. Efficient algorithms for globally optimal trajectories. IEEE Trans. on Automatic Control 40, 1528–1538.Google ScholarCross Ref
49. WESTERMANN, R., KOBBELT, L., AND ERTL, T. 1999. Real-time exploration of regular volume data by adaptive reconstruction of isosurfaces. The Vis. Comput. 15, 2, 100–111.Google ScholarCross Ref
50. YNGVE, G., O’BRIEN, J., AND HODGINS, J. 2000. Animating explosions. In Proc. SIGGRAPH 2000, vol. 19, 29–36. Google ScholarDigital Library