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
