Project 1: Polygon Scan Conversion

Objective

Note: p1_stub_scan2d_v2.zip is an update (8/31/2006) of p1_stub_scan2d.zip. The only difference between the two is one line of code in gtstuff.pde line 33: change "c = get(x, y);" to "c = get(x, height - y);".

What The GT Graphics Library Provides

gtClear (int red, int green, int blue);
gtWritePixel (int x, int y, int red, int green, int blue);
gtSetWriteMode (GT_OVERWRITE | GT_XOR);

gtClear (int red, int green, int blue);

This clears all the pixels in the framebuffer. Calls to this routine have already been placed in the stub program before drawing each test case, so you probably won't need to use it yourself to complete the assignment.

gtWritePixel (int x, int y, int red, int green, int blue);

This will write a pixel at the specified integer x and y location on the screen. The pixels are numbered in x from 0 to width-1 in the horizontal direction (from left to right) and they are numbered in y from 0 to height-1 in the vertical direction (from bottom to top). Note that the bottom-to-top numbering in the y direction is opposite of many windowing systems (including Processing, which assumes pixel 0,0 is in the upper-left hand corner). Pixel 0,0 is in the lower left-hand corner of the framebuffer. The color that is written to the pixel is given by the three integers, all of which must have a value from 0 to 255, inclusive. It is this gtWritePixel routine that you will be calling in the heart of your polygon scan conversion routine.

Note (9/6/2006): Here is the code for a faster version of gtWritePixel(). The main difference is that pixels[] is used to access the pixels. This requires a call to loadPixels() beforehand and a call to updatePixels() afterwards. The Processing online help on pixels[] notes that this is faster than using point(). Thanks to Romain Cledat for the code.

// assumes loadPixels() has been called before calls to this routine
// assumes updatePixels() will be called after calls to this routine
void gtWritePixel (int x, int y, int r, int g, int b) {
  color c;
  int cr, cg, cb;
  int index = (height - y) * width + x;
  if(gtWriteMode == GT_XOR) {
    c = pixels[index];
    cr = ((c >> 16) & 0xFF) ^ r;
    cg = ((c >> 8) & 0xFF) ^ g;
    cb = (c & 0xFF) ^ b;
  } else {
    cr = r;
    cg = g;
    cb = b;
  }
  pixels[index] = color(cr, cg, cb);
}

gtSetWriteMode (GT_REPLACE | GT_XOR);

This routine affects the behavior of the gtWritePixel routine. By default, gtWritePixel replaces the contents of the framebuffer at the given pixel by the color specified. If, however, the gtSetWriteMode routine is called with the parameter GT_XOR, then subsequent calls to gtWritePixel will cause a bitwise exclusive-or of the given color values with the contents of the framebuffer.

What You Write

gtBegin (GT_POLYGON);
gtEnd ();
gtColor3f (float red, float green, float blue);
gtVertex2f (float x, float y);

Here are the expected behaviors of these four routines:

gtBegin (GT_POLYGON);

This routine signals the start of a polygon that is to be drawn.

gtColor3f (float red, float green, float blue);

This specifies the red, green and blue components of the color of subsequent vertices. A given vertex specified by gtVertex2f() always acquires the color that was specified by the last call to gtColor3f().

gtVertex2f (float x, float y);

This routine specifies the x and y positions in screen-space of a vertex. This vertex is added to the growing list of vertices that are to be drawn. The color of this vertex is that of the last gtColor3f command that was executed. The x and y values of this routine do not correspond to pixel coordinates in the window. Rather, these floating-point values represent positions in the x range [0,1] and in the y range [0,aspect]. For example, on a square framebuffer the coordinates 0.5,0.5 will be in the exact center. The coordinates 0.1,0.9 specify a vertex that is near the upper left of the framebuffer. If the framebuffer is not square, the y values can vary from zero up to height/width (also called the aspect ratio).

Important Note: Do not round or truncate the coordinates of the vertices to the nearest pixel. You will need to keep sub-pixel accuracy in order to produce adjacent polygons that have no cracks between them and no overlaps.

gtEnd ();

This routine indicates that all the vertices of the polygon have been given and that the polygon should be drawn. The polygon should be scan converted when this routine is called, that is, the pixels should be written to the framebuffer.

As an example, here is the outline of a program that should draw a white square in the center of the screen:

/* clear the screen */
gtClear (0, 0, 0);

/* draw a white square */
gtBegin (GT_POLYGON);
gtColor3f (1.0, 1.0, 1.0);
gtVertex2f (0.25, 0.25);
gtVertex2f (0.25, 0.75);
gtVertex2f (0.75, 0.75);
gtVertex2f (0.75, 0.25);
gtEnd ();

Grading of the Assignment

• Produce no cracks between adjacent polygons
• Have no overlaps between adjacent polygons (test with XOR mode)
• Properly interpolate the colors of the vertices

There are two ways that you may wish to write this polygon scan converter. One way assumes that you will have at most two intersection points between the polygon edges and each scan line. This method is more simple to code than the general case because you only need to keep track of two edges at any one time (the left and right edge). This is the easier of the two alternatives, and it is a perfectly acceptable way of completing the assignment. The test cases will include only horizontally convex polygons.

The second approach to writing a polygon scan converter is to handle the case of arbitrary (convex and concave) polygons. In this approach, you must first create an Edge Table and then also have an ordered list of edges that changes as you move from one scanline to the next that is called the Active Edge Table. If you wish to have more of a programming challenge it is fine to complete the assignment using this more general approach. Both approaches will be graded out of 100%.

Use the even-odd rule for determining whether a pixel is inside the polygon. No polygon clipping is required in this assignment. Assume that all vertex coordinates are valid and within the framebuffer edges.

General Hints

The best resource for Processing language questions is the online or offline Processing language API (found in the "reference" subdirectory of the Processing release).

Authorship Rules