Figure 1: An Early Polygon Fill Test
Figure 2: A Large Number of Circles
Figure 3: Results of Test Code pass3a
Figure 4: Polygon Testing Function
Figure 5: Demonstration of Filled and Border Polygons, Polylines, Circles, and Ellipses
Alex Benn and Andrew Frampton
This week's objective was to implement a series of scanline fill algorithms for filling polygons, circles, and ellipses. Also, structures and companion function libraries for polylines and polygons were implemented. Polylines and Polygons are stored in a structure containing the number of vertices and a pointer to the block of vertices. To draw a polyline, the code draws a line from each vertex to the next using the line drawing function implemented previously. Drawing an empty polygon is accomplished in the same way, but a line from the last vertex to the first vertex is drawn after the list is completely cycled through, which creates an enclosed shape.
To fill the polygon, we use a scanfill algorithm whose skeleton code was largely coded by Prof. Bruce Maxwell. The algorithm works by first creating an edge list in order of the position of the edge, from top to bottom. Next, it fills each line pixel-by-pixel between two edge intersections through that line; if more than two intersections are on the same scanline, the algorithm continues to fill between pairs of edges until no more edges remain.
For the circle and ellipse fill algorithms, we made an effort to streamline the code significantly. The points being calculated were placed into an array, which were tested in turn to be sure that each lay within the bounds of the image. If so, they were used as-is; otherwise, they would be shifted to be contained within the image. Instead of simply using the general-purpose line-drawing code from before and connecting a line from a circle edgepoint to its mirrored point, we opted to fill in individual pixels in a for loop, which didn't need the general-purpose code bulk associated with the line-drawing code.
1. Our polygon is consistent and produces rectangles in the right area. This can be seen in Figure 3, produced from the test code; the blue square is exactly 20 pixels by 20 pixels, as specified. This is a result of two coding decisions: first, scanlines are drawn from the left edge to the last pixel which is strictly left of the righthand edge; that is, the less than comparator is used. Second, edges are only drawn to their vertical dimension minus one pixel, so that a 20-pixel-tall box starts at pixel 0 and goes through pixel 19.
2. Our code can produce toward 2000 polygons per second, it won't set the world on fire, but it gets the job done.
3. Our code for filled circles can draw 46,000+ circles per second.
4. No extensions