Final Exam

1. ( Change of coordinates ) Suppose x=au+bv+cw, with
and x = (x, y, z) in some coordinate system .

(a) Write the coordinates of x = (x, y, z) in terms of the coordinates of u, v, and w.

(b) Write the coordinates from part (a) in the form

where A is a 3*3 matrix

(c) Now suppose the coordinates of x = (x, y, z) are known, and given the coordinates of some u, v,
and w, we wish to find a, b, and c such that x = au+bv+cw. How can they be computed?

2. (Orthogonal change of coordinates) Continuing the previous problem , suppose u, v, and w are perpendicular
(orthogonal), i.e., u*v = 0, u*w = 0, and v*w = 0.

(a) compute ATA.

(b) If, in addition to being orthogonal, u, v and w are unit vectors, what is ATA?

(c) Use the result from part (b) to solve the equation

for a, b, and c.

(d) Use the result from part (a) to solve the equation if u , v, and w are orthogonal but not not necessarily
unit vectors.

3. (3*3 matrix inversion)
The previous exercises show how to compute the inverse of a matrix with orthogonal columns: the
key property is that A TA is a diagonal matrix, and hence is a small step from the identity matrix. This
is a special property of orthogonal matrices, for general matrices, it does not hold. However, if we
can construct a matrix B such that BTA is a diagonal matrix, the inverse of A is not far off.

Let

(a) Suppose B is some 3*3 matrix

Show that

(b) The matrix BTA is a diagonal matrix if u' is perpendicular to v and w, v' is perpendicular to u
and w, and w' is perpendicular to u and v. In this case, the vectors u', v', and w' are said to be dual to
u, v, and w.

Explain why the vectors

are dual to u, v, and w. (You may refer to a problem on the previous homework assignment.)

(c) With u', v', and w' as computed from u, v, and w as above, the product matrix BTA is a diagonal
matrix, but not the identity matrix. For what scalars a, b, and c does the matrix C having columns au',
bv' , and cw' produce CTA = I? (Hint: look at the code for matrix3d::inverse() if you get stuck.)

(d) Express the scalars a, b, and c directly in terms of the coordinates of u, v, and w, and show that
they all have the same value. Show that this common value is the determinant of A. (You may want
to refer to the scalar triple product problem from the previous homework.)

(e) It follows from the previous part that Write out BT in terms of the entries of A,
thereby providing a direct formula for the inverse of A.

4. The cosine of the angle between two vectors u and v is defined as

The C++ acos function can be used to compute q from this expression. One might try the following
C++ code for this:

float theta = acos(u.dot(v)/(u.length()*v.length())),

Is this guaranteed to work? Why or why not?

5. Although it is common to use the term “line” in graphics for the output of Bresenham’s midpoint
line-drawing algorithm, it has its shortcomings as a representation of a mathematical line , or even a
“line” drawn with pen on paper. Describe at least two such shortcomings.

6. Bresenham’s midpoint line-drawing algorithm, as given in class, uses only integer arithmetic to draw a
line between two points having integer coordinates. Explain how the algorithm could be modified for
points having general floating-point coordinates. Is it possible to do so using only integer arithmetic?

7. The function for the midpoint circle algorithm you implemented in the second lab assignment expected
three (integer) arguments: x0, y0 for the coordinates of the center of the circle, and r for the
radius. The draw crude circle function, however, used the (integer) coordinates x1, y1 of a point

(a) Write a C++ expression for the radius of a circle centered at x0, y0, through the point x1, y1,
appropriate for your Bresenham circle function. (Remember that the radius has to be an integer).

(b) If your Bresenham circle algorithm had to call the draw crude circle function (perhaps to
compare the result with the midpoint algorithm) what parameters would you pass to draw crude circle,

(c) Find an example of two points (x0, y0) and (x1, y1) for which the circle centered at (x0, y0) through
(x1, y1) has a non-integer radius. Is there an example for which the square of the radius is not an
integer?

(d) Could the Bresenham circle algorithm be modified to use a point on the circle, given by integer
values x1 and y1, instead of the (integer) radius and still use only integer arithmetic? Explain. (Remember
that there are essentially two parts: what pixel to start with and whether to proceed “East” or
“Southeast” at each iteration of the loop.)

8. One possible alternative to the even-odd rule for filling general polygons would be to fill all the
pixels between the outermost active edges at each scanline. Would this provide a satisfactory filling
algorithm in general? How would it perform on convex polygons?

9. While filling a general polygon by triangles is possible, it involves significant extra computation. On
the other hand, the general scanline polygon fill algorithm works as it stands for filling triangles. What
advantages are there to using the barycentric triangle algorithm over the general polygon algorithm for
filling triangles? Are there any drawbacks to using the barycentric version? Does it make a difference
if the triangle contains only a few pixels, or if it contains a large number of pixels ?

You need not go through a detailed algorithm analysis, a qualitative comparison is fine. (Actually, it is
not fair to compare the two algorithms directly, as the general polygon algorithm can be made much
more efficient than was presented in class).

 Prev Next