CSC 240: Computer Graphics

Homework 2: Polygons and Fill

Due: Tuesday, Sept. 27, 11:59pm on Moodle

The goal of this homework is to see how a fundamental computer science technique (recursion) can be used in combination with geometry and pixel coloring to create a fill algorithm.

For this assignment, you are welcome to work with a partner if you use proper pair-programming techniques (work on the code only together, on one computer, switching the "driver" every 30 minutes). Make sure to note that pair-programming groups should do 2 extensions at the end. If you choose this option, turn in code/images under ONE partners name, and clearly state the names in the pair as a comment at the top of your code.

1) Background color

Download hw2.html (right-click on this link and then choose "Save As"). Open this file in your preferred editor. Note that two global variables are defined at the top. For this assignment, we'll need a notion of the background color, because we would like to change it inside the polygon. However, since querying a location for the pixel color returns an [R,G,B,A] tuple, we'll need to encode our background color in both ways for comparison: 
 
  var backgroundColor = "white";
  var backgroundRGB = [255,255,255,255];
The 4th "A" value is the transparency. 255 is fully opaque, and 0 is completely transparent. Feel free to change the background color to anything you like, updating both the color "name" and the RGBA values.

Also note that inside draw() we will use this background color right away to color the entire background. This is because it does not actually have a default color to start with, so we would have nothing to compare it to later on. 

 
  graphics.fillStyle = backgroundColor;
  graphics.fillRect(0,0,canvas.width,canvas.height);

2) Regular polygon

Copy over your regular polygon function from Lab 2, and call it from within draw(). It may be useful to define variables for the center of the polygon, since we can then pass those into our fill algorithm as the starting point.

3) Flood fill

Now implement the flood fill algorithm, which takes in the (x,y) coordinates of the point to start filling (similar to where you might click the bucket icon in ms paint). It also takes in the "oldColor" or background color. It may seem strange not to take in the "newColor" or fill color, but this should be set BEFORE calling floodFill(). The reason is that floodFill() is recursive, so resetting the color many times can contribute to stack overflow. 
 
  function floodFill(x, y, oldColor) {
    // TODO
  }
We will first need to query what the color is at the given (x,y) pixel. This can be done as shown below: 

  // note that this returns [R,G,B,A]
  var pixColor = graphics.getImageData(x, y, 1, 1).data;
Then implement the algorithm as shown in class on Wednesday. Think about the following questions and how to incorporate them elegantly into the algorithm:
  • What should happen if the current pixel color is already the new fill color?

  • What should happen if the current pixel color is an edge color?

  • What should happen if the current pixel color is the old background color?
Use recursion to fill the polygon! (EDIT: reduced the size of the image to more accurately reflect how large a region you can fill with this algorithm before running into stack overflow.)
example

4) Color equal

In the process, it will be useful to have a way to determine when two colors are equal and when they're not. Implement the function colorEqual, which should take in two colors as [R,G,B,A] tuples and compare them.

5) Extension

Everyone should choose one extension below. If you are using pair-programming, choose two extensions.
  • Creative design: use a variety of polygons (not necessarily regular) and colors to create an artistic image. I will show some of these the following week.

  • Fill as part of Regular Polygon: incorporate the fill color as an input to your regular polygon function. So instead of filling from within draw(), the filling should happen within the regular polygon function.

  • Recursion analysis: at some point, too many recursive calls are added to the function stack and we get the dreaded stack overflow. See how large you can make your shapes before this happens. What about different browsers? What if you set the fill color inside the recursive function vs. outside? Does it matter if the fill color is a color "name" vs. RGBA? Write up a short analysis as a comment at the top of your code.

  • Sweep fill (EXTRA CREDIT): in addition to flood fill, implement the sweep fill algorithm discussed in class. There are a few tricks to make this less laborious, so feel free to post on Piazza about this part if you have any questions. How does this compare to flood fill in terms of speed?

  • EDIT: an additional option is to create an animation that shows the order of the pixels being filled (also EXTRA CREDIT).

6) Submit

Submit both a screenshot (hw2.png) and the code (hw2.html) on Moodle. If you worked as a pair, only submit one screenshot and one program (include both your names as a comment at the top of the code).