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

vertex-edge connectivity, to produce the second object. The correspondence between the two shapes is
established by the vertex-edge connectivity structure shared by the two objects. The interpolation prob-
lem is solved, as in the majority of techniques presented here, by interpolating three-dimensional vertex
positions.

4.4.2 Star-shaped polyhedra
If the two objects are both star-shaped

2 polyhedra, then polar coordinates can be used to induce
a two-dimensional mapping between the two shapes. See Figure 4.31 for a two-dimensional example.
The object surfaces are sampled by a regular distribution of rays emanating from a central point
in the kernel of the object, and vertices of an intermediate object are constructed by interpolating
between the intersection points along a ray. A surface is then constructed from the interpolated vertices
by forming triangles from adjacent rays. Taken together, these triangles define the surface of the poly-
hedron. The vertices making up each surface triangle can be determined as a preprocessing step and are
only dependent on how the rays are distributed in polar space. Figure 4.32 illustrates the sampling and
interpolation for objects in two dimensions. The extension to interpolating in three dimensions is
straightforward. In the three-dimensional case, polygon definitions on the surface of the object must
then be formed.

4.4.3 Axial slices
Chen [ 9 ] interpolates objects that are star shaped with respect to a central axis. For each object, the
user defines an axis that runs through the middle of the object. At regular intervals along this axis,
perpendicular slices are taken of the object. These slices must be star shaped with respect to the
point of intersection between the axis and the slice. This central axis is defined for both objects,
and the part of each axis interior to its respective object is parameterized from 0 to 1. In addition,
the user defines an orientation vector (or a default direction is used) that is perpendicular to the axis
(see Figure 4.33 ).

Polygon

Kernel

FIGURE 4.31
Star-shaped polygon and corresponding kernel from which all interior points are visible.

2 A star-shaped (two-dimensional) polygon is one in which there is at least one point from which a line can be drawn to any
point on the boundary of the polygon without intersecting the boundary; a star-shaped (three-dimensional) polyhedron is
similarly defined. The set of points from which the entire boundary can be seen is referred to as the kernel of the polygon
(in the two-dimensional case) or polyhedron (in the three-dimensional case).