# 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 A^{T}A.

(b) If, in addition to being orthogonal, u, v and w are unit vectors, what is
A^{T}A?

(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 ^{T}A 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 B^{T}A 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 B^{T}A 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 B^{T}A 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 C^{T}A = 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 B^{T} 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

on the circle instead of the explicit radius.

(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,

to guarantee the same radius?

(c) Find an example of two points (x_{0}, y_{0}) and (x_{1}, y_{1}) for which the circle
centered at (x_{0}, y_{0}) through

(x_{1}, y_{1}) 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 |