Simulating water and smoke with an octree data structure

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ann S. Almgren , John B. Bell , Phillip Colella , Louis H. Howell , Michael L. Welcome, A conservative adaptive projection method for the variable density incompressible Navier-Stokes equations, Journal of Computational Physics, v.142 n.1, p.1-46, May 1, 1998 [doi>10.1006/jcph.1998.5890]
	2	M. J. Berger , P. Colella, Local adaptive mesh refinement for shock hydrodynamics, Journal of Computational Physics, v.82 n.1, p.64-84, May 1989 [doi>10.1016/0021-9991(89)90035-1]
	3	BERGER, M., AND OLIGER, J. 1984. Adaptive mesh refinement for hyperbolic partial differential equations. J. Comput. Phys. 53, 484--512.
	4	Mark Carlson , Peter J. Mucha , R. Brooks Van Horn, III , Greg Turk, Melting and flowing, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545289]
	5	Jim X. Chen , Niels da Vitoria Lobo, Toward interactive-rate simulation of fluids with moving obstacles using Navier-Stokes equations, Graphical Models and Image Processing, v.57 n.2, p.107-116, March 1995 [doi>10.1006/gmip.1995.1012]
	6	S. Chen , B. Merriman , S. Osher , P. Smereka, A simple level set method for solving Stefan problems, Journal of Computational Physics, v.135 n.1, p.8-29, July 15, 1997 [doi>10.1006/jcph.1997.5721]
	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).
	8	Douglas Enright , Ronald Fedkiw , Joel Ferziger , Ian Mitchell, A hybrid particle level set method for improved interface capturing, Journal of Computational Physics, v.183 n.1, p.83-116, November 20, 2002 [doi>10.1006/jcph.2002.7166]
	9	Douglas Enright , Stephen Marschner , Ronald Fedkiw, Animation and rendering of complex water surfaces, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	10	ENRIGHT, D., LOSASSO, F., AND FEDKIW, R. 2004. A fast and accurate semi-Lagrangian particle level set method. Computers and Structures, (in press).
	11	Ronald Fedkiw , Jos Stam , Henrik Wann Jensen, Visual simulation of smoke, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.15-22, August 2001 [doi>10.1145/383259.383260]
	12	Bryan E. Feldman , James F. O'Brien , Okan Arikan, Animating suspended particle explosions, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	13	Nick Foster , Ronald Fedkiw, Practical animation of liquids, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.23-30, August 2001 [doi>10.1145/383259.383261]
	14	Nick Foster , Dimitri Metaxas, Realistic animation of liquids, Graphical Models and Image Processing, v.58 n.5, p.471-483, Sept. 1996 [doi>10.1006/gmip.1996.0039]
	15	Nick Foster , Dimitris Metaxas, Controlling Fluid Animation, Proceedings of the 1997 Conference on Computer Graphics International, p.178, June 23-27, 1997
	16	Nick Foster , Dimitris Metaxas, Modeling the motion of a hot, turbulent gas, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.181-188, August 1997 [doi>10.1145/258734.258838]
	17	Sarah F. Frisken , Ronald N. Perry , Alyn P. Rockwood , Thouis R. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.249-254, July 2000 [doi>10.1145/344779.344899]
	18	Frederic Gibou , Ronald P. Fedkiw , Li-Tien Cheng , Myungjoo Kang, A second-order-accurate symmetric discretization of the Poisson equation on irregular domains, Journal of Computational Physics, v.176 n.1, p.205-227, February 10, 2002 [doi>10.1006/jcph.2001.6977]
	19	F. E. Ham , F. S. Lien , A. B. Strong, A fully conservative second-order finite difference scheme for incompressible flow on nonuniform grids, Journal of Computational Physics, v.177 n.1, p.117-133, March 20, 2002 [doi>10.1006/jcph.2002.7006]
	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.
	21	HONG, J.-M., AND KIM, C.-H. 2003. Animation of bubbles in liquid. Comp. Graph. Forum (Eurographics Proc.) 22, 3, 253--262.
	22	Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	23	Michael Kass , Gavin Miller, Rapid, stable fluid dynamics for computer graphics, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.49-57, September 1990, Dallas, TX, USA
	24	Arnauld Lamorlette , Nick Foster, Structural modeling of flames for a production environment, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	25	Haeyoung Lee , Mathieu Desbrun , Peter Schröder, Progressive encoding of complex isosurfaces, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	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.
	27	Matthias Müller , David Charypar , Markus Gross, Particle-based fluid simulation for interactive applications, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
	28	Duc Quang Nguyen , Ronald Fedkiw , Henrik Wann Jensen, Physically based modeling and animation of fire, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	29	Yutaka Ohtake , Alexander Belyaev , Marc Alexa , Greg Turk , Hans-Peter Seidel, Multi-level partition of unity implicits, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	30	Ronald N. Perry , Sarah F. Frisken, Kizamu: a system for sculpting digital characters, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.47-56, August 2001 [doi>10.1145/383259.383264]
	31	Stéphane Popinet, Gerris: a tree-based adaptive solver for the incompressible Euler equations in complex geometries, Journal of Computational Physics, v.190 n.2, p.572-600, 20 September 2003 [doi>10.1016/S0021-9991(03)00298-5]
	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.
	33	Nick Rasmussen , Duc Quang Nguyen , Willi Geiger , Ronald Fedkiw, Smoke simulation for large scale phenomena, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	34	Olivier Roussel , Kai Schneider , Alexei Tsigulin , Henning Bockhorn, A conservative fully adaptive multiresolution algorithm for parabolic PDEs, Journal of Computational Physics, v.188 n.2, p.493-523, 1 July 2003 [doi>10.1016/S0021-9991(03)00189-X]
	35	Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
	36	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	37	SETHIAN, J. 1996. A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. 93, 1591--1595.
	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.
	39	Jos Stam, Stable fluids, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.121-128, July 1999 [doi>10.1145/311535.311548]
	40	Jos Stam, Flows on surfaces of arbitrary topology, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	41	John Strain, Fast tree-based redistancing for level set computations, Journal of Computational Physics, v.152 n.2, p.664-686, July 1, 1999 [doi>10.1006/jcph.1999.6259]
	42	John Strain, Tree methods for moving interfaces, Journal of Computational Physics, v.151 n.2, p.616-648, May 20, 1999 [doi>10.1006/jcph.1999.6205]
	43	John Strain, A fast modular semi-Lagrangian method for moving interfaces, Journal of Computational Physics, v.161 n.2, p.512-536, July 1, 2000 [doi>10.1006/jcph.2000.6508]
	44	Mark Sussman , Ann S. Almgren , John B. Bell , Phillip Colella , Louis H. Howell , Michael L. Welcome, An adaptive level set approach for incompressible two-phase flows, Journal of Computational Physics, v.148 n.1, p.81-124, Jan. 1, 1999 [doi>10.1006/jcph.1998.6106]
	45	Mark Sussman, A second order coupled level set and volume-of-fluid method for computing growth and collapse of vapor bubbles, Journal of Computational Physics, v.187 n.1, p.110-136, May 2003 [doi>10.1016/S0021-9991(03)00087-1]
	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.
	47	Adrien Treuille , Antoine McNamara , Zoran Popović , Jos Stam, Keyframe control of smoke simulations, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
	48	TSITSIKLIS, J. 1995. Efficient algorithms for globally optimal trajectories. IEEE Trans. on Automatic Control 40, 1528--1538.
	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.
	50	Gary D. Yngve , James F. O'Brien , Jessica K. Hodgins, Animating explosions, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.29-36, July 2000 [doi>10.1145/344779.344801]

Peer to Peer - Readers of this Article have also read:

Evaluating topic-driven web crawlers Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval
Filippo Menczer , Gautam Pant , Padmini Srinivasan , Miguel E. Ruiz
Partitioning-based standard-cell global placement with an exact objective Proceedings of the 1997 international symposium on Physical design
Dennis J.-H. Huang , Andrew B. Kahng
Information systems strategy and implementation: a case study of a building society ACM Transactions on Information Systems (TOIS) 12, 2
G. Walsham , T. Waema

Fedkiw and Muller-Fischer presenation videos are available from the citation page