phase 3:
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.
some filled circles and ellipses
![]()
![]()
![]()
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...
some filled angled ellipses
![]()
![]()
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.
some filled polygons
![]()
![]()
![]()
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.
some bordered fills
![]()
![]()
![]()
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)
gradients
Sweet, sweet gradients... conceptually, all a gradient is is a mapping from a line segment (in my world, a unit line segment, 0.0 to 1.0) to a bunch of colors, and then mapping from a space to be filled with the gradient to that line segment (which then maps to the color space). For instance, you might define a gradient which has blue at 0.0 and red at 1.0, then all of the inbetween colors are linearly interpolated. Then there are various ways to map from the fill space to the linear space -- one might use horizontal, vertical, or some diagonal distance from one end to the point in question, or radius from the center, or angular position along a circle...
flood fills
The basic flood fill algorithm works as follows: put the specified point on the stack, pop the top off the stack, color it, put its neighbors on the stack if they have not yet been colored and are not boundary pixels, then pop and repeat. In order to get patterns and gradients to map properly, I needed to measure the space to be filled before actually filling it, so I decided to add a flag to my Point data; the aforementioned algorithm then sets the appropriate flags while measuring the space, then just goes back and fills every flagged pixel. Also, rather than just filling a single color, there is support for a color tolerance parameter, which can be nice.
a cool flood-fill pic
![]()
and of course, my sweet ride of a car strikes again
![]()