Find mappings between two surface meshes (for morphing)

[Unrest]

I want to morph two surface meshes made from triangles and quadrilaterals.

They are already "compatible" so that one can be converted to the other simply by changing the coordinates of the vertices. No vertices, gaps, edges, etc. are created or destroyed.
Not sure of the terminology. I think that means they have some or all of these properties:
- Homeomorphic
- Topologically equivalent
- Combinatorially equivalent
- The same in every way except the (x,y,z) coordinates and the numbering/labeling of the vertices/elements.

I want to find all the possible ways the vertices could be numbered so the numbers match on both meshes. For example the circular mesh in the picture would have 6 ways to number the vertices 1,2,3,.. so they match the triangular mesh.

[PLAIN]http://dl.dropbox.com/u/21857463/meshes.png

 

[chiro]

I want to morph two surface meshes made from triangles and quadrilaterals.

They are already "compatible" so that one can be converted to the other simply by changing the coordinates of the vertices. No vertices, gaps, edges, etc. are created or destroyed.
Not sure of the terminology. I think that means they have some or all of these properties:
- Homeomorphic
- Topologically equivalent
- Combinatorially equivalent
- The same in every way except the (x,y,z) coordinates and the numbering/labeling of the vertices/elements.

I want to find all the possible ways the vertices could be numbered so the numbers match on both meshes. For example the circular mesh in the picture would have 6 ways to number the vertices 1,2,3,.. so they match the triangular mesh.

[PLAIN]http://dl.dropbox.com/u/21857463/meshes.png[/QUOTE]

Hey Unrest.

What you are looking for is an interpolation scheme.

If the edge structures during the transformation never change, then all you need to do is to setup interpolation schemes for each vertex.

Your interpolation scheme will contain a parameter t that goes from 0 to 1. p(t) will calculate the value of the point at time t. p(0) = initial point, p(1) = final point and other values are in-between.

There are quite a few different schemes for interpolation, but what I recommend you do is to look into the area of BSPLINES. If you want something simpler, I would use a Bezier curve.

Basically what a Bezier curve does is it uses four points (the cubic variety). The first and last point correspond to p(0) and p(1). You also have two other points in between which are control points which control the path of the interpolation. Basically the path is "dragged towards" the mid-points, but with a bezier curve they do not go through the 2nd and 3rd points and for this reason they are known as approximating curves and not interpolating curves (interpolating curves have the property that it goes through all control points).

Once you learn about interpolating schemes, then all you have to do is assign a parametric scheme to each point, and then for every step-size, compute each point, and perhaps recompute normal vertices if you are doing some kind of rendering application or if you need to use lighting, and then draw your shape. Since the edge data is the same, you don't have to update this.

If you have any other questions, I'll do my best to answer them.

 

[Unrest]

Thanks chiro

However, interpolation isn't my problem. I intend to simply use linear interpolation despite its problems.

It's the stage before interpolation that I'm stuck on. How can I find the pairs of vertices to interpolate between? In my example there are 6 possible sets of corresponding pairs. If I know all of them, then I can choose anyone and produce some sort of result.

 

[chiro]

You can use interpolation schemes that interpolate between all sets of points if that is what you are asking.

Just use a standard scheme and use those as your control points for the scheme.

Is this what you want to do? Do you want to find a way to morph between images in some way that looks good?

 

[Unrest]

No. I don't want to interpolate. Actually I already have linear interpolation working fine.

I want to find out which points to interpolate between. Most sets of pairs of points will produce a random tangle. I want to find, for example only those 6 sets shown in the picture.

Currently I manually number the vertices. And I carefully make sure that both meshes have identical vertex numberings. That's not very convenient. I'd prefer the computer to find the possible numberings itself and then the user just chooses a suitable one from a limited selection of correct ones.