Programming assignment #2 - Polygon scan converter

CS 248 - Introduction to Computer Graphics
Spring Quarter, 1995
Marc Levoy
Handout #8


Demos on Monday, May 8

Writeups due on Tuesday, May 9 by 5:00pm


Your assignment is to write a scan converter for rasterizing interactively specified triangles. You will also implement a postprocess that redraws a previously specified set of triangles using supersampling and averaging down to reduce aliasing artifacts. Your scan converter and postprocessor will be used in the renderer you will write in assignments #3 and #4.

Required functionality

  1. 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. Once the third vertex has been placed, erase the feedback and scan convert the triangle. Draw it filled, not as an outline. Allow any number of triangles to be specified and drawn in this way.

  2. Clipping. Your scan converter should discard a polygon if any of its vertices lie outside the boundaries of the canvas. One of the bells/whistles in assignment #3 will be to implement full polygon clipping (in the context of a perspective viewing frustum).

  3. Discarding degenerate triangles. Your scan converter should test for and discard degenerate triangles (two coincident vertices or three colinear vertices). Print a message on the terminal for each triangle you discard so that we know when you detect one. This test becomes important in assignment #3 where viewing transformations often produce degenerate triangles.

  4. Rapid redrawing. 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.

  5. Meshing. 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 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.

  6. 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, and be prepared to verbally defend (in informal terms) the quality of antialiasing that it produces. Some patterns work well, and some do not, as we shall discuss in class. Allow slider control over the number of samples per pixel (variable s in appendix A). In order to verify that your algorithm behaves correctly, provide the user with the option to assign a unique 24-bit color (random colors are fine) to each triangle. When this option is selected, you should not draw triangles with XOR. Make sure that pixels along polygon edges and at polygon edge crossings (in case of overlapping triangles) contain reasonable antialiasing.

A few hints

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. 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.

  • Sliver polygons, when rendered without antialiasing, may have gaps. This is to be expected. Don't try to fill them in. That is what antialiasing is intended to do.

  • In part one of the assignment, you might find it useful to include buttons on your main window to delete from the list and from the canvas all triangles drawn so far or the most recent triangle drawn.

  • Make liberal use of your ability to display the red, green, or blue components of your image, which are displayed without dithering even if you are working on an 8-bit workstation, to help you debug your antialiasing. To help us verify that your antialiasing is working correctly, be prepared to display the red, green, or blue components of your image in isolation during the demo.

    Submission requirements

    We will follow the same demo and submission procedure as in the last assignment. 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).

    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." Be prepared to demonstrate your program on a grader data file that we will provide on the spot during the demo. The file contains one text line per triangle. Each line consists of three pairs of floating point numbers that represent the X,Y-coordinates of the three vertices of each triangle. For example, the file

    10 20 15 25 8.5 16.5
    tells your program to draw one triangle with vertices (10,20), (15,25), and (8.5,16.5). Treat your canvas as occupying the all-positive quadrant in X and Y. To be sure you can read our format, we have placed some sample files in /usr/class/cs248/data/triangles.

    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.

    We intend to measure the speed of your scan converter during the demos by giving you a large file of triangles and timing your "Redraw" function using a stopwatch. Be prepared to handle up to 10000 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, you should provide some means to control your active drawing area within the canvas. This control can be either interactive or at program startup. Allow a drawing area of 100 x 100 pixels. We will use this size for our speed measurements.

    Working in teams

    You may work alone or in teams of two or three. For a team of two, you must implement two of the following bells and whistles. For a team of three, you must implement five. Alternatives are acceptable if approved in advance. If you have completed the assignment and wish to earn extra credit, you may add more bells and whistles.

    1. Draw rubber-band lines during interactive specification of each triangle. There are many reasonable designs for such an interface. Experiment a bit. Worth 1/2 bell.

    2. Implement pattern fill (section 3.8 of the textbook). Provide an interface that allows the user to select a rectangle from a painting (from assignment #1) for use as the generator for a repeating pattern. Worth 1/2 bell.

    3. Implement polygon scan conversion for concave polygons having an arbitrary number of sides. Decomposing complicated polygons into triangles is an acceptable strategy. Worth 1/2 bell. For another 1/2 bell, 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.

    4. 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 feedback. Worth 1/2 bell.

    5. 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 scaling and rotation of triangles around an interactively selected point in the canvas.

    6. 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 segements 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, and be prepared to prove this using XOR. See page 949 for solutions to this problem.

    7. Implement unweighted area sampling as described in section 3.17.2 of the textbook as a user-selectable alternative to accumulation buffer antialiasing. For an extra bell, implement weighted area sampling as described in section 3.17.3. You may assume for these bells that your triangles do not overlap.

    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 implement in your next assignment.

    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. I'll show you some examples of antialiased images. Meanwhile, look 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. Be careful of memory consumption. Don't try to compute large (wide and high) RGB images using 32-bit integer arrays. You'll bring your machine to its knees.


    levoy@cs.stanford.edu
    Friday, 20-Feb-1998 13:46:50 PST