Programming assignment #2 - Polygon scan converter
CS 248 - Introduction to Computer Graphics
Autumn Quarter, 2000
Due Tuesday, October 31 by 2:00pm
Your assignment is to write a scan converter for rasterizing triangles,
specified either interactively or from a text file. You will also implement a
postprocess that redraws a previously specified set of triangles using
supersampling and averaging down to reduce aliasing artifacts. Your executable
must run on the Sweet Hall SGI workstations (raptors).
Triangle scan conversion.
Allow the user to interactively specify a triangle whose vertices lie at
integer pixel coordinates on the canvas. Provide visual feedback of each
vertex as it is placed. (We suggest something larger than a 1-pixel dot.)
Once the third vertex has been placed, erase the feedback and scan convert the
triangle. Draw it filled, not as an outline. Allow up to 500,000 triangles to
be specified and drawn in this way.
Your scan converter should discard a polygon if any of its vertices lie outside
the boundaries of the canvas. You do not need to implement full polygon
clipping as covered in section 3.14 of the textbook. Don't print a message to
stderr (as in the next section) when you discard a triangle for this reason.
Discarding degenerate triangles.
Your scan converter should test for and discard degenerate triangles (two
coincident vertices or three colinear vertices). Print a message to stderr
for each triangle you discard so that we know when you detect
one. We provide a function WarnDegenerateTriangle() for this purpose, to
keep the error messages in a standard format - please use it.
Your interface should contain a button labeled "Redraw." When pushed, you
should erase the canvas and scan convert all previously specified triangles as
fast as possible, updating the canvas only once, after all triangles have been
drawn. You will be graded on speed. Note that scan conversion of triangles
should be "from scratch" each time the Redraw button is pushed; no fair caching
spans or other information from previous scan conversions.
The triangles you draw should mesh perfectly without holes or overlaps.
Satisfying this condition will require some care. In order to verify that your
algorithm behaves correctly in this regard, provide the user with the option to
draw all triangles in a single color, on a background of the same color, using
XOR (exclusive or). The effect of drawing with XOR is that each time a pixel
in the canvas is touched during scan conversion, its color is bitwise-inverted.
If presented with a set of triangles that should mesh, drawing them with XOR
will present obvious visible feedback of any meshing errors.
Supersampling and averaging down.
Your menu should contain a button labeled "Antialias." When pushed, you should
erase the canvas, step through a pattern of subpixel positions, shift the
vertices of all triangles as appropriate for that subpixel position, scan
convert them at the shifted position, and combine the results into the canvas
using the progressive refinement variant of the accumulation buffer algorithm,
as summarized in Appendix A of this handout.
Use any pattern of subpixel positions and any corresponding weights (summing to
1) that you like. In your README file you should describe your solution and
characterize (in informal terms) the quality of antialiasing that it produces.
Some patterns work well, and some do not, as we have discussed in class. Allow
slider control over the number of samples per pixel (variable s in appendix A),
making sure that you can select up to at least 50 samples per pixel.
Reading triangle coordinates from a file.
In addition to an interactive interface, your program should be capable of
reading triangle coordinates from a text file, so that we can test it with
"grader data." This file will contain one text line per triangle. Each line
will consist of three pairs of floating point numbers that represent the
X,Y-coordinates of the three vertices of each triangle, followed by three
integers that represent the color of the triangle. For example, the file
10 20 15 25 8.5 16.5 200 150 100
tells your program to draw one triangle with vertices (10,20), (15,25), and
(8.5,16.5), and with RGB color (200,150,100). Treat your canvas as occupying
the all-positive quadrant in X and Y, and treat color components as being
between 0 and 255. Make sure your canvas is 400 x 400 pixels. These colors
should be used during drawing if and only if the XOR coloring option (described
earlier) is not enabled.
We provide the code for reading files in this format. You should not need to
change this code unless you wish to change our Triangle data structure. To be
sure you can read our format and to help you in testing your program, we have
placed some sample files in /usr/class/cs248/data/triangles. However, these
are by no means the only data sets on which we will test your program!
We intend to measure the speed of your scan converter by running it with a
large file of triangles and timing your "Redraw" function. Your program should
handle up to 500,000 triangles. We will measure your redraw time with and
without antialiasing enabled. Since your rendering time with antialiasing
enabled will include a component due to updating the accumulation buffer, and
all your redraw times will include a component due to displaying the result,
everybody must use the same canvas size: 400 x 400 pixels.
To facilitate making these speed measurements, your program must respond to
certain command line arguments so that it can be invoked with no user
interaction. In this mode, you must load a given triangle data file, render it
quickly to a canvas, save the canvas to a .ppm file, and exit, printing to
stderr the amount of time spent during the scan-conversion phase. Details on
the command-line interface are given in the file GUIDELINES in the project
directory. This interface is already implemented in the starter file
rasterize.c, and you shouldn't need to change it. We will be reading stderr
for certain important diagnostic messages (degenerate triangles, and timing
information). The code we provide prints these messages to stderr. Any other
output that you wish to print to the console should be printed to stdout.
A few hints
You should begin the assignment with the files in the project directory
/usr/class/cs248/assignments/assignment2. This will give you a drawing canvas
and enough user interface widgets to implement the assignment, as well as the
functions to process the required command line arguments, read triangle files,
and time your rasterizer. Since much of this functionality is required
(specifically the command-line processing and the timing functionality), please
use our implementation to ensure uniformity. The GUIDELINES file suggests
which parts of the provided starter code you should and should not change.
The scan conversion algorithm presented in class, which is also covered in
section 3.6 of your textbook, works for convex or concave polygons having any
number of sides. Your assignment only requires you to scan convert triangles.
You should therefore think through this algorithm and simplify it as
The reason for wanting perfect meshing is so that one can, although we will not
require it in this course, correctly draw polygon mesh approximations of smooth
curved surfaces. To achieve this goal, it is necessary and sufficient to avoid
holes and double-drawn pixels in the following two cases:
Along an edge shared by two triangles where the edge is defined by the same
vertex coordinates in both triangles.
At a vertex shared by three or more triangles where the triangles, taken
together, wind completely around the vertex, i.e. the vertex is at the center
of a full pie.
Your method for insuring that triangles mesh perfectly should not require
global knowledge about the list of triangles to be scan converted. In other
words, it should be a set of rules that can be applied when scan converting a
single triangle, without knowing about the others. Thus, when scan converting
a triangle you are not permitted to examine the vertex positions of other
triangles. Furthermore, you not permitted to maintain a bitmask saying which
pixels have been touched by previous triangles. Since insuring perfect meshing
in the vicinity of T-intersections requires knowing about other triangles, we
do not require you to handle these. We also do not require any particular
behavior at a vertex shared by triangles that do not completely wind around the
vertex, i.e. at the center of a pie with one or more slices missing.
While it is reasonable to restrict vertices for interactively specified
triangles to lie on pixel centers, the supersampling portion of the assignment
requires that you scan convert triangles whose vertices are positioned with
subpixel precision. Assuming that your pixels coincide with the 2D integer
lattice, this means that you need to support non-integer vertex coordinates.
Page 948 of the textbook describes two solutions to non-integer vertices: a
floating point algorithm and a fixed point algorithm (i.e. by multiplying by a
fixed constant (the book suggests 1000)). We suggest a floating point
algorithm, mainly because it will be easier to code.
Try to anticipate every nasty triangle and set of triangles that we will want
to test, including degenerate triangles and out-of-bounds vertices. Note that
the test files we provide should not be considered adequate for debugging your
meshing rules and anti-aliasing; they are merely provided as examples of the
file format your program should be able to read. Exhaustively testing your
meshing rules and anti-aliasing is your task.
Sliver triangles, when rendered without antialiasing, may have gaps. Tiny
triangles might disappear entirely. This is to be expected. Don't try to fill
them in. That is what antialiasing is intended to do.
We have provided (in /usr/class/cs248/data/triangles) several test
datasets for you to play with. For some but not all of these, we will
supply matching .ppm files to give an idea of what they should look
like. Note that you will probably not match these images pixel for pixel,
depending on your choice of meshing and antialiasing strategies.
Since we are grading you for speed, you'll want to compile your code with a
reasonable level of compiler optimization enabled. Be careful though, the
highest level of optimization in SGI compilers sometimes makes working programs
stop working. It could also be to your advantage to learn how to use a code
profiling utility (use 'man speedshop' on the SGI's for more information).
Unlike the first assignment, this one will not be graded face-to-face.
Instead, you will submit the program to us online, and we will run it ourselves
later. Specifically, by 2:00pm on Tuesday, October 31, you should submit an
on-line executable program, a commented copy of your source code, and a README
describing the functionality implemented. Your README file should describe how
to run your program, including any command line arguments required. It should
also describe your supersampling solution, as outlined earlier. As in the
previous assignment, one screenful is enough, and if you did something
especially clever, tell us about it. To submit your program, source code, and
README, simply change the current directory to your assignment #2 directory and
run the submit script (not the freeze script), as you did for assignment #1.
The assignment will be graded on correctness (50 points), efficiency (30
points), programming style (10 points), and the elegance of your user interface
(10 points). Remember - your executable must run on the Sweet Hall SGIs. If
we can't get your program to run, or if it crashes, or if some of its
functionality - including the basics we provided in the starter implementation
- seems missing, your grade will suffer. Make sure your program runs reliably!
If you have completed the assignment you can earn extra credit by adding bells
and whistles. Here are some suggestions. Feel free to make up your own.
Draw rubber-band lines during interactive specification of each triangle.
There are many reasonable designs for such an interface. Experiment a bit.
Implement pattern fill (section 3.8 of the textbook). Provide an interface
that allows the user to select a rectangle from an image for use as the
generator for a repeating pattern.
Implement polygon scan conversion for interactively specified concave polygons
having an arbitrary number of sides. Decomposing complicated polygons into
triangles is an acceptable strategy. For more fun (and credit), make your
algorithm work correctly for polygons whose edges touch or cross (creating bow
ties, holes, disjoint areas, etc.) as enumerated in class. You needn't support
polygons with holes when those holes are defined by a separate set of edges.
Allow interactive specification of an arbitrarily shaped ellipse and implement
a scan converter for it. Draw it filled. We suggest using button-down to
specify one corner of the bounding box for the ellipse and button-up (after
dragging) to specify the diagonally opposite corner. Consider
rubber-band-style drawing of the ellipse during dragging for enhanced user
Allow the user to interactively move triangle vertices. Also allow the user to
move the triangle itself by pointing to its interior. Use gravity to
facilitate selection of triangles and vertices. Provide reasonable visual
feedback during selection and moving. Allow interactive scaling and rotation
of triangles around an interactively selected point in the canvas.
Implement an interface that allows input of a curve as a sequence of connected
line segments. We suggest using button-down to initiate a new curve and
button-up to terminate it. Line segments can be defined to connect successive
mouse positions or successive mouse positions once their distance apart exceeds
a specified threshold. If the threshold distance is large, you might want to
provide rubber-banding of the final segment for enhanced user feedback.
Experiment a bit. Segments should be drawn using one or more polygons. Allow
slider control over curve thickness. Pay careful attention to the endpoints of
each segment. See page 963 of the textbook for ideas. Avoid drawing pixels
more than once. See page 949 for solutions to this problem.
Implement unweighted area sampling as described in section 3.17.2 of the
textbook as a user-selectable alternative to accumulation buffer antialiasing.
For more fun, implement weighted area sampling as described in section 3.17.3.
You may assume (for these items only) that your triangles do not overlap.
Allow a large number of input file names on the command line, where each input
file is one frame of an animation. Play the animation by rasterizing the files
on-the-fly. Provide VCR-like controls: play, pause, step forward, step
backward, loop, etc. Find or algorithmically create an animation sequence.
Document it in your README file so we can enjoy it too!
Appendix A: the accumulation buffer algorithm
Let "canvas" and "temp" be 24-bit pixel arrays. Let "triangle color" be a
24-bit color unique to each triangle.
1 clear canvas to black
2 for (i=1; i<=s; i++) (for s subpixel positions)
3 clear temp to black
4 for each triangle
5 translate triangle vertices for this subpixel position
6 for each pixel in triangle (using your scan converter)
7 temp color <-- triangle color
8 for each pixel in canvas
9 canvas color <-- ((i-1)/i)*canvas color + 1/i*temp color
10 display changed portion of canvas
Line 7 causes later triangles to occlude earlier triangles in temp. This
"painter's algorithm" occlusion ordering is in lieu of a hidden-surface
algorithm, which you will learn about later in the course.
Line 9 implements a box filter, i.e. all subpixel positions are given equal
weight. By modifying this interpolation formula to include a weight that
varies with subpixel position relative to the center of the filter kernel, you
can implement other reconstruction filters.
Line 10 causes the screen to be updated after all triangles have been rendered
at each subpixel position, thus implementing a kind of progressive refinement.
This is the required functionality. If you want to see your scan converter run
faster, provide a check box that allows the user to disable display until the
end of the scan conversion process.
If your progressive refinement is working correctly, what you should see is:
after the first supersample location -> a canvas with all triangles at full
intensity but with jaggies, after the second -> an average of two
full-intensity images that are slightly spatially offset from one another,
producing a bit of blurring, and after all s positions -> a nicely antialiased
image. This week's lecture notes include a link to examples of antialiased
images. Look also at figure 3.56 in the text. The method they use to produce
that figure is different (that is prefiltering, not supersampling and averaging
down), but the visual effects are similar.
One final hint. For large numbers of samples (i.e. large values of s), line 9
will yield significant quantization artifacts. In these situations, you may
need to use canvas arrays of 16-bit or 32-bit integers (one each for R,G, and
B), sum your temp images into this array without first scaling each
contribution (i.e. don't scale by 1/i), then normalize into a third array of
8-bit per color component pixels for display on the SGI. I don't require that
you implement this, but if you do, you will have the pleasure of being able to
progressively refine your images even for large s.
Copyright © 2000 Marc Levoy
October 19, 2000 12:04:32 PM