Algorithm Design and Problem Solving   


Project 5: Repair of ice statues


Hand-out: 19.10., deadline: 9.11.


Story: You are an administrator of an ice statues museum. You did not care enough for the refrigeration, the temperature grew and the statues started to melt down: not too much but their edges are now rather soft. You would like to repair it before anybody notices. It means to work a bit on the statues in such a way the sharp edges reappeared.


  1. The input is a surface geometric model made of triangles, it can contain holes. Make a program which allows swapping edges in the triangulation according to the angle of neighbouring triangles sharing an edge (a choice of the “better” angle from two possibilities). The program has to allow an easy change of the criterion of edge swapping, possibility to constrain the swaps on only a subset of the given points. Input and changed data should be visualized in two windows, visualization of lighted and surface models, a possibility to visualize indices of points. Input and output data are in TRI file, input data will be given and explained by me. If you preferred NOT to write the visuzalization program and concentrate only on swapping, it is also possible, you can get the visualization program ready from me. You will get 6 points for the visualization program, 6 points for the edge swapping program and other 4 points in the case that your swapping will be more clever and will contain also “non-local“ criterion, i.e. following and recover of the sharp edges with considering higher number of triangles.


As you need some extra information for this project, I want to make a meeting with those who will be solving this problem. Therefore, you should proclaim your interest as soon as possible, till 22.10 at the latest, in order to make one meeting only.