Skip to end of metadata
Go to start of metadata

Abstract

The purpose of this assignment was to learn how to program and use graphics primitives to create images. In particular, we wrote algorithms to draw lines, circles, and ellipses, filled circles, and filled ellipses. We also wrote a flood fill algorithm to fill in empty polygons.

Description

Our goal was to use C programming language to write out the algorithms to generate graphics primitives. We then used these graphics primitives to generate simple images and output them in .ppm format.

Solution

The first algorithm we coded was the line_draw() algorithm. This function takes in a Line object, an Image object, and a Pixel object. The line object holds variables indicating the start and end points of the line. The Image object indicates the image that the line is being drawn onto. The pixel object indicates the color of the line.
The algorithm compares the change in x with the change in y for the line. Based on this comparison, it enters one of two loops for drawing the line. If dX (the change in x) is greater, it enters a loop where the x value is incremented in each iteration, and the y value is incremented based on the value of an error term. If dY (the change in y) is greater, it enters a loop where the y value is incremented in each iteration and the x value is incremented based on the value of an error term. At each iteration of the loop, the program draws the current point in the line (indicated by the current x and y values), before moving on to the next iteration. The loop terminates when the either the x value or the y value reaches the value passed into the function. At this point, the line has been completed.

The next algorithm we coded was the Circle_Draw() function. This function takes in a Circle object, an Image object, and a Pixel object. The Circle object holds variables indicating the origin of the circle, and its radius. The Image object indicates the image that the circle is being drawn onto. The Pixel objet indicates the color of the circle.
After initializing the variables that will be used later in the algorithm, the Circle_Draw() function draws the initial 4 points by offsetting the origin of the circle by the radius of the circle. The algorithm then enters a loop, at which point it checks the error variable, which we named f. If the value of f is greater than zero, it decrements y and updates the new error term. The loop then increments x and updates the error term. Finally, it draws 8 points based on the new x and y values. The algorithm makes use of the symmetry of a circle to draw 8 points at every iteration by reflecting a single point over the axes.

The Circle_drawFill() algorithm follows a similar pattern. However, instead of drawing 8 points at each iteration of the loop, it draws 4 horizontal lines between corresponding points. The reason it uses horizontal lines instead of vertical lines is to make use of cache memory, so the program runs faster and more efficiently (instead of having to pull data from main memory, it can pull it from the cache which is much faster). The horizontal lines eventually connect to make an opaque circle.

The Ellipse_Draw() function takes in three variables: an Eclipse object, and Image object, and a Pixel object. The Eclipse object holds variables indicating both of its radii and its origin. The Image object indicates the image that the circle is being drawn onto. The Pixel object indicates the color of the ellipse.
After initializing the necessary variables, the Ellipse_Draw() algorithm draws the first four points by offsetting the origin by the corresponding radius of the ellipse. The algorithm then enters a loop. This loop uses an error term to determine the next point to plot in the ellipse, then utilizes the symmetry of the ellipse to reflect that point to three other points. Unlike the Circle algorithm, the Ellipse_Draw() algorithm is broken into two loops which draw the different quadrants of the ellipse. The first loop iterates until the change in x is less than the change in y. When the change in x is less than the change in y, the initial quadrant has been drawn and the algorithm enters the loop for drawing the next quadrant. The algorithm continues until y = 0, at which point ¼ of the ellipse has already been plotted and reflected onto the remaining segments of the ellipse.

After completing the algorithms, we still needed to generate some sample images. To do this, we each drew a few sketches on graph paper. When we were satisfied with our drawings, we mapped out a coordinate system. We used this coordinate system to determine the input parameters for our code, (i.e. the start and end points of lines, the origins and radii of circles). We then used our code to generate computerized versions of our sketches.

The flood fill algorithm does not relay on the scanline procedure, but rather uses stack recursively invoking itself, with each iteration searching and moving in four directions to check if the boundary or already filled color have been reached. If not, the pixel is colored (here, at the known value for B and G channels and R depending on the depth of the algorithm, increasing at very small ( < 1) intervals per iteration, due to the number of iterations needed.)

Pictures


The prescribed image.


The benchmark file. Results oscillated between 190 and 230 thousands lines per second while ran on iMac Core 2 Duo in Olin labs.


Result of the flood fill.


The pseudo-3D image. We thought that to celebrate Poland being a host of Euro 2012 championships, a real FOOTBALL player would be perfect. (smile)


The change in color represents the spread depth of recursion during the flood fill (the reeder, the deeper the recursion is - and the latter it was filled). Here, it is symmetrical, as the seed is the centre of the circle.


Here, the same technique is applied to fill an irregular object. One can notice that the change occurs traveling clockwise (everything started from the leftmost, uppermost pixel within the frame).

Conclusions

We learned how to implement some of the algorithms we have been talking about in class in C programming language. One useful lesson was how to use the cache and image symmetry to make the program run more efficiently. A problem we ran into was the fact that the coordinate system of the pixels has the origin in the top left. Before we realized this, we were using the standard Cartesian coordinate system with the origin in the bottom left. This led to some confusion before we figured out our mistake.

Labels
  • No labels