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

other object (along with the two edge segments involved in the intersections) (see Figure 4.39 ) . Once
the configuration is determined, triangulating the region is a simple task. The procedure then continues
with the succeeding vertices or intersections in the order that they appear around the boundary of the
original triangle.
This completes the triangulation of the combined topologies on the sphere. The resulting mesh
can then be mapped back onto the surfaces of both objects, which establishes new definitions of the
original objects but with the same vertex-edge connectivity. Notice that geometric information is used
in the various mapping procedures in an attempt to map similarly oriented regions of the objects onto
one another, thus giving the user some control over how corresponding parts of the objects map to
one another.
4.4.5 Recursive subdivision
The main problem with the procedure above is that many new edges are created as a result of the merg-
ing operation. There is no attempt to map existing edges into one another. To avoid a plethora of new
edges, a recursive approach can be taken in which each object is reduced to two-dimensional polygonal
meshes [ 27 ]. Meshes from each object are matched by associating the boundary vertices and adding
new ones when necessary. The meshes are then similarly split and the procedure is recursively applied
until everything has been reduced to triangles. During the splitting process, existing edges are used
whenever possible to reduce the number of new edges created. Edges and faces are added during sub-
division to maintain topological equivalence. A data structure must be used that supports a closed, ori-
ented path of edges along the surface of an object. Each mesh is defined by being on a particular side
(e.g., right side) of such a path, and each section of a path will be shared by two and only two meshes.
The initial objects are divided into an initial number of polygonal meshes. Each mesh is associated
with a mesh from the other object so that adjacency relationships are maintained by the mapping. The
simplest way to do this is merely to break each object into two meshes—a front mesh and a back mesh.
A front and back mesh can be constructed by searching for the shortest paths between the topmost,
bottommost, leftmost, and rightmost vertices of the object and then appending these paths
( Figure 4.40 ) . On particularly simple objects, care must be taken so that these paths do not touch except
at the extreme points.
This is the only place where geometric information is used. If the user wants certain areas of the
objects to map to each other during the transformation process, then those areas should be the initial
meshes associated with each other, providing the adjacency relationships are maintained by the
associations.
When a mesh is associated with another mesh, a one-to-one mapping must be established between
the vertices on the boundary of the two meshes. If one of the meshes has fewer boundary vertices than
the other, then new vertices must be introduced along its boundary to make up for the difference. There
are various ways to do this, and the success of the algorithm is not dependent on the method. A sug-
gested method is to compute the normalized distance of each vertex along the boundary as measured
from the first vertex of the boundary (the topmost vertex can be used as the first vertex of the boundaries
of the initial meshes). For the boundary with fewer vertices, new vertices can be added one at a time by
searching for the largest gap in normalized distances for successive vertices in the boundary
( Figure 4.41 ) . These vertices must be added to the original object definition. When the boundaries have
the same number of vertices, a vertex on one boundary is said to be associated with the vertex on the
other boundary at the same relative location.