Assignment 1: 3D Rasterization
By zdevito and mmp

# 3D Rasterization

Due Date: Thursday, April 25, 11:59PM.

## Description

In this assignment, you will implement 3D rasterization algorithms in order to render images with motion blur. We will provide you with a number of micropolygon dumps from a Reyes renderer as well as skeleton code that handles loading micropolygons from disk, writing out final images, etc.

## Step 1: Review the relevant reading

Surely you've already done the reading for lecture 4, but in any case, review the papers "Stochastic Rasterization using Time-Continuous Triangles" and "Data-parallel Rasterization of Micropolygons with Defocus and Motion Blur", linked from here. In particular, pay attention to the description of the Interval algorithm.

## Step 2: Review the skeleton code

Download the source code framework. First, scan over the main() function in main.cpp to get a sense of the basic flow of the system; next, check out mbrast.h, the main header file. Your task will be to code up an implementation of the Rasterizer interface in that file, where your rasterizer does 3D rasterization with motion blur.

There is an example 2D rasterizer in rast2d.cpp; it's worth reading through this code as well to get an idea of how to use the various interfaces in mbrast.h.

Late addition: two simple test scenes (for use in debugging) are now available for Download.

## Step 3: Build and run the code

Run make in the directory; you should get an executable named mbrast. To test it, run ./mbrast bicubic.grids. The scene will be rendered with the 2D rasterizer and the output should complain that the generated images don't match the expected results (which is to be expected, since the expected results are images with motion blur!).

View the image files in the "golden/" directory to see the expected results. The numbers in filenames there correspond to the number of samples per pixel used when rendering the images. The images are in PPM format to make them easy to read and write. If your standard image viewer cannot display them, you can convert them to another format such as a .png using ImageMagick's convert command.

## Step 4: Spend less time looping over grids

The reference 2D rasterizer is fairly silly in that, for each bucket, it loops over all of the grids (possibly thousands), and then all of the micropolygons in each grid (up to millions), even if the grid doesn't at all overlap the bucket.

Your rasterizer should be smarter: you could compute a 2D bounding box for each grid, or you might want to build a small 2D data structure that records, for each bucket, which grids overlap. Take advantage of the call to the Rasterizer::PreprocessGrids() call that's made before rasterization begins to build a small data structure in your Rasterizer implementation. (Note that this method will be called multiple times over the course of rendering the scene with different bucket sizes, so your implementation should gracefully handle being called multiple times, discarding old state, etc.)

Measure the performance improvement from your changes (for example, using the 2D rasterizer for now.)

## Step 5: Implement a basic 3D rasterizer

Implement a baseline 3D rasterizer; for each triangle, first compute a conservative 2D bounding box of screen samples that it covers. Then, loop over all of the corresponding pixels and call GetSamples() to get the corresponding pixel samples; for each sample, interpolate the triangle's position for the corresponding time and test the (x,y) samples against the triangle.

Make sure that this rasterizer passes all of the checks against golden images for the provided scenes before moving on to the next step.

## Step 6: Implement the interval 3D rasterization algorithm

Once your rasterizer from step 5 generates correct results, use the value passed in the numIntervals parameter to Rasterizer::Rasterize to detemine a number of intervals to use for the Interval 3D rasterization algorithm. Bound the set of pixels the triangle covers for each of those intervals and then only test against the corresponding active time samples in the overlapping pixels.

Ensure that this change doesn't cause any image differences versus your rasterizer in step 5.

## Step 7: Evaluation

Write up a report that includes the performance of your rasterizer for each of the provided test scenes, using 1, 4, and 32 samples per pixel, and for all of the various numbers of intervals that the code framework uses. If your rasterizer doesn't pass all of the built-in tests, compare the reference image to the image you generate and discuss the differences.

Discuss the observed performance: how does the number of intervals used affect the performance observed? Why are the results different for different scenes? How might you adaptively choose the number of intervals based on the input to get the best of all worlds?

## Tips

Recall from lecture 4 that we must interpolate homogeneous (x,y,w) coordinates in time and then divide x and y by the interpolated w value to get the screen position of a vertex at a given time (x' = x/w, y'=y/w). This fact makes bounding a triangle's motion on the screen slightly more tricky: to bound motion of a number of vertices over a time interval [t0,t1], it's necessary to first bound x, y, and w individually over the time interval. Then, to get the minimum x' value in pixel coordinates, divide the minimum interpolated x value by the maximum w value, and similarly divide by the minimum seen w when computing the maximum x' and y' values. (This is the right approach since all w values should be positive!)

The tech report Efficient Triangle Coverage Tests for Stochastic Rasterization provides fairly efficient algorithms for testing sample points against moving triangles.

You may find the ResetAndStartTimer() and GetElapsedMCycles() functions in the timing.h file useful to help isolate where time is being spent in your rasterizer. Note that as currently written only a single timer can be active; if you want to have hierarchical or multiple active timers, you might want to wrap this functionality up in a small class.

Gathering statistics about your rasterizer may provide insight as well: what is the percentage of sample tests that are actually inside triangles? How does this value change as the number of intervals varies? Note that you may want to disable multithreading (i.e., at least temporarily have your Rasterizer::IsThreadSafe() method return "false") when gathering these statistics so that you don't need to worry about coordinating shared counter updates across multiple processing threads.

## Submission

To submit your work, create a .zip or .tar.gz file that contains:

• Your rast3D.cpp file and any other files you modified.
• Your writeup and evaluation as described above.
• A description of the extra-credit you attempted, if any.

To keep the file size down, please do not include any .grid files in your bundle. Use the assignment submission page to upload and submit your work. You can submit multiple times if you wish to make changes after your initial submission. A record of the submission including the date submitted and an md5 checksum of your bundle will appear on the submission page when it is successful.

## Grading

This assignment is fairly open ended, and there are many ways to correctly implement the assignment. In addition to the correctness of your code, your grade will depend largely on your ability to describe the strategies you tried and your evaluation of them on the test scenes. This assignment (as well as all future assignments in the class) will be graded on a 4 point scale:

• 0 points: Code doesn't compile, crashes when run, or produces no output.
• 1 point: Code does not work correctly: all tests against 'golden' images fail.
• 2 points: Code passes tests with some but not all test scenes.
• 3 points: Correct implementation, but minimal writeup (e.g. missing questions, etc), or no analysis of the observed results.
• 4 points: Completion of all requirements for 3 points as well as a clear writeup and analysis and justification of the approach taken.

## Extra credit

You may do one of the following three things for one point of extra credit (you're welcome to do more than one, but won't receive additional incremental extra credit for each one!)

1. Implement a 5D rasterizer that does both defocus blur and motion blur with the provided scenes. (Your submitted code should have this option disabled by default, but your writeup should tell us how to enable and configure it, so that we can test it.)

2. Add transarency to your rasterizer; read Carpenter's paper on the A-buffer or Salvi et al's paper on Adaptive Order-Independent Transparency and implement one of these algorithms. Render scenes with transparency and measure the performance difference compared to your regular rasterizer; your writeup should include some discussion of these results. (Note that the provided micropolygon dumps don't include per-vertex transparency values--you can just arbitrarily assume all micropolygons are 50% transparent or the like.)

3. Optimize your 3D rasterizer and measure the result of your optimizations versus a baseline implementation that doesn't include them. If your optimization efforts don't in fact lead to meaningful speedups (or lead to slow downs!), you can still earn this point of extra credit if you provide a good analysis and explanation of why they didn't work out well. Some optimization options include:

• Correct backface culling will substantially improve the performance of your rasterizer (by roughly 2x); see the paper on this topic in the optional reading for lecture 4 if you're interested in pushing performance. (Note that many previous papers about motion blur rasterization, including "Data-parallel Rasterization of Micropolygons..." incorrectly assumed that if a triangle was backfacing at both shutter open and shutter close time, then it would be backfacing throughout the intermediate times.)
• The Hierarchical Stochastic Motion Blur Rasterization paper in the optional reading for lecture 4 describes techniques for culling tiles of samples as well as computing bounds in time of samples that may hit a moving triangle. The sample pattern provided by GetSamples() is based on the sampling technique described in that paper, so in particular you can assume that the provided 3D samples will be sorted in time.
• You could try adapting the number of intervals based on the amount of grid or micropolygon motion rather than having a fixed number of them used for all micropolygons, as the code framework expects.
• You could try rasterizing pairs of triangles together or develop related techniques to take advantage of the shared edges in the grid of micropolygons.
• You could try adding occlusion culling to your rasterizer. For your convenience, the provided grids should be in generally front-to-back order.

## Extra Extra Credit

Your instructor will simultaneously try to write a fast 3D rasterizer using some of the approaches described above. If you can write a rasterizer that is faster than his, you can earn a second point of extra credit (as well as bragging rights.)