A fast and accurate semi-Lagrangian particle level set method
Introduction
Standard Eulerian advection algorithms, e.g. HJ-(W)ENO methods [18], [8] combined with TVD-based high order accurate Runge–Kutta schemes [18], require a strict bound on the maximum possible time step due to a stability-based CFL criterion. On the other hand, particles are not restricted by this stability criterion, rather the size of the time step used can be based solely on the degree of numerical accuracy desired. Grid based semi-Lagrangian advection methods are likewise not limited by a stability-based CFL condition, since each grid point is treated in a “particle-like” manner. However, semi-Lagrangian schemes can suffer from large amounts of numerical dissipation, making their use problematic. HJ-(W)ENO methods experience far less numerical dissipation due to their high order accurate adaptive nature. In order to take advantage of the stability afforded by particle based methods, the spatial and temporal coherency of Eulerian methods, and the opportunity for selective adaptive mesh refinement near the interface in order to resolve small scale features as discussed below, we propose to couple together a semi-Lagrangian advection scheme with a characteristic-based particle method to track a passively advected interface.
A flexible and easy-to-implement interface tracking technique is the level set method of Osher and Sethian [12]. By storing the distance to the interface at each point on a fixed computational grid, handling gross changes to interface topology, e.g. pinching and merging, becomes trivial as compared to standard Lagrangian techniques [25] that typically require ad hoc techniques to address mesh connectivity during merging and pinching. By avoiding these difficulties and utilizing well established numerical algorithms for the solution of nonlinear hyperbolic conservation laws, level set methods have been applied to a wide variety of problems including fluid mechanics, computer vision, material science, and computer graphics. One difficulty with the use of the level set method is the need to control the numerical diffusion (or mass loss) present in the method, especially in areas of high curvature and long, thin filamentary regions. Various authors [24], [22], [23] have attempted to correct this problem by reinitializing the level set function, ϕ to be signed distance to the interface after each time step. High order accurate TVD Runge–Kutta and HJ-(W)ENO techniques can be used to perform this reinitialization. While producing reasonable results, these methods suffer from the same Eulerian-based advection issues mentioned above such as small time step restrictions.
An alternative characteristic-based diffusion correction technique, the particle level set method [5], has been recently proposed. In this method, two sets of marker particles are placed near the interface, one set associated with the interior (ϕ ⩽ 0) region, and the other with the exterior (ϕ > 0) region. Errors due to numerical dissipation can then be identified when interior particles appear in the exterior region or exterior particles appear in the interior region. Since the particles are able to more accurately track the underlying flow characteristics, these “escaped” particles can be used to correct the level set representation of the interface. The particle level set method has been shown to possess excellent volume conservation properties and a high degree of geometrical accuracy in tracking contact discontinuities, comparable to other interface methods including volume-of-fluid (VOF) and explicit front tracking. At the same time the method maintains the highly desirable topological properties and ease-of-implementation of the original level set method. As an example of the flexibility of the particle level set method, its use in modeling complex three dimensional water surfaces can be seen in [6], [7].
In [5], HJ-WENO numerical methods were used to evolve and reinitialize ϕ. Reinitialization of ϕ was used in order to assist the particles in obtaining an accurate distance to the interface. Due to the HJ-WENO advection scheme used, a stability based CFL condition was imposed on the size of the time step. Use of this scheme in an adaptive mesh setting would impose a severe time step restriction on a simulation, discouraging the use of selective mesh adaptive to resolve small scale features. Due to the minimal amount of diffusion exhibited by the particle level set method, we can avoid the common but computationally costly approach of adapatation resolving the mesh just for the sake of minimizing numerical diffusion at the interface. Moreover, since the particles dictate a sharp and geometrically accurate interface, we propose to use a first order accurate semi-Lagrangian advection method [4], [15], [19]. Despite being unconditionally stable, use of a first order accurate semi-Lagrangian scheme has typically been shunned due to the large amount of numerical diffusion inherently incurred. Although a low order accurate semi-Lagrangian scheme was used by [20] for level set advection, computationally expensive higher order accurate semi-Lagrangian methods are usually preferred, see [21]. Due to the observed excellent diffusion limiting properties of the particles, we illustrate that the fast first order accurate semi-Lagrangian scheme is sufficient. Also, we replace the HJ-WENO reinitialization scheme with a fast, i.e. O(N log N), first order accurate marching technique first proposed by Tsitsiklis [26] and later popularized by Sethian and co-workers, see e.g. [17].
None of the methods we propose are bound by a grid based CFL stability condition, rather only numerical accuracy needs to be taken into account. The resulting numerical method is a computationally fast and geometrically accurate interface tracking technique that efficiently provides for the adaptive resolution of small scale features. We demonstrate this last claim by showing some preliminary computations on an octree data structure.
Section snippets
Level set method
The underlying idea behind level set methods is to embed an interface Γ which bounds a region Ω ⊂ R3 as the zero level set of a higher dimensional function . The level set function has the following properties,where we include ϕ = 0 with the negative ϕ values. Then the interface lies in between ϕ > 0 and ϕ = 0, but can of course be identified as ϕ = 0. Note that ϕ is a scalar function in R3 which greatly reduces the complexity of describing the interface,
Rigid body rotation of Zalesak’s disk
Consider the rigid body rotation of Zalesak’s disk in a constant vorticity velocity field [27]. The initial data is a slotted circle centered at (50, 75) with a radius of 15, a width of 5, and a slot length of 25. The constant vorticity velocity field is given byso that the disk completes one revolution every 628 time units.
To better understand the ability of the various coupled advection and reinitialization algorithms to accurately represent a passively advected
Conclusions
We proposed a fast semi-Lagrangian based particle level set method for the accurate capturing of passively advected interfaces. By utilizing massless marker particles nearby the interface as a characteristic-based diffusion control mechanism, we were able to forgo the use of higher order accurate advection schemes. These schemes significantly increase the computation time, due to the small time step required for stability of the scheme. Semi-Lagrangian methods do not suffer from this
Acknowledgment
Research supported in part by an ONR YIP and PECASE award (N00014-01-1-0620), a Packard Foundation Fellowship, a Sloan Research Fellowship, ONR N00014-03-1-0071, ONR N00014-02-1-0720, NSF DMS-0106694, NSF ITR-0121288 and DOE under the ASCI Academic Strategic Alliances Program (LLNL contract B341491). In addition, the first author was supported in part by an NSF postdoctoral fellowship (DMS-0202459).
References (27)
- et al.
A fast level set method for propagating interfaces
J Comput Phys
(1995) - et al.
A second-order projection method for the incompressible Navier–Stokes equations
J Comput Phys
(1989) - et al.
A numerical method for two phase flow consisting of separate compressible and incompressible regions
J Comput Phys
(2001) - et al.
A hybrid particle level set method for improved interface capturing
J Comput Phys
(2002) - et al.
Fronts propagating with curvature dependent speed: algorithms based on Hamiliton–Jacobi formulations
J Comput Phys
(1988) - et al.
A pdebased fast local level set method
J Comput Phys
(1999) - et al.
Reconstructing volume tracking
J Comput Phys
(1998) - et al.
Efficient implementation of essentially non-oscillatory shock capturing schemes
J Comput Phys
(1988) Semi-Lagrangian methods for level set equations
J Comput Phys
(1999)A fast modular semi-Lagrangian method for moving interfaces
J Comput Phys
(2000)