2D Polygon Scan-line Algorithm

Goal

For this assignment, you will implement the scan-line polygon fill algorithm described in class and in the text. You will be given a working program that allows you to enter vertices of a polygon using mouse clicks on an area of the screen, and which draws the polygon using the OpenGL glVertex2f() routine. You will replace this routine with your own routine that, given a series of (x,y) vertices, fills the interior of the polygon defined by those vertices. Your fill routine should render GL_POINTS only, each with a pixel size of 1.0.

In addition to submitting the code of your implementation of the polygon fill algorithm, you are to turn in a written report that answers questions about your work, given at the end of this assignment description. All work must be your own. You may discuss the algorithm involved with other students at a high level, but the implementation of the algorithm must be your own work.

What You Get

In the ~cs4390/OpenGL/Polygon directory, you will find the components of the program that you will modify, including a Makefile, the main file poly.c and its header, poly,h, which creates a window and contains the polygon rendering routine (drawPoly()), and the file handlers.c, which contains the code to accept mouse and keyboard input, and calls the polygon rendering routine when the window needs to be redrawn. If you copy all of the files in ~cs4390/OpenGL/Polygon to a directory in your account, and type "make" (when logged into a SGI machine), then the simple program should be compiled, producing an executable file called "poly".

When you run "poly", you should get a window on your screen

Left mouse click, which places a vertex at the location of the mouse pointer.

Right mouse click, which places a vertex and uses it and previous vertices to define the polygon.

Space, to clear the window of all polygons.

ESC, to exit the program.

Hint: Although entering points via the mouse is cool, for testing purposes you may wish to temporarily re-write the leftMouseClick() and rightMouseClick() routines in handlers.c to use specific, hard-coded, vertices. This could be used, among other things, to test your algorithm for the special case of two adjacent polygons. You will not be turning in your handlers.c code, so be sure that your program works correctly with the original handlers.c code before submitting your program.

What We Expect

To complete this assignment, you will need to replace the glVertex2f() routine in the drawPoly() function in poly.c with a call to your own routine that uses points and your scan-line polygon fill algorithm to render the interior of the polygon. You should include your own code in the poly.c file, which you should turn in by sending it via email to Drew (drew@cc.gatech.edu). You should not send any other program file to Drew.

Your submission will be graded on:

· Clarity of presentation. Your code should be well documented and formatted for easy reading and understanding.

· Correctness. Polygon interiors are completely filled. If two polygons share an edge, then there should be no gaps between the polygon, and no point should be used by both polygons. Your algorithm should handle self intersecting polygons using the rule that a point is "inside" the polygon if a line draw from it, in any direction, crosses an odd number of edges. For example, a star polygon would be rendered as shown in the ~cs4390/OpenGL/Polygon/star.rgb file (view it with "ipaste star.rgb" on an SGI machine)

Note that your code must compile and run correctly on an SGI machine in the SGI lab. If your program cannot be compiled and run, then you will not receive any credit for the assignment.

Written Questions

Written answers to these questions about your implementation of the scan-line polygon fill algorithm should be emailed (separately from the poly.c file) to Drew by the due date and time.

1)The polygon fill algorithm described in the text mentions four special cases that must be addressed to avoid drawing pixels multiple times. How does your program address each of these issues?

A)Ensure that filled pixels are inside the polygon (otherwise, they could overlap with other polygons).

B)Special case where a span begins or ends at an integer pixel coordinate. (Two polygons that share the edge containing this point would both want to highlight the pixel, but only one of them should.)

C)Special case where a span begins or ends at a polygon vertex. The start and end vertices of two different edges of the same polygon would both want to highlight this pixel, but only one of them should.)

D)Special case where the span is a horizontal edge at an integer y value. (Two polygons sharing that edge would both want to highlight it.)

2)Describe your algorithm for tracking the x coordinate of edges for all line slopes. Code or pseudo code is ok as long as you explain why it works.

Extra Credit (5 points)

For extra credit, allow the user to switch between a solid polygon and a pattern-filled polygon by pressing the `p' key. This will require augmenting your scan-line algorithm to deal with patterns, where a solid polygon is the special case of a solid pattern, and adding a routine that responds to the `p' key by switch the pattern from solid to something else. You should define in your code a default, non-solid pattern, and clearly describe in the documentation what that pattern will look like. If you want to get fancy, you could read new patterns from a file, if it exists. In this case, clearly define in the documentation how the pattern file is formatted.

If you decide to implement the pattern fill feature for extra credit, you will need to send in your handlers.c file as well as the poly.c file. You may send them in the same email message, or separately, as long as you clearly state that you have done the extra credit assignment and Drew should expect 2 files, not just 1.