Precious, Precious 2d Fills
cs40 assignment 3 web page
overview
This assignment extended the 2d drawing environment by implementing various forms of fills and filled shapes. Once basic fills were accomplished, seamless variable thickness borders, patterns, and gradients were added as extensions. Technical use of fill functions is covered in the draw.h and pattern.h sections of the api.
scanline filling circles and ellipses
Scanline filling of circles and ellipses is fairly straightforward, because they are regular and predictable shapes. By using the functionality implemented in the last lab for drawing variable thickness circles and ellipses, which use y-indexed lists of x values generated by the actual ellipse() drawing function, it is very easy to just draw scanlines between the ellipse center and the boundary x values (mirroring 4 ways). By drawing filled circles in this manner, my program can draw about 4800 circles of random radius 10 to 20 in 1.0 seconds.
scanline filling angled ellipses
This gets a bit trickier, because the prior technique of drawing from the center to the boundary does not work (because the center line from top to bottom is not necessarily fully contained by the ellipse), but by correctly mirroring in both x and y the boundary values for the right side of the ellipse also give the correct values for the left side. Though, as you can see, this is a bit glitchy at the moment...
scanline filling of polygons
Polygons are much more difficult to scanline fill, because they are not predictable in the same way that circles and ellipses are. A simple solution to the poly-fill problem would be to just draw the boundary and then flood fill the interior, but this is way too slow, and some form of scanline filling is essential.
What ends up working well is to preprocess the polygon as a collection of edges, then sort these edges by ascending y-value of the lower vertex (horizontal edges are discarded). Then, starting at the bottom, for each scanline an "active edge list" is generated/maintained, which is a list of all edges intersecting that scanline. The active edge list is sorted by ascending x-intersect value; then, if boundary conditions are handled properly, you are guaranteed to have an even number of edges per scanline, and you can just fill between the first two, then fill between the next two, and so on.
In my implementation of this algorithm, my polygon edges and edge x-values are generated by making calls to the internal function lineDeploy(), which is the same function which allows for variable thickness lines -- the point being, this way, the edges of my filled polygons correspond to the edges which would be generated by drawing corresponding lines. On my computer, my algorithm can draw about 3650 avg size 6-vertex polygons in 1.0 seconds.
bordered fills
As noted in phase 2, I am a bit obsessed with only drawing any given pixel once (for transparency reasons -- what I call "seamless" bordering). I have so far managed to implement this for circles and ellipses, with angled ellipses working mostly fine but with occasional glitches, and polygons working for thickness 1 lines but not for thick lines.
patterns
I implemented patterns as Image structs. Whenever applying a pattern, the lower-left corner of the region filled is passed in and used as an anchor point for applying the pattern. Parameters are available for offsetting this anchor point, and for staggering repeated patterns either horizontally or vertically. While any image can be used as a pattern, there are also a few routines available for generating standard patterns (checkerboard, stripe)
