A semi-Lagrangian contouring method for fluid simulation

ABSTRACT

In this article, we present a semi-Lagrangian surface tracking method for use with fluid simulations. Our method maintains an explicit polygonal mesh that defines the surface, and an octree data structure that provides both a spatial index for the mesh and a means for efficiently approximating the signed distance to the surface. At each timestep, a new surface is constructed by extracting the zero set of an advected signed-distance function. Semi-Lagrangian backward path tracing is used to advect the signed-distance function. One of the primary advantages of this formulation is that it enables tracking of surface characteristics, such as color or texture coordinates, at negligible additional cost. We include several examples demonstrating that the method can be effectively used as part of a fluid simulation to animate complex and interesting fluid behaviors.

REFERENCES

• 1: Arikan, O. 2005. Pixie: Photorealistic renderer. Go online to http://www.cs.utexas.edu/~okan/Pixie/pixie.htm.
• 2: Bærentzen, J. A. and Aanæs, H. 2002. Computing discrete signed distance fields from triangle meshes. Tech. rep. Informatics and Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark.
• 3: Bærentzen, J. A. and Christensen, N. J. 2002. Interactive modelling of shapes using the level-set method. Int. J. Shape Model. 8, 2, 79--97.
• 4: Jules Bloomenthal, An implicit surface polygonizer, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 5: J. D. Boissonnat , S. Oudot, Provably good surface sampling and approximation, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 6: 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]
• 7: 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]
• 8: 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
• 9: Courant, R., Isaacson, E., and Rees, M. 1952. On the solution of nonlinear hyperbolic differential equations by finite differences. Comm. Pure Appl. Math 5, 243--249.
• 10: 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
• 11: Mathieu Desbrun , Marie-Paule Gascuel, Animating soft substances with implicit surfaces, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.287-290, September 1995 [doi>10.1145/218380.218456]
• 12: 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]
• 13: Enright, D., Losasso, F., and Fedkiw, R. 2005. A fast and accurate semi-Lagrangian particle level set method. Comput. Struct. 83, 479--490.
• 14: Douglas Enright , Stephen Marschner , Ronald Fedkiw, Animation and rendering of complex water surfaces, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 15: 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]
• 16: 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]
• 17: Nick Foster , Dimitri Metaxas, Realistic animation of liquids, Proceedings of the conference on Graphics interface '96, p.204-212, May 1996, Toronto, Ontario, Canada
• 18: 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]
• 19: Goktekin, T. G., Bargteil, A. W., and O'Brien, J. F. 2004. A method for animating viscoelastic fluids. In Proceedings of ACM SIGGRAPH 2004. 463--468.
• 20: Green, D. and Hatch, D. 1995. Fast polygon-cube intersection testing. In Graphics Gems V. Academic Press Professional, Inc., San Diego, CA, 375--379.
• 21: 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
• 22: Hilton, A., Stoddart, A. J., Illingworth, J., and Windeatt, T. 1996. Marching triangles: Range image fusion for complex object modelling. In Proceedings of the International Conference on Image Processing. 381--384.
• 23: Hirt, C. W. and Nichols, B. D. 1981. Volume of fluid (VOF) method for the dynamics of free boundaries. J. Computat. Phys. 39, 201--225.
• 24: Jeong-Mo Hong , Chang-Hun Kim, Discontinuous fluids, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 25: Ben Houston , Michael B. Nielsen , Christopher Batty , Ola Nilsson , Ken Museth, Hierarchical RLE level set: A compact and versatile deformable surface representation, ACM Transactions on Graphics (TOG), v.25 n.1, p.151-175, January 2006 [doi>10.1145/1122501.1122508]
• 26: Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 27: LeVeque, R. J. 1990. Numerical Methods for Conservation Laws. Birkhauser-Verlag, Basel, Switzerland.
• 28: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 29: Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. In Proceedings of ACM SIGGRAPH 2004. 457--462.
• 30: 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
• 31: 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]
• 32: Nielsen, M. B. and Museth, K. 2006. Dynamic Tubular Grid: An efficient data structure and algorithms for high resolution level sets. J. Sci. Comput. 26, 1, 1--39.
• 33: Osher, S. and Fedkiw, R. 2003. The Level Set Method and Dynamic Implicit Surfaces. Springer-Verlag, New York, NY.
• 34: Stanley Osher , James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, v.79 n.1, p.12-49, Nov. 1988 [doi>10.1016/0021-9991(88)90002-2]
• 35: Mark Pauly , Richard Keiser , Bart Adams , Philip Dutré , Markus Gross , Leonidas J. Guibas, Meshless animation of fracturing solids, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 36: Poston, T., Wong, T.-T., and Heng, P.-A. 1998. Multiresolution isosurface extraction with adaptive skeleton climbing. Comput. Graph. For. 17, 3 (Sept.), 137--148.
• 37: Premože, S., Tasdizen, T., Bigler, J., Lefohn, A., and Whitaker, R. 2003. Particle-based simulation of fluids. Comput. Graph. For. 22, 3 (Sept.), 401--410.
• 38: N. Rasmussen , D. Enright , D. Nguyen , S. Marino , N. Sumner , W. Geiger , S. Hoon , R. Fedkiw, Directable photorealistic liquids, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028549]
• 39: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 40: Philip J. Schneider , David Eberly, Geometric Tools for Computer Graphics, Elsevier Science Inc., New York, NY, 2002
• 41: Sethian, J. A. 1996. A fast marching level set method for monotonically advancing fronts. Proc. Nat. Acad. Sci. USA 93, 4 (Feb.), 1591--1595.
• 42: Sethian, J. A. 1999. Level Set Methods and Fast Marching Methods, 2nd ed. Cambridge Monograph on Applied and Computational Mathematics. Cambridge University Press, Cambridge, U.K.
• 43: Raj Shekhar , Elias Fayyad , Roni Yagel , J. Fredrick Cornhill, Octree-based decimation of marching cubes surfaces, Proceedings of the 7th conference on Visualization '96, p.335-ff., October 28-29, 1996, San Francisco, California, United States
• 44: Shu, R., Chen, Z., and Kankanhalli, M. S. 1995. Adaptive marching cubes. Vis. Comput. 11, 202--217.
• 45: 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]
• 46: Dan Stora , Pierre-Olivier Agliati , Marie-Paule Cani , Fabrice Neyret , Jean-Dominique Gascuel, Animating lava flows, Proceedings of the 1999 conference on Graphics interface '99, p.203-210, September 1999, Kingston, Ontario, Canada
• 47: 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]
• 48: 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]
• 49: 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]
• 50: 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]
• 51: Strain, J. A. 2001. A fast semi-Lagrangian contouring method for moving interfaces. J. Computat. Phys. 169, 1 (May), 1--22.
• 52: Mark Sussman , Elbridge Gerry Puckett, A coupled level set and volume-of-fluid method for computing 3D and axisymmetric incompressible two-phase flows, Journal of Computational Physics, v.162 n.2, p.301-337, Aug 2000 [doi>10.1006/jcph.2000.6537]
• 53: Terzopoulos, D., Platt, J., and Fleischer, K. 1989. Heating and melting deformable models (from goop to glop). In Proceedings of Graphics Interface 1989. 219--226.
• 54: Greg Turk, Generating textures on arbitrary surfaces using reaction-diffusion, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.289-298, July 1991
• 55: Huamin Wang , Peter J. Mucha , Greg Turk, Water drops on surfaces, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 56: Andrew Witkin , Michael Kass, Reaction-diffusion textures, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.299-308, July 1991
• 57: Wyvill, G., McPheeters, C., and Wyvill, B. 1986. Data structure for soft objects. Vis. Comput. 2, 4, 227--234.
• 58: Yongning Zhu , Robert Bridson, Animating sand as a fluid, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
Natural phenomena, computational fluid dynamics, level-set methods, physically based animation, semi-Lagrangian contouring, surface tracking