Morphing, also known as metamorphosis, is the gradual transformation

of one shape into another. An algorithm to morph two simple polygons

with a correspondence between their vertices is presented.

The algorithm is the only solution to the polygon morphing problem

that analytically guarantees that the intermediate polygons are also

simple. This is achieved by reducing the problem to planar

triangulation morphing, for which morphing techniques, which preserve

triangle orientations have been developed.

To perform the reduction, it is necessary to compatibly triangulate

the interiors of the source and target polygons, and certain regions

exterior to the polygons. The basic algorithm is extended

to deal with not only simple polygons but any connected

straight-line plane graphs called `stick figures'.

Several algorithms to generate compatible triangulations of two polygons

are presented. One of the algorithm produces compatible triangulations

such that the number of additional (Steiner) vertices is close to optimal.

Being close to optimal in terms of the number of Steiner vertices, these

compatible triangulations are usually not of high quality, i.e., do not

have well-shaped triangles. The quality of these triangulations can be

increased by adding Steiner vertices in a compatible manner,

using several novel techniques for remeshing and mesh smoothing.

This allows to produce high-quality compatible triangulations with

a small number of triangles.

Such triangulations may be used for constructing sweeps,

suitable for finite element analysis, between two base polygons.

We also demonstrate how to exploit the developed techniques

for remeshing planar triangulations for 3D triangular meshes.

To be able to apply our 2D remeshing techniques to arbitrary genus 3D meshes,

we use a novel technique for constructing a dynamic patch-wise

parameterization. In addition, we show that mesh quality can be

improved further by improving the mesh regularity using a new simple

and efficient algorithm.