This is something that I find comes up quite a bit when programming, and I'm always in search of better / more elegant solutions... I'm sure there will be some well established maths techniques for this, if only I knew what to google for: <_<

Anyway, the problem is as follows:

1. You have a 2d array of values (think a texture). Could be RGB colours, could be normals, whatever. But for sake of simplicity if we consider this just 1 value at each location, perhaps a float.
2. Your starting knowledge of the array is incomplete. That is, you know a number of xy locations on the array, and their value, but nothing of the values inbetween.
3. The task is to use some kind of SMOOTH interpolation to guess all the locations in between the known data.

I realise of course that there is no fixed solution.

[attachment=32535:array.png]

I won't describe here the approaches I've used before, as I'm really interested in what springs to mind to others, rather than biasing the answers.

One key aspect though is that it should not involve simply partitioning the known data into triangles, and doing interpolation over just the triangles. This gives the ugly look I'm trying to remove by the processing. Each interpolated point should be taking into account e.g. 10+ data points to find a solution.

This is also a pre-process, so the emphasis isn't on speed. However equally well it should be able to perform without taking hours for say, interpolation of triangle corners on a UV map, so be able to deal with interpolating 30,000 or so data points on a 4096x4096 array.

So fire away with your ideas! :D

Three come to mind:
* Kriging: This is a complicated technique, but it gives very good results. I don't know if there is a readily available library implementation you can use.
* Natural neighbor interpolation.
* Constrained optimization using a quadratic penalty for difference between neighbors. I am sure this is not an original idea of mine, but I can't find a reference to it. You try to find the 4096x4096 array that agrees with your data at all the given points and that minimizes the sum of squares of differences between neighboring entries.

You can find a longer list of methods on Wikipedia.

Three come to mind:
* Kriging: This is a complicated technique, but it gives very good results. I don't know if there is a readily available library implementation you can use.
* Natural neighbor interpolation.
* Constrained optimization using a quadratic penalty for difference between neighbors. I am sure this is not an original idea of mine, but I can't find a reference to it. You try to find the 4096x4096 array that agrees with your data at all the given points and that minimizes the sum of squares of differences between neighboring entries.

You can find a longer list of methods on Wikipedia.

Krigling I think I got lost with the maths (reading maths is not my strong point lol :D )..

The natural neighbour is a good idea, I might give that a whirl at some point. I think I already have written code for doing voronoi / dirichlet tesselation stuff.

The third idea about minimizing differences is something I've dabbled with for this too, in various guises.

Ok enough with the lack of bias, some of the things I can remember trying:

1. Weighted averages, weighting the influence of each data point by distance. Either taking into account all the data points or have some kind of cutoff distance. I think I ended up using this last time I faced the problem.
2. Triangulating the points. Ugly.
3. Cellular automata type approaches. I think these might be ultimately the best but I had real problems coming up with good rules.

The cellular automata methods I tried were things like having discrete amount in each cell, then redistributing according to the neighbour amounts (like water flow). And also something similar but like a spring system, like FEM physics models (I think?). This is probably similar to your third method.

I do fancy the iterative cellular technique best if I could get it working well. It also has the advantage that has no significant extra cost for each data point, as you only need to 'seed' it. So the cost would just be related to the size of the grid.

Resurrecting a zombie for a moment...

Krigling I think I got lost with the maths (reading maths is not my strong point lol :D )

Wikipedia is actually an almost universally terrible resource for anything math or science related. Frequently, the meaning of topics on which I consider myself an expert is completely lost on me when I read the jumbled mess that is the Wikipedia article on that topic. The referenced article on Kriging is no exception to that rule of thumb, and I would suggest you search for alternative sources of information about the process before abandoning it. I was able to find one without too much difficulty here, which breaks down the concepts involved much less abstract terms. As an example of what I mean, let's look purely at the definition of Kriging from these two sources.

Wikipedia:

Kriging is a method of interpolation for which the interpolated values are modeled by a Gaussian process governed by prior covariances, as opposed to a piecewise-polynomial spline chosen to optimize smoothness of the fitted values.

Arcgis:

Kriging weights the surrounding measured values to derive a prediction for an unmeasured location. ... with the kriging method, the weights are based not only on the distance between the measured points and the prediction location but also on the overall spatial arrangement of the measured points.

The Wikipedia article is likely more precise... but to someone who doesn't already intimately understand all of the terminology (and likely even to many people who *do* already understand the terminology), it's also complete jibberish. When you have questions about a topic, Wikipedia is usually a great way to find out what some of your options are; however, I would strongly suggest moving away from it before attempting to actually understand or implement against those options.