Assignment #2 -- Scan Conversion

Due Date

This assignment is due at 11:59pm on Thursday, September 22nd. Projects turned in late will lose point as described in the policies handout. This assignment should be done alone or in pairs. You may share ideas with other groups, but you may not share code.

SUBMISSION DETAILS

You may code your assignment on any of the Unix, OS X, or Windows platforms. As discussed in the class hand out it must run properly on one of the instructional machines.

To submit the assignment use the turnin program described here.

I suggest that you do not touch any file after the submission date. In case some problem occurs with the turnin program, readers can check the file time stamps.

Regardless of which platform you used for the assignment, you should have an as2 directory in your home directory. You should put a README file into this directory that at the minimum contains the following data:

Your (and your partner's) name,
The platform your code runs on,
The location of your source code (i.e. indicate who in your group has done the submission, and on what platform). So only one of you in your group needs to submit the code, but everyone has to create as2 directory that contains the README file and use the turnin program.

All files needed to compile your code should appear in the directory along with your README file. It is your responsibility to make sure that they will compile and run properly.

Windows: The grader should be able to recompile your program by simply opening the project and rebuilding it from scratch.

Unix and OS X: The grader should be able to recompile your program simply by typing "make".

Do not wait until the last minute to start this assignment!

Check the news group regularly for updates on the assignment or other clarification. We will assume that anything posted there is henceforth known to all.

The TA has provided sample code for you to start with and discussed this code in section. If you chose to use that code, you are responsible for figuring out how to use it properly. If you have questions, post them to the news group or ask the Professor/TA during their office hours.

Overview

The assignment is to scan convert polygons. The input will be a file of the form described below. The output will be a display of the scan converted polygons. The polygons may be concave and self intersecting, so be sure to test as many cases as possible. You will be using the algorithm presented in class.

You will use a slightly different mapping for the display window to make it easier to view the results of this assignment. Your window should contain 50 rows of 50 "display-pixels" each. Each "display-pixel" may be very large. For instance, if your window were 500 by 500 pixels, each "display-pixel" would be 10 by 10 real pixels in size.

The lower left corner of the lower left pixel is (0.0, 0.0), while the lower left corner of the upper right pixel is (0.98, 0.98).

Each polygon should be drawn in a distinct (easily distinguishable) color as specified in the file. You should also draw a grid outlining the "display-pixels". The grid is one real pixel wide, in black. It may be drawn using regular OpenGL line drawing commands.

Your program should accept a single command line argument which is the name of a file containing the description for the polygons.

Your program should first generate a filled rendering of the input polygons with the outline of each polygon shown using a black one-real-pixel thick line (this thin outline may be generated with the regular line drawing commands).

The program should then wait for a left mouse-click. Once the user has clicked, the program should use your favorite line algorithm (DDE, Bresenham etc.) to draw the boundary of each polygon in large display-pixels. The lines should be drawn over the already displayed filled polygons. Note that when you do this no pixel that was filled in during the fill process should leak out of this outline. Also note that there cannot be any unfilled pixels inside the outline. Further left mouse-clicks should turn this option on/off (i.e toggle the thick lines).

File Format

The first line should contain an integer, designating the number of polygons your scene contains. There will then be a group of lines for each polygon. The first line in a group is three numbers indicating an RGB color triple (0-255 range). The subsequent lines will have an integer, which is the number of vertices a polygon contains followed by x,y pairs on each line for all the vertices in order, repeated for each polygon. For example, we can represent a scene containing 2 polygons (a red triangle, and a blue quad) by:
2
255 0 0
3
0.1 0.1
0.2 0.2
0.3 0.1
0 0 255
4
0.5 0.1
0.6 0.9
0.2 0.5
0.1 0.7

Vertex positions are in the normalized device coordinate system. So 0,0 is the lower-left corner of the lower-left-most pixel and 1,1 is the upper-right corner of the upper-right-most pixel.

Examples

An example showing a filled polygon with OpenGL lines indicating the boundary. Link
An example showing a filled polygon with "display pixel" lines indicating the boundary. Link
An example showing a filled polygon with extra credit "display pixel" lines indicating the boundary. (See below.)Link

Bonus

You can implement the following for additional marks:

If the program is called with an optional flag (-o output_file_name) then the image should be written to a file instead of displayed on the screen. Any common image format may be used, but we suggest PPM because it is easy to implement.
Notice that a regular line algorithm may fill in pixels that are not inside the polygon. However, you can fix this by modifying the line algorithm (note that this gets trickier, if the polygon is self intersecting). You will get bonus credits, if you can make the outline fit exactly to the polygon boundaries.

Questions should be posted to the news group or to cs184@imail.eecs.berkeley.edu.