The Fast Iterative Method is a way of solving the Eikonal Equation on a discrete grid, similar to the Fast Marching Method discussed in another question here.

The paper describes the overall algorithm, as well as providing a method for solving the quadratic, as follows:

SolveQuadratic(a, b, c, f)

Returns the value $u = Ux$ that solves $g(U, x) = 0$, where $a ≤ b ≤ c$

u ← c + 1/f
if u ≤ b return (u)
u ← (b + c + sqrt(−b^2 − c^2 + 2bc + 2/f^2))/2
if u ≤ a return (u)
u ← (2(a + b + c) + sqrt(4(a + b + c)^2 − 12(a^2 + b^2 + c^2 − 1/f^2)))/6
return (u)

That's easy enough to implement, as is the rest of the FIM algorithm. However, I'm unclear what the inputs $a, b, c$ are in the context of the problem (I do understand how to get $f$, though, I think). They are descried as "values $a, b, c$ of upwind neighbors in the cardinal directions of the grid".

I only need to solve in a 2-dimensional grid, so I believe I only need $f$ plus two inputs, and would drop the second test-and-recalculate step above, but I still need $b, c$.

I should note that I'm not a strong maths person; I have a BSc in Comp. Sci. but my maths skills are first-year / freshman level at best, and rusty...

Any pointers would be appreciated.


you have a 6-connected neighbourhood. Say a,b,c,d,e,f are the neighbour values. And (a,e) are in x direction, (b,e) are in y direction and (c,f) are in z direction. As your wavefront never changes the sign of its speed, the upwind-neighbourhood are those points with smaller values, that is a


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.