Exercise no. 2
Low-Distorion Parameterizations for Texture Mapping

Topics: Texture-mapping, parameterizations, relaxation.

Due date : 17.01.02


Your goal in this exercise is to get your hands dirty with computation of a low-distortion parameterization for a general shape 3D object. More specifically, you are required to extend the program you wrote for the previous exercise to receive as input a name of a texture image file, and a single integer number n. Your program should compute a parameterization (assign each vertex of the object's mesh a pair of texture coordinates [u,v] in [0,1]x[0,1]) with as little distortion as possible, and then display the texture-mapped object using OpenGL in your interactive viewer.

This exercise is deliberately somewhat open-ended, and obviously we do not expect a perfect solution for this essentially open problem. It is quite conceivable that despite your best efforts, some of the objects in the collection will result in very distorted texture mapping. That's perfectly fine, as far as we are concerned. On the other hand, your method will be expected to find good parameterizations for simpler objects.

Here's the course of action you should follow: start by superimposing an n by n regular grid over the texture parameter space (remember the parameter n from two paragraph ago?). Now for each junction on this grid you'll need to find a suitable location on the surface of the object. Your first step will be to find an initial guess for all these locations, and the second step will use relaxation in order to improve the locations you assigned in the previous step. The initial guess can be obtained, for example, using a cylinder as an intermediate surface.

As for the second step, we see two ways of doing that:

  1. Use relaxation, similarly to the way it is used for simulating reaction-diffusion directly on object surfaces. In other words, you have a system of point charges such  that between every two sufficiently near points there is a repulsion force inversely proportional to the distance between them. By iteratively moving each point in the direction of the total force vector operating on it, you should reach a local potential energy minimum.
  2. Construct a system of point masses connected by springs, and let it settle into a local energy minimum. This can be obtained similarly to relaxation (except each particle always has the same four neighbors applying forces on it). Note that there are much better methods than relaxation for such a system, we are just trying to make things easier here. You'll need to figure out what resting length to assign to each spring, and decide on a spring constant k. The magnitude of the force between two point masses is then simply |kx|, where x measures the length by which the spring has been stretched (or compressed). (You can also use |kx^2| if you like).
Finally, in order to display the texture-mapped object you'll have to somehow assign each vertex in the original mesh a pair of texture coordinates (using the results of the previous stage, of course).

You can do this exercise in pairs. A pair, however, will be expected to implement both variants for the second step above. A person working on his own, can just choose to implement just one of the two.

It will make sense to prepare a checkerboard texture, since it makes it easy to assess the quality of the parameterization. Also, be sure to prepare a README file that describes what you did, and gives some examples of objects on which the method works well, as well as some on which it fails.


Good Luck !