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:

1. 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 :-)).
2. 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. If the method survives your verification, you will get 3 points.
3. 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.