We are programming in C++, so our graphics environment consists of a class hierarchy. We have the image class that holds all the information and state variables for a particular image, and we have our graphics primitives (point, line, rect, circle, ellipse, polyline, and polygon) that all inherit from graphic. Each graphics primitive knows how to draw itself onto an image, and some know how to draw filled versions of themselves as well.

To answer the lab questions:

• What state variables do you have and what is their meaning? and How do you represent these variables and what are their types?
  All state variables are stored in the image class. Currently, we have color, of type Pixel, which is the current drawing pen color, and the ints rows, cols, and colors, which store information about the current image. Additionally, we store information about blending in the image alpha mask, stored in the array of unsigned chars called alpha.
• How do users modify/access the state variables? and How do the graphics routines access the state variables?
  Both users and graphics routines access the state variables through accessor methods in the image class. These accessor methods are listed below in the details of the image class.

Here is an outline of our graphics environment classes:

class image:
State variables

Pixel *data	A pointer to an array of Pixels. This holds the actual image data in an image class.
unsigned char *alpha	A pointer to an array of unsigned chars that holds the alpha mask of the image class.
int rows, cols, colors	These state variables hold the rows, cols, and colors of the current image in the image class.
Pixel color	This Pixel holds the current pen color of the image.

Constructors:
An instance of the image class can be created in any of the following ways:

image()	Create an empty image. Initial memory allocation is not performed.
image(string file)	Create a new image from the file path provided. File must be in the PPM format. The state variables rows, cols, and colors will be updated.
image(const image & copy)	Copy constructor -- make a new image from an old one.
image(int cols, int rows)	Make a new image of the given dimensions. Initial memory allocation will be performed.
image(int cols, int rows, Pixel c)	Make a new image of the given dimensions with c as the background color. Initial memory allocation will be performed.

Methods:
The following accessors, mutators, and other methods constitute the interface of the image class:

int getRows()	Accessor returns the number of rows in the current image.
int getCols()	Accessor returns the number of columns in the current image.
Pixel getPenColor()	Accessor returns the current pen color in the current image.
void setPenColor(Pixel p)	Mutator sets the pen color of the image.
Pixel getPixel(int x, int y)	Accessor returns the color value (as a Pixel) of (x, y) in the image.
unsigned char getAlpha(int x, int y)	Accessor returns the alpha value (as an unsigned char) of (x, y) in the image.
void setAlpha(int x, int y, unsigned char a)	Mutator sets the alpha value of (x,y) in the image. 255 is fully opaque, 0 is fully transparent.
void drawPixel(int x, int y)	Draw a pixel with the current pen color to the image at (x, y).
void drawPixel(int x, int y, Pixel color, unsigned char alpha)	Draw a pixel of the specified color and alpha value to the image at (x, y).
void drawPixel(int x, int y, Pixel color)	Draw a pixel of the specified color to the image at (x, y).
void writeImage(string file)	Writes the current image data to disk as a PPM with the specified file name.
bool inImage(int x, int y)	Returns true if the given location (x, y) falls within the image bounds, false if not.
image rotate(double rad)	Returns a new image object consisting of the current image rotated by rad radians. Positive values of rad rotate clockwise, negative values rotate counterclockwise.
image scale(double factor)	Returns a new image object consisting of the current image scaled by a factor of 'factor.'
void shrinkAlpha()	Performs a 4-connected shrink on the alpha mask, treating 255 as boolean true and 0 as boolean false. (Not particularly useful or effective, as it turned out.)
void drawImage(int x, int y, image i)	Draw image i using i's alpha mask at location (x, y) on the current image.
void drawGraphic(graphic &g)	Call the draw method of the given graphic object. The object will then draw itself onto this image.
void drawFilledGraphic(graphic &g)	Call the drawFilled method of the given graphic object. The object will then draw itself filled onto this image.
void fill(point l, Pixel c)	Perform a flood fill with initial seed at point l, looking for boundaries of color c (c is of class Pixel).
void gradFill(point l, Pixel grad)	Perform a gradient flood fill with initial seed at point l, looking for boundaries of any color not equal to the color of the pixel located at point l, and filling with the gradient defined by Pixel grad. Grad should be thought of as a RGB vector in color space that will be normalized to length one. This method is described more in the extensions section of this lab.

As discussed above, the following graphic primitives all inherit from the class graphic. This gives them the ability to be passed to image an using the image::drawGraphic and image::drawFilledGraphic functions. Therefore, along with the functions listed below, each of these classes implements void draw (image & i) and void drawFilled (image & i), which causes them to draw themselves on the image.

class point:
State variables:

long x, y

Holds the x and y location of the point

Constructors:

point()	Constructs an empty point
point(long x, long y)	Constructs a point from two integers, specifying the x and y position
point(const point &p)	Constructs a point from another point (copy contructor)

class line:
State variables:

point start, end

Keeps the location of the start and end of the line

Constructors:

line()	Constructs an empty line
line(point start, point end)	Constructs a line from two points, specifying the start and end of the line
line(int x1, int y1, int x2, int y2)	Constructs a line from four integers, specifying the start (in (x, y) format) followed by the end
line(const line &l)	Constructs a line from another line (copy contructor)

class rect:
State variables:

point lowerL, upperR

Keeps the location of the lower left corner and the upper right corner, stored as points

Constructors:

rect()	Constructs an empty rectangle
rect(point ll, point ur)	Constructs a rectangle from two points, specifying the lower left corner and the upper right corner
rect(point ll, int width, int height)	Constructs a rectangle from a point and two integers, specifying the lower left corner of the rectangle and its width and height

class circle:
State variables:

point center	Stores the location of the center of the circle
double r	Stores the radius of the circle

Constructors:

circle()	Constructs an empty circle
circle(point c, double r)	Constructs a circle from a point and a radius

class ellipse:
State variables:

point center	Stores the location of the center of the ellipse
int rx, ry	Stores radius of the ellipse in the x-direction and the y-direction

Constructors:

ellipse()	Constructs an empty ellipse
ellipse(point c, int rx, int ry)	Constructs a ellipse from a point specifying the center and two integers specifying the radius in the x-direction and in the y-direction

class polyline:
State variables:

point *points	Stores a pointer to an array of points, specifying the various points in the polyline
int pointCount, n	n stores the total number of points in the polyline. pointCount stores the number of points that are currently in the polyline.

Constructors:

polyline()	Constructs an empty polyline
polyline(int n);	Constructs a polyline with a maximum number of points equal to n

Methods:

void addPoint(point p)

Adds the point p to the polyline. If n points have already been added, it returns and error.

class polygon:
State variables:

point *points	Stores a pointer to an array of points, specifying the various points in the polygon
int pointCount, n	n stores the total number of points in the polygon. pointCount stores the number of points that are currently in the polygon.

Constructors:

polyline()	Constructs an empty polygon
polyline(int n)	Constructs a polygon with a maximum number of points equal to n

Methods:

void addPoint(point p)

Adds the point p to the polygon. If n points have already been added, it returns and error.

As described above, all of our graphics primitives (point, line, rect, circle, ellipse, polyline, polygon) inherit graphic, a virtual class. Because of this inheritance structure, all of our graphics primitives know how to draw themselves to an image object, and they can be stored and treated in similar ways. For example, the methods image::drawGraphic and image::drawFilledGraphic can take any graphic primitive as input (although not all graphic primitives know how to fill themselves.) In this section we will discuss some of the graphics primitives.

Bresenham's Line-Drawing Algorithm
We implemented Bresenham's Line-Drawing Algorithm with mathematical corrections to move the axis of each pixel from the center of the pixel to the pixel's lower left-hand corner. Additionally, we adopted the convention that lines will be drawn to the left of their actual mathematical line. Hence, rectangles will look correct (and surround the correct area) when drawn counterclockwise, but will look wrong when drawn clockwise. Here is an example image:

Required image 1: 8 example lines

Here are some benchmarking results for our implementation of Bresenham's Algorithm. These numbers are the average of five tests run on a 1000 Mhz Athlon processor.

• Lines per second: 174,559.
• Standard deviation: 10,746.

Additional useful resources on Bresenham's Line-Drawing Algorithm:

• The Bresenham Line-Drawing Algorithm
• Bresenham Line (google)

Circles and Ellipses
We used Bresenham's circle and ellipse drawing algorithms, modified from Chapter 3, p. 102 of Hearn and Baker. As with the line-drawing algorithm, we modified the circle and ellipse drawing code to so that the generated circles and ellipses bound the correct amount of area on the screen, given their mathematical definitions. As with line drawing, this is accomplished by moving each pixel's axis to the lower left-hand corner of the pixel. We benchmarked our code and got 33,619 circles per second and 35,449 ellipses per second. Additionally, we implemented filling for circles and ellipses. Here is an example image:

Required image 2: some curvy things

Polygons, Polylines, and Rectangles
Our polygons and polylines are arrays of point objects. As with all of our graphics primitives, they know how to draw themselves to an image object. The only difference between a polygon and a polyline is that a polygon automatically connects the last point to the first point, making a closed form. As with lines, by convention our polygons and polylines should be made counterclockwise. Here are some examples:

A polyline

A polygon

Required image 3: an awesome 3D car! (By Will)

Required image 3: totally cool gradient train! (By Andrew) (Added later while doing lab 3. Uses directional and circular gradients, introduced in lab 3.)

Here are our portfolio images:

Portfolio 5: Modern Art (Andrew)

Portfolio 6: Microsoft Paint would have been faster (Andrew)

Portfolio 5: Not quite Picasso (Will)

Portfolio 6: Straight? (Will) (Idea pilfered from mindfake.com)

1. Who did you work with on this assignment, and what tasks did each of you do?
   Will Moss and Andrew Cantino worked together on this lab, as with lab 1. We did much of the coding together, and we have discussed each other's code and techniques extensively. We both worked on circle drawing. Will implemented Bresenham's line-drawing algorithm and ported the benchmarking code, as well as made the benchmark images and some of the example images. Andrew worked on the ellipse code, and the filling code for circles, ellipses, and rectangles, as well as the flood/gradient filling algorithms. We worked together on the graphics environment, the web page, etc. Will did polygon and polyline, and worked on the image of the car. Basically, we split the lab equably and worked together in the computer lab extensively.
2. Describe the API for your graphics environment.
   Please see the section of this lab dedicated to the graphics environment.
3. Is your first required image consistent with how you would match screen coordinates to the true mathematical lines? Why, why not?
   (Please refer to this image.) Yes, we think it is consistent, as the lines appear to have the expected slopes in relation to their mathematical definitions and each other. However, as always, there is the issue of aliasing and our lines are obviously quantized approximations of the actual mathematical lines.
4. If you extended this assignment in any way, describe what you did and how you did it. Include pictures to support your description.
   Please see the section of this lab entitled extensions.

Flood Fill
As an extension, we implemented a 4-connected flood fill algorithm. The algorithm takes a seed point and a boundary color and draws lines horizontally to fill all available space bounded by the boundary color. We use a STL list to implement the seed point stack. The following animation demonstrates the algorithm:

Animation of the flood fill algorithm. Red pixels are seed points. Animation author: Bruce Maxwell

Flood filled polygon.

Flood filled circle.

Additionally, we wrote a second implementation of the flood fill algorithm that can fill with a gradient instead of just a single color. This algorithm takes a seed point and a gradient vector. The gradient vector is merely a RGB point in color space that is then normalized to length one. The algorithm uses the color at the location of the seed point as the background color to be replaced and replaces all pixels of that color reachable (4-connected) from the seed point. To generate the gradient value for any given pixel, we scale our normalized gradient vector by the pixel's horizontal location, scaled to the width of the image. Further work could easily make the gradient run in any direction and scale to the polygon width instead of the image width. Here are some examples of gradient fill:

Gradient filled polygon.

Another gradient!

Another polygon!

Others
We don't know if these are really extensions, but we also did the following that may not have been technically required for this lab:

• Polygons, polylines, and rectangles
• Filling of circles, ellipses, and rectangles (not using the above flood fill algorithm)