The task in this lab was to design an API for interacting with images, and implement some basic functions for plotting points, and drawing lines, circles, and ellipses.
We implemented a version of Bresenham's line drawing algorithm. It uses entirely integer math, and does some clever bit shifting to avoid having to multiply. It's not terribly optomized, in that it doesn't start from both ends or anything, but our plot function (which it calls to actually write a pixel to an image) is an inline function, which makes it pretty speedy. Using Bruce's benchmarking tool (modified somewhat to work with our API), we were averaging something like 550,000 lines per second on an Intel P4 running at 2.6 GHz when compiled with gcc 2.95.4, the Debian Stable build.
We wrote two versions of drawLine, one of which uses pixel centers as coordinate axis intersections, and the other of which uses the upper left (in screen space) corner of pixels. The latter is better suited to drawing polygons, because it allows us to have polygons that share verticies without having them overlap. It also gives polygons the correct geometric area with respect to their mathamatical side length. The pixel-centered version is useful to have around, however, for drawing lines that you want to include two known pixels as endpoints.
The circle algorithm we used was also concieved by Bresenham. We chose to draw in the upper half of the lower right quadrant of the circle, since this gives the circle the correct area, and then transforming the x and y coordinates so that the entire circle was drawn (taking advantage of the eight-way symmetry). By drawing lines between points horizontally accross the circle, we were able to easilly fill the circles in. When using alphp-blending to shade filled circles, it was neccessary to make sure we didn't draw the same lines twice, as this would make the color of those lines more intense.
The axis alligned ellipses were drawn in a fashion very similar to the circles, and were filled the same way. We used the code from Bruce's graphics web page (originally taken from Hearn and Baker) for this algorithm.
The arbitrarilly oriented ellipses were more complex, and we used a 2002 paper by C. Bond called "A New Algorithm for Scan Conversion of a General Ellipse" as a reference. We would like to note that it has a typo; the equation for 'd' on page 6 should read "2C..." rather than just "C...". It took us a very long time to figure out what was wrong, since we had derived all the other equations ourselves, but not the initial one. With this correction made, and having done all the math correctly, this algorithm works very nicely. The state variable 'd' must be a floating point number, but everything else can be safely left as an integer with no ill effects, and the algorithm is incremental, involving only additions and multiplications at each step to get the next value of 'd'. No trigonometric functions, and no square roots fall inside the update loop, though several are needed in the initialization. We do not have a filled in version of this function, since these ellipses are only symmetric accross a single axis, which means we cannot simply draw lines between points that are accross from each other. We would need to implement a flood-fill algorithm, and we have not done so yet.
The first thing to be aware of is that we chose to implement our graphics environment in C++, to make use of all of the advantages of classes and object-orientation. For example, this framework allows us to declare an instance of an image on the stack with a single command which does all of the initialization of all relevant state variables as well as memory allocation without having to do it all by hand every time. Not only is this easier on us, but it makes code much easier to read and debug.
The main class that we defined to deal with images is GraphicImage. This class handles allocation and file IO as well as providing an interface for all of our graphics primitives. It currently supports ppm and pgm filetypes, but could easily be expanded to handle other image formats without the need for modification to any user-level code. Thus, old programs could be recompiled with the new library and be able to read and manipulate the new image formats. GraphicImage contains member functions to initialize the image to black, as well as a number of accessors and mutators as follow:
int intensity(const Point &p);
/* Basic accessors and mutators.
* These are inline functions, and appear below.
*/
Pixel get(const Point &p); // returns the value at a point
Pixel get(int x, int y); // as above, but takes x, y instead of a point
void plot(int x, int y, GraphicContent *gc); // turns on the specified pixel
void plot(const Point &p, GraphicContent *gc);
void shade(int x, int y, GraphicContent *gc); // like plot, but uses alpha blending
void shade(const Point &p, GraphicContent *gc);
/* Graphics primitives for drawing in images.
* Code appears in DrawShapes.cpp
*/
void drawLineC(const Point &p1, const Point &p2, GraphicContent *gc); // pixel-center coordinate system line algorithm
void shadeDrawLineC(const Point &p1, const Point &p2, GraphicContent *gc); // as above, but does shading
void drawLine(const Point &p1, const Point &p2, GraphicContent *gc); // pixel-corner coordinate system line algorithm
void shadeDrawLine(const Point &p1, const Point &p2, GraphicContent *gc); // as above, but does shading
void drawPolyline(const PointList &p, GraphicContent *gc); // draw lines between each pair of points in the list
void shadeDrawPolyline(const PointList &p, GraphicContent *gc);
void drawPolygon(const PointList &p, GraphicContent *gc); // draw lines between each pair of points, connecting the last and the first
void shadeDrawPolygon(const PointList &p, GraphicContent *gc);
void fillPolygon(const PointList &p, GraphicContent *gc); // scanline polygon fill algorithm
void shadeFillPolygon(const PointList &p, GraphicContent *gc);
void drawRectangle(const Point &p1, const Point &p2, GraphicContent *gc); // takes opposite corners of a rectangle, and draws a box
void drawCircle(const Point &c, int r, GraphicContent *gc); // draws a Bresenham's circle
void shadeDrawCircle(const Point &c, int r, GraphicContent *gc);
void drawEllipse(const Point ¢er, int Rx, int Ry, GraphicContent *gc); // draws an axis-alligned ellipse
void fillEllipse(const Point &c, int Rx, int Ry, GraphicContent *gc); // fills an axis-alligned ellipse
void shadeFillEllipse(const Point &c, int Rx, int Ry, GraphicContent *gc);
void fillCircle(const Point &c, int r, GraphicContent *gc); // fills a circle
void shadeFillCircle(const Point &c, int r, GraphicContent *gc);
void drawOrientedEllipse(const Point ¢er, double semimajor, double semiminor, double theta, GraphicContent *gc); // draws an arbitrarily oriented ellipse
void shadeDrawOrientedEllipse(const Point ¢er, double semimajor, double semiminor, double theta, GraphicContent *gc);
/* These are general image manipulation functions.
* Code appears in ManipulateImage.cpp
*/
void goodResize(int newx, int newy); // not fast, but does a good job by projecting pixel corners from and doing area-based averaging
void reflectv(void); // reflect vertically
void reflecth(void); // reflect horizontally
void rotatecw(void); // rotate clockwise 90 degrees
void rotateccw(void); // rotate counter-clockwise 90 degrees
You may have noticed, Bruce, that all of the above drawing functions
take a pointer to something called a "GraphicContent." This is a class
that contains the state variables that tell plot what to draw. This
includes color, and alpha, which is a float between 0 and 1. Actually,
the plot function ignores alpha; it's only used if you call shade
instead of plot, which is why we need two prototypes for every
function. This class may later get other things, such as background
color, texture fill pattern, brush width or type, or other attributes.
So far, all the fields of this class are public, and can be set by
user-space programs, though it is possible that this will change in the
future, and we will add accessors and mutators to deal with things
which are more complicated.
Well Bruce, both our circles and our ellipses can be filled. Additionally, lists of points can be passed to drawPolyline and drawPolygon, and will be drawn in the specified order (drawPolygon connects the last to the first). Also, all drawing primitives (both draw and fill) have a shading version, which does alpha blending based on a constant that is part of the GraphicContent, which also contains the pen color, among other things. These cause the plotted color to be mixed with whatever it is being drawn over to a degree weighted by the constant alpha (range 0 - 1). We also implemented arbitrarily oriented ellipses using an incremental, mostly integer algorithm (see above).
Also, we drew some cool pictures. Which I guess is not
technically an extension, but there was nowhere else they really fit
in, so they're here at the end.
Here they are. Enterprise by Ben, Borg Cube by Zach. (Note: they're scaled
down so they both fit next to each other. Right click on one and say "view
image" if you want to see each one full scale.)
