Next: Solving the eikonal equation
Up: Fomel: Fast marching
Previous: The theoretic grounds of
In this section, I derive a discrete traveltime computation procedure,
based solely on Fermat's principle, and show that on a Cartesian
rectangular grid it is precisely equivalent to the update formula
(1) of the first-order eikonal solver.
triangle
Figure 3 A geometrical scheme for the
traveltime updating procedure in two dimensions.
|
| |
For simplicity, let us focus on the two-dimensional case. Consider a line segment with the end points A and B,
as shown in Figure 3. Let tA and tB denote the
traveltimes from a fixed distant source to points A and B,
respectively. Define a parameter such that at A,
at B, and changes continuously on the line segment
between A and B. Then for each point of the segment, we can
approximate the traveltime by the linear interpolation formula
| |
(9) |
Now let us consider an arbitrary point C in the vicinity of AB. If
we know that the ray from the source to C passes through some point
of the segment AB, then the total traveltime at C is
approximately
| |
(10) |
where sC is the local slowness, corresponds to the
projection of C to the line AB (normalized by the length |AB|),
and is the length of the normal from C to .
Fermat's principle states that the actual ray to C corresponds to a
local minimum of the traveltime with respect to raypath perturbations.
According to our parameterization, it is sufficient to find a local
extreme of tC with respect to the parameter . Equating the
derivative to zero, we arrive at the equation
| |
(11) |
which has (as a quadratic equation) the explicit solution for :
| |
(12) |
Finally, substituting the value of from (12) into
equation (10) and selecting the appropriate branch of the
square root, we obtain the formula
| |
|
| (13) |
where c = |AB|, a = |BC|, b = |AC|, angle corresponds to , and angle corresponds to
in the triangle ABC (Figure 3).
square
Figure 4 A geometrical scheme for
traveltime updating on a rectangular grid.
|
| |
To see the connection of formula (13) with the eikonal
difference equation (1), we need to consider the case
of a rectangular computation cell with the edge AB being a diagonal
segment, as illustrated in Figure 4. In this case,
, , , and formula (13) reduces to
| |
(14) |
We can notice that (14) is precisely equivalent to the
solution of the quadratic equation (13), which in our
new notation takes the form
| |
(15) |
What have we accomplished by this analysis? First, we have derived a
local traveltime computation formula for an arbitrary grid. The
derivation is based solely on Fermat's principle and a local linear
interpolation, which provides the first-order accuracy. Combined with
the fast marching evaluation order, which is also based on Fermat's
principle, this procedure defines a complete algorithm of
first-arrival traveltime calculation. On a rectangular grid, this
algorithm is exactly equivalent to the fast marching method of
Sethian (1996a) and Sethian and Popovici (1997). Second, the derivation
provides a general principle, which can be applied to derive analogous
algorithms for other eikonal-type (Hamilton-Jacobi) equations and
their corresponding variational principles.
Next: Solving the eikonal equation
Up: Fomel: Fast marching
Previous: The theoretic grounds of
Stanford Exploration Project
9/12/2000