Give detailed explanations and examples when necessary for full credit.

1) (5 pts) Will the symmetrical DDA algorithm discussed in class ever generate the same point three times in succession? Why or why not?

No. Epsilon (2^(-n)) is found by solving the following formula for n:
2^(n-1) <= max(abs(deltax),abs(deltay)) < 2^n

n  n-1  2^(n-1)  2^n  2^(n-1) <= x < 2^n 
1  0    1        2    1 
2  1    2        4    2,3
3  2    4        8    4,5,6,7
4  3    8        16   8,9,10,11,12,13,14,15

and so on.

What we see is that either epsilon*deltax or epsilon*deltay will be at least 1/2. In order to generate the same point three times we must stay on the same (x,y) point three times in succession, but this is clearly impossible since we are adding at least 1/2 each time to one of the coordinates. Example, let's assume that epsilon*deltax is 1/2 and x starts out at 0. Further, assume that we are plotting the round(x). This leads us to the following:

x   plot_pixel(round(x))
0   0
.5  1
1   1
1.5 2
2   2
2.5 3

2) (5 pts) How will the polygon scan conversion algorithm scan convert the following polygon at the current scan line?

There are two edges in the current edge list. When the scan conversion algorithm encounters the polygon at the current scan Line, the algorithm will fill from one edge to the other depending on the sorting algorithm. In either case, the fill will amount to a single point.

3) (10 pts) Consider a convex polygon (a polygon with each interior angle < 180 degrees) with N vertices being clipped against a rectangular window.

(a) Give a mathematical formula for the maximum number of vertices that can be produced in the resulting clipped polygon. Give a picture that represents this case.

My assumption was that the polygon could not be self-intersecting in which case the answer is: maxvertices = 2N.

We discussed pictures in class.

(b) Give a mathematical formula for the minimum number of vertices that can be produced in the resulting clipped polygon. Give a picture that represents this case.

minvertices = 0.

We discussed pictures in class.

4) (30 pts) Consider a window and viewport defined as follows:

set_window(0,25,-4,22);
set_viewport(0.6,1.0,0.5,1.0);

Given the line segment(P0P1) where P0=(9,9) and P1=(16,18) in the world coordinate system, answer the following three questions(Show all work for full credit!!):

(a) What is the coordinate of P0 in the viewport coordinate system?

Xnorm=(Xuser-Wxl)/(Wxh-Wxl)*(Vxh-Vxl)+Vxl
Ynorm=(Yuser-Wyl)/(Wyh-Wyl)*(Vyh-Vyl)+Vyl

Xnorm=(9-0)/(25-0)*(1.0-0.6)+0.6 = .744
Ynorm=(9-(-4))/(22-(-4))*(1.0-0.5)+0.5 = .75

(b) Assuming a display device with resolution 350x600 (0 to 349 in X) and (0 to 599 in Y), what are the absolute device coordinates of P0?

absx = .744(349) = 260 (round up) or 259 (trunc)
absy = .75(599) = 449 (round up or trunc)

(260,449) or (259,449)

(c) Clip the line segment(P0P1), where P0=(20,10) and P1=(32,6) in world coordinates, against the boundary defined by set_window above. What are the resulting segment coordinates.

x = Wxh = 25
y = y1 + (y2-y1)*(Wxh-x1)/(x2-x1)
= 10 + (6-10)*(25-20)/(32-20)
= 8.3

P0=(20,10) & P1=(25,8.3)

5) (5 pts) Assume an arbitrary line segment(P0P1) where P0=(X1,Y1) and P1=(X2,Y2). Give a general formula for finding the maximum number of steps the midpoint subdivision algorithm would go through in clipping this arbitrary line segment.

steps = log2(max(abs(x2-x1),abs(y2-y1)))

6) (5 pts) Assume the Cohen-Sutherland line clipping algorithm clips lines in the following order: bottom, right, top, left. Draw a line segment below which will produce worst case performance for this change.

Answer:

7) (5 pts) We defined a straight line using the chain code as follows: if no uneven substrings are contained in the digital arc, then this implies that the arc is a straight line. Further, a consequence of this is that "Only the symbol that occurs less frequently is isolated". Based on the previous definition, why must this be the case. Use an example for clarification. uneven is defined as "two substrings that are equally long have summed values that differ by more than 1". We know that the chain code for a straight line contains no uneven substrings.

Consider the chain code: 11011. This chain code represents a straight line because no uneven substrings are contained in the digital arc. It must also be the case that the symbol that occurs less frequently in this case, 0, is isolated for if it wasn't we could have something of the form: 110011, but that would not represent a straight line becasue this string is now uneven.