Overview
In this project, we try to draw triangle-composited shapes and images on display by sampling points. To produce images with less aliases, e.g. jaggies, we introduce supersampling, which samples more points for 1 display pixel. We will also introduce matrix transformation and barycentric coordinates, which are used to calculate colors and positions of shapes. Finally, we will look into how to map a texture image into a shape, and how to improve the texture mapping result using mipmap.
Section I: Rasterization
Part 1: Rasterizing single-color triangles
To rasterize a single-color triangle with given color, we first come up with a naive algorithm. For the naive algorithm, we find the top-left corner point which has minimum x and minimum y, and the bottom-right point which has maximum x and maximum y. We can base on those two points draw a rectangle (bounding box) and they are the top-left point and bottom-right correspond. We know the triangle must in this rectangle so we use the point-in-triangle tests to check if the center of each pixel (\(x+0.5, y+0.5\)) is in the triangle.
Below is an example of basic rasterization of triangles.
EC: improved algorithm
We find a faster approach, which finds the leftmost vertex of the triangle and 2 edges passed that vertex. Then we divide the triangle into top and bottom 2 parts by a horizontal line passing the leftmost vertex. For the top sub-triangle, we fill it row by row from y of the leftmost vertex to y of the topmost vertex. In every row, we fill the subtriangle from the corresponding edge to right until pixel is outside the triangle. Similarly, we fill the bottom sub-triangle. This method works better than naive method, which checks all pixels within the bounding box of the triangle, because we start checking fromn edge and stop checking as long as we start to exit the triangle, so we don't check most empty space.
Below is a speed comparsion between naive algorithm and improved algorithm. At most cases, imrpoved algorthim performs better.
| Naive | Improved | |
|---|---|---|
| basic/test3.svg | 1037 (0.001037 seconds) | 925 (0.000925 seconds) |
| basic/test4.svg | 674 (0.000674 seconds) | 644 (0.000644 seconds) |
| basic/test5.svg | 2089 (0.002089 seconds) | 2771 (0.002771 seconds) |
| basic/test6.svg | 1179 (0.001179 seconds) | 1093 (0.001093 seconds) |
However, there is a problem with imrpoved algorthim. When we enlarge the image and the leftmost vertex is outside the display window, the triangle can not be corrected resterized. That's because the first samples checked on some rows are outside the range, so the rest of the samples in the same row are not checked anymore, even through they are in the triangle.
Part 2: Antialiasing triangles
To do super sampling, instead of sampling 1 point for every pixel to display, we sample n(sample size) points by dividing the pixel into \(\sqrt{n}*\sqrt{n}\) "sub-pixels" and get the value for the pixel by averaging values of the "sub-pixels". It means instead of sampling by difference 1, sampling by difference \(\frac{1}{\sqrt{n}}\). All the values of "sub-samples" are stored in a 1-D sample buffer in order (from top to bottom, from left to right), and values of pixels are stored in a 1-D rgb frame buffer.
Supersampling is a useful anti-aliasing technique, because edge pixels rasterized in this way will have color depth propotional to the amount of the original triangle in that pixel, which reduce jaggies.
In the example below, we use 3 different sample size to rasterize triangles, and we can see clear difference especially on the skinny triangle. When sample size is 1, only the center of the pixel is sampled to determine if it's inside the triangle, and it's possible for the samples at the tip pixels to be in the triangle but not the pixels more far away from the tip in the direction towards the center of the triangle. When sample size increases to 4, more points are sampled inside every pixel instead of just 1, so the color is more continuous and connected. When sample size increases to 16, the color is even more continous and smoother, because more points are sampled and the average value is more precisely proportional to the position.
| sample size: 1 | sample size: 4 | sample size: 16 |
|---|---|---|
 |
 |
 |
Part 3: Transforms
The cubeman below is trying to catch a bus. it is running and waving its hands: two legs are rotated so that it looks like the cubeman is running, and the left arm is raising up and it shows the cubeman is waving its hands. We changed the color of every rectangles and modified position and angles of rotation of the rectangles. The rotation tag is added after the translate tag, so the block would rotate after we put it in to the correct position.
Section II: Sampling
Part 4: Barycentric coordinates
Barycentric coordinate \((\alpha, \beta, \gamma\)) is a 3-D cooridinate system with a base consisting 3 vertices of a triangle \((V_A, V_B, V_C\)), and it represents the relative distance of the point to the given 3 vertices. For a point inside the triangle, every value of \(\alpha, \beta, \gamma\) is the fraction of distance from the point to corresponding vertex to the height from the vertex, which is between 0 and 1. \[\alpha = \frac{-(x-x_B)(y_C-y_B)+(y-y_B)(x_C-x_B)}{-(x_A-x_B)(y_C-y_B)+(y_A-y_B)(x_C-x_B)}\] \[\beta = \frac{-(x-x_C)(y_A-y_C)+(y-y_C)(x_A-x_C)}{-(x_B-x_C)(y_A-y_C)+(y_B-y_C)(x_A-x_C)}\] \[\gamma = 1-\alpha-\beta \] Barycentric coordinate is used to estimate an attribute at a point according to the same attributes at 3 triangle vertices. \[V=\alpha V_A +\beta V_B +\gamma V_C \] The attribute values (V for the point, \(V_A, V_B, V_C\) for vertices) can be color, posistion, material attributes...
| calculate \(\alpha, \beta, \gamma\) | calculate attribute V |
|---|---|
 |
 |
Below is an example of a color wheel. The wheel is devided into small skinny triangles, and colors of points in triangles are calculated using barycentric coordinates based on preset colors at triangle vertices.
Part 5: "Pixel sampling" for texture mapping
Sampling for texture mapping is silimar to the sampling described in part 1 and part2, and the only difference is the color we assigned to every pixel. For every pixel on display, if the center of the pixel is in a specific triangle, instead of assign a specific color to that pixel, we will map a corresponding point in a texture image to that pixel. Given 3 pairs of correponding triangle vertices on display and texture image, we can use barycentric coordinate to find corresponding point on texture image of every point in the triangle on display.
There are 2 ways to sample the color of corresponding point in texture image: nearest sampling and bilinear sampling. For nearest sampling, we pick the color of pixel in texture image closest to the point (\(u_{11}\) in this example). For bilinear sampling, instead of using color of a specific color, we adjust the color by averaging colors of 4 pixels closest to the points with weight being the distances from these pixels to the point. We get the weighted color on nearest points which have the same x as the point but have integral y values above and below the point respectively (\(u_1\) and \(u_0\)), then we get the final weighted color of the point according to colors of the two points.
| Nearest Sampling | Bilinear Sampling |
|---|---|
 |
 |
Below are an example of texture mapping using different sampling methods and sample size. When sample size is 1, it's clear that bilinear sampling produces output which is smoother with less jaggies compared to nearest sampling. When sample size increases to 16, we can see the nearest sampling also produce a smoother output compared to nearest sampling with sample size 1, although it's still not as good as bilinear sampling. If we do bilinear sampling with sample size 16, the color change is smoother compared to bilinear sampling with sample size 1, but the difference between nearest and bilinear sampling at sampling size 16 is much smaller than difference at sample size 1.
Therefore, we conclude that larger the sampling size, smaller the difference between nearest sampling and bilinear sampling. The reason is that larger the sample size, more points are sampled on texture image. Although the color at every point is determined by only 1 pixel, points in 1 display pixel will be averaged to get the final color for the pixel, so the color change will be smoother. The principle of bilinear sampling is the same, which uses weighted average of nearby pixels. When sample size is large, the improvement using bilinear sampling will be small, because sampled points are very close to each other with close values, and weighted value of serveal close values won't change the result tremendously.
| Nearest Sampling with sample size 1 | Bilinear Sampling with sample size 1 |
|---|---|
 |
 |
| Nearest Sampling with sample size 16 | Bilinear Sampling with sample size 16 |
 |
 |
Part 6: "Level sampling" with mipmaps for texture mapping
Level sampling is sampling pixels in different level of mipmaps with different sizes according to the magnification of texture on display. Higher the level, smaller the texture image size. Level 0 represents the texture image at original size. In this way, we can reduce jaggies and make display clear. To implement level sampling for texture mapping, first, we calculate the level for sampling by finding barycentric coordinates of (x, y), (x+1,y), and (x,y+1), therefore corresponding points and derivatives in texture image. Finally, the level D is calculated from derivatives by following equation. D is rounded to nearest integer.
\[L = max(\sqrt{\frac{du}{dx}^2+\frac{dv}{dx}^2},\sqrt{\frac{du}{dy}^2+\frac{dv}{dy}^2})\] \[D = round(log_2{L})\]
We then find the corresponding color of (x, y) within the level D based on type of pixel sampling (Nearest & Bilinear) and type of level sampling (Zero level, Nearest level & Linear level) choosen by the user.
- If level sampling method is Zero level and pixel sampling method is Nearest, we call sample_nearest function on level 0.
- If level sampling method is Zero level and pixel sampling method is Bilinear, we call sample_bilinear function on level 0.
- If level sampling method is Nearest level and pixel sampling method is Nearest, we call sample_nearest on the level D.
- If level sampling method is Nearest level and pixel sampling method is Bilinear, we call sample_bilinear on the level D.
- If level sampling method is Linear level and pixel sampling method is Nearest, we get the weighted value of sample_nearest on level D and sample_nearest on level D', where D' is the second nearest integer to precise \(log_2{L}\), and the weights of the two values are corresponding difference between the level and precise value of \(log_2{L}\).
- If level sampling method is Linear level and pixel sampling method is Bilinear, we get the weighted value of sample_bilinear on level D and sample_bilinear on level D'.
There are tradeoffs between 3 level sampling methods.
- Zero level sampling takes least memory and running time, because no additional mipmap is needed. However, the antialiasing power is low without customizing the texture image.
- Nearest level sampling takes more memory and running time, because a mipmap at nearest level D is needed for every sampling point. The antialiasing power is greater than Zero level sampling, because mipmap at specified level will reduce aliasing effects.
- Linear level sampling takes most memory and running time, because 2 mipmaps at nearest level D is needed to calculate weighted value for every sampling point. The antialiasing power is also greatest, because the weighted average in 2 mipmaps will further reduce aliasing effects.
Below is an example using different level sampling and pixel sampling methods. We can see Nearest level sampling and Bilinear pixel sampling produces smoothest result, while Zero level sampling and Nearest pixel sampling produces roughest result.
L_ZERO and P_NEAREST  |
L_ZERO and P_LINEAR  |
L_NEAREST and P_NEAREST  |
L_NEAREST and P_LINEAR  |
Section III: Art Competition
Part 7: Draw something interesting!
Reusing the transformation from texture of campanile to display and svg file in test6, we try to produce some exaggerated funny faces of cartoon characters Spongebob and Patrick! To make sure a specific part of the face gets exaggerated, we try to place that part on corresponding center of enlargement in the input image.
| Original image 1 | Large heads! |
|---|---|
 |
 |
| Original image 2 | Large eyes & large mouth! |
 |
 |