Algorithm
Design and Problem Solving

Project 4:
Metamorphoses

Hand-out:
12.10., deadline: 2.11.

**Story: **Imagine that you
program a computer game. One of characters is Batman – a hero that should
change from bat to a man and vice versa. You want it look pretty good – not
just a dissolve of pixels. In order to carry out such a trick, you need a
technique called morphing or metamorphosis – a technique which gradually transforms the
source object to a target object. A recommended approach is first to find a correspondence
of vertices of the source and target objects and then between corresponding
vertices to interpolate linearly. The goal of this project is to try auxiliary
techniques for this marvelous effect.

Let us suppose only planar version of this
problem, when two shapes are given by their boundaries – simple polygons – and
a correspondence of the vertices is already known, i.e., it is known which
vertex of the source polygon corresponds to which vertex of the target polygon.

As both input polygons can have a different
number of vertices, a new polygon is created on the basis of their
correspondence (the so-called superpolygon). Its
property is that it can be transformed either to the source or to the target
polygon shape. In the second step, the corresponding vertices are interpolated
– in this way we achieve an animation of transition between shapes. Your task
is the second step, the interpolation of the corresponding vertices. Input is
thus given as two polygons (or, better, one superpolygon
transformed into the source and target polygon shape) and the task is to find a
proper trajectory for each vertex of the polygon, we know the start and end
position of each vertex. A trivial solution is a plain linear interpolation,
i.e., the vertex will move on a line. If the source and target shapes are very
different (e.g., two spirals with the opposite orientation), the interpolated
polygon self-intersects – and it is a disturbing effect. The goal of the work
is a detection of this self-intersection and improvement of these trajectories
in such a way that the self-intersection is prevented.

You can solve none, any or all of the
subprojects below:

- Make
a program for 2D visualization and testing of qualities of the morphing
trajectories. The program should enable as much auxiliary settings as
possible (polygon editing, changes in trajectories, mapping ...) because
it should be used a s a tool for debugging of the
proposed algorithms. You will get
**5 points**for this program. If you preferred to avoid writing this program (which is rather elaborate and does not bring anything new from the algorithmic point of view), you can get this program from me for your experiments (then no points for subproject 1, of course :-)). - Implement
and verify the method for self-intersection prevention given to you by me,
you are suppose to verify it at least on 10 non-trivial cases, you should
prepare such examples which can be critical for the method. You will get
**6 points**for implementation and experiments and**1 extra point**for each case where you find the method does not work, together maximally**5 points**.**3 points.** - You
can try to think out your own method how to solve this self-intersection,
again with verification as in subproject 2, for
**6 points**if the method will work at least on common data, and**8 points**, if it survives even very sophisticated tests. I recommend you to consult the proposed method with me before you start to implement, to lower the probability of failure.

As for solution of this method you need also
some extra information not written here, you should let me know quickly **(till 15.10.)** that you want to solve
it, and I will organize a meeting with extra information.