Elsevier

Computers & Structures

Volume 83, Issues 6–7, February 2005, Pages 479-490
Computers & Structures

A fast and accurate semi-Lagrangian particle level set method

https://doi.org/10.1016/j.compstruc.2004.04.024Get rights and content

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.

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 ϕ(x,t). The level set function has the following properties,ϕ(x,t)>0forxΩϕ(x,t)0forxΩ,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 byu=(π/314)(50-y),v=(π/314)(x-50),so 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).

Cited by (0)

View full text