Draft for solutions to the exam in TSBK05 050607


1. OpenGL programming

a) Draft code, mark the code telling what does whhat part of the transformation pipeline. The question wants you to show that you know how theory and practice fits together. Note that it is no problem at all if you don't remember the exact names of OpenGL calls! API names are unimportant, you look them up when you need them.

// May be part of "redraw" or "display" or done in user interface parts
// World coordinates to camera coordinates (camera placement)
// Part of the "display" function in GLUT or similar
// Model coordinates to world coordinates (place model in world)
glPushMatrix(); // Preserve the camera placement
draw model
// Not mandatory for solution:
// May be part of "redraw" function in GLUT or similar
// Camera coordinates to projected coordinates

b) GLUT (like SDL) is a library that hides the system dependent parts of OpenGL under a cross-platform interface. If such an API is not used, we must do some tasks using system dependent libraries, that is GLX (Unix, X-Windows), WGL (MS Windows), AGL (Macintosh). (GLU was mentioned as a side-track and is irrelevant to the question.)

Notes: OpenGL questions generally focuses on transformations (like a), with minor questions on system-level issues (like b). As noted above, mis-spellings of OpenGL calls are generally accepted as long as it is clear what function you


2. Transformations

a) This is really not one of the best transformation problems, since it isn't very well founded in practicval problems. On the other hand, it is pretty easy: Translate a vertex to origin, rotate and mirror, translate to the new position of that vertex. Most problems should be formulated to that we do the more interesting transform to origin - transform - transforma back sequence.

Full matrices should be given (see the book), angles in rotations should be properly derived from geometry. The full transformation multiplication sequence should be given in the proper order.

b) This is the look-at problem, covered by the book, section 7-3 and 7-4. Note that a "forward vector" is in the opposite direction to the view-plane normal vector. The final reult should be equivalent of formula 7-4.


3. Curve generation

a) This question demand that you reformulate the Bresenham line drawing algorithm to a strict midpoint algorithm, a nice and easy variant of all the more tedious ellipse and circle algorithms.

A line can be formulated as y = mx + b. Rewrite to f1(x, y) = m*x + b - y. This is a function which is positive above the line and negative below. But, it is not integers. With one end point x0, y0 and total lengths x and y, m = y/x and b = y 0 - x0 * y / x. Multiply by x and everything are integers! Then we get:

f2(x, y) = x*y - y*x - x0*y + y0*x

The curve should be 8-connected so the possible steps should be (1, 0) and (1, 1), putting the midpoint in xk+1, yk+1/2. But when we insert this midpoint in f2 we find that the half step causes non-integer values. We fix that by multiplting with 2, which gives us the final curve function

f(x, y) = 2(x*y - y*x - x0*y + y0*x)

Using pk = f(xk+1, yk+1/2) we calculate pk+1 - pk

for diagonal and horizontal moves. As expected they come out as 2y-2x and 2y, respectively.

Finally we calculate the starting value: f(x0 + 1, y0 + 1/2) = 2y - x

Same result, other (more general) method.

b) If you get the result above, this is obviously true, but how can you prove it without having the Bresenham algorithm available? You should do its very first part, calculating dupper and dlower, and find that their difference multiplied with x results in the same thing.

c) Note how each pair of update steps supports a limited direction interval. The figure you draw should mark which part uses which pair of update steps and the point where you need to switch. See the section in the book about ellipse drawing.


4. Miscellaneous

a) Ray-triangle intersection.

First derive the formula for the intersection by inserting the line equation in the plane equation.

Then describe how the intersection is placed in the triangle, and how we can use barycentric coordinates or some equivalent method for checking that we are in the triangle. See the supplement.

b) Problem 1: Heavy stack use. Problem 2: Massive numbers of function calls. Problem 3: No stopping rule that guarantees that it ends.


5. Mapping techniques.

a) See the supplement. (The book also covers this but IMHO not as well.)

b) Resolution pyramid for textures, in order to reduce aliasing. The cost is 33% more memory for each texture (that is, it is cheap).


6. Collission detection

a) Sorting, for example linear sorting, quad trees or octrees,

b) See the supplement, two figures with colliding polyhedra. The tests involved are containment tests and edge-polygon intersection tests.


7. Visible surface detection

a) First: z-1 is linear in screen space, which z is not. Second, z-1 gives higher resolution near the camera, which is highly desirable for the Z-buffer.

b) It is the set of polygons that need to be drawn from one specific cell to rennder the scene properly. It can be rendered by rendering the entire world as polygon indices (rather than textures and shades). All polygons for which there are indices in the resulting images are part of the PVS. By rendering in all directions from several positions in a cell we get a good approximation of the perfect PVS.

c) Decomposition, building of tree: See the book and the supplement. It will be correctly rendered since we choose branch in real-time depending on vieweing direction.


8. Light, shading and ray-tracing

a) Yes. The Phong model can be used for calculating shades per vertex with support for specular reflections. Phong shading can be used without using the specular reflection component in the three-component model; nothing stops us from interpolating normals and calculating light per pixel even if the object is diffuse.

b) The rays start at the camera, and are traced until they reach a diffuse surface or max search depth.

c) Ek is emitted light from light sources, pk the reflectivity, B k is the total emitted light and F k the form factor. If you know that, the calculations should be easy.