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:
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.