Assignment 1: Drawing to the Screen

Cecilia Zhang

In this assignment, we implemented rasterizer that allows us to draw on a screen, basically by firing up pixels with calculated pixel values. We started with basic point and line drawing, then moved to color and texture mapping. Different sampling schemes were explored and compared against each other, and anti-aliasing was also shown to be alleviated using super sampling. Nearest neighbor, bilinear and trilinear sampling were considered when for texture mapping.

Part 1: Rasterizing Lines

Line rasterizing is implemented in this section using Bresenham's algorithm. The algorithm describes which pixels to fire up in order to approximate a line segment. Basically we move one step (pixel unit) each time along x or y axis, and using the slope of the line to draw the pixel along the other axis. The basic algorithm works for one of the eight octant in the x-y coordinate space, and thus we need to consider the other seven cases to have a complete line rasterizer.

First, since we need the slope of the line, we need to consider the case when the slope doesn't exist, or when the line is a vertical line.

Second, we need to determine which axis we want to move along. This depends on the bigger change between x and y dimension for the starting and ending points of the line segment. At the beginning of my line rasterizer, I compared Δx and Δy . Once we have one case implemented, same codes could be used by simply swapping x and y coordinates for the other case. Instead of considering 8 different senarios, now we can only consider for 4.

Third, we have to decide whether to increase or decrease the step we move along, and this depends on the order of starting and ending points, as well as the slope of the line. But similar to the second point described in the last paragraph, we could use a unified code by swapping the order of the two points and then follow a simpler configuration (This simplifies the senarios from 4 to 2). We need to consider the remaining 2 conditions. For example, if we fix our procedure by steping incrementally along the x axis, there are still two cases when the slope of the line is either postive or negative. Thus we need to explicitely code for two conditions.

Below is the screen shot from my line rasterizer,

screen shot of a rasterized line

Part 2: Rasterizing single-color triangles

Triangle rasterizer is implemented in the section using two methods for computation time comparison. First approach is using a naive bounding box with three line test, in which I calculated the minimum and maximum of x and y coordinate values for the three vertices. Only points inside this pre-defined bounding box would be iterated through. Then for each sample point, I used the three line test algorithm to determine whether the point is inside, outside or on the edge of the triangle.

With this method, I struggled for a bit not being able to render the other half of the symmetric flower shape svg file. Then I realized that I didn't consider the counterclock-wise requirement for the ordering of triangle vertices. The ordering is important in that we would compute the normal of each edge and do cross product with each sample point, and the normal orientation is related to whether we are moving clock-wise or counterclock-wise. But we need to at the same time keep the matching between screen and texture vertices, otherwise wrong texel value would be assigned to the screen vertices. A point is considered inside a triangle if it passes all three line test, or fails all three line tests.

The second approach I implemented was dividing the triangle into upper and lower flat triangles (shown below), and render each two using my line rasterizer (by filling a flat triangle with horizontal lines). The downside of the algorithm is the necessity of finding the ordering of the triangle vertices in order to make a division. But the afterwards operations of line filling are cheaper than the point iteration used in the three line test algorithm. I clocked the time as specified in the instruction and got a 3X time faster.

illustration of the speedup implementation of triangle rasterization

A table with averaged time (averaged over five trials for each case) is shown below:

test3:triangles

test4:cube

naive implementation

8.778000 ms

2.752000 ms

speedup implementation

30.229000 ms

13.651000 ms

Below is the screen shot from my line rasterizer,

screen shot of rasterized triangles

From the figure above, we could see gaps at thin edges. This is caused by having too small triangles in between sampled pixels that no sample lies inside the triangle. These problems could be alleviated using super sampling, as described in the next section.

Part 3: Antialiasing triangles

Antialiasing is implemented by super sampling. The key idea is to sample more points within each pixel on the screen so that finer edges and features of images could be rendered. This is equivalent as sampling a signal at a higher sampling rate, being able to capture more high frequency information.

I implemented the method by creating a superbuffer that is sample_rate times larger than the original framebuffer. At the resolve() step, for each pixel, all the super sampled points are summed up and averaged by dividing the total number of super sampled points inside the pixel.

I created a method:

 void DrawRend::rasterize_sample( float x, float y, float xx, float yy, Color color ) 
in which xx and yy are the super sample's coordinates, and the augmented super sample buffer is used in this method.

I also created a method:

 void DrawRend::rasterizePointAnti( float x, float y, Color color) 
which is used for rasterizing line. This method replaces the call to the original
 DrawRend::rasterize_point( float x, float y, Color color ) 
method. Then line rasterizer would also use super sample buffer so that it wouldn't be affected by the resolve() function called in redraw.

I got a bit struggled here when calling

 memset 
to create the super sample buffer, not aware of the necessity to resize the buffer whenever we change the
 sample_rate. 

Part 4: Transforms

Three transformation matrices are implemented here: translate, scale and rotate. All three matrices are in homogeneous coordinates, and are shown below.

[1 0 dx
0 1 dy
0 0 1]
[sx 0 0
0 sy 0
0 0 1]
[cos(θ) -sin(θ) 0
sin(θ) cos(θ) 0
0 0 1]

I created a new svg file that draws some stars as individual elements, and also some Chinese lanterns as groups (since it's Chinese New Year this week). Stars are drawn using the basic star element, while the anterns is drawn as a group consisting a line, two rectangles and one polygon. The first svg file is the reference one, and I modified the other three using transformation matrix stacks for the lantern groups for demonstration. I first show the four screenshots for the four svg files, and then I will explain what I did to create each of the variations.

For the variation shown in the second screenshot, I used a transformation stack of translation and scaling. I applied scaling first and then translation. The ordering of the transformation matters, as shown in the below illustration. The green lattern is by applying scaling then translation, while the blue lattern is by applying translation first and then scaling. Notice that all three transformation matrices are relative to the (0, 0) coordinate, so that a scaling also automatically leads to translation. Thus the change of matrix ordering will change the resulting location of the objects.

ordering of scaling and translation

As for the variation applied shown in the third screenshot, I used a transformation stack of translation and rotation. The rotation is also relative to the (0, 0) origin, and thus there is also a slight difference using different transformation hierarchy.

ordering of rotation and translation

Lastly I experimented with rotation and scaling and rotation. When the scaling along different dimensions is the same, scaling and rotation ordering doesn't matter, but when the scale changes along different dimensions are different, as shown below, the ordering matters. All these could be verified using the matrix multiplications. If we find A*B and B*A, then the ordering of transformation doesn't matter, and vice versa.

ordering of rotation and scaling

Describe what you did in Part 4. Show your result here. Explain any bugs you had to work through, with pictures if possible. Describe the new svg file you created, and show the rasterized result. Explain the reasoning behind your use of the transform stack in your new file. If you added any extra features to the GUI, describe them, and depict the result if it is visualizable (e.g. if you add rotation controls).

For an extra part, I add a feature to the GUI, by using spare keys 'R' and 'G' to rotate the viewport clock-wise or counterclock-wise by a fixed degree (I set to 10). Screenshots are shown below for illustration:

press key 'R' to rotate viewport clockwise
press key 'G' to rotate viewport counterclockwise

Part 5: Barycentric coordinates

Barycentric coordinates allows us to express a point as a weighted average of the vertices of the triangles. It's useful in the following two ways: 1. determining whether a point is inside the triangle, and 2. doing linear interpolation of the triangle. Basically, it's a coordinate system that describes the mass distribution of a triangle. So (1/3,1/3,1/3) in barycentric coordinates would mean the center of mass of the triangle.

To better explain the idea, I creatd a svg file that draws a single triangle with three vertices in red, blue and green, respectively. A screen shot of the svg file is attached below. In this case, barycentric coordinate helps interpolate the color values. Areas closer to the vertices contain color that is closer to that of certain vertices. While the more towards the center of mass of the triangle, weights for three colors are more similar and thus the darker and more gray is shown.

barycentric coordinates for a single triangle
barycentric coordinates for color mapping

Part 6: Pixel sampling for texture mapping

Texture mapping is to find the correspondence between pixels and texels. Similar with last part where we use barycentric coordinate to calculate per sample color value, for texture mapping, we use barycentric coordinate to calculate per sample texture value. The optimal case is a one-to-one mapping between texel and pixel. However, magnification(texel covers more pixels) and minification(pixel includes more texels) happen more often. Two sampling schemes were explored in this part: nearest-pixel sampling and bilinear sampling. Nearest neighbor sampling is easier to implement and requires little computation, but causes more artifacts such as texture missing or gapping. Bilinear sampling requires more computation as it considers all four surrounding neighboring values, but results in more accurate texture mapping when magnification and minification happen.

To demonstrate the advantage of using bilinear sampling over nearest pixel sampling, we want the texture to be magnified in the rendered image. Thus we want to zoom out the screen space a bit. As shown below, when sampling rate = 1, nearest pixel sampling causes some latitude lines missing in the rendered image. Since only the nearest texel is considered, some pixels may miss the texel they are supposed to be mapped to. Using bilinear under the same situation results in a better texture mapping, the texture seems more blurred though.

Supersampling alleviates the antialiasing problem, but in a computation-costly way. It took almost 10x times slower with sampling rate = 16 than without supersampling. Under supersampling, we can still observe an enhancement of bilinear samping over nearest pixel sampling. Nearest pixel sampling appears more blurred at thin edges than using bilinear sampling.

Nearest pixel sampling with sampling rate = 1
Bilinear sampling with sampling rate = 1
Nearest pixel sampling with sampling rate = 16
Bilinear sampling with sampling rate = 16

Part 7: Level sampling with mipmaps for texture mapping

As different mappings between screen pixel and texture texel may be needed for a single rendering (especially when there is perspective/depth information in an image), we use a pyramid-like mipmap hierarchy for more accurate texture mapping. Mipmap stores texture map at different downsampled scales. The level of texture to be mapped is determined by the distance between neighboring pixels under texture coordinate (uv coordinate). If neighboring screen pixels are mapped to distant texture coordinate, that means the screen mesh is rather coarse that it doesn't need very fine texture, so that we use a downsampled version of texture map. On the other hand, if close screen pixels have close texture coordinates, then we may stick to the original texture map resolution. Mipmap leads to another sampling scheme: trilinear sampling that considers a 3D-sense neighboring values. Both the mipmap level above and below are considered in calculation of the texel value for a screen sample.

I spent some time searching for an png file to effectively illustrate the sampling differences. An effective example would be an image with thin edges or very fine patterns. I chose an 'extreme' case of an image cosisting only with thin curves. Another consideration is the resolution of the image. With known screen resolution, a high res image would demonstrate the effectiveness of using mipmap. By zooming out the rendered image, we are able to inspect the advantage of certain sampling schemes over the others.

L_ZERO with P_NEAREST
L_ZERO with P_BILINEAR
Nearest neighbor sampling performs worth than bilinear sampling as it ignores the neighboring values. When the rendered image is zoomed out, lower resolution of texture is needed to alleviate antialiasing. Thus from the figures shown below, we are able to observe an improvemennt using multi-scale mipmap texture sampling scheme. The best result is when we use both mipmap and bilinear sampling.
L_NEAREST with P_NEAREST
L_NEAREST with P_BILINEAR

Part 8: My drawing

In this part I wrote a small program that triangulates an input png image file. I first implemented a prototype using MATLAB, based on delaunay triangulation algorithm along with the following step:

I wrote a svg file generator that contains screen pixel vertices got from the above program, and the uvs coordinates are the normalized vertices. The generated svg file is passed to the rasterizer Below are some results I got from the above simplified triangulation algorithm. I put pairs of images side by side. The left are original png images, and the right are rendered triangulated images.

original png-->lollipop
Triangulated png-->tri-lollipop
original png-->cupcake
Triangulated png-->tri-cupcake
original png-->icecream
Triangulated png-->tri-icecream
original png-->cake
Triangulated png-->tri-cake