Our scanline fill algorithm implements the standard scanline fill algorithm (from class notes). We first build a list of the non-horizonatal edges in the polygon, storing the start and end y value for each edge, as well as its initial x value, and the change in x with respect to y. Starting at the minimum y value, we check to see which edges exist at that y value, and build a list of those "active" edges. Then by sorting the list of active edges, and drawing horizontal lines between the x values of pairs of edges, we are able to fill all the correct pixels on that scan line. We then update the list of active edges, by adding the dx value to the initial x value (since we are about to scan on the next line, and have therefore increased y by one) and checking to see if there are any new edges that should be active and whether any of the active edges are not longer active. We then repeat for every value of y that intersects any of the edges in the polygon.

Required image one: A scanline filled polygon.

Another scanline filled polygon.

A scanline gradient filled polygon!

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?
   The polygon and scanline polygon filling algorithms are consistent with screen coordinates. To make the algorithm consistent, we had to subtract 1 pixel in the y direction from the end of every edge. To see that the polygons are consistent, take the following image as an example. It is a filled polygon (not a rect). The polygon is 5x5, defined as (0, 0), (5, 0), (5, 5), (0, 5), and the image is 10x10. The square fills exactly 1/4 of the images, demonstrating that it is of the correct area, thus mathematically consistent.
   
2. How many filled polygons of a reasonable (400 pixels less then area less then 1000 pixels) size and complexity (5-7 edges) can your algorithm draw in 1 second?
   On average, we could draw 4763 polygons/sec, with a standard deviation of 670 polygons/sec.
3. How many filled circles of a reasonable size (10 pixels less then r less then 20 pixels) can your algorithm draw in 1 second?
   On average, we could draw 17,999 circles/sec, with a standard deviation of 1,598 circles/sec.
4. If you extended this assignment in any way, describe what you did and how you did it. Include pictures, or links to pictures that show what you did.
   Please see our extensions section.

Required image 2: an awesome 3D car! (By Will) Updated since the last lab to use our new filling techniques and added road detail with pattern filling.

Required image 2: totally cool gradient train! (By Andrew)

A colorful bull's eye (Andrew's Portfolio 7)

Still life with Stewie (Will's Portfolio 7)

AC stands for...? (Andrew's Portfolio 8)

Faded Circles (Will's Portfolio 8)

Pattern Filling
We added a pen pattern option, so that we can draw pixels with a pattern fill. This works on all drawing operations because it works at the level of the pen. Here is how it works:

     newPixelX = (positionX - patternOriginX) % patternWidth
     newPixelY = (positionY - patternOriginY) % patternHeight

Here are the new methods:

• void setPenPattern(const image &i) -- Set the pen pattern. Takes an image as input.
• void setPatternOrigin(const point &p) -- Set the reference point from which patterns are drawn. (Polygons know to set this as one of their points, so that patterns move with polygons.)
• void disablePattern() -- Turn drawing of the stored pen pattern off.
• void enablePattern() -- Turn drawing of the stored pen pattern on.
• void clearPattern() -- Remove the stored pattern and try to manage memory.

A filled polygon with a pattern.

The same polygon shifted. Notice how the pattern origin moves with the polygon.

Flood Fill:
We actually added flood filling in the last lab.

Gradients: The Next Generation:
In the last lab we added limited gradient filling with flood fill. In this lab we extend gradient filling in the following ways:

• Gradients can now extend in any direction, instead of simply left to right.
  Making this work involves projecting a given point (x, y) onto the vector defining the gradient direction, then scaling that by the possible length of the gradient and shifting it so that it matches the start position of the gradient. Stepping through RGB colorspace is done parametrically.
• Gradients can follow any linear path through RGB color space.
• We can do circular gradients. (Please see the gradient train's wheels as an example.)

Enough talk, lets see them examples!

A pretty filled rect with a diagonal gradient and interesting color scheme.

And a circle.

Another rectangle.

We can gradient lines too!