Scanline Fill Algorithms - Writeup
Phil Katz and Stephen St.Vincent
home   |   images
Lab description


Lab summary:

This lab was mostly an extension of the previous lab. We built upon our line, circle, and ellipse primitives from last week. First, we created the ability to create polygons (connected) and polylines (not connected) from a series of lines. To do this, we meticulously ensured that our line-drawing algorithm maintained the proper boundaries for all cases.

With that complete, the next task was to create the ability to fill all of our shapes with a solid color. For circles and ellipes, this was fairly trivial. For polygons, we implemented the scanfill algorithm. While it is not perfect in that it does not fill in a polygon witout overlapping the borders, it does fill that entire inner area without spilling over outside the borders, so that if a user first plotted the filled polygon and then the line-only polygon, everything would look correct.

Questions:
  1. Is your polygon algorithm consistent with respect to screen coordinate issues, and does it produce rectangles that are the correct area? What changes to the algorithm did you have to make in order to make it consistent? You might want to make a simple image to demonstrate the mathematical consistency on your web page.
    Our polygon algorithm is consistent with screen coordinate issues. We took great pains to ensure that our implementation of Bresenham's algorithm was correct in all cases. As such, implementing the polygon drawing algorithm was fairly trivial and automatically maintained polygon area. The image at the left is a brief example of our algorithm on a square.


  2. How many filled polygons of a reasonable (400 pixels < area < 1000 pixels) size and complexity (5-7 edges) can your algorithm draw in 1 second?
    Our polygWe made one polygon with 5 edges of about 200 pixels per side. We managed to draw about 830 polygons per second. The image to the left shows the polygon that we repeatedly drew.


  3. How many filled circles of a reasonable size (10 pixels < r < 20 pixels) can your algorithm draw in 1 second?
    We filled 18145.6 circles per second where each circle had a radius of 20. The image to the left shows the circle that we repeatedly drew.




    4. This is the first required image.


    This is the second required image.


    This image shows that we've handled clipping for circles.


    This image shows that we've handled clipping for ellipses.


    This image shows that we've handled clipping for polygons.