EECS 488: Assignment 1

Scan Converting Lines & Filling Polygons

Out: 1/16/96
Due: 2/13/96 at 4:00pm

In this assignment you will implement the Midpoint Line algorithm and the Polygonal Fill algorithm given in class and in the textbook using C and Mesa. This will show you how some of the most common graphics routines are implemented, and how the frame buffer works. You will not be issuing any OpenGL calls in this program; all code using OpenGL routines is given to you in the shell program.

You can find a shell of the program here and appropriate Makefiles here

The shell deals with opening a graphics window, accepting keyboard commands, and drawing a user-allocated frame buffer on the screen; so you can concentrate on implementing the algorithms which modify the contents of the frame buffer. The shell draws a simple rectangle, and then fills that rectangle when the user presses the space-bar. Your program will replace these routines with more general routines.

Your program should be run as:
assignment1 polygon-file-name

where polygon-file-name is a text file containing a sequence of vertices specified as X Y where each vertex is connected to the next, and the last vertex is connected to the first, with a line segment.

For example polygon-file-name could contain 4 vertices specifying a rectangle:

You can assume that the file will contain at least 3 lines (vertices), and at most ten lines (vertices) and that the lines will be properly formatted, and contain only integral values. You can also assume that the values given will fall within the bounds of the frame buffer (ie you will not need to perform any clipping.)

You may also reverse the order that a line segment is drawn (e.g. you can assume in this assignment that a line segment drawn from (Xo,Yo) to (X1,Y1) is the same as a line segment drawn from (X1,Y1) to (Xo,Yo).)

Your program should be well commented and be a good example of literate programming.

Your program will be submitted electronically. Odie will talk about this further in the discussion section. You can compile your program using the OpenGL libraries or any of the implementations of the Mesa libraries, but be sure that it compiles and runs under Mesa on the EECS suns because that is where we will be compiling and running your program.

We will test your program using several polygon data files of our own choosing, so be sure your program is robust enough to handle all possible cases. You should therefor test your program on several different data files of your own creation. Some sample polygons are given below which get progressively more complex:

Note that the routines given in the text are not complete; they deal with only a subset of the possible cases. However the other cases are handled by suitably modifying the given algorithms.

I would suggest first looking at the shell and understanding how it works (especially with regard to the orientation of the frame buffer ... hint! hint!). Then add in the code to read in the vertices and draw just the vertices in the frame buffer to be sure they are read in correctly. Then proceed onto the Midpoint Line algorithm starting with lines with 0<=slope<=1 and proceeding onto lines with other slopes. Then add in the code for the Polygonal Fill algorithm. Understand the algorithms before you start coding. If you try and modify them by randomly flipping signs or adding a 1 here or there you will get into trouble very quickly.

Since you know the maximum number of line segments possible you can do this program using just arrays, rather than arrays of linked lists, for the ET and the AET, though I think linked lists are easier to manage.