# Ideas, Problems, and Investigations in Computer Graphics

The following annotated sketches explore various ideas and problems drawn from computer graphics applications in all of these areas.

### Studies in Shape

#### Morphing Letterforms

If a single geometric transformation has captured the imagination of the special effects industry in the 1990s, it's "morphing." When morphing, an arbitrary shape transforms dynamically to take on the appearance of some other shape. At the movies, science fiction and horror genres have disported the morphing process in no end of screenplays rich with shape-shifters, werewolves, and other metamorphic agents (for example, John Carpenter's *The Abyss* or James Cameron's *Terminator II*). Conventional human forms emerge dramatically from shapeless blobs of ectoplasm: no mathematician would call morphing a rigid transformation!

A simplified form of morphing can be explored in planar geometry by transforming one (arbitrary) simple polygon into another. In overview, the process involves identifying a mapping between all points on the perimeter of the first shape (the pre-image) and points on the perimeter of the second (the image). Once such a mapping has been defined, morphing the pre-image into the image simply involves sending pre-image points (representing the pre-image's perimeter) to their corresponding image points so that they arrive at their destination simultaneously.

The problems to solve in constructing a morphing of shapes are to identify mathematically both the mapping of pre-image to image points, and to specify the mechanism for moving the former to the latter.

Figure 1. Mapping |

One solution to these problems is approached by Figure 1, which considers the morph of a letterform N (represented by an irregular 10-gon) and the letterform O (represented by a circle). A mapping between the two shapes has been defined by first placing the pre-image (N) completely within the image (O), and then drawing a ray from the center of O through some point *Pre* on the pre-image. The intersection of the ray with the image circle is defined as point *Post*, and since any ray from the center of a circle must intersect that circle, this construction guarantees that every point *Pre* on the pre-image corresponds to some other point *Post* on the image.

It's worth momentarily considering this mapping as a mathematical function, which for each input value *Pre*, generates an output value *Post*, or *Post*=f(*Pre*). The domain of the function is N; the range O. Is the function one-to-one? Inspection of Figure 1 suggests not: the mapping ray passes through three points on the perimeter of the pre-image (three possible values of *Pre*) all of which correspond to the same point *Post*.

Once the mapping has been established, generating intermediate images of the morph is straightforward. Consider the segment between *Pre* and *Post*. This segment determines the domain of each point on the perimeter of the morphing polygon, as it evolves from N to O. Thus the midpoint of this segment represents a point on the perimeter of a polygon morphed "half-way" between pre-image and image. In general, any point *Tween* on this segment corresponds to a point on the perimeter of an intermediate morph we can call the mid-image.

What does the mid-image look like for a given position of *Tween*? Clearly, if *Tween* and *Pre* are coincident, then the pre-image and the mid-image are identical: they form an N. If *Tween* and *Post* are coincident, then the mid-image is the same as the image: O. Intermediate values of *Tween* describe mid-images that are |*Pre**Tween*|/|*Pre**Post*| of the way between N and O.

In Sketchpad, the mid-image corresponding to a given point *Tween* (on the segment between *Pre* and *Post*) can be generated by constructing the locus of *Tween* as *Pre* travels about the pre-image. If *Tween* is an arbitrary point on the segment between *Pre* and *Post* (as opposed to some specific point, such as the midpoint), then it can be dragged freely between the segment's endpoints. Correspondingly, the locus of *Tween* morphs smoothly between N and O, as illustrated in Figure 2.

Figure .: Morphing N to O |

Defining morphed images as the locus of

*Tween*is a geometric application of linear interpolation

^{[2]}:

*Tween*is interpolated on the (linear) segment between

*Pre*and

*Post*. But morphing can be a more compelling application of linear interpolation than the traditional mode by which it's introduced to students, where it's used to find values not explicitly mentioned in the log tables at the back of a textbook.

#### Further Exploration

Students who have covered the basics of morphing can go on to investigate a number of more detailed questions.

- This example morphs between a polygon and a circle. How might one construct the morph between a polygon and a line (or a segment)? Or between one arbitrary polygon and another?
- Imagine if
*Tween*were defined on the line passing through*Pre*and*Post*, rather than on the segment between them. What would happen to the morphed mid-image if*Tween*was no longer between*Pre*and*Post*? (This is extrapolation, as opposed to interpolation.) - How would you define a morphing mapping between one photograph and another, where you were concerned not just with the perimeter of shapes but with their interior details as well?

^{[2]} For accuracy's sake, I should note that the term *morphing* is usually reserved for transitions between fully colored and shaded pre-images and images. The process of morphing only the perimeter of shapes is known in the computer graphics community as *tweening*, and was used in the early days of computer graphics to generate automatic, intermediate movie frames between "key-frames" that were hand-drawn by a professional illustrator in animated pictures (cartoons). The tweened frames were then colored by hand, and if the number of key frames was sufficiently high, the audience tended not to notice that animated characters were moving not according to the laws of cartoon anatomy but according to strict linear interpolation.