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

Question

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.

Answer 1

Comments on existing answers:

It seems to me that Mau's and martient's answer describe a solution to problem of approximating a known form with polygon mesh (and you don't have a known form).

Algorithm that Dave mentions would smooth any form, but not necessarily in the intended way.

If you look at You's answer you will see that the new points come from linear interpolation between the points, and if that is good enough for you all solutions are comparable (except Dave's).

Such increase in the mesh density will not make the resulting mesh look any 'nicer' - more similar to original form. If that's not good enough then you first have to decide what is the actual form/shape that you are trying to represent with the mesh (if you could expand on your example it might be a bit more obvious; is this tool creating only circle meshes or it can take any shape and 'mesh fill' it?).

Also, you should notice that you don't work with a polygon mesh, but with mesh of curves (probably bezier), which is another reasons why some of the answers would not directly apply to your problem.

EDIT: After looking more closely on how corel does this and assuming that you actually know the curves not only the points(!):

• You begin with set of curves, and it seems to me that you have horizontal and vertical curves to begin with
• If you want to increase the resolution (for example horizontal resolution), you could take two consecutive vertical curves and divide every segment of the horizontal curves they pass through at mid point thus creating a set of points that define the new curve; you could also interpolate the angle at which the curve passes through the point

alt text http://img706.imageshack.us/img706/5693/path5818.png

The above (manually drawn) picture shows tries to illustrate a) adding of the new curve (red) that you would generate in this way. b) adding the linearly interpolated polyline (blue), that goes more towards polygon mesh approach (so you can judge if that is acceptable for you)

Note: Depending on the algorithm for which you are preparing the mesh you might or might not have any benefits in considering the mesh lines to be curves (difference between red and blue solutions might be negligible for certain algorithm and important for other). If the algorithm simply expect points then you should also look at how to approximate bezier curves with points (reading through this might help; though you don't need pixel precision).

For highest precision/best results you should first increase the density of curves and the approximate them with lines.