McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.

DATE: Friday, December 11th, 1998
TIME: 12:30-13:30
PLACE: McConnell 320
TITLE: A Review of Polygon Morphing Techniques
SPEAKER: Mark Grundland, McGill University

How do you smoothly and continuously transform one polygon into another in a way that appears graceful to the eye? Polygon morphing is a key technique of two dimensional computer animation. It is related to applications in pattern recognition, where the amount of work involved in the morphing one shape into another measures the degree of similarity between them, as well as in the reconstruction of 3-D solids from 2-D contours, where morphing is used to generate intermediate contours.

The transition between an initial and a final polygon demands a representation of the shape that addresses two separate tasks. The vertex correspondence problem involves matching the relevant features of the polygons, where typically a full one-to-one matching of vertices must be surmised from a partial matching of anchor points supplied by the user. The vertex path problem requires finding the motion that each vertex of the polygon will follow from its initial to its final position. Typically, this motion is composed of a global affine component, which seeks an optimal alignment of the the two polygons, and a local elastic component, which determines the deformation of the polygon features. The solutions proposed in the literature range from linear interpolation of vertex positions or edge lengths and angles, to fuzzy set and distance field methods.

The seminar will present a survey of some of these approaches, evaluating their common goals as well as assumptions, with a view toward directions in future research into how to make metamorphosis visually compelling.

Link to the bibliography.