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

  • ©Frank Losasso, Frédéric Gibou, and Ronald Fedkiw




    Simulating water and smoke with an octree data structure



    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

ACM Digital Library Publication:

Overview Page: