2d Drawing Primitives
cs40 assignment 2 web page
the objectives
The goal of this assignment was to extend the groundwork begun in phase 1 for the graphics environment to come, primarily through the creation of key state structures, and then to implement basic 2d drawing primitives such as lines, circles, and ellipses. Documentation on the graphics environment is available at the api. What follows is primarily a discussion of the difficulties one faces in drawing lines, circles, and ellipses in a discrete image space.
drawing lines
The problem with drawing most anything to the screen is that you are trying to map a continuous entity (eg. a line) onto a discontinuous space. The basic strategy is of course to determine which pixels best represent the geometric entity of, say, a line. For this and other tasks variants of Bresenham's algorithm were used, which allows for entirely integer based calculations. In short, the way Bresenham's algorithm works is to realize that, as we plot pixels to draw a line, after plotting a pixel, the next pixel to plot will either be immediately to the right or the one to the right and above (this of course only applies to the first octant, but the generalization to all 8 octants is fairly obvious).
circles and ellipses
Circles and ellipses can be drawn using a version of Bresenham's algorithm similar to the line version. In the case of circles, we can take advantage of 8-way symmetry to draw the circle much faster; for ellipses, we only have 4-way symmetry. Again, the basic way this works is that, given your position on the circle/ellipse at any moment, the position of the next pixel depends on which pixel center the path of the true geometric circle/ellipse passes through, and through clever arithmetic this can be determined from a single integer error term, allowing for very fast drawing of circles and ellipses.
screen coordinate issues
Another problem that comes up in drawing lines is how long to make them -- in a geometric sense, if I draw a line from (0,0) to (0,3), we should end up with a line that is 3 pixels long, but if you activate pixels (0,0), (0,1), (0,2), and (0,3), you end up with a line that is four pixels long. So... you don't draw the last pixel. More to the point, the approach that is taken in this graphics environment is to center the coordinates not on pixel centers but on the spaces in between pixels. When addressing an actual pixel, the point at its lower left is used, but there is a distinction made between pixel coordinates and screen coordinates. One consequence of this is that not all lines drawn from point (0,0) will activate pixel (0,0).
Another problem related to screen coordinates lies in how to draw circles and ellipses. If, say, you're drawing a circle of radius 5 from the origin, if you turn on both pixels (0,5) and (0,-5), you end up with a circle of radius 11, which is of course not what we want. The solution is to only plot up to (0,4), which can be accompished by adjusting the radius value used in calculation and then mirroring appropriately to the relevant points.
(remember, screen coordinates are given at the lower-left corner of a pixel)
circle with radius 5 with center and points 5 away from center in red
arbitrary angle ellipses
It turns out that drawing ellipses with their axes at an angle to the screen axes is a bit tricky, but it can be done, though in this case we only get 2-way symmetry to speed the calculation. The algorithm is, not surprisingly, yet another variant of bresenham's algorithm, and can be downloaded here. It was fairly straightforward to modify the algorithm so that all of the actual iterative calculations (stuff in for loops) are integer calculations. I did not, however, adjust the algorithm to take into account screen coordinate issues, so the ellipses generated by ellipseAngled() are a little bit bigger than they should be... but they look so pretty!
