Common algorithm question

Question

Hello!

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

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

Sounds like a job for Bilinear Interpolation (where the coordinate system is on the sphere surface).

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

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.