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

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.

Have you looked at subdivision? Should work for refining meshes like that.

What You're looking for is a mesh smooth algorithm. Unfortunately I don't have any resources at hand, so I can only suggest to google for "mesh smoothing". That's a huge field.

EDIT

Here's a nice, short, roundup of a couple of methods/algorithms to achieve mesh smoothing: http://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_surf3.pdf