{{FULL_COURSE}} Homework 3 - Rasterizer

0 Goal

To create a rasterizer for drawing scenes composed of polygons. This rasterizer will be the basis for a 3D scene renderer next week.

1 Supplied Code

We provide you code to read 3D scene files in OBJ format, some sample models, and a sample camera that should work well with all the provided models. You will also have to incorporate your linear algebra library and PPM reading/writing code into this project. Copy your mat4.cpp and vec4.cpp files into the project before you begin coding.

Click here to download the basecode.

2 Help Log

Maintain a log of all help you receive and resources you use. Make sure the date and time, the names of everyone you work with or get help from, and every URL you use, except as noted in the collaboration policy. Also briefly log your question, bug or the topic you were looking up/discussing. Ideally, you should also the answer to your question or solution to your bug. This will help you learn and provide a useful reference for future assignments and exams. This also helps us know if there is a topic that people are finding difficult.

3 Preparatory Questions

Before you begin the programming portion of this homework assignment, read and answer the following conceptual questions. These will not be graded but will help you plan out your work.

• What are the three different configuration cases when determining the intersection of a pixel row with a triangle edge? In all three cases, what simple criterion can one use to determine whether the triangle edge overlaps the pixel row at all?
• How might one use barycentric interpolation to determine whether or not a given point in space lies within the bounds of a triangle? In rasterization, would this method be more efficient than row bound checking for determining which pixels lie within a triangle? Why or why not?
• Describe in detail the sequence of transformations that must occur in order to project a set of triangles given in 3D world space into the coordinate system of the pixelized screen.

4 Code Requirements

You are welcome to modify your vec4 and mat4 files (including the headers) from the last assignment. You will submit your modified versions with this assignment, so you are free to add/remove/change any methods or functions you wish. You may also create as many additional .cpp and .h as you like. You will submit all of your code, including the .pro file as a ZIP archive. (You should not need to modify the TinyOBJ code we provide, but you may do so if you wish, since you will need to submit it with everything else anyway.)

Create a C++ command-line (non-GUI) project in Qt Creator, then download and add tiny_obj_loader.h and tiny_obj_loader.cpp to it. Both files are included in the base code. Also add copies of you vec4 and mat4 code and your PPM reading code. You may create either a non-Qt or a Qt project. You do not need Qt for this project, but you are free to use Qt libraries such as QVector, QString, and QImage if you want. The standard C++ libraries such as std::vector will work just as well.

4.1 The TinyOBJ Library

You will use the TinyOBJ library to parse object files into data structures that can be used by your rasterizer. It consists of only two files you downloaded in the previous step, and you only need to use a single function, which will become available if you include tiny_obj_loader.h:

tinyobj::LoadObj(std::vector<shape_t> &shapes, std::vector<material_t> &materials, const char *filename, const char *mtl_basepath = NULL);

TinyOBJ uses the C++ standard library’s std::vector as a resizeable array and works by passing in references to empty std::vectors for the shapes and materials parameters. filename refers to the path to the object file. If the function executes correctly, TinyOBJ will have filled those vectors with shapes and materials parsed from the object file. You can check if this happened by checking if the string returned by LoadObj is the empty string.

Shapes are represented as shape_t structs, and materials as material_t structs. Each shape_t contains a mesh_t struct, which in turn holds a collection of triangles. You will need to rasterize all the triangles in all the meshes. The mesh_t data structure contains the following members that you will need to use.

• positions: This is a vector of vertex coordinates. Its length is a multiple of 3, and every three elements are the x-, y-, and z- coordinates of one point. You can use the positions as is, or you may wish to convert them to a vector of vec4s, with a w coordinate of 1.
• normals: This is a vector of normal coordinates at each vertex. Since a triangle mesh is usually an approximation of a more detailed surface, it is customary to specify surface normals at each vertex rather than computing them for each triangle. These can be used to calculate smoother lighting effects that hide the triangle mesh structure. You won't need to use these right away. When you do, you may wish to convert them to a vector of vec4s with a w coordinate of 0 (since they represent directions rather than points).
• texcoords: This is a vector of texture coordinates; if the vector is not empty, there will be two coordinates per vertex. You can ignore this unless you choose to implement texture mapping as extra credit.
• indices: This is a vector of vertex indices. Every three indices specify the three vertices of a triangle that you need to render. For instance, if the first three array elements are 7, 94, and 13, you need to render a triangle whose vertices are at (positions[7*3], positions[7*3+1], positions[7*3+2)), (positions[94*3], positions[94*3+1], positions[94*3+2)), and (positions[13*3], positions[13*3+1], positions[13*3+2)). You may wish to define a simple Face data structure that contains three indices, and convert this data to a vector of Faces.
• material_ids: This is a vector specifying the material for each face. There will be one entry for every triangle in the mesh (i.e. one entry for every group of three indices). It will be an index into the vector of materials that LoadOBJ filled in. For now, use the material's diffuse field as the triangle's color. For some of the extra credit options, you will use additional fields.
• Note 1: Color values in material_t structs are always floats between 0 and 1. Once you compute the final color of a pixel, you will need to multiply by 255 and round to the nearest integer in order to produce a PPM.
• Note 2: You will not need to construct any model matrices for this assignment. All vertices in OBJ files are always specified in world coordinates.

4.2 Cameras

Camera positions are specified in ASCII text files in the following format (all numbers are floats):

left right bottom top
near far

eye_x eye_y eye_z
center_x center_y center_z
up_x up_y up_z

The first 6 numbers are the view frustum parameters. eye is the camera's position. center is a point that the camera is look straight at, so the z-axis (or forward in the lecture slides) is center - eye. up is the y-axis. Make sure to normalize both the y- and z-axes, then use a cross product to compute the x-axis. We are using this representation of the camera position and orientation to match OpenGL's traditional gluLookAt function.

You will need to compute the projection matrix using the frustum formula, and the view matrix, using the eye, center, and up values. See the documentation for gluLookAt for the view matrix formula. Use the formula below for your frustum:

Note that this formula is slightly different than the formula used by OpenGL's glFrustum: OpenGL's convention is to map the near plane to z = -1, but we are mapping it to z = 0 instead. The formula is also appears different than the one based on field-of-view in the lecture slides, although it isn't really. If you assume the camera is looking at the middle of the window, then \(b = -t\) and \(l = -r\). So \(\frac{2n}{t - b} = \frac{n}{t}\). Now consider the triangle formed by the camera center (0, 0, 0), the center of the image at the near plane's depth (0, 0, n), and the point at the top center of the near plane (0, t, n). This is a right triangle whose angle at the origin is half the field of view (remember the field of view stretches from \(t\) to \(-t\)). So the ratio of the opposite edge (from (0, 0, n) to (0, 0, t)) over the adjecent edge (from (0, 0, 0) to (0, 0, n)) is \(\tan \frac{fov}{2}\). The formula above uses the reciprocal \(\frac{2n}{t - b} = \frac{n}{t} = \frac{1}{\tan{\frac{fov}{2}}}\).

4.3 Rendering Triangles

Create a program rasterize that takes the following command lines options:

rasterize <input.obj> <camera.txt> <width> <height> <output.ppm> [--color_option]

Read in the specified OBJ and camera file (you will need to write the code for reading in a camera yourself), and rasterize all the triangle in the OBJ into an image of the specified width and height:

1. For each triangle, multiply each vertex coordinate by the view matrix, then the projection matrix, divide through by w, and convert the x- and y- coordinates to pixel coordinates using the formula from the slides.
2. If all three z-coordinates are less than 0 or all three are greater than 1, the triangle is completely in front of the near plane or complete behind the far plane. So skip it because it isn't visible.
3. Compute the 2D bounding box of the triangle. If it doesn't overlap the image at all, skip the triangle because it isn't visible.
4. For every row of the image, calculate the x-coordinates where the row crosses each edge of the triangle. Figure out which two edges it actually crosses.
• Using the formula on the lecture slides, pixels are actually treated as small squares, just like they really are. The top-left pixel in the image is a square that stretches from (0, 0) to (1, 1). You should use scan-lines that cross through the middle of each pixel, so the y-values of your scanlines should be 0.5, 1.5, 2.5, ..., height - 0.5.
• Be careful of special cases, including vertical edges (could cause a divide-by-zero if you're not careful), horizontal edges (the scan line could run along the entire edge instead of just intersecting it), and situations where the scan line intersects a vertex (i.e. it intersects two triangle edges at exactly the same place). You do not have to deal with degenerate triangles (e.g. triangles where two vertices are actually the same point, or where all three vertices lies along a straight line).
• Once you've calculated the x-coordinates where the current scan line enters and exits the triangle, treat every pixel as a mathematical point (i.e. color it only if the exactly coordinates (col, row) are inside the triangle. Color pixels using the coloring scheme specified by --color_option (see section 4.5). If no option is specified, use the diffuse color found in the corresponding material_t struct.

4.4 Z-Buffering

Add a z-buffer, which should be an array with one float per pixel. Initialize each z-buffer value to 2 (or any other value > 1), so that any triangle that is inside the frustum will have a smaller z-value. Update your code to only color a pixel if the triangle's z-coordinate (after projection) is between 0 and 1 and is smaller than the value stored in the z-buffer. Whenever you do color a pixel, update the z-buffer with that point's depth.

You need to use tri-linear interpolation to calculate the depth value at every pixel. Once you figure out where the scan line enters and exits the triangle, interpolate the z values at those points. For each pixel along the scan line, interpolate beween the z values of the two end points.

4.5 Additional Required Elements

Implement the following command-line options to determine how to color each pixel:

• No option specified: color the pixel using the triangle material's diffuse color. Compute the z value at each pixel using trilinear interpolation, without accounting for perspective distortion. These are the base diffuse colors for each file:
• cube: blue (0.1, 0.1, 1.0)
• dodecahedron: magenta (1.0, 0.1, 1.0)
• square: cyan (0.1, 1.0, 1.0)
• square_big: green (0.1, 1.0, 0.1)
• wahoo: red (1.0, 0.1, 0.1)
• --white: color each pixel white. This is useful for testing .obj files that don't specify a diffuse color (the default that TinyOBJ uses is black, which won't show up at all).
• --norm_flat: Transform the normals provided by TinyOBJ using the rotation component of the view matrix. The easiest way to do this is to convert the normals to vec4s, and set their w component to 0. Then you can left-multiply the view matrix and the right thing will happen. Next, compute a color for each vertex using this formula:
  • Red: Use the normal's x-coordinate for red. A value of -1 maps to a red value of 0, +1 maps to 255. Since normal vectors are unit length, all coordinate values should fall between -1 and 1.
  • Green: Use the normal's y-coordinate.
  • Blue: Use the normal's z-coordinate.
  Color all pixels based on the normal/color of the first vertex listed for the face.
• --norm_gouraud: Compute colors for each vertex as above. Using Gouraud shading to calculate the color of each pixel. Recall that Gouraud shading interpolates between the vertices to get the colors along the edges, then interpolates those values along each scan line. For this version, you should interpolate the projected colors and ignore perspective distortion.
• --norm_bary: Same as above, but use barycentric weighting instead.
• --norm_gouraud_z: Compute z values at each pixel using perspective-correct interpolation. In other words interpolate the value for \(\frac 1 z\) then take the reciprocal, as described in the slides. Use this value for your z-buffer depth test. Also use it to compute the perspective-correct weights for interpolating colors at each pixel using Gouraud shading.
• --norm_bary_z: Same as above, but use perspective-correct barycentric weighting, as described in the slides, instead of Gouraud shading.

4.6 Extra Credit

The following extra features will all qualify for extra credit. If you have other ideas for enhancements, please check with a member of the course staff:

• Optimization: Eliminate all multiplications, square roots, and divides (except the perspective divide, texture lookups, and normal interpolation [see below]) from your rasterization loop (i.e. after you have converted all vertex coordinates to screen space). You will need to use Goraud-style interpolation for colors and texture coordinates in this mode. You will also need to break up the scan lines into groups that all connect the same two edges. Within each of these spans, calculate the incremental changes position, color, and texture coordinates as you step from pixel to pixel. Also compute the incremental changes to the left and right edges of the triangle as you move from row to row. The resulting code is a bit more complex and a bit less accurate, but until recently was much, much, much faster. Until every had 3D graphics cards, this was essential to get remotely reasonable performance.
• Lambertian shading. You will need to compute normals using spherical linear interpolation (slerp). Slerping sounds complicated, but is isn't really. Just linearly interpolate the normals like you interpolated the colors, then normalize the resulting vector to unit length (remember: the w coordinate should be 0 for normals because they are vectors, not points). If you do Goraud-style interpolation, normalize the length at each step, not just the final result.
• Phong shading: Phong shading adds a specular term on top of the Lambertian diffuse term, so it doesn't make sense to implement this without first implementing Lambertian shading. You may need to fiddle with the ambient, specular, and glossiness (the exponent) terms in the material files to create good test cases.
• Implement texture mapping. Keep in mind that texture coordinates run from (0, 0) for the lower-left corner of the texture to (1, 1) for the upper-right. You need to flip and scale these coordinates to (0, 0) for the upper-left to (width - 1, height - 1) for the bottom-right. Use perspective-correct interpolation for depths and texture coordinates. If you implemented Lambertian or Phong shading models, these should use textures rather than a fixed color for any terms with a specified a texture in the material file. Warning: For very narrow, "sliver," triangles, your barycentric interpolation weights may not sum to the triangle's area due to rounding area. As a result, you can end up with texture coordinates that are out-of-bounds. The easiest way to work around this is to divide by the sum of the weights rather than by the triangle's area.
• Implement normal/bump mapping. You'll need to search for OBJ files that specify a normal map. Remember to interpolate normals using SLERP.

5 Submission

Submit a .zip file containing your code and the .pro file created by Qt Creator. Please don't include the build directory with your compiled code. Submit your helplog separately as an ASCII text file.