Level-set method: Difference between revisions

Revision as of 17:12, 10 June 2024

Latest revision as of 06:14, 30 August 2025

(6 intermediate revisions by 6 users not shown)

Line 1:

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

{{Tone|date=June 2024}}

[[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 method''' ('''LSM''') is a conceptual framework for using [[level set]]s as a tool for [[numerical analysis]] of [[Surface (topology)|surface]]s and [[shape]]s. LSM can perform [[Numerical computation|numerical computations]] involving [[curve]]s and surfaces on a fixed [[Cartesian grid]] without having to [[Parametric surface|parameterize]] these objects.<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> LSM makes it easier to perform computations on shapes with sharp corners and [[Shape|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.

Line 8 ⟶ 6:

== 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 <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 topology changes as it is split in two. It is challenging to describe this transformation numerically by [[Parametrization (geometry)|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 downwardsupwards, 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]] <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" />

Line 50 ⟶ 48:

* [[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 ⟶ 59:

==External links==

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

* [http://vivienmallet.net/fronts/ Multivac]{{Dead link|date=August 2025 |bot=InternetArchiveBot |fix-attempted=yes }} 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.

* [[Stanley Osher]]'s [https://www.math.ucla.edu/~sjo/ homepage].

Line 73 ⟶ 71:

[[Category:Computational fluid dynamics]]

[[Category:Articles containing video clips]]

[[Category:Implicit surface modeling]]