rasterizer

Nadia Hyder, CS 184 Spring 2021

OVERVIEW

In this project, I implemented a vector graphics renderer for simplified Scalar Vector Graphics (SVG) files. I implemented several functionalities and features including triangle rasterization, supersampling, hierarchical transforms, and texture mapping with antialiasing.

TASK 1: DRAWING SINGLE COLOR TRIANGLES

I first created a simple, single-color triangle rasterizer using 2D sampling. To perform 2D sampling more efficiently, I traversed pixels within the given triangle’s bounding box (determined by finding minimum and maximum vertex x and y coordinates), only filling pixels with centers within the triangle.

To check if a pixel (or in this case, center of a pixel: x+0.5, y+0.5) was inside the triangle, I implemented a three line point-in-triangle test. Given vertices , , , and some point , we can compute line equations to check if a point is inside, outside, or on an edge:

=

	:	point on edge
	:	outside edge
	:	inside edge

Below are 2 images: the output of triangle rasterization using 2D sampling, and the output zoomed in on the tip of the blue triangle.

TASK 2: ANTIALIASING BY SUPERSAMPLING

Next, I performed antialiasing by supersampling, or sampling several times per pixel (determined by the sample_rate). The results from task 1 show that sampling once per pixel creates sharp edges/ artifacts (also known as jaggies) in the raster image from aliasing, whereas supersampling produces a better raster image yielding smoother edges.

Supersampling required several modifications to the rasterization pipeline. While traversing over the triangle’s bounding box, I also traversed sample_rate # of subsamples for each pixel, checking whether the center of the subsample was within the triangle. If so, I added the subsample to a sample buffer (as opposed to filling the entire pixel like in task 1). The sample buffer is dynamically sized to manage memory appropriately.

Finally, to resolve the supersamples to the framebuffer, I downsampled to width x height final pixels by averaging down the grid of sample values for each pixel in the sample buffer. These final pixels were written to the framebuffer.

Overall, supersampling allowed for more precision and averaging and downsampling pixel values yielded smoother edges and fewer jaggies. The effects as the sample rate increases are considerable. Below is the output of antialiasing by supersampling using sample rates 1, 4, and 16, zoomed in at the right vertex of the red triangle:

sample_rate = 1	sample_rate = 4	sample_rate = 16

TASK 3: TRANSFORMS

Next, I implemented 3 transforms using homogenous coordinates: translate, scale, and rotate. On the left is the original cubeman, and on the right is the cubeman running, after a few transformations are applied.

TASK 4: BARYCENTRIC COORDINATES

Next, I used barycentric interpolation to rasterize and fill triangles given only vertices and their colors. Given a point P within a triangle, Barycentric interpolation provides a balanced system of equations to find weights for v1, v2, and v3 that tell how much of P’s coordinates are made of v1, v2, and v3. These weights are found using the following equations:

After interpolating the colors at vertices v1, v2, and v3 with their weights w1, w2, and w3, we achieve the following output:

The following is another output produced using the same logic with default viewing parameters and a sample rate of 1:

TASK 5: “PIXEL SAMPLING” FOR TEXTURE MAPPING

I used pixel sampling to perform texture mapping. In pixel sampling, we create a mapping from a texture triangle’s uv coordinates to its barycentric coordinates in order to map a texture to its appropriate color.

There are 2 methods for pixel sampling:

1. Nearest – selects the texture of the closest sample in the texture to the given uv coordinate

2. Bilinear interpolation – uses a weighted average of the 4 nearest samples to perform 2 rounds of linear interpolation (horizontally and vertically).

Bilinear sampling performs better than nearest sampling in several cases; sampling only the nearest texel can miss lines and relevant texels, causing discontinuities. Comparing the images below elucidates this. The image on the left shows nearest sampling and the image on the right shows bilinear sampling, both with a sample rate of 1. There are clear gaps in lines produced by nearest neighbor sampling, while lines are contiguous and smoother when using bilinear sampling.

nearest pixel output	bilinear output

Below are a few more outputs:

nearest sampling, sample_rate = 1	nearest sampling, sample_rate = 16

bilinear sampling, sample_rate = 1	bilinear sampling, sample_rate = 16

We can see clear differences as explained before. Supersampling/ antialiasing creates smoother lines in both cases, so increasing the sample rate improves performance. Furthermore, these output images reinforce that bilinear sampling is better at maintaining continuity as opposed to nearest sampling.

TASK 6: “LEVEL SAMPLING” WITH MIPMAPS FOR TEXTURE MAPPING

Finally, I implemented level sampling to perform texture mapping by mipmap level. In level sampling, we sample from mipmap levels (of an image pyramid where each level has a progressively lower resolution than the previous one). Using lower resolution versions of the same texture saves computation and avoids aliasing caused by high frequencies.

To perform level sampling, I passed the barycentric coordinates of (x+1, y) and (x, y+1) to find its uv coordinates, and calculate du/dx, dv/dx, du/dy, and dv/dy. I calculated the mipmap level using the following logic and formula:

We choose both how we want to resample the image: using either nearest or bilinear interpolation, and how to resample the mipmap level: using level 0, nearest D, or linear interpolation. There are several speed/ memory/ antialiasing tradeoffs when deciding which sampling technique to use:

· Level 0 sampling is memory intensive and subpar antialiasing (does not take advantage of mipmap capabilities)

· Nearest level sampling is less memory intensive than level 0 and performs better for antialiasing, but is not perfect

· Bilinear level sampling has good antialiasing capabilities but is very slow

· Nearest pixel sampling has good rendering speed but poor antialiasing capabilities (as shown before, has lots of discontinuities)

· Bilinear pixel sampling is also slow but performs antialiasing well

I used an image of Sather Gate to show 4 versions of the image. The outputs show how level sampling methods and pixel sampling methods produce different antialiasing results.

L_ZERO & P_NEAREST	L_ZERO & P_LINEAR
L_NEAREST & P_NEAREST	L_NEAREST & P_LINEAR

CONCLUSION

Overall, this project was both incredibly challenging and rewarding. This project has given me deeper insight into how complex computer graphics is, and how useful linear algebra is! It also made me a better debugger because a single pixel could affect the entire output. Rasterization takes a lot of geometry, linear algebra, and precision.