CS 248: Introduction to Computer Graphics

Pat Hanrahan

Assignment 2 Frequently Asked Questions (FAQ)

Q1. Can I use gcc / g++ instead of cc / CC?

Q2. Do I have to output the same exact image as sample_viewer?

Q3. What exactly is passed in with the vertices that are to be rasterized?

Q4. How does texture coordinate interpolation work?

Q5. How can I get my RasterizeXor code to run faster?

Q6. Do I have to clamp (u, v) on every pixel?

Answers

Yes, you may use gcc / g++ instead of cc / CC. But we strongly suggest against it for performance reasons. Because cc / CC is written by MIPS, the SGI subsidiary that makes the R4K's, and benchmarks that are used to measure processor performance go through these compilers, these compilers are much better at optimization. Specifically, the MIPS compilers are much better at register allocation and instruction scheduling than the GNU compilers. On the source file you give us (rasterize.*), we will first try the MIPS compilers. If they don't compile the code, we will then try the GNU compilers. If they don't compile either, then we get annoyed :).

Q2. Do I have to output the same exact image as sample_viewer?

No, your image does not have to be the same pixel by pixel as our image.
However, there are at least three requirements that you should meet:


1. You only color pixels inside the triangles.


2. You correctly mesh adjecent triangles.


3. Two triangles that fill up the bounds (-1, -1) to (1, 1) also fill up the whole screen.

Q3. What exactly is passed in with the vertices that are to be rasterized?

A vertex looks like this:

typedef struct Vertex_st {
    float x, y, z, w;            /* geometry coordinates */
    float u, v;                  /* texture  coordinates */
} Vertex;

Any field in (x, y, z, w, u, v) can hold a number in any range.

(x, y, z, w) is the homogenous coordinate of the vertex. You should clip to the 2D region defined by (-1 < X < 1, -1 < Y < 1). This means that the left edge of the image buffer corresponds to (X = -1), the right edge to (X = 1), the bottom edge to (Y = -1), and the top edge to (Y = 1). It is your responsibility to map the vertices into screen space, which includes considering that the input vertex is given in homogeneous coordinates. If a triangle has a pixel outside of the boundaries of the screen space, it is your responsibility to not draw it.

(u, v) are the texture coordinates of a vertex. (0, 0) corresponds to the bottom left corner of the texture, and (1, 1) corresponds to the top right corner of the texture. As you are interpolating texture coordinates, the coordinate should be clamped to the range [0, 1).

Q4. How does texture coordinate interpolation work?

As stated during the lecture on texture mapping (slides 10 through 14), and as described in the course notes (Paul Heckbert's article page 59), the mapping of texture coordinates to screen pixels can be concisely written as

[ x ]     [ u ]
[ y ] = T [ v ]
[ w ]     [ 1 ]

where T is a 3x3 matrix; in particular, T is the result on compositing all transformations that texture coordinates undergo until they are mapped to the screen:
• Mapping the texture to the polygon.
• Positioning the polygon relative to a complete object.
• Placing the object in the scene.
• Placing the camera relative to the scene.
• Projecting (taking a picture using the camera).
• Relating screen coordinates to pixels (raster coordinates).

Rewriting the formula as

[ u ]              [ x ]      [ x ]
[ v ] = Inverse(T) [ y ] = T' [ y ]
[ 1 ]              [ w ]      [ w ]

we see that, during the rendering of a particular triangle, there is some constant matrix T' relating raster coordinates and texture coordinates. What you are given per triangle is the u, v, x, y, and w values at the vertices. Using this information, it is possible to compute the elements of T' by solving 3 sets of 3 linear equations, each in 3 unknowns (the elements of a row of T').

Alternatively, without ever calculating T' per se, we can find u and v for every pixel within the triangle by linear interpolation. In particular, the above equation can be written as

[ U ]   [ u/w ]      [ x/w ]      [ X ]
[ V ] = [ v/w ] = T' [ y/w ] = T' [ Y ]
[ Q ]   [ 1/w ]      [ w/w ]      [ 1 ]

by dividing both sides by w. This equation implies that the three quantities U, V, and Q - namely the homogenous texture coordinates - are linearly related to X and Y -namely the pixel coordinates generated during scan conversion. Moreover, U, V, and Q are known at the vertices, since u, v, and w are given at the vertices. It follows that U, V, and Q can be incrementally calculated using the standard interpolation mechanism described in the course notes (lecture 8, page 29). And from these, u and v can be obtained using

u = U/Q
v = V/Q

For last year's CS 248, we wrote a detailed recipe for texture mapping that you might want to consult. Bear in mind though that the class had a very different structure last year, and a different approach was taken; so don't be surprised if you can't follow all the details.

Q5. How can I get my RasterizeXor code to run faster?

First thing, you should make no global references inside your inner loops. The following is what you should not do:

buffer[x + y * winWidth] ^= currColor;

Instead, you should have:

local_buffer[x + y * local_winWidth] ^= local_currColor;

where local_* are just local variable copies of the global counterpart. The reason you do this is because the compiler is required to reload globals at every iteration of the loop (due to aliasing), but not required to reload locals.

Also, you should incrementalize the buffer address computation since integer multiplies are so expensive. Thus you code should look like:

scanline[x] ^= local_currColor;

Q6. Do I have to clamp (u, v) on every pixel?

Because of efficiency concerns, many of you don't clamp (u, v) at every pixel because you know that (u, v) are in the range [0, 1] from the environment map viewer.

This is the incorrect thing to do.

First, in "render.h", we ask that these values be clamped. Note that clamping at the vertices is not the same as clamping at the pixels. As far as the interface is concerned, this is required: we could give you (u, v) outside of [0, 1].

Second, there is a bigger problem in the assumption that just because (u, v) is in the range [0, 1] at the vertices, then (u, v) will be in the range [0, 1] at the pixels. In a perfect mathematical world, this assumption is correct. However, in the world of floating-point roundoff error, this is not the case. Even though you are interpolating on the range [0, 1], you will get pixels with (u, v) outside of this range on the boundaries of the cube faces. No matter how much you try to minimize these roundoff errors, they will always be there (i.e., going to double lessens the problem, but does not eradicate it). We will be looking for this.