Allison Barlow and David German - Engineering 26 Portfolio

Lab 3: Scanline Fill

In this lab exercise, we expanded the graphics system developed in Lab 2. We added a new C library that geometrically defines a Polygon and supplies routines to rasterize it using a scanfill algorithm. We also added scanfill routines to the existing Circle and Ellipse libraries, and implemented a Polyline primitive.

Procedure

Our graphics environment continues to follow Prof. Maxwell's Graphics Environment Specification.

To draw a solid figure using scanfill, we iterate over rows, coloring each pixel in that row contained by the figure. Our implementation of Bresenham's algorithm for drawing circles and ellipses already exploited the symmetry of those figures to draw points at both horizontal extremes of a scanline simultaneously. We were therefore able to add scanfill capability simply by drawing lines between the symmetric points. To scanfill polygons, we used Prof. Maxwell's skeleton code, filling in the missing implementation. It converts a Polygon structure's vertices to a list of edge records, sorted by the scanline of the edge's lower extreme. Each edge record contains the edge's upper extreme, its x-intersect with the present scanline, and its x-delta per scanline. The software maintains a list of edges that are "active" for the present scanline, incrementing each active edge's x-intersect by the x-delta each iteration until the edge becomes inactive when its upper extreme is reached. It then fills in all pixels on the scanline that are bracketed by the x-intersects of active edges.

As we worked, we discovered bugs responsible for the geometric difficulties discussed in the "Conclusions and Future Work" section of the Lab 2 report. Coordinatization was not, in fact, the primary issue; rather, the Line and Ellipse libraries both contained logical flaws. Lines with negative slope were erroneously incrementing on negative Bresenham error, creating an off-by-one effect. Ellipse drawing was inconsistent about the sign of Bresenham error and initialized the Region 2 error to slightly too large a value.

Results

Group Images

We developed a benchmark program to test the performance of our scanfill algorithm for polygons and circles. As specified in the lab instructions, it draws circles of radius between 10 and 20 pixels, and polygons with 5 to 7 vertices and area between 400 and 1000 pixels. We implemented Jeff Kaufman '08's algorithm for generating "random" polygons: after picking between 5 and 7 points around a circle of area 400, we add theta and radius jitter to each point. On chervil.cs.swarthmore.edu, which has dual AMD Opteron 248 processors at 2.2 GHz, we could draw about 40,000 to 50,000 circles per second, and 16,000 to 17,000 polygons per second. This is poor performance on a powerful machine, doubtless because we are making such heavy use of the FPUs.

lots of circles
Image 1. Output of our circle-drawing benchmark.

lots of polygons
Image 2. Output of our polygon-drawing benchmark.

Maxwell test image
Image 3. Prof. Maxwell provided test code to generate this image. Note that the square is within its corner-coordinatized mathematical boundaries, filling exactly 400 pixels.

correct adjacent triangles
Image 4. We can draw adjacent polygons with a correct boundary.

a correct ellipse
Image 5. Also, we can now draw mathematically reasonable ellipses.

a solid choo-choo train!
Image 6. We can use the ellipses and polygons to build a better choo-choo train!

Allison's Portfolio Images

ball
Image 1. Simple circles of different shades on a line. Each circle is only one color, but there is an illusion that each has a gradient.

gradient
Image 2. Playing with different ways to color the random polygons resulted in a scaly texture.

rendition1 rendition2
Images 3 and 4. Coloring the random polygons based on an original image was used to create two renditions of my favorite painting, Pablo Picasso's "The Old Guitarist".

David's Portfolio Images

Conclusions and Future Work

Pressed for time, we did not implement any extensions to this assignment. Antialiasing is a high priority, and will be added to the graphics system at the first opportunity. We may antialias the edges of polygons intelligently, or we may build supersampling into the Image methods for antialiasing that is more general, but expensive.

To the best of our knowledge, our libraries do not leak any memory. They also remain well enough organized and documented, and acceptably safe against the likeliest programming errors. Though we haven't done anything fancy, we have a sturdy framework for future assignments.

Appendices

Our code is available with AES256 encryption. The passphrase is only available to Dr. Maxwell.

Allison developed the train image while David tracked down the stray mathematical bugs. The rest of the project was pair-programmed.