## Improved Velocity Extensions

The velocity extension method currently in common usage was described in Section 4.2.5, and can be attributed to [3]. However, as noted in [23], the velocity extension characteristics are not supposed to be the straight line extensions that are currently constructed. While it is true that VF ■ V<p = 0 should hold at the initial interface, it does not necessarily hold off the interface.

As an example of what can happen with the current velocity extension method, consider the example of an interface consisting of two circles, with the left circle having speed 1, and the right circle having speed 2 (see Fig. 4.13). The current velocity extension method is such that the left half-plane will have F = 1, and the right half-plane will have F = 2, with the break indicated by the dashed line in Fig. 4.13. The evolution makes a clear error when the right circle expands to the dividing line. Once the circle crosses that line, the velocity extension incorrectly changes the speed from 2 to 1. By noting the gap between successive contours, it is clear that the right-hand circle has slowed down on the left side. The reason that the velocity extension in Fig. 4.13 failed is because the characteristics of the problem were not respected. Once the interface crossed the center line, the velocity came from the left circle, while the characteristics came from the right circle. Ultimately, this happened because the velocity extension was done independent of, and prior to, the actual evolution.

Figure 4.12: A contour map of the distance from the origin on the manifold 2 = 3 sin(3^x) sin(3^ y), computed using the ordered upwind method. Reprinted with permission from [101].

Figure 4.12: A contour map of the distance from the origin on the manifold 2 = 3 sin(3^x) sin(3^ y), computed using the ordered upwind method. Reprinted with permission from [101].

The solution is to do both the fast marching method with the velocity extension at the same time:

The discretization of these two equations is the same as before, but the solution method requires some explanation. Again, suppose the values of \$ and F are already determined at xi_i,j and xij+i. Then Eqs. 4.40 and 4.41 become

Fti ((D-faj )2 + (D+faj )2) = 1, (D- F,j )(D-faj ) + ( D+Fj )(D+faj ) = 0.

These equations correspond to Eqs. 4.22 and 4.34 respectively, where the unknowns are Fi j and \$i j, and the remainder of the terms are known. This pair

Figure 4.13: Example of two circles expanding using the current velocity extension method.

of equations results in a quartic polynomial in F, j which can be solved using a Newton solver or by a direct quartic polynomial solver. Once F^ j is computed, the value of j is easily computed from Eq. 4.43.

The initialization of this method uses a similar bicubic representation as was discussed in Section 4.2.3. The initialization process is based upon the following theorem from [23], and illustrated in Fig. 4.14:

Theorem 1. Suppose F = {(x, y) : ax + by = c} and F0(x, y) = dx + ey + f for (x, y) e F with F0 not identically zero on T, then the equations

lines of constant 9

lines of constant 9

solution.

= F0(x, y), have a solution of the form r db — ea t----

X(x, y) = (x — A) — (y — B), (4.48) Va2 + b2 Va2 + b2

F (x, y) = (x — A) + J^ ( y — B) (4.49) Va2 + b2 Va2 + b2

and where A = ec+f, B = The solution is valid in the set R2 \ L, where ae—bd bd—ae v '

L is an arbitrary line passing through the point (A, B).

If db — ea = 0, then F0(x, y) = F0 is constant on r, and the solution becomes

valid on all R2.

Given an initial piece of the interface, the interface is approximated using a linear function, and also the speed, F, along the interface uses a linear approximation. The linear approximation allows the solutions in the theorem to apply, where it is observed that the characteristics travel in circles with varying speed F, and the linear approximation of F designates a center of rotation, (A, B), depending on where F crosses zero. This leads to a generalized form of Eq. 4.28:

Note that Eq. 4.28 is recovered if VF = 0 is assumed. Equations 4.27 and 4.52 are solved in the same manner as described in Section 4.2.3.

Using the modified velocity extension method on the earlier two-circle example produces the correct results as shown in Fig. 4.15.

Another example that illustrates the difference between the two velocity extension methods is given by an initial circle, with F varying linearly with respect to x, and near zero on the left side. The largest difference between the two methods can be seen on the side where F is small. In the old method,

Figure 4.15: Two-circle example with the modified velocity extension method.

Figure 4.15: Two-circle example with the modified velocity extension method.

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Figure 4.16: Comparison of the old (left) and new (right) velocity extension methods.

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Figure 4.16: Comparison of the old (left) and new (right) velocity extension methods.

the interface slows down when it approaches the left side, while with the new method the interface wraps around and merges. The two solutions are shown side by side in Fig. 4.16. The characteristics for this example, represented by the lines of constant F, are shown in Fig. 4.17, illustrating the analogous solution as computed in the theorem. Note how the lines of constant F are orthogonal to the lines of constant 0, as a result of solving Eq. 4.41.