Latest revision as of 22:47, 8 October 2011

Project 3: Rasterization

In this project you will implement your own software rasterizer. We provide some code that will allow you to integrate your rasterizer with OpenGL.

The project has three parts. You can obtain full credit (100 points) for completing the first two parts. The third one is optional.

This project is due on Friday October 14, 2011. You need to present your results in the lab as usual. The homework introduction in the computer lab will be on Monday, October 10 at 3pm (Lex Lacson).

0. Getting started

Base Code

We provide base code for you which displays a frame buffer on the screen. Your task is to rasterize your scene into this frame buffer. Throughout this assignment do not use any OpenGL routines which aren't already in the base code! Instead, use your own vector and matrix classes from assignment #1 and add your own rasterization routines.

1. Rendering vertices (30 points)

The goal of the first step towards building your software rasterizer is to project vertices of given geometry to the correct locations in the output image (frame buffer). Use the house geometry from homework assignment 2 as your geometry.

You can re-use your model (M), camera (C), and projection (P) matrices from the previous assignment. Add a viewport matrix (D). Implement a method to set the viewport matrix based on the window size (window_width and window_height) and call it from the reshape function. Your program must correctly adjust projection and viewport matrix, as well as frame buffer size when the user changes the window size. Correctly means that the house needs to remain centered in the window and get uniformly scaled to match the window size. (5 points)

Then write a method to rasterize a vertex. You can use drawPoint from the base code to set the values in the frame buffer. Call this method from the draw callback (display function in base code) for every vertex in the sample scene. For this part of the assignment, create a method rasterizeVertex which projects each vertex of the house to image coordinates and sets the color of the corresponding pixel to white using drawPoint. (15 points)

To make sure your implementation is correct, use the same values for camera and projection matrix as in Image 2 of Exercise 1c of homework assignment 2, and compare the result of your rasterized vertices to the image. (10 points) As a reminder, here are the values again:

• Aspect ratio: window dependent (window_width/window_height)
• Vertical field of view: 60 degrees
• Near, far clip planes: 1, 100
• Center of projection: -10, 40, 40
• Look at point: -5, 0, 0
• Up vector 0, 1, 0

2. Rasterization and z-buffering

For this part of the project you will need to implement a triangle rasterizer based on barycentric coordinates as discussed in class. The rasterizer should first compute a bounding box around the triangle, limited to the extent of the triangle. It then needs to step through all pixels of the bounding box and test if they lie within the triangle by computing their barycentric coordinates.

2a. Basic rasterizer with linear color interpolation (30 points)

Implement linear interpolation (as opposed to hyperbolic interpolation) of colors using barycentric coordinates. Implement a z-buffer data structure to resolve visibility when rendering multiple triangles. For z-buffering, you should linearly interpolate z/w and scale it from [0,1] and use it as the value in the z-buffer.

Use this colorful house geometry to test and demonstrate your algorithm. Use the same camera and projection matrices as in exercise 1. Scores: correct depth display (using z-buffer): 15 points; correct linear color interpolation: 15 points.

2b. Perspectively correct interpolation (20 points)

Note that this algorithm will be discussed in more detail in the lecture on Oct 11. In the meantime you can safely skip to part 2c and revisit this part later, unless you can figure out the equations from the lecture slides.

Implement perspectively correct interpolation of colors using hyperbolic interpolation. Apply it to the colorful house from exercise 2a. Add keyboard support to switch between linear ('l' key) and hyperbolic ('h' key) interpolation: use the glutKeyboardFunc callback (see base code). 15 points

The house geometry is not a great example for this section of the assignment, because the visual difference between linear and hyperbolic interpolation is very subtle. So we ask you to additionally render a more suitable object. Create a black-and-white striped triangle in the following way: set one vertex's color to (1,1,1) and the other two to (0, 0, 0). After computing the interpolated color use the following repetitive function on each component of the color to generate the repetitive stripe pattern: f(x) = ((int)floor(10*x)) % 2.

Compare the result to the same striped triangle rendered with the linear interpolation from exercise 2a. Choose model, camera and projection matrices with strong perspective distortion to make the difference obvious. Like with the house, allow the user to switch between linear ('l' key) and hyperbolic ('h' key) interpolation. 5 points. Note: you will only get full credit if your perspective distortion is strong enough to see an obvious difference between the two modes.

2c. Two-level hierarchy (20 points)

Extend your rasterizer by adding a two-level hierarchy as discussed in class: The main idea is to split each projected triangle's bounding box into n*n smaller tiles of equal size. Before testing each pixel within a tile, the rasterizer determines if the triangle overlaps with the tile. The whole tile can be skipped if this is not the case. Use the house geometry from exercise 1, not the colorful house. (10 points) To demonstrate how the algorithm works, outline the tile boundaries of one triangle in the frame buffer in red. (5 points)

Test the performance of the tiling approach by measuring rendering times for at least three different numbers of tiles (different values of n): let the house rotate about its origin and measure the time it takes to render 100 frames of the rotating house. Report the average frame rate (=number of frames rendered per second) in the console window. Support three different tile sizes and allow the user to switch between them using the keys '1', '2', and '3'. Don't draw the bounding boxes for this performance test. Your algorithm must show a speedup for certain values of n, compared to n = 1. What value of n gives you the best performance? (5 points)

Note: In Linux, the C++ function gethrtime() can be used to measure time; in Windows, clock() can be used.

3. Optional Exercise: Performance Optimization (max. 10 points)

Rasterization is the computational bottleneck in many rendering systems. Therefore, optimizing this part of your rendering pipeline is a worthwhile endeavor. The goal of this optional part of the project is to squeeze as much rendering performance as possible out of your rasterizer. In order to get the points, you need to demonstrate your optimized algorithm in comparison to the non-optimized algorithm, which you should do by supporting key strokes: 'n' for non-optimized, 'o' for optimized. You also need to display the frame rate (e.g., in the console window), and use complex enough geometry to produce a noticeable change between non-optimized and optimized mode.

You can choose one of the two following optimization techniques.

Multi-level hierarchy (10 points)

Extend the two-level hierarchy from part 2c to a multi-level hierarchy with adaptive tile sizes. This strategy allows you to start with large tiles, and discard large areas that do not overlap with the triangle. By splitting tiles that overlap partially with the triangle into smaller tiles, you avoid the overhead of a two-level hierarchy with large tiles. This technique is also known as a Quadtree.

Multi-threading (10 points)

Rasterization is an "embarrassingly parallel" operation. Any number of threads may, in parallel, test whether pixels are inside a triangle and perform z-buffering. Chances are that your CPU either has multiple cores or supports hyper-threading. This means that rasterizing using multi-threading should increase rendering performance. The idea is to start several threads (depending on the number of cores your CPU has, times two if hyper-threading is supported) to rasterize each triangle. Each thread could compute the pixels of one line of pixels, moving on to the next unassigned line when done. In the two-level scheme, the threads could work on different tiles.

Here are a couple of pointers to get started:

• Multithreading in Windows
• Multithreading in Linux