c++ 2D array non-regular grid interpolation

Question

I got a non regular 2D array.

Here's some parts of the arrray, using "nearest neighbor" interpolation.

I would like to go from that :

to that :

I can't use bicubic interpolation, because my grid is not regular.

What can I use ? (need to be fast - realtime render...)

Answer 1

Create a Delaunay triangulation of your irregular point cloud. Interpolate the color at every pixel across the triangle interior using the values in triangle vertices.

http://en.wikipedia.org/wiki/Delaunay_triangulation