Level-set method

Last updated
Video of spiral being propagated by level sets (curvature flow) in 2D. LHS shows zero-level solution. RHS shows the level-set scalar field.

Level-set methods (LSM) are a conceptual framework for using level sets as a tool for numerical analysis of surfaces and shapes. The advantage of the level-set model is that one can perform numerical computations involving curves and surfaces on a fixed Cartesian grid without having to parameterize these objects (this is called the Eulerian approach). [1] Also, the level-set method makes it very easy to follow shapes that change topology, for example, when a shape splits in two, develops holes, or the reverse of these operations. All these make the level-set method a great tool for modeling time-varying objects, like inflation of an airbag, or a drop of oil floating in water.

Contents

An illustration of the level-set method Level set method.png
An illustration of the level-set method

The figure on the right illustrates several important ideas about the level-set method. In the upper-left corner we see a shape; that is, a bounded region with a well-behaved boundary. Below it, the red surface is the graph of a level set function determining this shape, and the flat blue region represents the xy plane. The boundary of the shape is then the zero-level set of , while the shape itself is the set of points in the plane for which is positive (interior of the shape) or zero (at the boundary).

In the top row we see the shape changing its topology by splitting in two. It would be quite hard to describe this transformation numerically by parameterizing the boundary of the shape and following its evolution. One would need an algorithm able to detect the moment the shape splits in two, and then construct parameterizations for the two newly obtained curves. On the other hand, if we look at the bottom row, we see that the level set function merely translated downward. This is an example of when it can be much easier to work with a shape through its level-set function than with the shape directly, where using the shape directly would need to consider and handle all the possible deformations the shape might undergo.

Thus, in two dimensions, the level-set method amounts to representing a closed curve (such as the shape boundary in our example) using an auxiliary function , called the level-set function. is represented as the zero-level set of by

and the level-set method manipulates implicitly, through the function . This function is assumed to take positive values inside the region delimited by the curve and negative values outside. [2] [3]

The level-set equation

If the curve moves in the normal direction with a speed , then the level-set function satisfies the level-set equation

Here, is the Euclidean norm (denoted customarily by single bars in PDEs), and is time. This is a partial differential equation, in particular a Hamilton–Jacobi equation, and can be solved numerically, for example, by using finite differences on a Cartesian grid. [2] [3]

The numerical solution of the level-set equation, however, requires sophisticated techniques. Simple finite-difference methods fail quickly. Upwinding methods, such as the Godunov method, fare better; however, the level-set method does not guarantee the conservation of the volume and the shape of the level set in an advection field that does conserve the shape and size, for example, uniform or rotational velocity field. Instead, the shape of the level set may get severely distorted, and the level set may vanish over several time steps. For this reason, high-order finite-difference schemes are generally required, such as high-order essentially non-oscillatory (ENO) schemes, and even then the feasibility of long-time simulations is questionable. Further sophisticated methods to deal with this difficulty have been developed, e.g., combinations of the level-set method with tracing marker particles advected by the velocity field. [4]

Example

Consider a unit circle in , shrinking in on itself at a constant rate, i.e. each point on the boundary of the circle moves along its inwards pointing normal at some fixed speed. The circle will shrink and eventually collapse down to a point. If an initial distance field is constructed (i.e. a function whose value is the signed euclidean distance to the boundary, positive interior, negative exterior) on the initial circle, the normalised gradient of this field will be the circle normal.

If the field has a constant value subtracted from it in time, the zero level (which was the initial boundary) of the new fields will also be circular and will similarly collapse to a point. This is due to this being effectively the temporal integration of the Eikonal equation with a fixed front velocity.

In combustion, this method is used to describe the instantaneous flame surface, known as the G equation.

History

The level-set method was developed in 1979 by Alain Dervieux, [5] and subsequently popularized by Stanley Osher and James Sethian. It has become popular in many disciplines, such as image processing, computer graphics, computational geometry, optimization, computational fluid dynamics, and computational biology.

A number of level-set data structures have been developed to facilitate the use of the level-set method in computer applications.

Applications

Computational fluid dynamics

To run a Math Model in the interface of two different fluids we need to soften the interactions between the fluids. Therefore we need to apply a specific function: Compact Level Set Method.

As a “spin off”, the CompactLSM is a complement of the LSM, that helps solving LSM equations. It can be used in numerical simulation of flow, for example, if we are working with discretization of the interface water-air, compacts at sixth order, ensures the accurate and fast calculation of the interface equations (Monteiro 2018).

The LSM uses a distance function to locate different fluids. A distance function is that whose value represents the smallest distance from the point where it is being analyzed to the interface. This distance function is identified by isolines (2D) or isosurfaces (3D), showing that  the negative values refer to one of the fluids, positive values refer to the other and the zero value corresponds to the position of the interface.

But, how Heaviside function its inserted in the Compact Level Set Method?

Since the specific mass and viscosity are discontinuous at the interface, both excess diffusion problem (interface widening) and numerical oscillations are expected if there is no adequate treatment of the fluid near the interface. To minimize these problems, the Level Set method uses a smooth, cell-related Heaviside function that explicitly defines the interface position (∅ = 0).

The transition in the interface is kept smooth, but with a thickness of the order of magnitude of the cell size, to avoid the introduction of disturbances with a length scale equal to that of the mesh, since the interface infers an abrupt jump property from one cell to the next (Unverdi and Tryggvason, 1992). To reconstruct the material properties of the flow, such as specific mass and viscosity, another marker function, I (∅), of the Heaviside type is used:

      (1)

where δ is an empirical coefficient, usually equal to 1; 5 and Δ is the characteristic discretization of the problem, which varies according to the phenomenon to be simulated. The value of δ represents an interface with a thickness of three cells, and thus δΔ represents half the thickness of the interface. Note that in this method, the interface has a virtual thickness, as it is represented by a smooth function. Physical properties, such as specific mass and kinematic viscosity, are calculated as:

      (2)

where ρ1, ρ2, v1 and v2 are the specific mass and kinematic viscosity of fluids 1 and 2. Equation 2 can be applied analogously to the other properties of the fluids.

See also

Related Research Articles

Navier–Stokes equations Equations describing the motion of viscous fluid substances

In physics, the Navier–Stokes equations are a set of partial differential equations which describe the motion of viscous fluid substances, named after French engineer and physicist Claude-Louis Navier and Anglo-Irish physicist and mathematician George Gabriel Stokes.

In mathematics, a Green's function is the impulse response of an inhomogeneous linear differential operator defined on a domain with specified initial conditions or boundary conditions.

In statistics, econometrics and signal processing, an autoregressive (AR) model is a representation of a type of random process; as such, it is used to describe certain time-varying processes in nature, economics, etc. The autoregressive model specifies that the output variable depends linearly on its own previous values and on a stochastic term ; thus the model is in the form of a stochastic difference equation. Together with the moving-average (MA) model, it is a special case and key component of the more general autoregressive–moving-average (ARMA) and autoregressive integrated moving average (ARIMA) models of time series, which have a more complicated stochastic structure; it is also a special case of the vector autoregressive model (VAR), which consists of a system of more than one interlocking stochastic difference equation in more than one evolving random variable.

In physics and fluid mechanics, a Blasius boundary layer describes the steady two-dimensional laminar boundary layer that forms on a semi-infinite plate which is held parallel to a constant unidirectional flow. Falkner and Skan later generalized Blasius' solution to wedge flow, i.e. flows in which the plate is not parallel to the flow.

In numerical methods, total variation diminishing (TVD) is a property of certain discretization schemes used to solve hyperbolic partial differential equations. The most notable application of this method is in computational fluid dynamics. The concept of TVD was introduced by Ami Harten.

In numerical analysis and computational fluid dynamics, Godunov's theorem — also known as Godunov's order barrier theorem — is a mathematical theorem important in the development of the theory of high resolution schemes for the numerical solution of partial differential equations.

Young–Laplace equation

In physics, the Young–Laplace equation is a nonlinear partial differential equation that describes the capillary pressure difference sustained across the interface between two static fluids, such as water and air, due to the phenomenon of surface tension or wall tension, although use of the latter is only applicable if assuming that the wall is very thin. The Young–Laplace equation relates the pressure difference to the shape of the surface or wall and it is fundamentally important in the study of static capillary surfaces. It is a statement of normal stress balance for static fluids meeting at an interface, where the interface is treated as a surface :

In applied mathematics, discontinuous Galerkin methods form a class of numerical methods for solving differential equations. They combine features of the finite element and the finite volume framework and have been successfully applied to hyperbolic, elliptic, parabolic and mixed form problems arising from a wide range of applications. DG methods have in particular received considerable interest for problems with a dominant first-order part, e.g. in electrodynamics, fluid mechanics and plasma physics.

In computational fluid dynamics, the immersed boundary method originally referred to an approach developed by Charles Peskin in 1972 to simulate fluid-structure (fiber) interactions. Treating the coupling of the structure deformations and the fluid flow poses a number of challenging problems for numerical simulations. In the immersed boundary method the fluid is represented on an Eulerian coordinate and the structure is represented on a Lagrangian coordinate. For Newtonian fluids governed by the incompressible Navier–Stokes equations, the fluid equations are

In fluid dynamics, Luke's variational principle is a Lagrangian variational description of the motion of surface waves on a fluid with a free surface, under the action of gravity. This principle is named after J.C. Luke, who published it in 1967. This variational principle is for incompressible and inviscid potential flows, and is used to derive approximate wave models like the mild-slope equation, or using the averaged Lagrangian approach for wave propagation in inhomogeneous media.

The Kansa method is a computer method used to solve partial differential equations. Partial differential equations are mathematical models of things like stresses in a car's body, air flow around a wing, the shock wave in front of a supersonic airplane, quantum mechanical model of an atom, ocean waves, socio-economic models, digital image processing etc. The computer takes the known quantities such as pressure, temperature, air velocity, stress, and then uses the laws of physics to figure out what the rest of the quantities should be like a puzzle being fit together. Then, for example, the stresses in various parts of a car can be determined when that car hits a bump at 70 miles per hour.

The power law scheme was first used by Suhas Patankar (1980). It helps in achieving approximate solutions in computational fluid dynamics (CFD) and it is used for giving a more accurate approximation to the one-dimensional exact solution when compared to other schemes in computational fluid dynamics (CFD). This scheme is based on the analytical solution of the convection diffusion equation. This scheme is also very effective in removing False diffusion error.

The hybrid difference scheme is a method used in the numerical solution for convection–diffusion problems. It was first introduced by Spalding (1970). It is a combination of central difference scheme and upwind difference scheme as it exploits the favorable properties of both of these schemes.

In computational fluid dynamics, the Stochastic Eulerian Lagrangian Method (SELM) is an approach to capture essential features of fluid-structure interactions subject to thermal fluctuations while introducing approximations which facilitate analysis and the development of tractable numerical methods. SELM is a hybrid approach utilizing an Eulerian description for the continuum hydrodynamic fields and a Lagrangian description for elastic structures. Thermal fluctuations are introduced through stochastic driving fields.

Finite volume method for one-dimensional steady state diffusion

The Finite volume method in computational fluid dynamics is a discretization technique for partial differential equations that arise from physical conservation laws. These equations can be different in nature, e.g. elliptic, parabolic, or hyperbolic. The first well-documented use of this method was by Evans and Harlow (1957) at Los Alamos. The general equation for steady diffusion can be easily be derived from the general transport equation for property Φ by deleting transient and convective terms.

Central differencing scheme

In applied mathematics, the central differencing scheme is a finite difference method that optimizes the approximation for the differential operator in the central node of the considered patch and provides numerical solutions to differential equations. It is one of the schemes used to solve the integrated convection–diffusion equation and to calculate the transported property Φ at the e and w faces, where e and w are short for east and west. The method's advantages are that it is easy to understand and implement, at least for simple material relations; and that its convergence rate is faster than some other finite differencing methods, such as forward and backward differencing. The right side of the convection-diffusion equation, which basically highlights the diffusion terms, can be represented using central difference approximation. To simplify the solution and analysis, linear interpolation can be used logically to compute the cell face values for the left side of this equation, which is nothing but the convective terms. Therefore, cell face values of property for a uniform grid can be written as:

Unsteady flows are characterized as flows in which the properties of the fluid are time dependent. It gets reflected in the governing equations as the time derivative of the properties are absent. For Studying Finite-volume method for unsteady flow there is some governing equations >

The upwind differencing scheme is a method used in numerical methods in computational fluid dynamics for convection–diffusion problems. This scheme is specific for Peclet number greater than 2 or less than −2

Finite volume method (FVM) is a numerical method. FVM in computational fluid dynamics is used to solve the partial differential equation which arises from the physical conservation law by using discretisation. Convection is always followed by diffusion and hence where convection is considered we have to consider combine effect of convection and diffusion. But in places where fluid flow plays a non-considerable role we can neglect the convective effect of the flow. In this case we have to consider more simplistic case of only diffusion. The general equation for steady convection-diffusion can be easily derived from the general transport equation for property by deleting transient.

Finite volume method for two dimensional diffusion problem

The methods used for solving two dimensional Diffusion problems are similar to those used for one dimensional problems. The general equation for steady diffusion can be easily derived from the general transport equation for property Φ by deleting transient and convective terms

References

  1. Osher, S.; Sethian, J. A. (1988), "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton–Jacobi formulations" (PDF), J. Comput. Phys., 79 (1): 12–49, Bibcode:1988JCoPh..79...12O, CiteSeerX   10.1.1.46.1266 , doi:10.1016/0021-9991(88)90002-2, hdl:10338.dmlcz/144762
  2. 1 2 Osher, Stanley J.; Fedkiw, Ronald P. (2002). Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag. ISBN   978-0-387-95482-0.
  3. 1 2 Sethian, James A. (1999). Level Set Methods and Fast Marching Methods : Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press. ISBN   978-0-521-64557-7.
  4. Enright, D.; Fedkiw, R. P.; Ferziger, J. H.; Mitchell, I. (2002), "A hybrid particle level set method for improved interface capturing" (PDF), J. Comput. Phys., 183 (1): 83–116, Bibcode:2002JCoPh.183...83E, CiteSeerX   10.1.1.15.910 , doi:10.1006/jcph.2002.7166
  5. F. Thomasset, A. Dervieux, A finite element method for the simulation of a Rayleigh-Taylor instability, Lectures Notes in Mathematics, Vol.771, 145-158 (1979)