Liquid simulation on lattice-based tetrahedral meshes

ABSTRACT

We describe a method for animating incompressible liquids with detailed free surfaces. For each time step, semi-Lagrangian contouring computes a new fluid boundary (represented as a fine surface triangulation) from the previous time step's fluid boundary and velocity field. Then a mesh generation algorithm called isosurface stuffing discretizes the region enclosed by the new fluid boundary, creating a tetrahedral mesh that grades from a fine resolution at the surface to a coarser resolution in the interior. The mesh has a structure, based on the body centered cubic lattice, that accommodates graded tetrahedron sizes but is regular enough to aid efficient point location and to save memory used to store geometric properties of identical tetrahedra. Although the mesh is warped to conform to the liquid boundary, it has a mathematical guarantee on tetrahedron quality, and is generated very rapidly. Each successive time step entails creating a new triangulated liquid surface and a new tetrahedral mesh. Semi-Lagrangian advection computes velocities at the current time step on the new mesh. We use a finite volume discretization to perform pressure projection required to enforce the fluid's incompressibility, and we solve the linear system with algebraic multigrid. A novel thickening scheme prevents thin sheets and droplets of liquid from vanishing when their thicknesses drop below the mesh resolution. Examples demonstrate that the method captures complex liquid motions and fine details on the free surfaces without suffering from excessive volume loss or artificial damping.

REFERENCES

• 1: {BE92} Bern M., Eppstein D.: Mesh generation and optimal triangulation. In Computing in Euclidean Geometry, Du D.-Z., Hwang F., (Eds.), vol. 1 of Lecture Notes Series on Computing. World Scientific, Singapore, 1992, pp. 23--90.
• 2: Adam W. Bargteil , Tolga G. Goktekin , James F. O'brien , John A. Strain, A semi-Lagrangian contouring method for fluid simulation, ACM Transactions on Graphics (TOG), v.25 n.1, p.19-38, January 2006 [doi>10.1145/1122501.1122503]
• 3: {Blu67} Blum H.: A transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form (1967), 362--380.
• 4: Marie-Paule Cani-Gascuel , Mathieu Desbrun, Animation of Deformable Models Using Implicit Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.3 n.1, p.39-50, January 1997 [doi>10.1109/2945.582343]
• 5: Nuttapong Chentanez , Tolga G. Goktekin , Bryan E. Feldman , James F. O'Brien, Simultaneous coupling of fluids and deformable bodies, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 6: Mark Carlson , Peter J. Mucha , Greg Turk, Rigid fluid: animating the interplay between rigid bodies and fluid, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 7: Mathieu Desbrun , Marie-Paule Gascuel, Smoothed particles: a new paradigm for animating highly deformable bodies, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.61-76, December 1996, Poitiers, France
• 8: Douglas Enright , Stephen Marschner , Ronald Fedkiw, Animation and rendering of complex water surfaces, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 9: Sharif Elcott , Yiying Tong , Eva Kanso , Peter Schröder , Mathieu Desbrun, Stable, circulation-preserving, simplicial fluids, ACM Transactions on Graphics (TOG), v.26 n.1, p.4-es, January 2007 [doi>10.1145/1189762.1189766]
• 10: 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]
• 11: Mark Foskey , Ming C. Lin , Dinesh Manocha, Efficient computation of a simplified medial axis, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781623]
• 12: Nick Foster , Dimitri Metaxas, Realistic animation of liquids, Proceedings of the conference on Graphics interface '96, p.204-212, May 1996, Toronto, Ontario, Canada
• 13: Bryan E. Feldman , James F. O'Brien , Okan Arikan, Animating suspended particle explosions, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 14: Bryan E. Feldman , James F. O'Brien , Bryan M. Klingner, Animating gases with hybrid meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 15: Bryan E. Feldman , James F. O'Brien , Bryan M. Klingner , Tolga G. Goktekin, Fluids in deforming meshes, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073405]
• 16: 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]
• 17: Tolga G. Goktekin , Adam W. Bargteil , James F. O'Brien, A method for animating viscoelastic fluids, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 18: Eran Guendelman , Andrew Selle , Frank Losasso , Ronald Fedkiw, Coupling water and smoke to thin deformable and rigid shells, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 19: Janghee Kim , Deukhyun Cha , Byungjoon Chang , Bonki Koo , Insung Ihm, Practical animation of turbulent splashing water, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 20: Bryan M. Klingner , Bryan E. Feldman , Nuttapong Chentanez , James F. O'Brien, Fluid animation with dynamic meshes, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 21: Frank Losasso , Frédéric Gibou , Ron Fedkiw, Simulating water and smoke with an octree data structure, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 22: François Labelle , Jonathan Richard Shewchuk, Isosurface stuffing: fast tetrahedral meshes with good dihedral angles, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 23: Frank Losasso , Tamar Shinar , Andrew Selle , Ronald Fedkiw, Multiple interacting liquids, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 24: {McC87} McCormick S. F.: Multigrid Methods. Society for Industrial and Applied Mathematics, Philidelphia, 1987.
• 25: 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
• 26: M. Müller , R. Keiser , A. Nealen , M. Pauly , M. Gross , M. Alexa, Point based animation of elastic, plastic and melting objects, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028542]
• 27: 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
• 28: {Owe98} Owen S. J.: A survey of unstructured mesh generation technology. In 7th International Meshing Roundtable (July 1998), pp. 239--267.
• 29: {PTB*03} Premože S., Tasdizen T., Bigler J., Lefohn A., Whitaker R.: Particle-based simulation of fluids. Computer Graphics Forum 22, 3 (Sept. 2003), 401--410.
• 30: Andrew Selle , Nick Rasmussen , Ronald Fedkiw, A vortex particle method for smoke, water and explosions, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 31: 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]
• 32: John Strain, Semi-Lagrangian methods for level set equations, Journal of Computational Physics, v.151 n.2, p.498-533, May 20, 1999 [doi>10.1006/jcph.1999.6194]
• 33: {Str01} Strain J. A.: A fast semi-Lagrangian contouring method for moving interfaces. Journal of Computational Physics 169, 1 (May 2001), 1--22.
• 34: N. Thürey , R. Keiser , M. Pauly , U. Rüde, Detail-preserving fluid control, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 35: Adrien Treuille , Andrew Lewis , Zoran Popović, Model reduction for real-time fluids, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 36: Ulrich Trottenberg , Anton Schuller, Multigrid, Academic Press, Inc., Orlando, FL, 2000
• 37: {TPF89} Terzopoulos D., Platt J., Fleischer K.: Heating and melting deformable models (from goop to glop). In Graphics Interface 1989 (June 1989), pp. 219--226.
• 38: {WSHD04} Warren J., Schaefer S., Hirani A. N., Desbrun M.: Barycentric coordinates for convex sets. Advances in Computational and Applied Mathematics, 2004.
• 39: Yongning Zhu , Robert Bridson, Animating sand as a fluid, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 40: Wen Zheng , Jun-Hai Yong , Jean-Claude Paul, Simulation of bubbles, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation

Keywords:
computational fluid dynamics, natural phenomena, physically based animation, tetrahedral mesh