This project served as a high-level introduction into how both rasterization of images and antialiasing work. Throughout the project I implemented various different sampling methods and was able to visually compare their antialiasing effectivenesses as well as determine their relative time and space complexities. Completion of this project has significantly expanded my understanding of how rgb color values work together to create an image, as well as how they can be manipulated to modify images. Although this project had a strong focus on improving the quality of images with reasonable efficiency, I am happy to say I also feel much more comfortable working with C++ and Xcode.
Rasterizing triangles is done by checking pixels and seeing if they are contained within the bounds of the given triangle. There are various algorithms for checking this, some more efficient than others. Due to project time constraints, I opted to not implement the most optimal solution I could think of; however I will explain both my solution and a more optimal one below.
I first limit checking of pixels to that of the bounds of the smallest box that contains the triangle. Given the three vertices of the triangle, the bounds of this box are found by finding both the min and max x and y values of these three points. Each of the four combinations of x and y values (ie: {(minX, minY), (minX, maxY), (maxX, minY), (maxX, maxY)}) correspond to a vertex of the bounding box. From there I check each pixel within this box to see if it’s contained within the triangle and fill it in if it is. This is the step I do not perform optimally. A more optimal solution might only check pixels at the bounds of the triangle and then after the triangle is bounded, retroactively fill in the inside of the triangle.
The algorithm I use to check if a pixel is contained by the triangle is slightly different than the one taught in class. In my triangle contains algorithm, I check if a pixel is contained by calculating each of the areas of the triangle made by the pixel and each combination of two vertices from the bigger triangle. If the sum of the areas of these three triangles made using the pixel is equal to that of the area of the main original triangle, then the main original triangle must contain the pixel.
|
|
Supersampling is the process of sampling at higher frequency than the number of pixels available and then averaging the values into the pixels that correspond to the samples. Thus supersampling is a good antialiasing technique because it stores extra data in each pixel value that may be lost if a lower sampling frequency had been used. In terms of the algorithm, similar to part one, I iterate through every pixel. The only difference with supersampling is that now for each pixel I iterate through each subpixel within that pixel, and store its rgb color values in the supersample_buffer at the proper index. Once the supersample_buffer is filled with all the samples, I averaged the subpixel rgb values into rgb values for the actual pixels in the resolve_to_framebuffer() method. When implementing supersampling, I did have to make one minor change to the rasterize_point(float x, float y, Color color) method in order for points and lines to still appear. This change was that this method now treats points as supersamples instead of pixels. At the conclusion of the rasterizing resolve_to_framebuffer() is called and fill_pixel(size_t x, size_t y, Color c) is called on each of those points that were put in the supersample_buffer.
|
|
|
In this section the goal was to implement the translation, scalar and rotation matrices. The results of which can be seen in the blue block man below. To create him, I modified the previous red block man’s body proportions and rotated and translated the arms and legs of my new blue block man such that he is making a celebratory power pose. In order to create this pose, I positioned his arms up at a 45 degree angle and bent one of his legs at a 30 degree angle.
|
Barycentric coordinates refer to the defining of a point based on its relative position to three other points. Its relative position to each of the three points becomes a coordinate with a value between 0 and 1.The sum of these coordinate values is always one. Because of how I had previously implemented the triangle rasterization method, it was very simple to modify it to incorporate barycentric coordinates. All that was required to include it was that I had to reuse the area values that I had already been using to see if a point lies inside the triangle and use them as scalar values.
|
|
Pixel sampling is the process of choosing the rgb color values for a pixel based on sampling from another image. There are two types of pixel sampling methods we implemented in this project. The first is nearest sampling which works by assigning a pixel the value of the closest corresponding pixel from the other image. In order to color this pixel, I found its center and found where that point would appear on the sampling image. From there, I found the nearest pixel center in that image and copied its rgb color values to the original pixel. Bilinear sampling is quite similar to nearest sampling, the main difference being that instead of choosing the closest pixel in the sampling image, I took a weighted average of the four closest pixels based on their proximity to the point. I was able to use these sampling methods to perform texture mapping because each pixel color in the image to be mapped to could be easily attained by using one of the two mentioned sampling methods.
As can be seen in the images below, bilinear sampling helps preserve more data in the pixels when the sample rate is low. This is due to the fact that bilinear sampling averages the pixel's color values, whereas nearest sampling takes the closest pixel color value. This has a similar effect as super sampling because color values for pixels computed using super sampling also use the surrounding pixels as inputs. This means that if the frequency of the image that is being sampled is higher than that of the image that is being mapped to, both super sampling and bilinear sampling will preserve the data of surrounding pixels that nearest sampling would ignore. To state it explicitly, this means that bilinear sampling will have a great effect of preserving data when the sample rate is smaller.
|
|
|
|
Level sampling is the process of using different resolution images in different situations in order to prevent aliasing from downsampling a high resolution image. For example, if you are looking off into the horizon and see a mountain, you aren’t going to notice the texture of the dirt from far away. However, if you are standing on the mountain, you are going to see the texture of the dirt. Because there are only so many pixels available, if you tried to preserve the texture of the dirt when far away from the mountain, there would be a lot of aliasing. Mip levels use this idea to preemptively store lower resolution images that don’t contain aliasing and look normal from a distance.
The three types of level sampling that I implemented in this project were L_ZERO, L_NEAREST and L_LINEAR. L_ZERO works by always using the highest resolution image. L_NEAREST works by always using the mip level image closest to what I need. L_LINEAR works by taking a weighted average of the two closest mip level images.
I was able to compute the exact mip level (D) required using the following formula from lecture. The values of du/dx, dv/dx, du/dy and dv/dy were obtained by subtracting the barycentric mappings of (x + 1, y) and (x, y + 1) from the barycentric mapping of (x, y).
|
Due to a small bug, both nearest level and bilinear level interpolation result in a grid like design on top of the image.
|
|
|
|
Concluding analysis of the various sampling techniques implemented in this project:
Regular sampling:
This is the most naive sampling method. Although quite quick, and computationally fairly inexpensive, it can also result in a decent amount of aliasing.
Supersampling:
Supersampling is one of the most effective ways of antialiasing. It does a tremendous job of preserving image data, however, can come at a significant cost in terms of time and space complexity, especially at high per pixel sample rates.
Pixel sampling for texture mapping:
Nearest pixel sampling functions quite similarly to regular sampling in terms of its results. Bilinear pixel sampling functions quite similarly to supersampling in terms of its results.
Level sampling:
Level sampling is very fast because only mip levels need to be computed and the images are already saved at these resolutions. Although each image corresponding to each mip level needs to be stored, the extra space required is less than two times the space required to store the highest resolution image (assuming each subsequent level stores half as much data as the previous). Thus level sampling does a great job of anti aliasing in a timely manner and is commonly used because of that. Trilinear filtering takes antialiasing a step further, and comes at a very minimal cost to time complexity.