Blending polygonal shapes with different topologies

In this paper, we propose a new method for morphing between two polygonal, possibly non-simply connected, shapes in the plane. The method is based on reconstructing an xy-monotone surface whose extreme cross-sections coincide with the given shapes. The surface generated by our algorithm does not con tain any self-intersections, does not change the topologies of the input sl ices, does not contain any horizontal triangles, and guarantees that all th e topology changes occur at a mid-height which is a degenerate form of both input topologies. All these properties are highly desirable for blending s hapes of different topologies. (C) 2001 Elsevier Science Ltd. All rights re served.