On The 2D Shape Metamorphosis Based On Isomorphism Triangulations

Morphing (metamorphosis) refers to the process of transforming one shape (the Source) into another (the Target). This operation is also known variously as shape blending, shape averaging or shape interpolation. It has been widely used in computer graphics, animation, CAD/CAM, advertisement and so on.In this area, though many algorithms have been given, a perfect one is still hardly to find. And commercial software packages which greatly depends on man-machine interaction sometimes yields undesired results. This thesis presents some effective and robust algorithms to resolve the 2D object metamorphosis. The major works involved are as follows:1.This thesis summarizes several typical algorithms of vertex correspondence problem, analyses the disadvantage, strongpoint and the application domain of the algorithms. The techniques of vertex correspondence based on the approximate skeleton are discussed particularly.2. Based on the similarity of source polygon and target polygon, an isomorphism triangulating algorithm for planar polygon is presented. Firstly, the similar parts of the source polygon and target polygon are triangulated without extra vertex. This can simplify the two polygons, called the two resulted polygons as simplified source polygon and simplified target polygon. Then using the existed algorithm triangulates the two simplified polygons. Using the algorithm, the triangulation of the original polygon and the target polygon is simplified and the results are satisfied. The number of extra vertexes can be cut down, so the complexity and the computation cost ofmetamorphosing the planar polygons are reduced.