Shape Blending Using the Star-Skeleton Representation

Michal Shapira (Etzion) and Ari Rappoport

We present a novel approach to the problem of generating a polygon sequence that blends two simple polygons given a correspondence between their boundaries. Previous approaches to this problem, including direct vertex interpolation and an interpolation based on edge lengths and angles between edges, tend to produce self intersections and shape distortions. Our approach introduces the star-skeleton representation, a structure comprised of equivalent decompositions of the two polygons into star-shaped pieces and a skeleton connecting the star pieces. We utilized the concept of a star polygon since two star polygons can be fairly blended without any self intersections.

We present algorithms for creating equivalent star-skeletons for the two polygons and for blending two star-skeletons by interpolating their skeletons and unfolding intermediate polygons from the skeletons. We also demonstrate the usage of the star-skeleton for blending multiple polygons and images. We show examples from a working system that demonstrate the improved blend sequences generated by the method.

The intrinsic reasons for the good results obtained are the fact that the interiors of the polygons are considered, not only the boundaries, and that the star-skeleton explicitly models an interdependence between all the vertices of the polygons.

IEEE Computer Graphics and Applications, 15(2):44-50, March 1995.