Rasterization is the process of projecting 3D objects to a screen and then finding which pixels of screen belong to which object and coloring them accordingly.

This post is my understanding of rasterization pipeline and implementation for the Assignment 1 of the course CMU 15-462/662, so there might be some mistakes or conceptual errors.

Rasterization Pipeline

Bresenham’s Line algorithm

Let the line equation be given as

$$\begin{align*} \frac{y - y_0}{x - x_0} &= \frac{y_1 - y_0}{x_1 - x_0} \\ y &= \frac{\Delta{y}}{\Delta{x}} (x - x_0) + y_0 \\ \end{align*}$$

For a line of slope $\in [0, 1]$, let $x_i$ and $y_i$ be a point that is plotted. To plot $x_{i + 1} = x_i + 1$ one can choose $y_{i+1} = y_i$ or $y_{i + 1} = y_i + 1$. This has to be decided by checking whether the actual point $y^*$ is closer to $y_i$ or $y_i + 1$. Let the distance of $y^*$ to $y_i$ and distance of $y^*$ to $y_i + 1$ be $d_1$ and $d_2$ respectively. Consider the below diagram

$$\begin{align*} d_1 &= (y_i + 1) - y^* \\ d_2 &= y^* - y_i \\ d_1 - d_2 &= 2 \cdot y_i - 2 \cdot y^* + 1 \\ \text{So, } \\ y_{i + 1} &= \begin{cases} y_i + 1 & d_1 - d_2 \ge 0 \\ y_i & d_1 - d_2 \lt 0 \end{cases} \\ \end{align*}$$

If $d_1 - d_2 \ge 0 \implies d_1 \ge d_2$ .So, $d_1$ is closer to true $y^*$
Otherwise, $d_2$ is closer to true $y^*$. In essence, one increments $x$ values by 1 each time and then check whether $y$ or $y + 1$ is closer to true value and color accordingly.

This algorithm assumes a slope between 0 to 1, similarly one needs to handle for slope in $[1, \infty)$ and also negative slopes, but its very similar. For slope $> 1$ one increments y values by 1 and then calculate x values. And in case of negative slopes, one needs to decrement x and y values, depending on slope.

Rasterizing Triangles

To rasterize different shapes, they are generally split into primitives. These primitives can be spheres, quads, triangles, other polygons etc. However the most commonly used approach is to use triangles. Why? Because they are the simplest of polygons, that can approximate any shape, triangles are always planar (so no need to worry about overlapping edges), are convex shapes, and are easy to interpolate using the corners.

To rasterize a triangle, first I find a bounding box for the triangle and then for every pixel inside, I check whether it falls within the triangle. To test whether a point lies inside a triangle, we check whether the point lies on same half plane for every edge. To illustrate,

Considering that the vertices A, B, C are given in counter clockwise direction, consider the vectors $AB = B - A$ and $AP = P - A$. The cross product of these two vectors points towards the screen. Similarly, for cross products of $BC$ and $BP$. For a point to be inside a triangle, cross products of each edge (in counter clockwise) with the point must be in same direction, in other words the magnitude sign should be same.

function isWithinTriangle(Point p, Point A, Point B, Point C) {
    double ABxAP = sign(cross(B - A, p - A));
    double BCxBP = sign(cross(C - B, p - B));
    double CAxCP = sign(cross(A - C, p - C));

    return sameSign(ABxAP, BCxBP, CAxCP);
}

Supersampling

Since triangles are discretized to draw them on the screen, edges are not smooth as can be seen in previous image. To remove such artifacts, to ‘anti-alias’ them, a technique called Supersampling is used. Multiple samples are taken per pixel and then the intensity / color of pixel is the average of these samples. (Other filters apart from averaging can also be used, but here I have used the box area filter, giving the effect of averaging)

Texture Mapping and Trilinear Filtering

To add more details to triangles (or other primitives) texture mapping is done. Texture mapping is mapping some texture file (can think of it as an image file which says how the pixel should look, but it can also have other details) to each pixel thats visible on the screen for the given view. In the assignment texture mapping is used to rasterize an image on to the screen. So for each pixel, have to find (u, v) coordinates which lie in the range $[0, 1]$. These coordinates are then used to find the color value by linear interpolation of nearest texture coordinates. If we are interpolating from nearest coordinates in 2 directions, x and y, that is bilinear interpolation. Another case to handle here is zooming in and out. As we zoom out, if texture map is used directly we again face the issue of aliasing. So have to generate multiple levels of texture maps, also called mipmaps. Level 0 has the texture map as is, as we go higher the texture map becomes coarser by averaging nearby texels (texture pixels). These averaged texture maps are precomputed and stored for a particular number of levels, in this case $\log_2(\text{texture size})$. Then we do an interpolation among different levels, depending on the view size and texture size. This is trilinear interpolation. (Since linear interpolation is done along 3 dimensions).

Procedure:

1. Compute $(u, v)$ coordinates by mapping image size to $[0, 1]$
2. Compute the mipmap levels to be used.
3. Compute nearby texel locations by mapping $(u, v)$ coordinates to texture size of mip map level computed above and the next level.
4. Do trilinear interpolation for the two levels and 2 sets of texel coordinates.

Alpha Compositing

Occlusion and Depth buffer

When there are many objects occluding one another, how to identify which should be drawn, since all the triangles are drawn one by one? For every pixel (or supersample) keep track of closest depth seen. And for a new pixel, if its depth is greater than the current depth skip drawing it. But this gets more complicated when triangles are semi transparent. This is handled by compositing.

TODO