Level-set method

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.

Lumbung was started by Andri Saputra in 2010. Andri studied architecture at the Udayana University between 2004-2008. Upon graduation, he worked with three architecture consultants in Bali to develop experience and knowledge in both western and local architectural practices. Then he also worked and traveled with senior foreign architects from France and Australia for the next 3 years. Afterward, Andri Saputra decided to establish his first architectural firm in 2010, Studio Lumbung Architect. Lumbung Architect is based in Bali and it has around 60 staff employed. They currently have completed projects throughout Bali, Jakarta, Nigeria, and the Bahamas. By recruiting the professional team in his field which includes a team of architects, structural engineers, quantity surveyors, mechanical, electrical, and plumbing engineers, Lumbung Architect strives to provide an excellent solution for the client’s need.

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 $\varphi$ 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 $\varphi$ , while the shape itself is the set of points in the plane for which $\varphi$ 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 to be 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 $\Gamma$ (such as the shape boundary in our example) using an auxiliary function $\varphi$ , called the level-set function. The curve $\Gamma$ is represented as the zero-level set of $\varphi$ by

\Gamma =\{(x,y)\mid \varphi (x,y)=0\},

and the level-set method manipulates $\Gamma$ implicitly through the function $\varphi$ . This function $\varphi$ is assumed to take positive values inside the region delimited by the curve $\Gamma$ and negative values outside.^[1]^[2]

The level-set equation

If the curve $\Gamma$ moves in the normal direction with a speed $v$ , then by chain rule and implicit differentiation, we get that the level-set function $\varphi$ satisfies the level-set equation

{\frac {\partial \varphi }{\partial t}}=v|\nabla \varphi |.

Here, $|\cdot |$ is the Euclidean norm (denoted customarily by single bars in partial differential equations), and $t$ 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.^[1]^[2]

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.^[3]

Example

Consider a unit circle in ${\textstyle \mathbb {R} ^{2}}$ , 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,^[4] 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
Combustion
Trajectory planning
Optimization
Image processing
Computational biophysics
Discrete complex dynamics: visualization of parameter plane and dynamic plane

References

^ ^a ^b Osher, Stanley J.; Fedkiw, Ronald P. (2002). Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag. ISBN 978-0-387-95482-0.
^ ^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.
^ 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
^ 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.

External links

See Ronald Fedkiw's 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.
Multivac is a C++ library for front tracking in 2D with level-set methods.
James Sethian's web page on level-set method.
Stanley Osher's homepage.
The Level Set Method. MIT 16.920J / 2.097J / 6.339J. Numerical Methods for Partial Differential Equations by Per-Olof Persson. March 8, 2005
Lecture 11: The Level Set Method: MIT 18.086. Mathematical Methods for Engineers II by Gilbert Strang

[osher-1] Osher, Stanley J.; Fedkiw, Ronald P. (2002). Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag. ISBN 978-0-387-95482-0.

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

[3] 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

[4] 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.

[1]

[2]

[3]

[4]