How to compute locations of mesh points when resolution is increased?

Suppose we have some mesh (see the illustrating picture from CorelDraw, which uses the same technique in "Mesh fill" instrument).

_{(source: sonic.net)}

Obviously this kind of mesh is represented by a set of points and lines between them are actually determined using that set of points (probably somehow interpolated). This instrument also has buttons to increase mesh resolution.

My question is the following - how are such sort of things computed? Suppose I have some set of points that actually represent a mesh (for easy case let's even assume, that points on the "border" are static and can't move). And I want to increase the mesh resolution, for example, in 4 times (so that number of mesh points actually becomes 4 * initial_points_count).

How should I compute the locations of new points if the only data that I have is that initial point matrix?

The fastest (even approximated) method would suit me, but I don't know where to search or how to develop such kind of algorithm.

Thank you.

Solution

I would start by adding halfway points on all lines by interpolating (the curves in the illustration are most likely Bézier curves of some sort, so I would interpolate them as such, or use biliniear interpolation as Mau suggested) and placing new points halfway between the old ones, giving me 3 times the resolution. I would then interpolate between these new points (both ways if precision is key) and place a new point at the intersection (or halfway). See "illustration" below.

Initial state  =>  Interpolate  =>  Place points  =>  Interpolate => Final state
  x       x         x-------x        x   x   x         x   x   x      x   x   x
                    |       |                              |    
                    |       |        x       x         x---+---x      x   x   x
                    |       |                              |
  x       x         x-------x        x   x   x         x   x   x      x   x   x