Interpolation

After finding the simplexes, we need to interpolate in their interiors. In our current implementation, we considered a linear variation between the vertices that would ensure that the resulting surface is continuous at the boundaries, though it would not have a continuous derivative across. Other options we considered are to use polynomial fits or cubic-spline functions, but only if we need increased precision that cannot be achieved otherwise, due to the extra computational cost. The latter options would provide a surface that is both continuous and has a continuous derivative across the triangle boundaries.

The final question we had to answer is which points of the grid fall inside the simplex. We considered two possible answers:

1.

Find a domain in the rectangular grid that completely bounds each simplex, and search for all the points of the rectangular grid that fall inside the analyzed simplex. This is obviously not the best choice because we have to analyze more than the necessary number of points (twice as many in the 2-D case and three times as many in the 3-D case). The number of operations is proportional both to the number of triangles and to the size of the interpolation grid.

2.

Search for the limits of the intersection of each simplex with the rectangular grid and consider all the points inside. Such an algorithm can be implemented fairly easily and is a lot faster than the preceding one. The number of operations is proportional to the number of triangles and does not depend on the size of the grid. This is a way to build the optimal solution and avoid a blind search.