article

A fast and accurate semi-Lagrangian particle level set method

Authors:

Douglas Enright,

Ronald FedkiwAuthors Info & Claims

Computers and Structures, Volume 83, Issue 6-7

Pages 479 - 490

https://doi.org/10.1016/j.compstruc.2004.04.024

Published: 01 February 2005 Publication History

Abstract

In this paper, we present an efficient semi-Lagrangian based particle level set method for the accurate capturing of interfaces. This method retains the robust topological properties of the level set method with- out the adverse effects of numerical dissipation. Both the level set method and the particle level set method typically use high order accurate numerical discretizations in time and space, e.g. TVD Runge-Kutta and HJ-WENO schemes. We demonstrate that these computationally expensive schemes are not required. Instead, fast, low order accurate numerical schemes suffice. That is, the addition of particles to the level set method not only removes the difficulties associated with numerical diffusion, but also alleviates the need for computationally expensive high order accurate schemes. We use an efficient, first order accurate semi-Lagrangian advection scheme coupled with a first order accurate fast marching method to evolve the level set function. To accurately track the underlying flow characteristics, the particles are evolved with a second order accurate method. Since we avoid complex high order accurate numerical methods, extending the algorithm to arbitrary data structures becomes more feasible, and we show preliminary results obtained with an octree-based adaptive mesh.

References

[1]

Adalsteinsson, D. and Sethian, J., A fast level set method for propagating interfaces. J Comput Phys. v118. 269-277.

Digital Library

[2]

Bell, J., Colella, P. and Glaz, H., A second-order projection method for the incompressible Navier-Stokes equations. J Comput Phys. v85. 257-283.

[3]

Caiden, R., Fedkiw, R. and Anderson, C., A numerical method for two phase flow consisting of separate compressible and incompressible regions. J Comput Phys. v166. 1-27.

[4]

Courant, R., Issacson, E. and Rees, M., On the solution of nonlinear hyperbolic differential equations by finite differences. Commun Pure Appl Math. v5. 243-255.

[5]

Enright, D., Fedkiw, R., Ferziger, J. and Mitchell, I., A hybrid particle level set method for improved interface capturing. J Comput Phys. v183. 83-116.

Digital Library

[6]

Enright, D., Marschner, S. and Fedkiw, R., Animation and rendering of complex water surfaces. ACM Trans Graphics (SIGGRAPH 2002 Proc). v21. 736-744.

[7]

Enright D, Nguyen D, Gibou F, Fedkiw R. Using the particle level set method and a second order accurate pressure boundary condition for free surface flows. In: Kawahashi M, Ogut A, Tsuji Y, editors. Proc of the 4th ASME-JSME Joint Fluids Engineering Conf, number FEDSM2003-45144. ASME, 2003

[8]

Jiang, G.-S. and Peng, D., Weighted eno schemes for Hamilton-Jacobi equations. SIAM J Sci Comput. v21. 2126-2143.

[9]

LeVeque, R., High-resolution conservative algorithms for advection in incompressible flow. SIAM J Numer Anal. v33. 627-665.

[10]

Losasso F, Gibou F, Fedkiw R. Simulating water and smoke with an octree data structure. In: ACM Trans Graph (SIGGRAPH Proc). in press

[11]

Osher, S. and Fedkiw, R., Level set methods and dynamic implicit surfaces. 2002. Springer-Verlag, New York.

[12]

Osher, S. and Sethian, J., Fronts propagating with curvature dependent speed: algorithms based on Hamiliton-Jacobi formulations. J Comput Phys. v79. 12-49.

[13]

Peng, D., Merriman, B., Osher, S., Zhao, H.-K. and Kang, M., A pdebased fast local level set method. J Comput Phys. v155. 410-438.

Digital Library

[14]

Rider, W. and Kothe, D., Reconstructing volume tracking. J Comput Phys. v141. 112-152.

Digital Library

[15]

Roberts, A., A stable numerical integration scheme for the primitive meterological equations. Atmos Ocean. v19. 35-46.

[16]

Sethian, J., A fast marching level set method for monotonically advancing fronts. Proc Natl Acad Sci. v93. 1591-1595.

[17]

Sethian, J., Fast marching methods. SIAM Rev. v41. 199-235.

[18]

Shu, C. and Osher, S., Efficient implementation of essentially non-oscillatory shock capturing schemes. J Comput Phys. v77. 439-471.

[19]

Staniforth, A. and Côté, J., Semi-Lagrangian integration schemes for atmospheric models-a review. Mon Weather Rev. v119. 2206-2223.

[20]

Strain, J., Semi-Lagrangian methods for level set equations. J Comput Phys. v151. 498-533.

Digital Library

[21]

Strain, J., A fast modular semi-Lagrangian method for moving interfaces. J Comput Phys. v161. 512-536.

Digital Library

[22]

Sussman, M. and Fatemi, E., An efficient, interface-preserving level set redistancing algorithm and its application to interfacial incompressible fluid flow. SIAM J Sci Comput. v20. 1165-1191.

[23]

Sussman, M., Fatemi, E., Smereka, P. and Osher, S., An improved level set method for incompressible two-phase flows. Comput Fluids. v27. 663-680.

[24]

Sussman, M., Smereka, P. and Osher, S., A level set approach for computing solutions to incompressible two-phase flow. J Comput Phys. v114. 146-159.

Digital Library

[25]

Tryggvason, G., Bunner, B., Esmaeeli, A., Juric, D., Al-Rawahi, N. and Tauber, W., A front-tracking method for the computations of multiphase flow. J Comput Phys. v169. 708-759.

Digital Library

[26]

Tsitsiklis J. Efficient algorithms for globally optimal trajectories. In: Proc of the 33rd Conf on Decision and Control, December 1994. p. 1368-73

[27]

Zalesak, S., Fully multidimensional flux-corrected transport algorithms for fluids. J Comput Phys. v31. 335-362.

Cited By

Li XNi XZhu BWang BChen B(2023)GARM-LS: A Gradient-Augmented Reference-Map Method for Level-Set Fluid SimulationACM Transactions on Graphics10.1145/361837742:6(1-20)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618377
Li WMa YLiu XDesbrun M(2022)Efficient kinetic simulation of two-phase flowsACM Transactions on Graphics10.1145/3528223.353013241:4(1-17)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530132
Lévy B(2022)Partial optimal transport for a constant-volume Lagrangian mesh with free boundariesJournal of Computational Physics10.1016/j.jcp.2021.110838451:COnline publication date: 15-Feb-2022
https://dl.acm.org/doi/10.1016/j.jcp.2021.110838
Show More Cited By

Recommendations

An unconditionally stable fully conservative semi-Lagrangian method

Semi-Lagrangian methods have been around for some time, dating back at least to [3]. Researchers have worked to increase their accuracy, and these schemes have gained newfound interest with the recent widespread use of adaptive grids where the CFL-based ...
Semi-Automatic Instantiation of Data Cleaning Operations Specified at Conceptual Level
A conservative semi-Lagrangian method for inhomogeneous Boltzmann equation
Abstract
The Boltzmann equation is well-known for its good predictability of behaviors of rarefied gas flows, which may not be resolved enough by continuum models. In this work, we propose a high order conservative semi-Lagrangian method for the ...
Highlights
- We propose a conservative semi-Lagrangian method for the Boltzmann equation.
- Semi-Lagrangian approach enables us to avoid CFL-type restrictions on the time step.
- The fast spectral method L̂2-correction guarantees spectral accuracy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Structures

Computers and Structures Volume 83, Issue 6-7

February, 2005

127 pages

ISSN:0045-7949

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2004.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 February 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li XNi XZhu BWang BChen B(2023)GARM-LS: A Gradient-Augmented Reference-Map Method for Level-Set Fluid SimulationACM Transactions on Graphics10.1145/361837742:6(1-20)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618377
Li WMa YLiu XDesbrun M(2022)Efficient kinetic simulation of two-phase flowsACM Transactions on Graphics10.1145/3528223.353013241:4(1-17)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530132
Lévy B(2022)Partial optimal transport for a constant-volume Lagrangian mesh with free boundariesJournal of Computational Physics10.1016/j.jcp.2021.110838451:COnline publication date: 15-Feb-2022
https://dl.acm.org/doi/10.1016/j.jcp.2021.110838
Wang CWang WPan SZhao F(2022)A Local Curvature Based Adaptive Particle Level Set MethodJournal of Scientific Computing10.1007/s10915-022-01772-491:1Online publication date: 18-Feb-2022
https://dl.acm.org/doi/10.1007/s10915-022-01772-4
Aanjaneya MHan CGoldade RBatty C(2019)An Efficient Geometric Multigrid Solver for Viscous LiquidsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/33402552:2(1-21)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3340255
Gibou FHyde DFedkiw R(2019)Sharp interface approaches and deep learning techniques for multiphase flowsJournal of Computational Physics10.1016/j.jcp.2018.05.031380:C(442-463)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1016/j.jcp.2018.05.031
Lee JKim JLee HKim S(2019)Realistic fluid representation by anisotropic particleJournal of Visualization10.1007/s12650-018-0535-x22:2(313-320)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s12650-018-0535-x
Xiong TRusso GQiu J(2019)Conservative Multi-dimensional Semi-Lagrangian Finite Difference SchemeJournal of Scientific Computing10.1007/s10915-018-0892-679:2(1241-1270)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s10915-018-0892-6
Biedert TSohns JSchröder SAmstutz JWald IGarth CHentschel BChilds HCucchietti F(2018)Direct raytracing of particle-based fluid surfaces using anisotropic kernelsProceedings of the Symposium on Parallel Graphics and Visualization10.5555/3293524.3293525(1-12)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.5555/3293524.3293525
You GShi RXu Y(2018)An Efficient Lagrangian Interpolation Scheme for Computing Flow Maps and Line Integrals using Discrete Velocity DataJournal of Scientific Computing10.1007/s10915-017-0620-776:1(120-144)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s10915-017-0620-7
Show More Cited By

View Options

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents