5
$\begingroup$

The Fast Marching Method, Fast Iterative Method, and Fast Sweeping Method are three ways of solving the Eikonal Equation on a discrete grid, essentially just a wavefront spreading out from initial points, e.g.:

enter image description here

The idea is that we want to compute the time $T(x, y)$ at which a wavefront, moving across a field with a velocity function $F(x, y)$, reaches each point in a grid, e.g.:

enter image description here

Where walls and such would be represented with $F(x, y)=\epsilon$ for some very small $\epsilon$.

This is good and these methods work very well in practice, however they all apply to fixed size grids.

In many applications, it is better to represent the speed field with some sort of tree, say a quadtree or octree. Areas with a larger tree cell representing them would simply then all have the same speed, though some sort of interpolation may even be possible. This can be interpreted by saying that we desire "higher resolution" results in some areas with a higher tree density, and "lower resolution" results in some areas with a lower tree density. Either way, is it possible to apply these methods (or methods like them) for solving $T(x, y)$ using a speed field $F(x, y)$ represented with some kind of a tree?

Trivially, I know you could simply find the "lowest resolution" of your tree - IE the smallest cell - then transform each larger cell into these smaller cells as the algorithm runs over them, but this seems far less than optimal, and kinda defeats the point of a tree in the first place. Thus, is there a better way to do this?

It seems pretty clear that the goal would be to have a $T(x, y)$ field that is also represented in the same kind of tree that $F(x, y)$ is represented in, to give similar density results, however I don't know if that's the best way to think about it either. More specifically $T(x, y)$ would probably end up being some kind of form where inner points (if we were trying to recreate the fixed-size discrete grid) are interpolations between the corners of the tree grid, but this is also essentially what it's doing anyway in order to map a discrete grid answer to a continuous one, so I don't feel like that's too big of a concern.

Really, this question was just motivated because current implementations of an Eikonal Equation solver are slow, for two reasons:

  1. The dependencies each grid cell has on its neighbor's results. Something like the Fast Iterative Method makes them essentially less "tied together" so some level of parallelization is possible, but I'm wondering if there would be some way to further split up the work into independent grid cells that possibly derive results dependent on their neighbor values which will eventually be computed. This is sort of a side-note but I feel like the tree aspect may be tied into it due to how "low density" results would have to be smoothly approximated by "higher density" neighbors. This gets into point two:

  2. The current methods compute the same accuracy for all points in the grid. In many situations good accuracy is only needed for specific portions of the map, so it would be nice if it were possible to "split up" the work into sections of desired high resolution results and sections of desired low resolution results. Doing that using some kind of a tree doesn't seem that straightforward with the current methods of solving this equation though.

$\endgroup$
4
$\begingroup$

This may not be your definitive solution, but what you need in any case is to change the discretization method that replace the continuous Eikonal equation with some discrete numerical scheme on the grid. The classical methods like fast marching method etc. are based mostly on the Rouy-Tourin scheme.

In the work of Gibou and Min you can find the discretization methods on quadtree or octree data structures for level set equations, my quick search gave me:

http://www.math.lsa.umich.edu/~psmereka/LEVELSET/LSPAPERS/min_gibou.pdf

In that paper they solve the Eikonal equation for so called reinitialization purpose, but they do not use any kind of fast method. May be you can learn how to obtain the numerical scheme on your grid and then the fast sweeping method could be applied.

At least this may be a direction where to look for a solution of your problem.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! It looks like I have a lot of learning to do, so I'll get back to this once I understand the level set methods in more detail, because they seem like a good direction to go. $\endgroup$ – Phylliida Apr 15 '15 at 15:15
  • $\begingroup$ Specifically I found this textbook if anyone else is interested in learning about these as well. $\endgroup$ – Phylliida Apr 15 '15 at 16:13

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.