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

shapes is typically not considered in volume-based approaches. Thus, some information, often impor-
tant in animation, is lost. Volume-based approaches will not be discussed further.
The terms used in this discussion are defined by Kent et al. [ 19 ] and Weiler [ 35 ]. Object refers to
an entity that has a three-dimensional surface geometry; the shape of an object refers to the set of
points in object space that make up the object's surface; and model refers to any complete description
of the shape of an object. Thus, a single object may have several different models that describe its
shape. The term topology has two meanings, which can be distinguished by the context in which they
are used. The first meaning, from traditional mathematics, is the connectivity of the surface of an
object. For present purposes, this use of topology is taken to mean the number of holes an object
has and the number of separate bodies represented. A doughnut and a teacup have the same topology
and are said to be topologically equivalent. A beach ball and a blanket have the same topology. Two
objects are said to be homeomorphic (or topologically equivalent) if there exists a continuous, invert-
ible, one-to-one mapping between the points on the surfaces of the two objects. The genus of an
object refers to how many holes, or passageways, there are through it. A beach ball is a genus 0 object;
a teacup is a genus 1 object. The second meaning of the term topology, popular in the computer
graphics literature, refers to the vertex/edge/face connectivity of a polyhedron; objects that are equiv-
alent in this form of topology are the same except for the x -, y -,

z -coordinate definitions of their

vertices (the geometry of the object).
For most approaches, the shape transformation problem can be discussed in terms of the two sub-
problems: (1) the correspondence problem , or establishing the mapping from a vertex (or other geo-
metric element) on one object to a vertex (or geometric element) on the other object, and (2) the
interpolation problem , or creating a sequence of intermediate objects that visually represent the trans-
formation of one object into the other. The two problems are related because the elements that are inter-
polated are typically the elements between which correspondences are established.
In general, it is not enough to merely come up with a scheme that transforms one object into another.
An animation tool must give the user some control over mapping particular areas of one object to par-
ticular areas of the other object. This control mechanism can be as simple as aligning the object using
affine transformations, or it can be as complex as allowing the user to specify an unlimited number of
point correspondences between the two objects. A notable characteristic of the various algorithms for
shape interpolation is the use of topological information versus geometric information. Topological
information considers the logical construction of the objects and, when used, tends to minimize the
number of new vertices and edges generated in the process. Geometric information considers the spatial
extent of the object and is useful for relating the position in space of one object to the position in space
of the other object.
While many of the techniques discussed in the following sections are applicable to surfaces
defined by higher order patches, they are discussed here in terms of planar polyhedra to simplify
the presentation.

4.4.1 Matching topology
The simplest case of transforming one object into another is when the two shapes to be interpolated
share the same vertex-edge topology. Here, the objects are transformed by merely interpolating the
positions of vertices on a vertex-by-vertex basis. For example, this case arises when one of the previous
shape-modification techniques, such as FFD, has been used to modify one object, without changing the