Abstract
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.
Supplemental Material
Available for Download
- 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
- BERGER, M., AND COLELLA, P. 1989. Local adaptive mesh refinement for shock hydrodynamics. J. Comput. Phys. 82, 64--84. Google ScholarDigital Library
- BERGER, M., AND OLIGER, J. 1984. Adaptive mesh refinement for hyperbolic partial differential equations. J. Comput. Phys. 53, 484--512.Google ScholarCross Ref
- 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
- 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
- CHEN, S., MERRIMAN, B., OSHER, S., AND SMEREKA, P. 1997. A simple level set method for solving stefan problems. 8--29. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- FEDKIW, R., STAM, J., AND JENSEN, H. 2001. Visual simulation of smoke. In Proc. of ACM SIGGRAPH 2001, 15--22. Google ScholarDigital Library
- 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
- FOSTER, N., AND FEDKIW, R. 2001. Practical animation of liquids. In Proc. of ACM SIGGRAPH 2001, 23--30. Google ScholarDigital Library
- FOSTER, N., AND METAXAS, D. 1996. Realistic animation of liquids. Graph. Models and Image Processing 58, 471--483. Google ScholarDigital Library
- FOSTER, N., AND METAXAS, D. 1997. Controlling fluid animation. In Computer Graphics International 1997, 178--188. Google ScholarDigital Library
- FOSTER, N., AND METAXAS, D. 1997. Modeling the motion of a hot, turbulent gas. In Proc. of SIGGRAPH 97, 181--188. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- LAMORLETTE, A., AND FOSTER, N. 2002. Structural modeling of natural flames. ACM Trans. Graph. (SIGGRAPH Proc.) 21, 3, 729--735. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- PERRY, R., AND FRISKEN, S. 2001. Kizamu: a system for sculpting digital characters. In Proc. SIGGRAPH 2001, vol. 20, 47--56. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- SAAD, Y. 1996. Iterative methods for sparse linear systems. PWS Publishing. New York, NY. Google ScholarDigital Library
- SAMET, H. 1989. The Design and Analysis of Spatial Data Structures. Addison-Wesley, New York. Google ScholarDigital Library
- SETHIAN, J. 1996. A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. 93, 1591--1595.Google ScholarCross Ref
- 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
- STAM, J. 1999. Stable fluids. In Proc. of SIGGRAPH 99, 121--128. Google ScholarDigital Library
- STAM, J. 2003. Flows on surfaces of arbitrary topology. ACM Trans. Graph. (SIGGRAPH Proc.) 22, 724--731. Google ScholarDigital Library
- STRAIN, J. 1999. Fast tree-based redistancing for level set computations. J. Comput. Phys. 152, 664--686. Google ScholarDigital Library
- STRAIN, J. 1999. Tree methods for moving interfaces. J. Comput. Phys. 151, 616--648. Google ScholarDigital Library
- STRAIN, J. 2000. A fast modular semi-lagrangian method for moving interfaces. J. Comput. Phys. 161, 512--536. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- TSITSIKLIS, J. 1995. Efficient algorithms for globally optimal trajectories. IEEE Trans. on Automatic Control 40, 1528--1538.Google ScholarCross Ref
- 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
- YNGVE, G., O'BRIEN, J., AND HODGINS, J. 2000. Animating explosions. In Proc. SIGGRAPH 2000, vol. 19, 29--36. Google ScholarDigital Library
Index Terms
- Simulating water and smoke with an octree data structure
Recommendations
Simulating water and smoke with an octree data structure
SIGGRAPH '04: ACM SIGGRAPH 2004 PapersWe 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 ...
Automatic off-body overset adaptive Cartesian mesh method based on an octree approach
This paper describes a method for generating adaptive structured Cartesian grids within a near-body/off-body mesh partitioning framework for the flow simulation around complex geometries. The off-body Cartesian mesh generation derives from an octree ...
A vortex particle method for smoke, water and explosions
SIGGRAPH '05: ACM SIGGRAPH 2005 PapersVorticity confinement reintroduces the small scale detail lost when using efficient semi-Lagrangian schemes for simulating smoke and fire. However, it only amplifies the existing vorticity, and thus can be insufficient for highly turbulent effects such ...
Comments