More Web Proxy on the site http://driver.im/

article

A semi-Lagrangian contouring method for fluid simulation

Authors:

Adam W. Bargteil,

Tolga G. Goktekin,

James F. O'Brien,

John A. StrainAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 25, Issue 1

Pages 19 - 38

https://doi.org/10.1145/1122501.1122503

Published: 01 January 2006 Publication History

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]

Bloomenthal, J. 1994. An implicit surface polygonizer. In Graphics Gems IV. Academic Press Professional, Inc., San Diego, CA, 324--349.

[5]

Boissonnat, J. D. and Oudot, S. 2003. Provably good surface sampling and approximation. In SGP '03: Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. Eurographics Association, Aire-la-Ville, Switzerland, 9--18.

[6]

Cani, M.-P. and Desbrun, M. 1997. Animation of deformable models using implicit surfaces. IEEE Trans. Visual. Comput. Graph. 3, 1 (Jan.), 39--50.

[7]

Carlson, M., Mucha, P. J., R. Brooks Van Horn, I., and Turk, G. 2002. Melting and flowing. In SCA '02: Proceedings of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. ACM Press, New York, NY, 167--174.

[8]

Carlson, M., Mucha, P. J., and Turk, G. 2004. Rigid fluid: Animating the interplay between rigid bodies and fluid. ACM Trans. Graph. 23, 3, 377--384.

[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]

Desbrun, M. and Cani, M.-P. 1996. Smoothed particles: A new paradigm for animating highly deformable bodies. In Proceedings of Computer Animation and Simulation 1996. 61--76.

[11]

Desbrun, M. and Gascuel, M.-P. 1995. Animating soft substances with implicit surfaces. In the Proceedings of SIGGRAPH 95, 287--290.

[12]

Enright, D., Fedkiw, R., Ferziger, J., and Mitchell, I. 2002a. A hybrid particle level set method for improved interface capturing. J. Computat. Phys. 183, 1, 83--116.

[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]

Enright, D. P., Marschner, S. R., and Fedkiw, R. P. 2002b. Animation and rendering of complex water surfaces. In Proceedings of ACM SIGGRAPH 2002. 736--744.

[15]

Fedkiw, R., Stam, J., and Jensen, H. W. 2001. Visual simulation of smoke. In the Proceedings of ACM SIGGRAPH 2001. 15--22.

[16]

Foster, N. and Fedkiw, R. 2001. Practical animation of liquids. In the Proceedings of ACM SIGGRAPH 2001. 23--30.

[17]

Foster, N. and Metaxas, D. 1996. Realistic animation of liquids. In Proceedings of Graphics Interface 1996. 204--212.

[18]

Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000. Adaptively sampled distance fields: A general representation of shape for computer graphics. In SIGGRAPH '00: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY/Addison-Wesley Publishing Co., Reading, MA, 249--254.

[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]

Guendelman, E., Selle, A., Losasso, F., and Fedkiw, R. 2005. Coupling water and smoke to thin deformable and rigid shells. ACM Trans. Graph. 24, 3, 973--981.

[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]

Hong, J.-M. and Kim, C.-H. 2005. Discontinuous fluids. ACM Trans. Graph. 24, 3, 915--920.

[25]

Houston, B., Nielsen, M. B., Batty, C., Nilsson, O., and Museth, K. 2006. Hierarchical RLE level set: A compact and versatile deformable surface representation. ACM Trans. Graph. 25, 1, xx--xx.

[26]

Ju, T., Losasso, F., Schaefer, S., and Warren, J. 2002. Dual contouring of hermite data. In SIGGRAPH '02: Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 339--346.

[27]

LeVeque, R. J. 1990. Numerical Methods for Conservation Laws. Birkhauser-Verlag, Basel, Switzerland.

[28]

Lorensen, W. E. and Cline, H. E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. In SIGGRAPH '87: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 163--169.

[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]

Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. In ACM SIGGRAPH 2003 Symposium on Computer Animation. 154--159.

[31]

Müller, M., Keiser, R., Nealen, A., Pauly, M., Gross, M., and Alexa, M. 2004. Point based animation of elastic, plastic and melting objects. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Symposium on Computer Animation.

[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]

Osher, S. and Sethian, J. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. J Computat. Phys. 79, 12--49.

[35]

Pauly, M., Keiser, R., Adams, B., Dutré, P., Gross, M., and Guibas, L. J. 2005. Meshless animation of fracturing solids. ACM Trans. Graph. 24, 3, 957--964.

[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]

Rasmussen, N., Enright, D., Nguyen, D., Marino, S., Sumner, N., Geiger, W., Hoon, S., and Fedkiw, R. 2004. Directable photorealistic liquids. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Symposium on Computer Animation. ACM Press, New York, NY, 193--202.

[39]

Samet, H. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley Longman Publishing Co., Inc., Reading, MA.

[40]

Schneider, P. J. and Eberly, D. H. 2002. Geometric Tools for Computer Graphics, 1st ed. Morgan Kaufmann, San Francisco, CA.

[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]

Shekhar, R., Fayyad, E., Yagel, R., and Cornhill, J. F. 1996. Octree-based decimation of marching cubes surfaces. In VIS '96: Proceedings of the 7th conference on Visualization '96. IEEE Computer Society Press, Los Alamitos, CA, 335ff.

[44]

Shu, R., Chen, Z., and Kankanhalli, M. S. 1995. Adaptive marching cubes. Vis. Comput. 11, 202--217.

[45]

Stam, J. 1999. Stable fluids. In the Proceedings of ACM SIGGRAPH 99. 121--128.

[46]

Stora, D., Agliati, P.-O., Cani, M.-P., Neyret, F., and Gascuel, J.-D. 1999. Animating lava flows. In Proceedings of Graphics Interface 99. 203--210.

[47]

Strain, J. A. 1999a. Fast tree-based redistancing for level set computations. J. Computat. Phys. 152, 2 (July), 648--666.

[48]

Strain, J. A. 1999b. Semi-Lagrangian methods for level set equations. J. Computat. Phys. 151, 2 (May), 498--533.

[49]

Strain, J. A. 1999c. Tree methods for moving interfaces. J. Computat. Phys. 151, 2 (May), 616--648.

[50]

Strain, J. A. 2000. A fast modular semi-Lagrangian method for moving interfaces. J. Computat. Phys. 161, 2 (July), 512-- 536.

[51]

Strain, J. A. 2001. A fast semi-Lagrangian contouring method for moving interfaces. J. Computat. Phys. 169, 1 (May), 1--22.

[52]

Sussman, M. and Puckett, E. G. 2000. A coupled level set and volume-of-fluid method for computing 3D and axisymmetric incompressible two-phase flows. J. Comput. Physat. 162, 2, 301--337.

[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]

Turk, G. 1991. Generating textures on arbitrary surfaces using reaction-diffusion. In SIGGRAPH '91: Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 289--298.

[55]

Wang, H., Mucha, P. J., and Turk, G. 2005. Water drops on surfaces. ACM Trans. Graph. 24, 3, 921--929.

[56]

Witkin, A. and Kass, M. 1991. Reaction-diffusion textures. In SIGGRAPH '91: Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 299--308.

[57]

Wyvill, G., McPheeters, C., and Wyvill, B. 1986. Data structure for soft objects. Vis. Comput. 2, 4, 227--234.

[58]

Zhu, Y. and Bridson, R. 2005. Animating sand as a fluid. ACM Trans. Graph. 24, 3, 965--972.

Cited By

Kim DLee MMuseth K(2024)NeuralVDB: High-resolution Sparse Volume Representation using Hierarchical Neural NetworksACM Transactions on Graphics10.1145/364181743:2(1-21)Online publication date: 23-Jan-2024
https://dl.acm.org/doi/10.1145/3641817
Jain PQu ZChen PStein O(2024)Neural Monte Carlo Fluid SimulationACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657438(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657438
Narita FAndo R(2023)Tiled Characteristic Maps for Tracking Detailed Liquid SurfacesComputer Graphics Forum10.1111/cgf.1463841:8(231-242)Online publication date: 20-Mar-2023
https://doi.org/10.1111/cgf.14638
Show More Cited By

Index Terms

A semi-Lagrangian contouring method for fluid simulation
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Physical simulation
    2. Shape modeling
  2. Modeling and simulation
    1. Simulation types and techniques
      1. Simulation by animation
2. Mathematics of computing
  1. Continuous mathematics
    1. Topology
      1. Geometric topology

Recommendations

Liquid simulation on lattice-based tetrahedral meshes
SCA '07: Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation

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 ...
A method for animating viscoelastic fluids

This paper describes a technique for animating the behavior of viscoelastic fluids, such as mucus, liquid soap, pudding, toothpaste, or clay, that exhibit a combination of both fluid and solid characteristics. The technique builds upon prior Eulerian ...
A texture synthesis method for liquid animations
SCA '06: Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation

In this paper we present a method for synthesizing textures on animated liquid surfaces generated by a physically based fluid simulation system. Rather than advecting texture coordinates on the surface, our algorithm synthesizes a new texture for every ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 25, Issue 1

January 2006

175 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1122501

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2006

Published in TOG Volume 25, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

124
Total Citations
View Citations
1,840
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)5

Reflects downloads up to 25 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kim DLee MMuseth K(2024)NeuralVDB: High-resolution Sparse Volume Representation using Hierarchical Neural NetworksACM Transactions on Graphics10.1145/364181743:2(1-21)Online publication date: 23-Jan-2024
https://dl.acm.org/doi/10.1145/3641817
Jain PQu ZChen PStein O(2024)Neural Monte Carlo Fluid SimulationACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657438(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657438
Narita FAndo R(2023)Tiled Characteristic Maps for Tracking Detailed Liquid SurfacesComputer Graphics Forum10.1111/cgf.1463841:8(231-242)Online publication date: 20-Mar-2023
https://doi.org/10.1111/cgf.14638
Liu SYang Z(2022)Virtual water wave simulation with multiple wavenumbersVirtual Reality10.1007/s10055-022-00729-027:2(1221-1231)Online publication date: 7-Dec-2022
https://dl.acm.org/doi/10.1007/s10055-022-00729-0
Hong BZhang QKim CLee JKim J(2021)Accelerated Smoke Simulation by Super-Resolution With Deep Learning on Downscaled and Binarized SpaceIEEE Access10.1109/ACCESS.2021.30959049(98615-98629)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3095904
Kim JLee J(2020)Efficient preservation and breakup of liquid sheets using screen-projected particlesPLOS ONE10.1371/journal.pone.022759015:2(e0227590)Online publication date: 5-Feb-2020
https://doi.org/10.1371/journal.pone.0227590
Chen YMeier JSolenthaler BAzevedo V(2020)An extended cut-cell method for sub-grid liquids tracking with surface tensionACM Transactions on Graphics10.1145/3414685.341785939:6(1-13)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417859
Wang SDing MGast TZhu LGagniere SJiang CTeran J(2019)Simulation and Visualization of Ductile Fracture with the Material Point MethodProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/33402592:2(1-20)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3340259
Yang MYe JDing FZhang YYan D(2019)A Semi-Explicit Surface Tracking Mechanism for Multi-Phase Immiscible LiquidsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2018.286428325:10(2873-2885)Online publication date: 1-Oct-2019
https://doi.org/10.1109/TVCG.2018.2864283
Bak SKim PKim D(2019)A semi-Lagrangian approach for numerical simulation of coupled Burgers’ equationsCommunications in Nonlinear Science and Numerical Simulation10.1016/j.cnsns.2018.09.00769(31-44)Online publication date: Apr-2019
https://doi.org/10.1016/j.cnsns.2018.09.007
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents