Level-set method: Difference between revisions

Revision as of 09:13, 2 February 2024

Latest revision as of 06:19, 21 January 2025

(31 intermediate revisions by 29 users not shown)

Line 1:

{{Short description|Conceptual framework used in numerical analysis of surfaces and shapes}}

{{Tone|date=December 2023}}

[[File:Levelset-mean-curvature-spiral.ogv|thumb|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 methodsmethod''' ('''LSM''') constituteis a conceptual framework for using [[level set]]s as a tool for the [[numerical analysis]] of [[Surface (topology)|surface]]s and [[shape]]s. Invented in 1988 by Osher and Sethian, the key advantage of LSM iscan itsperform ability to perform[[Numerical computation|numerical computations]] involving [[curve]]s and surfaces on a fixed [[Cartesian grid]] without having to [[Parametric surface|parameterize]] these objects (this is called the ''Eulerian approach'').<ref>{{Citation |last1 = Osher |first1 = S. |last2 = Sethian |first2 = J. A.| title = Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton–Jacobi formulations| journal = J. Comput. Phys.| volume = 79 |issue = 1 |year = 1988 |pages = 12&ndash;49 |url = http://math.berkeley.edu/~sethian/Papers/sethian.osher.88.pdf |doi=10.1016/0021-9991(88)90002-2|bibcode = 1988JCoPh..79...12O |hdl = 10338.dmlcz/144762 |citeseerx = 10.1.1.46.1266|s2cid = 205007680 }}</ref> Importantly, LSM makes it easier to followperform computations on shapes with sharp corners orand [[Shape|shapes]] that change [[topology]], for(such example,as when a shapeby splitssplitting in two, develops holes, or thedeveloping reverse of these operationsholes). These characteristics make LSM an effective method for [[modeling]] objects that vary in time-varying objects, likesuch inflation ofas an [[airbag]], inflating or a drop of oil floating in water.

[[Image:level set method.png|thumb|right|400px|An illustration of the level-set method]]

== Overview ==

The figure on the right illustrates several ideas about LSM. 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 ''X-Y'' 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's cantopology bechanges seenas changingit itsis topology by splittingsplit in two. It would beis difficultchallenging to describe this transformation numerically by [[Parametrization (geometry)|parameterizing]] the boundary of the shape and following its evolution. One would need anAn algorithm tocan be ableused 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 accomplishesis thissampled changeis bytranslated translatingupwards, downward.on Thiswhich isthe anshape's examplechange ofin whentopology itis candescribed. beIt is less easierchallenging to work with a shape through its level-set function rather than with the shapeitself directly, wherein thewhich a 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]] <math>\Gamma</math> (such as the shape boundary in our example) using an [[auxiliary function]] <math>\varphi</math>, called the level-set function. The curve <math>\Gamma</math> is represented as the zero-level set of <math>\varphi</math> by

:<math>\Gamma = \{(x, y) \mid \varphi(x, y) = 0 \},</math>

and the level-set method manipulates <math>\Gamma</math> ''implicitly'' through the function <math>\varphi</math>. This function <math>\varphi</math> is assumed to take positive values inside the region delimited by the curve <math>\Gamma</math> and negative values outside.<ref name="osher" /><ref name="sethian" />

==The level-set equation==

If the curve <math>\Gamma</math> moves in the normal direction with a speed <math>v</math>, then by chain rule and implicit differentiation, weit getcan be determined that the level-set function <math>\varphi</math> satisfies the ''level-set equation''

:<math>\frac{\partial\varphi}{\partial t} = v|\nabla \varphi|.</math>

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

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

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 normalnormally 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 ==

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

*In mathematical modeling of [[combustion]], this methodLSM is used to describe the instantaneous flame surface, known as the [[G equation]].

A number of *[[level set (data structures)|levelLevel-set data structures]] have been developed to facilitate the use of the level-set method in computer applications.

* [[Computational fluid dynamics]]

* [[Trajectory|Trajectory planning]]

* [[Mathematical optimization|Optimization]]

* [[Image processing]]

* [[Computational biophysics]]

* Discrete [[complex dynamics]]: (visualization of the [[b:Fractals/Iterations in the complex plane/Mandelbrot set|parameter plane]] and the [[b:Fractals/Iterations in the complex plane/Julia set|dynamic plane]])

==History==

The level-set method was developed in 1979 by Alain Dervieux,<ref>{{cite book |last1=Dervieux |first1=A. |last2=Thomasset |first2=F. |chapter=A finite element method for the simulation of a Rayleigh-Taylor instability |chapter-url= |title=Approximation Methods for Navier-Stokes Problems |publisher=Springer |series=Lecture Notes in Mathematics |volume=771 |date=1980 |isbn=978-3-540-38550-9 |pages=145–158 |doi=10.1007/BFb0086904}}</ref> 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 (mathematics)|optimization]], [[computational fluid dynamics]], and [[computational biology]].

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

==Applications==

* [[Computational fluid dynamics]]

* [[Combustion]]

* [[Trajectory|Trajectory planning]]

* [[Mathematical optimization|Optimization]]

* [[Image processing]]

* [[Computational biophysics]]

* Discrete [[complex dynamics]]: visualization of [[b:Fractals/Iterations in the complex plane/Mandelbrot set|parameter plane]] and [[b:Fractals/Iterations in the complex plane/Julia set|dynamic plane]]

==See also==

{{Div col|colwidth=20em}}

* [[Contour boxplot]]

* [[Zebra striping (computer graphics)analysis]]

* [[G equation]]

* [[Advanced Simulation Library]]

* [[Volume of fluid method]]

* [[Image segmentation#Level-set methods]]

* [[Immersed boundary method]]s

* [[Stochastic Eulerian Lagrangian method]]s

* [[Level set (data structures)]]

* [[Posterization]]

Line 61 ⟶ 58:

==External links==

* See [[Ronald Fedkiw]]'s [http://graphics.stanford.edu/~fedkiw/ academic web page] for many stunning pictures and animations showing how the level-set method can be used to model real-life phenomena, like fire, water, cloth, fracturing materials, etc.

* [http://vivienmallet.net/fronts/ Multivac] is a C++ library for front tracking in 2D with level-set methods.

* [[James Sethian]]'s [http://math.berkeley.edu/~sethian/ web page] on level-set method.

Line 74 ⟶ 71:

[[Category:Computational fluid dynamics]]

[[Category:Articles containing video clips]]

[[Category:Implicit surface modeling]]