Due: Monday, 25 Sept., 11:59 PM on Moodle
Introduction
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. Make sure to note that pair-programming groups should do 2 extensions at the end. If you choose this option, clearly state both names in the pair as a comment at the top of your code.
Background Color
Fork the starter repl for this homework and study the code. 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"; // color name var backgroundRGB = [255,255,255,255]; // RGBA tuple
We've already seen RGB triplets using three numbers to specify color. The 4th "A" value in RGBA is the transparency, or alpha channel. 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);
Regular Polygon
Copy over your regular polygon function from Lab 2, and call it from within draw() to produce a small polygon. (We are keeping the polygons small, say less than 20 pixels radius, because the recursive algorithm runs slowly for large shapes, and may even overflow the stack.) 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.
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 a painting program). 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 in the graphics object 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 Tuesday. 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!
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. You can't just compare them with == since each color is made up of four numbers. Instead you should implement the function colorEqual, which will take in two colors as [R,G,B,A] tuples and compare each of their components separately. Only if all comonents are the same will colorEqual return true. I recommend that you test your colorEqual function on a few sample inputs to make sure it is working right, before you try to use it inside the recursion.
Extensions
Basic flood fill meets the bronze standard for this homework. For silver, everyone should choose at least one extension below. Everyone working as a pair should choose at least 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. Try to have each of your polygon types drawn by a function with some parameters that determine its exact configuration.
- Additional arguments to the regular polygon function: 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. Also include a parameter that controls the rotation of the shape (i.e., the angle of the first vertex drawn).
- Approximate color matching: Because the standard line-drawing function uses anti-aliasing, your filled polygon may appear to leave a small margin of background between the filled area and the boundary. Actually these pixels are not quite the same as the background color, since the anti-aliasing has mixed in a bit of the boundary line color. Thus the flood fill considers them boundary pixels. For this extension, you should create a new function based on colorEquals that will return true if the two colors are within some chosen tolerance of each other. Using this new function in floodFill will allow you to fill the borderline pixels at the boundary.
- 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.
- Scanline fill (gold standard/extra credit): in addition to flood fill, implement the scanline fill algorithm discussed in lecture. You will have to do some investigation to figure out how to do this -- for example, how to store the polygon vertices in an array, how to sort the intersection points, etc.. How does scanline compare to flood fill in terms of speed?
- An additional option is to create an animation that shows the order of the pixels being filled (also extra credit if completed in addition to another extension). Caution: the most obvious way to do this actually changes the original order and thus shows the wrong result. (Why?) There is a way to do it using Javascript's await construct, but using that goes far beyond the scope of this course.
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).