2

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.

Community
  • 1
lharper71
  • 21
  • 1

1 Answers1

1

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

joeyjoejoejabadu
  • 11
  • 2