Jump to content

Level-set method: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
No edit summary
m added references and fixed grammar
Line 7: Line 7:
[[Image:level set method.png|thumb|right|400px|An illustration of the level-set method]]
[[Image:level set method.png|thumb|right|400px|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 <math>\varphi</math> determining this shape, and the flat blue region represents the ''xy'' plane. The boundary of the shape is then the zero-level set of <math>\varphi</math>, while the shape itself is the set of points in the plane for which <math>\varphi</math> is positive (interior of the shape) or zero (at the boundary).
The figure on the right illustrates several 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 <math>\varphi</math> determining this shape, and the flat blue region represents the ''xy'' plane. The boundary of the shape is then the zero-level set of <math>\varphi</math>, while the shape itself is the set of points in the plane for which <math>\varphi</math> is positive (interior of the shape) or zero (at the boundary).


In the top row, the shape can be seen changing its topology by splitting in two. It would be difficult 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 bottom row, however, the level set function accomplishes this change by translating downward. This is an example of when it can be easier to work with a shape through its level-set function than with the shape directly, where the method would need to consider and handle all the possible deformations the shape might undergo.
In the top row, the shape can be seen changing its topology by splitting in two. It would be difficult 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 bottom row, however, the level set function accomplishes this change by translating downward. This is an example of when it can be easier to work with a shape through its level-set function than with the shape directly, where the method would need to consider and handle all the possible deformations the shape might undergo.
Line 20: Line 20:
Here, <math>|\cdot|</math> is the [[Euclidean norm]] (denoted customarily by single bars in PDEs), and <math>t</math> is time. This is a [[partial differential equation]], in particular a [[Hamilton–Jacobi equation]], and can be solved numerically, for example, by using [[finite difference]]s on a Cartesian grid.<ref name=osher>{{cite book |last=Osher |first=Stanley J. |authorlink = Stanley Osher |author2=Fedkiw, Ronald P. |authorlink2=Ronald Fedkiw |title=Level Set Methods and Dynamic Implicit Surfaces|publisher=[[Springer-Verlag]] |year=2002 |isbn= 978-0-387-95482-0}}</ref><ref name=sethian>{{cite book |last=Sethian |first=James A. |authorlink = James Sethian |title= Level Set Methods and Fast Marching Methods : Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science|publisher=[[Cambridge University Press]] |year=1999 |isbn= 978-0-521-64557-7}}</ref>
Here, <math>|\cdot|</math> is the [[Euclidean norm]] (denoted customarily by single bars in PDEs), and <math>t</math> is time. This is a [[partial differential equation]], in particular a [[Hamilton–Jacobi equation]], and can be solved numerically, for example, by using [[finite difference]]s on a Cartesian grid.<ref name=osher>{{cite book |last=Osher |first=Stanley J. |authorlink = Stanley Osher |author2=Fedkiw, Ronald P. |authorlink2=Ronald Fedkiw |title=Level Set Methods and Dynamic Implicit Surfaces|publisher=[[Springer-Verlag]] |year=2002 |isbn= 978-0-387-95482-0}}</ref><ref name=sethian>{{cite book |last=Sethian |first=James A. |authorlink = James Sethian |title= Level Set Methods and Fast Marching Methods : Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science|publisher=[[Cambridge University Press]] |year=1999 |isbn= 978-0-521-64557-7}}</ref>


The numerical solution of the level-set equation, however, requires sophisticated techniques. Simple finite-difference methods fail quickly. [[Upwinding]] methods, such as the [[Godunov's scheme|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.<ref>{{Citation |last1 = Enright |first1 = D. |last2 = Fedkiw |first2 = R. P.| last3 = Ferziger |first3 = J. H. |authorlink3 = Joel H. Ferziger| last4 = Mitchell |first4 = I.| title = A hybrid particle level set method for improved interface capturing| journal = J. Comput. Phys.| volume = 183 |issue = 1 |year = 2002 |pages = 83&ndash;116| url = http://www.cs.ubc.ca/~mitchell/Papers/myJCP02.pdf |doi=10.1006/jcph.2002.7166|bibcode = 2002JCoPh.183...83E |citeseerx = 10.1.1.15.910}}</ref>
However, numerical solution of the level set equation may require complex techniques. Simple finite difference methods fail quickly. [[Upwind scheme|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 complex methods have been developed to overcome this; for example, combinations of the leveling method with tracking marker particles suggested by the velocity field.<ref>{{Citation |last1 = Enright |first1 = D. |last2 = Fedkiw |first2 = R. P.| last3 = Ferziger |first3 = J. H. |authorlink3 = Joel H. Ferziger| last4 = Mitchell |first4 = I.| title = A hybrid particle level set method for improved interface capturing| journal = J. Comput. Phys.| volume = 183 |issue = 1 |year = 2002 |pages = 83&ndash;116| url = http://www.cs.ubc.ca/~mitchell/Papers/myJCP02.pdf |doi=10.1006/jcph.2002.7166|bibcode = 2002JCoPh.183...83E |citeseerx = 10.1.1.15.910}}</ref>


==Example==
==Example==
Consider a unit circle in <math display="inline">\mathbb{R}^2</math>, 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 normalized gradient of this field will be the circle normal.
Consider a unit circle in <math display="inline">\mathbb{R}^2</math>, 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 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.
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]].
In [[combustion]], this method is used to describe the instantaneous flame surface, known as the [[G equation]].
Line 67: Line 67:
{{NumBlk|:| <math>\rho = (1-I)\rho_1+I\rho_2 \qquad e\qquad v=(1-I)v_1+Iv_2 </math>|{{EquationRef|2}}}}
{{NumBlk|:| <math>\rho = (1-I)\rho_1+I\rho_2 \qquad e\qquad v=(1-I)v_1+Iv_2 </math>|{{EquationRef|2}}}}


where <math>\rho_1</math>, <math>\rho_2</math>, <math>v_1</math> and <math>v_2</math> are the specific mass and kinematic viscosity of fluids 1 and 2. Equation {{EquationNote|2}} can be applied analogously to the other properties of the fluids.
where <math>\rho_1</math>, <math>\rho_2</math>, <math>v_1</math> and <math>v_2</math> are the specific mass and kinematic viscosity of fluids 1 and 2. Equation {{EquationNote|2}} can be applied analogously to the other properties of the fluids.<ref>{{Cite web |title= |url=https://www.airloads.net/Downloads/Textbooks/Computational-Fluid-Dynamics-the-Basics-With-Applications-Anderson-J-D.pdf}}</ref>


==See also==
==See also==

Revision as of 18:40, 15 December 2023

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.

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 easier to follow shapes that change topology, for example, when a shape splits in two, develops holes, or the reverse of these operations. These characteristics make the level-set method an effective method for modeling time-varying objects, like inflation of an airbag, or a drop of oil floating in water.

An illustration of the level-set method

The figure on the right illustrates several 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, the shape can be seen changing its topology by splitting in two. It would be difficult 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 bottom row, however, the level set function accomplishes this change by translating downward. This is an example of when it can be easier to work with a shape through its level-set function than with the shape directly, where the method 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]

However, numerical solution of the level set equation may require complex 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 complex 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 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 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.

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 (CFD)

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 - abbreviated as CompactLSM.

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 is the Heaviside function 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 ().

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, , 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 , , and 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.[6]

See also

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. ^ a b Osher, Stanley J.; Fedkiw, Ronald P. (2002). Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag. ISBN 978-0-387-95482-0.
  3. ^ a b 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.
  6. ^ https://www.airloads.net/Downloads/Textbooks/Computational-Fluid-Dynamics-the-Basics-With-Applications-Anderson-J-D.pdf. {{cite web}}: Missing or empty |title= (help)