The flex gridding algorithm

Flex gridding uses a system of differential equations whose solution yields the values of grid nodes that meet the following two criteria:

1. The interpolated surface must pass through, or at least very close to, the data in the XYZ space.

2. As much as possible without violating criterion 1, the surface must fit a mathematical criterion selected by the user:

   • Minimum Tension or rubber sheet—the surface must be tightly stretched over the data. Visualize a rubber sheet with a grommet at each grid node, stretched over a set of posts through each grommet. When a node has data, the grommet is nailed to the post at the level of the datum. The other grommets slide up or down their posts under the tension of the stretched rubber; the rubber sheet will relax to the position where its overall tension is minimized. The function that gives the solution for one grid node is called the LaPlacian operator, named for the LaPlacian equation that it solves.

   • Minimum Curvature or as smooth as possible—the RMS curvature of the surface shall be as small as possible. Visualize, instead of the rubber sheet, a thin sheet of spring steel that will relax to the smoothest surface it can when grommets with data are nailed to their posts; the surface will relax to the position where the overall curvature is minimized. The function that gives the solution for one grid node is called the “biharmonic operator”, named for the “biharmonic equation” that it solves.

   • A blend of a and b—the operator used is a weighted blend of the biharmonic and LaPlacian operators.

Because a simultaneous solution of all the equations is computationally intractable, an iterative solution is used. Each of the equations applies to one grid node and has terms that include just a dozen of its neighbors. Thus they are all coupled together, but the coupling to distant nodes is weak and indirect. For this reason, each equation is solved to yield a grid value, assuming the neighboring nodes are constant. As the other nodes change, this process is repeated. With an infinite number of iterations, the grid will converge to the desired solution, but in practice we get a good result with far fewer iterations.

Because the filters apply a local operator to each grid node, a very many iterations are needed to massage the influence of a datum across many grid columns or rows. Indeed, the number of iterations needed to spread the influence across N rows or columns seems to be roughly proportional to exp)N).

Because of this, we start with a very small initial grid. Each datum is applied to the nearest grid node, and the filter is applied to make a smooth surface between the data. Because the grid is very small, the data are smeared across only a few columns and rows, and the filter has only to hit a small number of nodes. Then the tiny grid is copied and interpolated into a finer grid, and the flexing is repeated. This process of multi-grid refinement and flexing is repeated until the final grid is acceptable. The flexing of the tiny coarse grids massages in the overall trends, and the flexing of the finer grids works in the local details, so the finer grids do not need a large number of passes of the flexing filter