Level Set Methods and Dynamic Implicit Surfaces

In one spatial dimension, suppose we divide the real line into three distinct pieces using the points x = -1 and x = 1. That is, we define (-∞, -1), (-1, 1), and (1, ∞) as three separate subdomains of interest, although we regard the first and third as two disjoint pieces of the same region. We refer to Ω^- = (-1, 1) as the inside portion of the domain and Ω⁺ = (-∞, -1) ∪ (1, ∞) as the outside portion of the domain. The border between the inside and the outside consists of the two points ∂Ω = {-1, 1} and is called the interface. In one spatial dimension, the inside and outside regions are one-dimensional objects, while the interface is less than one-dimensional. In fact, the points making up the interface are zero-dimensional. More generally, in ℜ ⁿ , subdomains are n-dimensional, while the interface has dimension n - 1. We say that the interface has codimension one.

In the last chapter we defined implicit functions with φ(x↦) ≤ 0 in the interior region Ω^-, φ((x↦) > 0 in the exterior region Ω⁺, and φ((x↦) = 0 on the boundary ∂Ω. Little was said about φ otherwise, except that smoothness is a desirable property especially in sampling the function or using numerical approximations. In this chapter we discuss signed distance functions, which are a subset of the implicit functions defined in the last chapter. We define signed distance functions to be positive on the exterior, negative on the interior, and zero on the boundary. An extra condition of |∇φ(x↦)| = 1 is imposed on a signed distance function.

Suppose that the velocity of each point on the implicit surface is given as V↦(V↦); i.e., assume that V↦(V↦) is known for every point (V↦ with φ(V↦) = 0. Given this velocity field V↦ = (u, v, w), we wish to move all the points on the surface with this velocity. The simplest way to do this is to solve the ordinary differential equation (ODE) for every point V↦ on the front, i.e., for all V↦ with φ(V↦) = 0. This is the Lagrangian formulation of the interface evolution equation. Since there are generally an infinite number of points on the front (except, of course, in one spatial dimension), this means discretizing the front into a finite number of pieces. For example, one could use segments in two spatial dimensions or triangles in three spatial dimensions and move the endpoints of these segments or triangles. This is not so hard to accomplish if the connectivity does not change and the surface elements are not distorted too much. Unfortunately, even the most trivial velocity fields can cause large distortion of boundary elements (segments or triangles), and the accuracy of the method can deteriorate quickly if one does not periodically modify the discretization in order to account for these deformations by smoothing and regularizing inaccurate surface elements.

In the last chapter we discussed the motion of an interface in an externally generated velocity field V↦(x↦, t). In this chapter we discuss interface motion for a self-generated velocity field (x↦ that depends directly on the level set function φ. As an example, we consider motion by mean curvature where the interface moves in the normal direction with a velocity proportional to its curvature; i.e., V↦ = -bκN↦, where b > 0 is a constant and κ is the curvature. When b > 0, the interface moves in the direction of concavity, so that circles (in two dimensions) shrink to a single point and disappear. When b < 0, the interface moves in the direction of convexity, so that circles grow instead of shrink. This growing-circle effect leads to the growth of small perturbations in the front including those due to round-off errors. Because b < 0 allows small erroneous perturbations to incorrectly grow into 0(1) features, the b < 0 case is ill-posed, and we do not consider it here. Figure 4.1 shows the motion of a wound spiral in a curvature-driven flow. The high-curvature ends of the spiral move significantly faster than the relatively low curvature elongated body section. Figure 4.2 shows the evolution of a star-shaped interface in a curvature-driven flow. The tips of the star move inward, while the gaps in between the tips move outward.

In this chapter we discuss numerical methods for the solution of general Hamilton-Jacobi equations of the form where H can be a function of both space and time. In three spatial dimensions, we can write as an expanded version of equation (5.1). Convection in an externally generated velocity field (equation (3.2)) is an example of a Hamilton-Jacobi equation where H(∇φ) = 0056;↦ ·∇φ. The level set equation (equation (4.4)) is another example of a Hamilton-Jacobi equation with H(∇φ) = V _n |∇φ| Here V _n can depend on 0078;↦, t, or even ∇φ /|∇φ|.

In this chapter we discuss the motion of an interface under an internally generated velocity field for constant motion in the normal direction. This velocity field is defined by V↦ = a N↦ or V _n = a, where a is a constant. The corresponding level set equation (i.e., equation (4.4)) is where a can be of either sign. When a > 0 the interface moves in the normal direction, and when a < 0 the interface moves opposite the normal direction. When a = 0 this equation reduces to the trivial φ _t = 0, where φ is constant for all time. Figure 6.1 shows the evolution of a star-shaped interface as it moves normal to itself in the outward direction.

As we have seen, a number of simplifications can be made when φ is a signed distance function. For this reason, we dedicate this chapter to numerical techniques for constructing approximate signed distance functions. These techniques can be applied to the initial data in order to initialize φ to a signed distance function.

In the last chapter we constructed signed distance functions by following characteristics that flow outward from the interface. Similar techniques can be used to propagate information in the direction of these characteristics. For example, (8.1) is a Hamilton-Jacobi equation (in S) that extrapolates S normal to the interface, i.e. so that S is constant on rays normal to the interface. Since \( H\left( {\nabla S} \right) = \overrightarrow N \cdot \nabla S \), we can solve this equation with the techniques presented in Chapter 5 using H ₁ = n₁, H ₂ = n₂, and H ₃ = n ₃ .

The great success of level set methods can in part be attributed to the role of curvature in regularizing the level set function such that the proper vanishing viscosity solution is obtained. It is much more difficult to obtain vanishing viscosity solutions with Lagrangian methods that faithfully follow the characteristics. For these methods one usually has to delete (or add) characteristic information “by hand” when a shock (or rarefaction) is detected. This ability of level set methods to identify and delete merging characteristics is clearly seen in a purely geometrically driven flow where a curve is advected normal to itself at constant speed, as shown in Figures 9.1 and 9.2. In the corners of the square, the flow field has merging characteristics that are appropriately deleted by the level set method. We demonstrate the difficulties associated with a Lagrangian calculation of this interface motion by initially seeding some marker particles interior to the interface, as shown in Figure 9.3 and passively advecting them with \( {\overrightarrow x_t} = \overrightarrow V \left( {\overrightarrow x, t} \right) \) where the velocity field V↦(x↦ t) is determined from the level set solution. Figure 9.4 illustrates that a number of particles incorrectly escape from inside the level set solution curve in the corners of the square where the characteristic information (represented by the particles themselves) needs to be deleted so that the correct vanishing viscosity solution can be obtained.

Typically, level set methods are used to model codimension-one objects such as points in ℜ¹, curves in ℜ², and surfaces in ℜ³. Burchard, Cheng, Merriman, and Osher [22] extended level set technology to treat codimension-two objects using the intersection of the zero level sets of two level set functions. That is, instead of implicitly representing codimension-one geometry by the zero isocontour of a function φ, codimension-two geometry is represented as the intersection of the zero isocontour of a function φ₁ with the zero isocontour of another function φ_2. In one spatial dimension, zero isocontours are points, and their intersection is usually the empty set. In two spatial dimensions, zero isocontours are curves, and the intersections of curves tend to be points which are of codimension two. In three spatial dimensions, the zero isocontours are surfaces, and the intersections of these surfaces tend to be codimension two curves.

A basic idea in this field is to view a gray-scale image as a function u ₀ (x, y) defined on a square Ω,: {(x,y)|0 ≤ x,y ≤ 1}, with u₀ taking on discrete values between 0 and 255, which we take as a continuum for the sake of this discussion.

The basic idea in active contour models (or snakes) is to evolve a curve, subject to constraints from a given image u ₀, in order to detect objects in that image. Ideally, we begin with a curve around the object to be detected, and the curve then moves normal to itself and stops at the boundary of the object. Since its invention by Kass et al. [94] this technique has been used both often and successfully. The classical snakes model in [94] involves an edge detector, which depends on the gradient of the image u ₀, to stop the evolving curve at the boundary of the object.

Surface reconstruction from an unorganized data set is very challenging. The problem is ill-posed, i.e., there is no unique solution. Furthermore, the ordering or connectivity of the data set and the topology of the real surface can be rather complicated. A desirable reconstruction procedure should be able to deal with complicated topology and geometry as well as noise and nonuniformity of the data to construct a surface that is a good approximation of the data set and has some smoothness (regularity). Moreover, the reconstructed surface should have a representation and data structure that is not only good for static rendering but also good for deformation, animation, and other dynamic operations on surfaces.

We begin this chapter by addressing general systems of hyperbolic conservation laws including numerical techniques for computing accurate solutions to them. Then we discuss the equations for one-phase compressible flow as an example of a system of hyperbolic conservation laws.

Chronologically, the first attempt to use the level set method for flows involving external physics was in the area of two-phase inviscid compressible flow. Mulder et al. [115] appended the level set equation to the standard equations for one-phase compressible flow, equation (14.47). Here V↦ is taken to be the velocity of the compressible flow field, so that the zero level set of φ corresponds to particle velocities and can be used to track an interface separating two different compressible fluids. The sign of φ is used to identify which gas occupied which region, i.e., to determine the local equation of state. In [115], only gamma law gas models were considered, with γ = γ₁ for φ > 0 and γ = γ₂ for φ ≤ 0. Later, Karni [93] pointed out that this method suffered from spurious oscillations at the interface. Figure 15.1 shows a sample calculation using the method proposed in [115]. Here a right going shock wave impinges upon the interface, producing both reflected and transmitted shock waves. Note the spurious oscillations in both the pressure and the velocity profiles near the centrally located contact discontinuity that separates the two different gamma-law gases.

For a contact discontinuity we separated the variables into two sets based on their continuity across the interface. The continuous variables were copied into the ghost fluid in a node-by-node fashion, capturing the correct interface values, while the discontinuous variables were extrapolated in a one-sided fashion to avoid numerical dissipation errors. In order to apply this idea to a general interface moving at speed D in the normal direction, we need to correctly determine the continuous and discontinuous variables across the interface. For example, consider a shock wave where all variables are discontinuous, and extrapolation of all variables for both the preshock and postshock fluids obviously gives the wrong answer, since the physical coupling is ignored. We generally state, For each degree of freedom that is coupled across a discontinuity, one can define a variable that is continuous across the discontinuity, and all remaining degrees of freedom can be expressed as discontinuous variables that can be extrapolated across the discontinuity in a one-sided fashion, as the key to extending the GFM. For the Euler equations, conservation of mass, momentum, and energy can be applied to any discontinuity in order to abstract continuous variables; i.e., the Rankine-Hugoniot jump conditions always dictate the coupling between the prediscontinuity and postdiscontinuity fluids. This idea was proposed by Fedkiw et al.

Solid-fluid interaction problems are still rather difficult for modern computational methods. In general, there are three classical approaches to such problems: One can treat both the solid and the fluid with Eulerian numerical methods, the fluid with an Eulerian numerical method and the solid with a Lagrangian numerical method, or both the solid and the fluid with Lagrangian numerical methods.

Starting from conservation of mass, momentum, and energy, the equations for incompressible flow are derived using the divergence-free condition ∇ • V↦ = 0, which implies that there is no compression or expansion in the flow field. The equation for conservation of mass becomes indicating that the (possibly spatially varying) density is advected along streamlines of the flow. The Navier-Stokes equations for viscous incompressible flow are where μ is the viscosity and g is the acceleration of gravity. These equations are more conveniently written in condensed notation as a row vector where “T” is the transpose operator, g↦ = <0, g, 0>, and τ is the viscous stress tensor which can be expressed in a more compact form as

Consider a two-phase incompressible flow consisting of water and air. The two phase interface separating these fluids has rather complicated dynamics that we will discuss later (in Chapter 21). In many situations the behavior of the heavier fluid significantly dominates the behavior of the lighter fluid. In these situations, the model can be simplified by treating the air as a simple constant-pressure fluid that exerts no other stress (i.e., except pressure forces) on the interface. This removes any relevant dynamic effects from the air, leaving only a simple uniform pressure force normal to the interface independent of the interface topology or motion.

Liquid-gas interactions, e.g., the vaporization and subsequent combustion of liquid fuel droplets or the shock-induced mixing of liquids, are rather difficult problems in computational fluid dynamics. These problems address the interaction of liquid droplets with a compressible gas medium. There are three classical approaches to such problems: Both phases can be treated as compressible fluids (as we did in Chapter 15), both phases can be treated as incompressible fluids (as we did in Chapter 21), or the gas can be treated as a compressible fluid while the liquid is treated as an incompressible fluid. A completely incompressible treatment can be ruled out any time one is interested in shock waves or other compressible phenomena. A completely compressible treatment is not desirable, since a relatively high sound speed in the liquid phase can impose a restrictive (and inefficient) CFL condition. Moreover, a completely compressible approach is limited to liquids for which there are acceptable models for their compressible evolution. To overcome these difficulties, Caiden et al. [23] modeled the gas as a compressible fluid and the liquid as an incompressible fluid. They coupled a high-resolution shock-capturing scheme for the compressible gas flow to a standard incompressible flow solver for the liquid phase.

The earliest real success in the coupling of the level set method to problems involving external physics came in computing two-phase incompressible flow, in particular see the work of Sussman et al. [160] and Chang et al. [38]. In two-phase incompressible flow, the Navier-Stokes equations are used to model the fluids on both sides of the interface. Generally, the fluids have different densities and viscosities, so these quantities are discontinuous across the interface. Both the discontinuous viscosity and surface tension forces cause the pressure to be discontinuous across the interface as well. In addition, a discontinuous viscosity leads to kinks in the velocity field across the interface.

In Chapter 21 the interface moved with the local fluid velocity only, and individual fluid particles did not cross the interface. In this chapter we consider interfaces across which a chemical reaction is converting one incompressible fluid into another. The interface moves with the local velocity of the unreacted fluid plus a reaction term that accounts for the conversion of one fluid into the other as material moves across the interface. Consider an interface separating liquid and gas regions where the liquid is actively vaporizing into the gaseous state. Juric and Tryg-gvason [90] developed a front-tracking approach to this problem using a δ-function formulation to treat the interface boundary conditions. Son and Dir [153] and Welch and Wilson [171] developed level-set-based and volume-of-fluid-based (respectively) approaches to this same problem also using a δ-function formulation.

Starting from conservation of mass, momentum, and energy one can derive where k is the thermal conductivity and T is the temperature. Assuming that e depends on at most temperature, and that the specific heat at constant volume,c _v is constant leads to e = e ₀ + c _v (T - T ₀ ), where e ₀ is the internal energy per unit mass at some reference temperature T ₀ (see, for example, Atkins [10]). This and the incompressibility assumption ∇ • V↦ = 0 simplify equation (23.1) to which can be further simplified to the standard heat equation by ignoring the effects of convection, i.e., settingV↦ = 0.