CS40: Computer Graphics, Lab 3

Graphics Primitives

By Jeff Kaufman

In this lab I extended the graphics library I started in lab 2 by adding Polygons, Polylines, and filled shapes.

Polygons and Polylines are very similar, the only difference being that Polylines do not have their first vertex connected to their last vertex. Their data structures could be the same, as for both an array of points is reasonable, so I made them the same. As a result, my graphics library will not complain if you tell it to Polygon_drawFill on a Polyline or Polyline_drawFrame on a Polygon. These are not, however, in the spec and so should not be relied on.

Antialiasing

All the drawing routines for Polys are antialiased. For outline drawings of Polys this is implemented using the integerized antialiased line drawing code implemented in lab 2. For filled Polygons the algorithm is one I came up with, but it is simple and so likely standard.

The Polygon antialiasing algorithm has two cases, split by the slope of the edge. For steep slopes (dxPerScan <= .5) we take the last pixel in the row and color it by what would be the Bresenham's error term. For less steep slopes we do a linear gradient over the last dxPerScan+.5 pixels.

The circle and ellipse algorithms are not antialiased.

Speed

I wrote modified versions of testbench.c to determine how quickly my drawing routines ran. On a CS lab machine with a 3.0 GHz Pentium 4 processor it could draw 45000 figures per second for both circles and ellipses. For polygons it could draw only 17000. This is still somehat impressive because the calculations are floating point, the edges are antialiased, and there are more things to be keeping track of.

Writing this test code reasonably was actually somewhat difficult. The testbench.c provided was easy to adapt from line counting to circles and ellipses, but for polygons it was tricky. In order to be sure that the area of the polygon was between 400 and 1000 or close I needed pretty good control over which polygons were generated. I wrote a function which picked a random point in the image and went in a circle from there, jumping PI/4 to PI/8 after plotting each point at a random radius. This generated reasonable polygons which had no more than 1300 or less than 300 pixels, but almost all the time were in the desired range. They also look relatively pretty:

API Info

The basic API is presented in the graphics specification for the lab. I wrote in C, and so implemented the C portion of the spec, extending the portions I wrote last week. I did not write any addtional functions for this week.

Mathematicality

I tested the correctness of these methods by drawing polygons, calculating by hand where they should be, and testing against what xv reported. Unfortunately my program didn't do that well. The main problem is that in anti-aliasing the edges I only shade pixels that would be in the polygon. This then makes the polygon appear smaller than it ought to. This also results in ugly places where you can see some of the background through what ought to be a tight joint. Attempts to fix this by drawing polygons larger looked worse, so things are left as they are. If this becomes particularly troublesome later or I think of a nice solution I'll fix it.

Pretty Pictures

The test image:

A trolley car:

Jeff Kaufman : 2005
cbr at sccs dot swarthmore dot spam edu. Remove spam.

main page