Interpolation-Based Animation - Computer Animation: Algorithms and Techniques - page 147

Once the meshes have been associated, each mesh is recursively divided. One mesh is chosen for
division, and a path of edges is found across it. Again, there are various ways to do this and the pro-
cedure is not dependent on the method chosen for its success. However, the results will have a slightly
different quality depending on the method used. One good approach is to choose two vertices across the
boundary from each other and try to find an existing path of edges between them. An iterative proce-
dure can be easily implemented that tries all pairs halfway around and then tries all pairs one less than
halfway around, then two less, and so on. There will be no path only if the “mesh” is a single triangle—
in which case the other mesh must be tried. There will be some path that exists on one of the two meshes
unless both meshes are a single triangle, which is the terminating criterion for the recursion (and would
have been previously tested for).
Once a path has been found across one mesh, then the path across the mesh it is associated with must
be established between corresponding vertices. This may require creating new vertices and new edges
(and, therefore, new faces) and is the trickiest part of the implementation, because minimizing the num-
ber of new edges will help reduce the complexity of the resulting topologies. When these paths (one on
each mesh) have been created, the meshes can be divided along these paths, creating two pairs of new
meshes. The boundary association, finding a path of edges, and mesh splitting are recursively applied to
each new mesh until all of the meshes have been reduced to single triangles. At this point the new
vertices and new edges have been added to one or both objects so that both objects have the same topol-
ogy. Vertex-to-vertex interpolation of vertices can take place at this point in order to carry out the
object interpolation.
4.5 Morphing (two-dimensional)
Two-dimensional image metamorphosis has come to be known as morphing . Although really an image
postprocessing technique, and thus not central to the theme of this topic, it has become so well known
and has generated so much interest that it demands attention. Typically, the user is interested in trans-
forming one image, called the source image, into the other image, called the destination image. There
have been several techniques proposed in the literature for specifying and effecting the transformation.
The main task is for the user to specify corresponding elements in the two images; these correspon-
dences are used to control the transformation. Here, two approaches are presented. The first technique
is based on user-defined coordinate grids superimposed on each image [ 37 ]. These grids impose a coor-
dinate space to relate one image to the other. The second technique is based on pairs of user-defined
feature lines. For each pair, one line in each image is marking corresponding features in the two images.
4.5.1 Coordinate grid approach
To transform one image into another, the user defines a curvilinear grid over each of the two images to
be morphed. It is the user's responsibility to define the grids so that corresponding elements in the
images are in the corresponding cells of the grids. The user defines the grid by locating the same num-
ber of grid intersection points in both images; the grid must be defined at the borders of the images in
order to include the entire image ( Figure 4.42 ). A curved mesh is then generated using the grid inter-
section points as control points for an interpolation scheme such as Catmull-Rom splines.