When an image appears on the computer, how exactly is the image depicted through the pixels? While there is an infiniteness of visual information to process in the real world, the computer screen is discrete and limited.
Thus, cometh Rasterization.
As one of computer graphic's core processes, the rasterization pipeline allows for computers to mathmatically interpret and/or transform points, lines, triangles, and other polygons and map them appropriately onto a fixed grid of framebuffer pixels. When it comes time to fill the pixels with colors and textures, rasterization utilizes pixel sampling processes to color in polygons, giving us a product image. In addition, improvements can be made to the image using antialiasing techniques such as supersampling to rid of aliasing artifacts that can make images appear uncanny and unnatural.
It was interesting to see the many sampling techniques we can utilize to improve an image's outcome through interpolation and averaging. Through computer graphics, we are allowed to manipulate, improve, and distort polygons in ways that stays consistent to the UI screen size and window. Using scalable coordinate mapping systems and precomputed textures, we are able to achieve a "smarter" image that deals with aliasing quite well. It is curious on the other ways one may sample an image file and the pros and cons of them compared to the ones implemented in this section.
In detail, the 2D vector-based rasterizer takes scalable vector graphics (SVG) files as input and features supersampling, transforms, barycentric interpolation, texture and level mapping (mipmapping), which are implemented and discussed on this page.
Given three vertices in the cartesian coordinate system and a Color object, we can easily rasterize single-colored triangles into the framebuffer by iterating through all pixels and querying whether the midpoint of a pixel
(x + 0.5, y + 0.5), where x and y are integers within the frame
is inside the triangle through point-in-triangle tests. However, as the framebuffer represents so many pixels, it is inefficient to iterate through the entire grid, which some blocks of pixels are no where near the triangle. Thus, to significantly improve runtime, each triangle will be bounded by the smallest possible rectangle that encapsulates all three vertices.
For our point-in-triangle tests, we define
L(x,y) = (x - x0) * (y0 - y1) + (y - y0) * (x1 - x0),
where (x,y) is point P, and (x0,y0) and (x1,y1) defines one triangle edge
|
|
|
If this midpoint P is "inside" all three edges of the triangle, the point's pixel is inside the triangle!
A caveat to keep in mind is that point-in-triangles assume that all triangles are consistently represented as either clockwise or counterclockwise. For me, I chose to follow a counterclockwise orientation. To do this, we check if the triangle's orientation is clockwise:
(y1 - y0) * (x2 - x1) - (x1 - x0) * (y2 - y1) > 0 , where (x0, y0), (x1, y1), (x2, y2) are vertices of a triangle
If this is true, then the points can easily be swapped to turn the triangle counterclockwise.
Implementing this would allow for the rasterizer to make single-colored triangles with a sample rate of 1. But now we face aliasing artifacts, such as "jaggies" seen below.
One antialiasing technique is supersampling. Meaning, instead of sampling a pixel once at its midpoint, we can sample one pixel multiple times (sampling rate) by partitioning the pixel into equal parts. Then we take the midpoint of each of those parts.
|
|
Following the same procedure as sampling once per pixel, once we figure which subpixels are inside the triangle, we can average sample_rate subpixels in one pixel to form a new averaged down color. This is will create an effect of a blur. The rasterization pipeline is now updated with the new parameter sample_rate.
|
|
In a way, supersampling helps improve the "quality" of each pixel by sampling more per pixel. With much more information at our disposal, we can deal with high frequency changes in our images better through averaging. This phenomenon is explained in the nyquist theorem. With more samples, we can ultimately eliminate aliasing in our images.
To implement supersampling, we used a global data structure supersample_buffer, which is a vector/list of colors of size (width * height * sample_rate). With the supersample_buffer, we can record each subpixel's color (colors are determined and recorded based on whether that subpixel is inside its respective triangle) inside the frame (width * height) via looping through each subpixel midpoint in the bounding box and calling the point-in-triangle test. We can use the helper function fill_supersample to easily fill in the color in the correct index. This helper function will uniquely map a subpixel on the framebuffer to the supersample_buffer using the unique key:
supersample_buffer[s * width * height + (y * width + x)]
Once the supersample_buffer is completely filled with its appropriate colors, we can finally call RasterizerImp::resolve_to_framebuffer() to average the colors of the appropriate subpixels of a pixel in the supersample_buffer and color in the pixel with the averaged color on the RGB framebuffer.
Notes: don't forget to clear and resize the supersample_buffer depending on the window's size and sample_rates!
Also, the rasterization pipeline is updated so that drawing/filling only happens AFTER the supersample_buffer is done being filled with needed subpixel colors.
Implementing supersampling allows for the rasterizer to antialias our image with varying a sample rates of 4, 9, and 16. Jaggies now seem more like blurs and the image appears more realistic. That's better!
|
|
|
By sampling more in one pixel, we can detect subpixel samples points that are inside the really skinny triangle corner, which sampling one midpoint of a pixel was unable to do. With these subpixel samples, we can average the colors of the subpixels in one pixel and have a lightly colored pixel. This is much better than white pixels seen in sample_rate = 1.
Sometimes we wish to change the orientation of elements in the image. To do this, we can utilize 3x3 matrices with homogeneous coordinates and linear algebra to transform points and vectors. Our rasterizer features translation, scaling, and rotation according to the SVG spec. Each utilizes their own unique matrix.
Transform matrices can even be combined through matrix multiplication. (Order matters!)
|
is rotated 5 degrees, and the left leg is translated down by 60px, and scaled up 0.1px |
Barycentric coordinates are (α, β, γ) "area" coordinates in respect to a triangle. Each vertex is assigned a mass/weight, to which we can represent any point (x,y) inside the triangle in respect to these weights and vertices (x0,y0), (x1,y1), (x2,y2). The relational equation:
(x,y) = α * (x0,y0) + β * (x1,y1) + γ * (x2,y2), where α + β + γ = 1
By assigning each vertex a weight, we can easily interpolate colors of the pixels inside the triangle (this makes up a gradient!). Using the same equation and concept of ratios, we can determine the pixel color at (x,y) as:
Color color_at_xy = α * c0 + β * c1 + γ * c2, where c0, c1, c2 are colors of the vertices
This is where things continue to get interesting. Previously, we performed color interpolation to fill in a triangle based on a color gradient. Now, we can use a similar concept for pixel sampling to interpolate a triangle with a texture mapping. Given three triangle vertices in the (u,v) texture coordinates, we can map every pixel in the triangle to some pixel on the texture. But, the problem is that the pixel in the triangle may get mapped to a non-integer indexed (tx,ty) coordinate that is not an exact pixel on the texture mapping, which can cause inaccuracy in the resulting texture in the triangle. Hence, we used two types of pixel sampling methods to make the resulting texture more accurate: the nearest and bilinear pixel sampling. For nearest pixel sampling, the non-integer pixel coordinate is rounded to the “nearest” integer pixel coordinate and uses the texture pixel at the rounded integer coordinate for the triangle pixel. For bilinear pixel sampling, we take the weighted average of the texture pixel of the 4 neighboring pixel coordinates.
|
|
|
|
By comparing nearest and bilinear, we can see that bilinear clearly provides a superior-looking image in sample_rate = 1 due to its averaging qualities. Once we start antialiasing with sample_rate = 16, the difference between the two becomes less apparent, though bilinear is slightly better than nearest sampling.
The main difference between the two pixel sampling methods is that nearest pixel sampling will simply utilize the closest pixel without attempting to consider what the other surrounding pixels are. On the other hand, bilinear pixel sampling will take the weighted average of surrounding texture pixels and blend them to interpolate the pixel. Therefore, if the texture difference between neighboring pixels is very large, this will cause the most difference between the two methods, because the nearest will simply take the closest texture pixel, potentially making the resulting triangle texture pixel “jump” and impact the smoothness and uniformness of the image. On the other hand, bilinear pixel sampling will include both contrasting, neighboring texture pixels by “blending” them, making the resulting image appear more smoothly and have less sharp texture change.
Level sampling is a technique specifically to improve the overall image quality and reduce aliasing by producing an image composed of different levels of resolutions. The crucial idea is that even with a full resolution texture image, there can be aliasing because different texture shapes can be complex and their footprint is too large, such as fine wall patterns appearing in the distant background. Hence, by storing successive lower resolution images, we can use level sampling to determine what areas of the image we can apply different resolutions of the image. To implement this technique for texture mapping, we need to calculate what mipmap level to use for a given point in the triangle. To get the mipmap level, we take the derivative of the triangle point in question and another adjacent point in terms of how much the u and v coordinate change with respect to the x and y coordinate, then take their distance and finally apply log to the result. The larger the derivative, the greater the mipmap level will be used for that point in the triangle. This intuitively makes sense, because if the texture becomes very complex and changes shape/color significantly (implying a higher derivative and higher change between pixels), then a lower resolution image should be used there to remove any aliasing.
In terms of speed, the fastest combination is where we use nearest pixel sampling and zero level sampling, because performing nearest pixel sampling is faster than performing bilinear pixel sampling, and zero level sampling simply uses the original texture resolution, requiring little overhead. The worst combination is where we use bilinear pixel sampling and bilinear zero level sampling (also known as trilinear sampling), because the most amount of computations is done for this combination to compute the weighted averages for all neighboring pixels. In terms of memory usage, it’s a similar story where the nearest pixel sampling and zero level sampling uses the least amount of memory, because the least amount of data needs to be stored in cache to process the pixels, whereas the trilinear sampling is the worst because it requires storing the most amount of intermediate data for all neighboring cells. In terms of antialiasing power, the trilinear sampling is the best because it performs weighted average across pixels and levels to produce an image with the least amount of aliasing. On the other hand, nearest pixel sampling and zero level sampling does the least amount of work and does not perform good anti-aliasing for areas that have very complex textures and shapes appearing in far distances. Nearest level sampling is in between zero level and linear level sampling in terms of the three metrics above. And, for all of the above, when we are zoomed more into the picture, it takes longer to compute the sampling, requires more memory due to the high computation power, but results in a higher quality texture image.
|
|
|
|
|
|