Level-set method

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

The Level-set method (LSM) is a conceptual framework for using level sets as a tool for numerical analysis of surfaces and shapes. LSM can perform numerical computations involving curves and surfaces on a fixed Cartesian grid without having to parameterize these objects. [1] LSM makes it easier to perform computations on shapes with sharp corners and shapes that change topology (such as by splitting in two or developing holes). These characteristics make LSM effective for modeling objects that vary in time, such as an airbag inflating 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

Overview

The figure on the right illustrates several ideas about LSM. In the upper left corner 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 X-Y 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, the shape's topology changes as it is split in two. It is challenging to describe this transformation numerically by parameterizing the boundary of the shape and following its evolution. An algorithm can be used to detect the moment the shape splits in two and then construct parameterizations for the two newly obtained curves. On the bottom row, however, the plane at which the level set function is sampled is translated upwards, on which the shape's change in topology is described. It is less challenging to work with a shape through its level-set function rather than with itself directly, in which a method would need to consider 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. The curve 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 by chain rule and implicit differentiation, it can be determined that the level-set function satisfies the level-set equation

Here, is the Euclidean norm (denoted customarily by single bars in partial differential equations), 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]

However, the numerical solution of the level set equation may require advanced techniques. Simple finite difference methods fail quickly. Upwinding methods such as the Godunov method are considered better; however, the level set method does not guarantee preservation of the volume and shape of the set level in an advection field that maintains shape and size, for example, a uniform or rotational velocity field. Instead, the shape of the level set may become distorted, and the level set may disappear over a few time steps. Therefore, high-order finite difference schemes, such as high-order essentially non-oscillatory (ENO) schemes, are often required, and even then, the feasibility of long-term simulations is questionable. More advanced methods have been developed to overcome this; for example, combinations of the leveling method with tracking marker particles suggested 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 normally 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 normalized 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.

Applications

History

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

See also

Related Research Articles

<span class="mw-page-title-main">Polar coordinate system</span> Coordinates comprising a distance and an angle

In mathematics, the polar coordinate system is a two-dimensional coordinate system in which each point on a plane is determined by a distance from a reference point and an angle from a reference direction. The reference point is called the pole, and the ray from the pole in the reference direction is the polar axis. The distance from the pole is called the radial coordinate, radial distance or simply radius, and the angle is called the angular coordinate, polar angle, or azimuth. Angles in polar notation are generally expressed in either degrees or radians.

In mathematics, the tangent space of a manifold is a generalization of tangent lines to curves in two-dimensional space and tangent planes to surfaces in three-dimensional space in higher dimensions. In the context of physics the tangent space to a manifold at a point can be viewed as the space of possible velocities for a particle moving on the manifold.

<span class="mw-page-title-main">Navier–Stokes equations</span> Equations describing the motion of viscous fluid substances

The Navier–Stokes equations are partial differential equations which describe the motion of viscous fluid substances. They were named after French engineer and physicist Claude-Louis Navier and the Irish physicist and mathematician George Gabriel Stokes. They were developed over several decades of progressively building the theories, from 1822 (Navier) to 1842–1850 (Stokes).

<span class="mw-page-title-main">Potential flow</span> Velocity field as the gradient of a scalar function

In fluid dynamics, potential flow or irrotational flow refers to a description of a fluid flow with no vorticity in it. Such a description typically arises in the limit of vanishing viscosity, i.e., for an inviscid fluid and with no vorticity present in the flow.

<span class="mw-page-title-main">Geodesic</span> Straight path on a curved surface or a Riemannian manifold

In geometry, a geodesic is a curve representing in some sense the shortest path (arc) between two points in a surface, or more generally in a Riemannian manifold. The term also has meaning in any differentiable manifold with a connection. It is a generalization of the notion of a "straight line".

In vector calculus, Green's theorem relates a line integral around a simple closed curve C to a double integral over the plane region D bounded by C. It is the two-dimensional special case of Stokes' theorem.

Geometrical optics, or ray optics, is a model of optics that describes light propagation in terms of rays. The ray in geometrical optics is an abstraction useful for approximating the paths along which light propagates under certain circumstances.

<span class="mw-page-title-main">Signed distance function</span> Distance from a point to the boundary of a set

In mathematics and its applications, the signed distance function is the orthogonal distance of a given point x to the boundary of a set Ω in a metric space, with the sign determined by whether or not x is in the interior of Ω. The function has positive values at points x inside Ω, it decreases in value as x approaches the boundary of Ω where the signed distance function is zero, and it takes negative values outside of Ω. However, the alternative convention is also sometimes taken instead.

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.

Numerical continuation is a method of computing approximate solutions of a system of parameterized nonlinear equations,

<span class="mw-page-title-main">Differential geometry of surfaces</span> The mathematics of smooth surfaces

In mathematics, the differential geometry of surfaces deals with the differential geometry of smooth surfaces with various additional structures, most often, a Riemannian metric. Surfaces have been extensively studied from various perspectives: extrinsically, relating to their embedding in Euclidean space and intrinsically, reflecting their properties determined solely by the distance within the surface as measured along curves on the surface. One of the fundamental concepts investigated is the Gaussian curvature, first studied in depth by Carl Friedrich Gauss, who showed that curvature was an intrinsic property of a surface, independent of its isometric embedding in Euclidean space.

<span class="mw-page-title-main">Finite element method</span> Numerical method for solving physical or engineering problems

The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat transfer, fluid flow, mass transport, and electromagnetic potential.

In the finite element method for the numerical solution of elliptic partial differential equations, the stiffness matrix is a matrix that represents the system of linear equations that must be solved in order to ascertain an approximate solution to the differential equation.

The Kansa method is a computer method used to solve partial differential equations. Its main advantage is it is very easy to understand and program on a computer. It is much less complicated than the finite element method. Another advantage is it works well on multi variable problems. The finite element method is complicated when working with more than 3 space variables and time.

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 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.

<span class="mw-page-title-main">Finite volume method for one-dimensional steady state diffusion</span> Scientific Technique

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 easily be derived from the general transport equation for property Φ by deleting transient and convective terms.

<span class="mw-page-title-main">Central differencing scheme</span>

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:

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.

<span class="mw-page-title-main">Finite volume method for two dimensional diffusion problem</span>

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, S2CID   205007680
  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. Dervieux, A.; Thomasset, F. (1980). "A finite element method for the simulation of a Rayleigh-Taylor instability". Approximation Methods for Navier-Stokes Problems. Lecture Notes in Mathematics. Vol. 771. Springer. pp. 145–158. doi:10.1007/BFb0086904. ISBN   978-3-540-38550-9.