Content deleted Content added
GraziePrego (talk | contribs) Tagging for tone, references to "we see", and describing techniques as "great" |
Eatingbugs (talk | contribs) mNo edit summary |
||
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.]]
'''Level-set methods''' ('''LSM''') are a conceptual framework for using [[level set]]s as a tool for [[numerical analysis]] of [[Surface (topology)|surface]]s and [[shape]]s. The advantage of the level-set model is that one can perform 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–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}}</ref> 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.
[[Image:level set method.png|thumb|right|400px|An illustration of the level-set method]]
Line 13 ⟶ 9:
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).
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.
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. <math>\Gamma</math> is represented as the zero-
:<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>.
==The level-set equation==
If the curve <math>\Gamma</math> moves in the normal direction with a speed <math>v</math>, then 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 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. |
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–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 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.
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,<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
▲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 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.
==
* Computational fluid dynamics
* Combustion
Line 59 ⟶ 43:
* Discrete [[complex dynamics]]: visulalisation of [[b:Fractals/Iterations in the complex plane/Mandelbrot set|parameter plane]] and [[b:Fractals/Iterations in the complex plane/Julia set|dynamic plane]]
==
{{unreferenced section|date=August 2022}}
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.
Line 108 ⟶ 91:
* [[James Sethian]]'s [http://math.berkeley.edu/~sethian/ web page] on level-set method.
* [[Stanley Osher]]'s [https://www.math.ucla.edu/~sjo/ homepage].
* [https://math.mit.edu/classes/18.086/2007/levelsetpres.pdf The Level Set Method. MIT 16.920J / 2.097J / 6.339J.
{{Numerical PDE}}
| |||