The Fast Marching algorithm uses a first order numerical approximation of the Eikonal equation (5) based on the following operators. Suppose a function u is given with values U j k = u(x j k ) on a 3D Cartesian grid with grid spacing h.
• Forward operator (direction i): D+jk(u) = (ui+1jk -u^)/h
• Backward operator (direction i): D-jk(u) = (ujjk - ui-1jk )/h Forward and backward operators in directions j and k are similar.
The following upwind scheme, originally due to Godunov (Godunov, 1969) and well explained in (Rouy & Tourin, 1992) and in (Sethian, 1999), is used to estimate the gradient Vu in three dimensions:
max(D-i,k (u), D+|,k (u),o)2 + max(D-j,k(u)/Dl+j,k(u)/o)2 = t ij (8)
Was this article helpful?