CS 184/284A: Computer Graphics and Imaging, Spring 2024

Homework 1: Rasterizer

Colin Steidtmann

Overview

I did something amazing: I programmed triangles on a screen! Before this class, I took computer graphics for granted. Pixels are little squares, so besides lines that go perfectly vertical or horizontal, it's remarkable that we can put together pixels to form circles or diagonal lines that create triangles. In this assignment, I learned and implemented algorithms behind displaying smooth diagonal lines and images we often take for granted. Along the way, I learned why graphics in old-school video games look so pixelated and struggled in my attempts to create SVG files by hand (see the end).

Section I: Rasterization

Part 1: Rasterizing single-color triangles

To rasterize triangles (render triangles on the screen), I created a function that took in the 3 (x,y) coordinates of my triangle and iterated over it's bounding box, testing whether each pixel is in the triangle or not. This is a type of sampling. If a pixel was in the triangle then I colored it in. 

I tested if a point was inside a triangle by calculating the dot product of the normal vector for each edge of the triangle with the vector connecting the point to the corresponding vertex. If all three dot products were positive, it meant the point was inside the triangle, and I colored it in. Each positive dot product indicated the 'push' from the triangle's wall, confirming the pixel's location within the shape.

Part 2: Antialiasing triangles

To implement antialiasing for my triangle rendering, I introduced supersampling by increasing the sampling rate to capture high-frequency details. This involved adding a sample_rate variable and sampling sample_rate times within each pixel. The individual colors were then averaged to determine the final pixel shade. This approach replaces my previous method of simply checking if the pixel's center was inside the triangle; now, the shading reflects the percentage of samples found within the triangle's area.

As you can see, supersampling produces much smoother transitions along the triangle boundary due to the increased sampling rate within each pixel. This is achieved by evaluating sample_rate points and averaging their results. However, this improvement comes at a cost. I had to increase my buffer size that stores sample points by a factor of sample_rate and increase my runtime by the same factor.

Part 3: Transforms

The following robot images were created using SVG file formats, which used the transformation, rotation, and scaling functions I implemented. 

My code implements simple transformations by multiplying the image points (as a vector) by a transformation matrix. In computer graphics, we add a "homogeneous coordinate" to the image point vector. This extra dimension allows us to represent translations using simple matrix multiplication alongside rotations and scaling. Any transformation can be decomposed into one or more rotations, scaling, and translation matrix multiplications. To rotate something not around the origin, we first translate it to the origin, rotate it around the origin, then translate it back to its original position. The three matrix transforms that we multiply together are: Translate(-c) dot Rotate(c) dot Translate(c).

Extra Credit: All the images in this report came from a GUI that displayed what I had rasterized. To earn some bonus points, I added the ability to rotate the viewport clockwise and counterclockwise using the keys N and M, respectively. This involved finding the code that dealt with keyboard events, adding my extra conditional keys (N & M), and calling a function I wrote to rotate the viewport. Inside my rotation function, I first got the device coordinates by converting from the SVG coordinates. I then translated the viewport center to the origin, rotated it by the degree amount passed in as an argument using a matrix multiplied with the device coordinates, and finally translated the viewport center back to the device center. The results above show screenshots taken every PI/8 rotation, first rotated counterclockwise and then clockwise. Finally, I uploaded all the images to a site that could create a GIF from them.

Section II: Sampling

Part 4: Barycentric coordinates

Barycentric coordinates are used to represent the location of a point within a geometric shape, such as a triangle. Instead of using standard x and y coordinates, you express the point's position relative to the vertices (corners) of the shape. To calculate barycentric coordinates, you label the triangle's corners as A, B, and C, and calculate three corresponding parameters - alpha, beta, and gamma - that indicate how close the test point is to each corner (alpha + beta + gamma = 1).

Part 5: "Pixel sampling" for texture mapping

My next challenge was to incorporate textures into the triangles using a texture image where each pixel is a "texel." The triangle's corners are assigned (u,v) coordinates corresponding to the texture region they should map to. Using the alpha, beta, and gamma values, (x,y) coordinates within the triangle are mapped to (u,v) coordinates near the nearest texel in the texture, known as pixel sampling. Two pixel sampling methods are commonly used:

1. Nearest Neighbor: Calculate alpha, beta, gamma, multiply these weights by the triangle's corner (u,v) coordinates, scale them by the texture dimensions, and round to the nearest whole integer to assign a texel to each pixel.

   • Pros: Fast and preserves sharp lines without blurring.

   • Cons: Can cause aliasing such as jagged edges.

2. Bilinear: Similar to nearest neighbor, but blend the 4 nearest texels (weighted appropriately) and assign the blended texture color to the pixel.

   • Pros: Smoother appearance and less aliasing.

   • Cons: Slower runtime and can blur fine details.

Part 6: "Level sampling" with mipmaps for texture mapping

To enhance texture mapping and reduce aliasing, another method involves using Mipmaps, which are multiple scaled-down and lower resolution versions of the original texture. By calculating the rate of change of texture coordinates across a surface, we can determine the level of detail needed and select the appropriate Mipmap. This process, known as level sampling, filters out high-frequency signals by downsampling the higher resolution mipmaps, effectively averaging the color information of neighboring texels. This reduces aliasing by smoothing transitions between pixels, resulting in a more natural appearance, especially at angles or when scaled up or down. Mipmaps are stored efficiently as each additional level consumes less memory. With level sampling, we choose between the original texture image (level 0), the nearest level (determined by the rate of change), or a bilinear combination of two nearest levels, which is often the most optimal when the desired level sits between two levels.

Now we can compare a new set of sampling methods:

1. Number of Samples per Pixel (Supersampling):

   • Pros: Provides the best antialiasing by averaging colors from multiple surrounding pixels, with no memory overhead.

   • Cons: Slowest option.

2. Pixel Sampling:

   • Pros: Fast (using nearest neighbor), lowest memory footprint, antialiasing capabilities (using bilinear).

   • Cons: Aliasing occurs using nearest neighbor at low resolutions and bilinear at high resolutions.

3. Level Sampling (Mipmapping):

   • Pros: Offers good antialiasing at all resolution levels, faster than supersampling.

   • Cons: Higher memory overhead, slower than nearest neighbor pixel sampling, more code complexity.

Ultimate Comparison

First we'll see that on a zoomed-out image with lots of detail and using the nearest texel, interpolation across different Mipmap levels doesn't provide significant benefits.

Next, instead of using the nearest texel on a zoomed-out image, using the nearest 4 texels helps tremendously, especially when using the appropriate Mipmap level.

While the above images show that choosing the appropriate Mipmap level helps greatly when sampling only once per pixel, the results are closer when sampling 16 times per pixel, as seen below.

In my opinion, the results above hit the sweet spot for displaying this image. However, for fun, we can look at bilinear sampling, which averages the nearest 4 texels. It seems to over-blur when sampling 16 times per pixel, as shown below:

It's similar to selecting the best smartphone photo after a certain level of antialiasing. As you invest more effort into methods like supersampling, bilinear pixel sampling, or texture image level sampling, there are diminishing returns. Eventually, the antialiasing efforts can actually degrade the image quality rather than improve it.