Programming Assignment 2

Assigned 18 February 2002

Due 4 March 2002

In this assignment you are to implement a triangle scan conversion routine and Z-buffer hidden surface algorithm.

Your method should take a vector of 3 double-precision X-Y coordinates for the vertices in screen coordinates. Each vertex should also have an associated Z value (actually 1/Z) in double precision, and a color value expressed as 3 bytes giving red, green, and blue values.

Only sample the triangle at pixel centers (you decide where the center is relative to the pixel coordinate system). Linearly interpolate 1/Z, R, G, and B across the triangle.

Your method does not have to be particularly fast (optimization is fun but not part of this exercise) but I do want you to think about how you would optimize for either 1) large triangles (> 50 pixels) or 2) tiny triangles (~ 1 pixel). You don't have to do both cases, just choose one.

Feel free to look at code from the web or from books but do not copy code. You are responsible for making sure you understand your code. You can implement your routine in any programming language.

Set up a linear model describing the time behavior of your algorithm and determine the parameters of your model. For example, a routine optimized for large triangles probably has some "setup" code, some "per scanline" code, and some "per pixel" code. So my model would be something like Ttotal = Tsetup + NLines * Tline + NPixels * Tpixel. I'd run large numbers of triangles of differing sizes and collect total times using whatever timer is available. Then I'd solve the equations for the unknown parameters. Finally, I'd check the residual of my equations to see how well I did. I would have to experimentally adjust the number of triangles in each timing run to be sure I got enough timing accuracy.

Send email to gb@cs.unc.edu with subject line "Programming Assignment 2". Give me the URL of a web page describing your results. It should include:

1. A short description of the approach you took to scan conversion and interpolation.
2. How you suggest optimizing your method for either large or small triangles
3. Your model for the time behavior of your algorithm and the numerical values you determined for the parameters. Include a discussion of how well your model fits the actual performance of the code.
4. A few images including overlapping color interpolated triangles to demonstrate that your interpolation and Z-buffering work.