Exam solution for 090605 with comments

Note: Some strange errors may have been introduced by an over-ambitious spelling checker.

Sorry about the lack of formatted formulas. This is due to lack of time on my part. I know that raw text is primitive but it is fast to write.


1a)

glPushMatrix();
	glTranslatef(px, 0, pz);
	glRotatef(alpha, 0, 1, 0);
	drawBody();

	glPushMatrix();
		glTranslatef(0, ya, -za);
		glRotatef(beta, -1, 0, 0);
		drawAxe();
	glPopMatrix();

	glPushMatrix();
		glTranslatef(0, y1, z1);
		glRotatef(delta1, -1, 0, 0);
		drawWheels();
	glPopMatrix();

	glPushMatrix();
		glTranslatef(0, y2, z2);
		glRotatef(delta2, -1, 0, 0);
		glScalef(1, 0.5, 0.5);
		drawWheels();
	glPopMatrix();

glPopMatrix();



Notes:

Mis-spelling of functions calls (like skipping the "f" suffix ) or reasonable mistakes in parameters are generally acceptable as long as it is clear to me what you mean.

Reasonable assumptions on any vagueness in the problem description tend to be acceptable, doubly so if you define your interpretation properly.

The push/pop around the last pair of wheels can be skipped.

Typical reasons for point deductions:
- No PushMatrix (or equivalent)
- Wrong order of operations
- Obvious deviations from the specified animation (like not scaling the wheels)
- Other mistakes that will give a clearly incorrect result.


1b)

Three of the following errors will give full score:

- No #include
- No return value of main()
- No arguments to main()
- No pointers
- gl_Test is an illegal name for user defined variables.
- Mixed swizzling (rxsz) is not allowed.
- vec4(0) is not recommended (but works with some GLSL compilers)
- No printf()
- No strings
- gl_FragCoord is read only
- No valid output

That's quite a few errors for 6 lines of code!

2a)

Translate to origin: T(-p)
Rotate: Ry(d)
Translate back: T(-p)

T(-p) = 1 0 0 -px
        0 1 0 -py
        0 0 1 -pz
        0 0 0 1

T(p) = 1 0 0 px
       0 1 0 py
       0 0 1 pz
       0 0 0 1

Ry(d) = cos(d) 0 sin(d) 0
          0    1   0    0
       -sin(d) 0 cos(d) 0
          0    0   0    1

Total transformation: T(p) * Ry(d) * T(-p)


Note: This is an unusually simple transformation question. They are usually more complex and may include transformations like scaling and mirroring.

The translation matrix can be given once, implicitly used for the other case.

If you are unsure on whether you got the parts correct on the rotation matrices (e.g. where the minus should be) remember that it is very easy to multiply your matrix by a simple vector like (1, 0, 0, 1) and see if it rotates in the right direction.

2b)

Seemingly scary question which is really not that bad.

The answer follows section 6.6 in the book.

- Multiply the given matrix by (x, y, z, 1), producing (xh, yh, zh, h), divide by h to get projected coordinates (xp, yp, zp).

- Derive xp, yp (one is enough) from the geometry of figures 31-32.

These two should end up the same.

3a)

Your figures should be similar to Figure 56 and 59.

Bezier is approximating. Only some of the control points are on the curve. Points are on the curve when they have the blending value 1 and all others are zero. This is true for at the start and end of a Bézier curve.

Catmull-Rom is interpolating. All control points will at some point have weight 1 and all other 0. This is not totally obvious from the figure, but the control points with small contribution will contribute more to another part of the curve.

Thus, zero crossings are significant as points where the curve intersects a control point.

b)

The decision is a choice between two candidate pixels, which either is a horizontal or diagonal step from the previous pixel. The decision is taken using a decision variable (pk), which is a function of the distances between the continuous line and the two candidate pixels.

4a)

- Redefine the tan-1 function to produce the full direction space instead.

arctan(x, y) = tan-1(y/x) if x > 0
               tan-1(y/x)+Pi if x < 0

- Normalize the mapping so values in the interval [0, 1] if produced.

so if

u = arctan(x, y)
v = z

then you normalize by

s = (u + Pi/2)/2Pi
t = (v - zmin)/(zmax - zmin)

Note: Sorry about the lack of formatting. "tan-1" is the arcus tangens function, not tangens minus one.

4b)

The direction space has a discontinuity at 2Pi. A polygon may overlap this discontinuity and get incorrect texturing (see page 117). This can be solved on polygon level, by detecting polygons which overlaps the edge, and duplicate suitable vertices to produce modified texture coordinates for the problem polygons (figure 84-85).

5a)

Shadows in ray-tracing are produced as follows: Given a surface point hit by a ray, for which lighting should be calculated, shadow rays are cast to every light source to detect whether any object blocks the path of the light.

b)

Shadows in radiosity are implicitly generated by the model, by the form factors which define how much of the light from one surface element that hits another element.

It should be noted that although one surface element may be out of view from another, thereby having form factor zero, it may be hit indirectly by light from the other surface.

Note: This particular question does not require any detailed description about how the form factors are calculated.

c)

See figure 36. The total formula is given piece by piece in section 7.1. A total formula should look like this (with reservation for formatting problems):

i = kd*ia + SUM(id*kd*max(n DOT l, 0) + is*ks*max((r DOT e)n, 0))

6a)

This is just basic vector algebra.

Project a to n: an = a DOT n * n

Subtract this vector twice to get the mirrored vector:

am = a - 2(an) = a - 2(a DOT n)*n

b)

Straight random values are not acceptable due to bad frequency behavior. We get too much high frequencies.

The following methods are acceptable (as well as some variations on these themes)

1: Random values, low-pass filter by a spatial filter
2: Random values in frequency space, low-pass filter in frequency space, FFT to spatial data
3: Recursive subdivision, offset by smaller and smaller values.

7a)

See section 13.4. Relevant depth cues: Parallax scroll, scale and shadows.

b)

Sphere
AABB (axis-aligned bounding box)
OBB (oriented bounding box)
Cylinder
k-DOP (discrete oriented polytopes)

c)

Several methods possible (often similar to VSD methods):

- 1-dimensional sorting
- BSP trees (kD-tree)
- Octrees or quad trees
- Simplify collision detection outside the viewing frustum
- Clustering, using bounding spheres for groups of objects

8a)

Z-buffer (depth buffer) is not compatible with transparency. Any transparent surface drawn before any more distant surface will eliminate the latter since the Z-buffer values are set to the distance to the transparent surface. A full remedy for this problem is to render transparent surfaces after all other, and back-to-front (using Painter's Algorithm).

There are a number of simpler tricks to make the effect less disturbing. Good descriptions of such remedies can qualify for good score, but I would prefer the sorting solution above.

b)

Two reasons:

- View plane oriented billboards are easier to implement. Just set the rotation part of the transformation to identity matrix for the billboard.
- No risk for artifacts due to overlapping. This also makes sorting easy, a simple 1-dimensional problem.

c)

Use bounding spheres for the objects. See section 12.4, figure 103. The solution is a simple dot product solution. You will need a point in the frustum plane, which we call a (not shown in figure 103).

If a DOT n - c DOT n > r, then the sphere is outside. This test is done for all planes in the frustum, and if all fail, then the sphere intersects the frustum.

(If you change the direction of n, the formula will change slightly.)

Note: The near plane can be omitted from the test.

Note: The test is typically make in world coordinates.

Note: You can, as suggested in the book, start by computing an extreme point on the sphere, called p in the book. This is fully equivalent.