**1: Polygon Filling – 50 points**

Show the contents of the ET, AET, along with the events that change them and which pixels are filled in, scanline by scanline, while filling the following polygon: (10,10), (20,10), (20,16), (16,16), (13,13), (10,16) where an edge connects each point to the next and the last back to the first.

**2: 3D Graphics – 120 points**

Assume you have the following two polygons defined by their coordinates in X,Y,Z, assuming a right handed coordinate system (Z coming out of the screen, same as used in class) and no clipping

Polygon 1: (20,0,0), (20,20,0), (20,20,20), (20,0,20)

Polygon 2: (20,0,0), (40,0,0), (20,20,0)

For each of the following conditions draw and label a diagram showing the 2 sets of axis, the 2 polygons, the PRP, and the window. Also in a second drawing, show what will appear in the window. So you should have 6 drawings total.

VRP 20,0,20

VPN 1,0,0

VUP 0,1,0

PRP 0,0,25

U -25 to 25

V –25 to 25

perspective

VRP 20,0,0

VPN 0,0,1

VUP 0,1,0

PRP 0,0,25

U -25 to 25

V –25 to 25

perspective

VRP 20,0,20

VPN 0,1,0

VUP 1,0,0

PRP 0,0,25

U -25 to 25

V –25 to 25

perspective

**3: OpenGL**

Assume you have the same shell that you used in the first Assignment with the camera projection set up as follows:

glMatrixMode(GL_PROJECTION);

glLoadIdentity();

gluOrtho2D(-200, 200, 200, -200);

glClearColor(0.0, 0.0, 0.0, 1.0);

and the following functions for drawing:

void DrawSquare(void) /* Draw a square centered at the origin with
sides of length 1 */

void DrawCircle(void) /* Draw a circle centered at the origin with
diameter of length 1 */

void DrawTriangle(void) /* Draw a triangle with the three corners
(-1,0), (1,0), (0,1) */

Write a program to create the following scene:

**Question 1: BSP Trees – 75 points**

Given the following set of 6 polygons with front-facing normals shown, generate the BSP tree starting with A and adding polygons in alphabetical order. Then generate the BSP tree starting at F and adding polygons in reverse alphabetical order. Once that is done generate the far to near sequence of polygons for each of the eye positions (1 and 2) using the first BSP tree.

**Question 2: Depth Sort – 75 points**

1. Sort all polygons based on their farthest z
coordinate

2. Resolve ambiguities

3. Draw the polygons in order from back to front

Where step 2 deals with any polygons whose z extents overlap. We start with the furthest polygon and call it P. Polygon P must be compared with every polygon Q whose z extent overlaps P's x extent. 5 comparisons are made. If any comparison is true then P can be written before Q. If at least one comparison is true for each of the Qs then P is drawn and the next polygon from the back is chosen as the new P.

1. do P and Q's x-extents not overlap.

2. do P and Q's y-extents not overlap.

3. is P entirely on the opposite side of Q's plane from the
viewport.

4. is Q entirely on the same side of P's plane as the viewport.

5. do the projections of P and Q onto the (x,y) plane not overlap.

If all 5 tests fail we quickly check to see if switching P and Q will work. Tests 1, 2, and 5 do not differentiate between P and Q but 3 and 4 do. So we rewrite 3 and 4

3’ is Q entirely on the opposite side of P's plane from
the viewport.

4’ is P entirely on the same side of Q's plane as the viewport.

If either of these two tests succeed then Q and P are swapped and the new P (formerly Q) is tested against all the polygons whose z extent overlaps it's z extent.

On the next page draw me an example for each of these 7 cases (1, 2, 3, 4, 5, 3’, 4’) to illustrate the condition where that case is satisfied but the previous conditions were not. For example for #3 you need to draw a scene where condition 1 and 2 are false, but 3 is true.

Make sure the drawings are very clear, and unambiguous. You may want to have multiple drawings showing different views of the same case if that helps. Be sure your axis are labelled

**Question 3: OpenGL - 150 Points**

One of the types of games that we did not code in the course is the ‘tetris’ game, where there are bricks falling from the top of the screen down towards the bottom and piling up. In this question you are to write the complete code for such a game (including all the GLUT code) given the following constraints:

- The playing field is 8 squares wide by 20 squares tall

- One brick will fall every second from the center of the top of
the screen

- All of the bricks will be square and take up one square on the
screen (which greatly simplifies the game compared to the original
where there were multiple brick shapes)

- Each brick moves slowly downwards and lands on top of whatever
is beneath it (perhaps another brick, perhaps the bottom of the
window)

- The user can move the brick left and right one square at a time
using the arrow keys while it is falling

- Whenever a complete row of 8 squares is filled then that row
disappears. All bricks above that row drop down one row.

Half of your score is based on the implementation and half of the score is based on your design, so I would work out the design first and how you are going to break the program into modules before coding. Comments are also a very good idea so I know what you are trying to do …

Closed Book, Closed Note, Closed Neighbour, Closed
Electronic Devices & no tinkertoys

Please turn off all cell phones and pagers for the duration of the
exam

**Question 1: BSP Trees – 75 points**

Given the following set of 6 polygons with front-facing normals shown, generate the BSP tree starting with A and adding polygons in alphabetical order. Then generate the BSP tree starting at F and adding polygons in reverse alphabetical order. Once that is done generate the far to near sequence of polygons for each of the eye positions (1 and 2) using the first BSP tree.

**Question 2: Warnock’s Algorithm – 75
points**

Use Warnock's Algorithm to assign values to the following scene. Recurse as far as necessary drawing in the divisions you are using on the diagram below and ensuring each of your boxes is labeled in one of five ways.

1. all disjoint

2. single contained or intersecting

3. single surrounding

4. front surrounding

5. needs further subdivision beyond the resolution of the diagram

**Question 3: OpenGL - 150 Points**

One of the types of games that we did not code in the course is a ‘breakout’ game, where the screen looks similar to the pong screen except that in front of the top wall there are several rows of bricks, and when the ball hits one of those bricks the brick is destroyed. The goal is to destroy all the bricks. In this question you are to write the complete code for such a game (including all the GLUT code) given the following constraints:

- The player’s paddle moves left/right across the bottom
of the screen

- There will be 4 rows of bricks stretching left to right across
the upper half of the screen

- There are 10 bricks in each row

- If the ball hits a brick then the brick is destroyed at the
ball’s Y velocity is reversed. Note that the ball may hit the
brick from the top or bottom

- The ball will have a constant horizontal and vertical speed

- The ball bounces off the sides of the screen as in the Poing
assignment – by reversing the appropriate velocity

- There is a bottom wall below the paddle so the ball can never
leave the playing field (so its impossible to lose the game)

- The ball starts out moving downward at 45% starting out
inbetween the bricks and the player’s paddle.

Half of your score is based on the implementation and half of the score is based on your design, so I would work out the design first and how you are going to break the program into modules before coding. Comments are also a very good idea so I know what you are trying to do …