Project 1: Rasterizer
CS 184: Computer Graphics and Imaging, Spring 2019
Andrew Campbell, cs184-adu
Overview
In this project, I implemented rasterization and other features for a simple vector graphics renderer. At a high-level, the program converts an image described in a vector format (in this case, points, lines, and triangles) into a pixel grid for a computer display. The program takes in modified SVG (Scalable Vector Graphics) files and renders them in an interactive viewer with support for antialiasing via supersampling, hierarchical transforms, and texture mapping, including different pixel sampling and level sampling options.
This project gave me insight into how vector graphics work; practical ways of implementing antialiasing; a useful new coordinate system for trinagles; and how to realistically render textures at different distances. I have a greater grasp on how computers convert from models to pixels and the practical implementation details of the methods discussed in lecture.
Section I: Rasterization
Part 1: Rasterizing single-color triangles
Nearly any complex structure can be represented as a mesh of triangles. As the simplest polygon, they have many useful properties which make them the cornerstone of the rendering process.
Triangle rasterization is the fundamental process of converting a geometric triangle construct into framebuffer pixel values. The process is as follows: compute a bounding box containing the three triangle vertices; loop over pixel coordinates within the bounding box; check if the coordinates lies within the triangle, and if so, fill the framebuffer with the appropriate color.
In the above graphic, each cell in the grid represents a single pixel on a display. We “sample” a point (x, y) located at the center of the pixel and perform the check inside(tri, x, y) as described in lecture; the idea is to check if a point lies on the same side of all three half planes as determined by the three edges.
The core of the algorithm is implemented in the DrawRend::rasterize_triangle function. I dealt with edge cases by simply relaxing the > constraint to >= in the line equation. I used the simplistic approach of computing the bounding box based on the minimum and maximum x and y values of the triangle vertices and simply iterating over every value in a double for loop. I noticed the program would get very slow when zoomed in - I fixed this by exiting the loops early if any of the values went out of bounds of the width or height of the view (basically, don’t test what won’t be displayed).
The above screenshots show the rasterization of illustration/06_sphere.svg (left) and basic/test4.svg (right). Notice the jagged edges of the green triangle as shown in the pixel inspector; this issue will be addressed in the following section.
Part 2: Antialiasing triangles
The “jaggies” seen above are artifacts from aliasing. The display window does not have enough resolution to portray a smooth line.
Supersampling is a technique for anti-aliasing. The idea is to take color samples at several locations inside the pixel (not just at the center) in order to calculate an average color value. The end result is an image with smoother edge transitions since it is effectively a down-sampled version of a higher-resolution image.
To implement supersampling, I simply looped over the additional sqrt(sample_rate) sample points per side within each pixel - then averaged the resulting colors in get_pixel_color().
Below we see basic/test4.svg with sample rates of 1, 4, and 16. Notice that the skinny tip of the red triangle gets smoothed out at higher sample rates. This occurs the averaged subpixel values contain more information about the true image than if the sampling had been performed at display resolution.
Sample rate: 1
Sample rate: 4
Sample rate: 16
In the standard sample rate of 1, we see the aliasing effect from high frequency components - the edges of a triangle meeting at a small angle. With a sample rate of 4, we see a noticeable improvement in that pixels that are partially covered by the triangle are partially colored the triangle's color. A sample rate of 16 gives an even smoother transition, effectively eliminating the jaggies.
Part 3: Transforms
I implemented translation, scaling, and rotation matrices to support basic geometric transforms on polygons. The 2D transformation matrix formulas (for homogeneous coordinates) are shown below.
I ran into some trouble before realizing that I needed to convert degrees to radians.
Using some basic transforms, I made the stiff robot svg (left) have wavy arms (right). To achieve this, I added rotations to the individual limbs and minor translations.
Section II: Sampling
Part 4: Barycentric coordinates
Barycentric coordinates are a convienient and useful coordinate system for use with triangle rasterization. The idea is to represent points as linear combinations of the three vertices of a triangle.
The parameters uniquely indicate the barycentric coordinates of the point with respect to the triangle. This coordinate system is particularly useful for linear interpolation of values at vertices, such as color, texture coordinates, etc. I used the closed-form solution as given in lecture to solve for the barycentric coordinates.
Below is a screenshot of basic/test7.svg demonstrating the linear interpolation of color values using barycentric coordinates. Using barycentric coordinates, each point is a weighted average of the three vertices of the triangle, resulting in a smooth transition of interpolated colors when moving from vertex to vertex and within the triangles.
Part 5: “Pixel sampling” for texture mapping
The idea behind texture mapping is to give surface detail to objects. We map a 2D texture image onto a piece of geometry. Pixels of the texture are called texels, in the range , and are refferred to as coordinates.
In texture mapping, the vertices of a triangle are manually assigned coordinates. Using barycentric coordinates, we can easily interpolate to any texture coordinate inside the triangle. This brings up the need for “pixel sampling”, or acquiring the right texture pixel for a (possibly floating point) coordinate.
For nearest neighbor sampling, I simply rounded the coordinates to the nearest integers and retrieved the corresponding texel. For bilinear sampling, I calculated a weighted average of the four nearest texels.
The graphic below shows the mathematical implementaion of bilinear filtering.
Shown below are screenshots comparing nearest sampling and bilinear sampling for a graphic using the globe as texture.
The top left and top right show nearest sampling at 1 sample per pixel and 16 samples per pixel, respectively. The bottom left and bottom right show bilinear sampling at 1 sample per pixel and 16 samples per pixel, respectively.
While both methods benefit from a higher sampling rate, we see that bilinear sampling results in a more antialiased image for the same sampling rate. The latitude and longitude lines are smoothed over and averaged, reducing the jaggedness. At a sample rate of 16, the improvement from nearest sampling is less pronounced since the higher sampling rate compensates for the minifixied texels, but there is still some improvment. In general, bilinear interpolation is most noticeable for texture minification (i.e. the screen pixel samples are taken at a lower rate compared to that of the texels). This is because the texels effectively have higher frequency when minified, and the averaging nature of bilinear sampling helps smooth the edges. However, due to the extra computational cost of bilinear interpolation, nearest sampling can be preferable in some contexts.
Part 6: “Level sampling” with mipmaps for texture mapping
Aliasing artifacts can result from sampling high-resolution textures on objects far from the camera. At the same time, low-resolution textures result in too few details. Level sampling aims to solve this problem by using different levels of detail according to the distance between object and viewpoint.
A mipmap is an image pyramid consisting of levels of progressively lower resolution representations of the same image. A high-resolution mipmap image is used for objects close to the camera while lower-resolution images are used for objects that appears farther away.
To get the correct mipmap level, I estimated and as the difference between the coordinates corresponding to points and , and respectively. Upon scaling them up to the appropriate texture dimensions, I proceeded by following the mipmap level formula as shown below.
The L_ZERO sample method simply uses level 0, or the highest resolution texture image for sampling. The L_NEAREST method rounds the computed to the nearest integer. The L_LINEAR method performs a linear interpolation between the result of sampling at the level and level. Note that either pixel sampling method (i.e. nearest or bilinear) can be used at any level sampling method.
The renderer can now support different pixel sampling methods, level sampling methods, and sampling rates. Bilinear sampling and nearest sampling have the same memory cost, but bilinear sampling is slower. It will, however, produce stronger antialiasing for highly magnified textures.
L_NEAREST and L_LINEAR level sampling methods require a modest amount of additional memory (to store the lower-resolution texture images) and require the cost of calculating the mipmap level. However, both methods can potenially be faster than L_ZERO sampling because it is faster to take a constant number of samples from the appropriately downfiltered textures. L_ZERO sampling can result in aliased textures for far-away objects; L_LINEAR sampling solves this problem and provides smooth transitions between mipmap levels.
In general, increasing the sample rate by a factor of increases the memory and time complexity of rasterization by . It does, however result in antialiased edges at all zoom levels.
Below we compare different level and pixel sampling methods for a warped image using the School of Athens as texture.
L_ZERO + P_NEAREST (left) and L_ZERO + P_BILINEAR (right).
L_NEAREST + P_NEAREST (left) and L_NEAREST + P_BILINEAR (right).
L_LINEAR + P_NEAREST (left) and L_LINEAR + P_BILINEAR (right).
Section III: Art Competition
To create the above image, I took a still from WALL-E (the best Pixar movie) and plugged into Geometrize to reconstruct it out of triangles. The result used 1,221 triangles. I exported it as a SVG file and manually modified the format to be compatible with the draw program (e.g. removing opacities and non-supported polygons). Then I added code in svgparser.cpp to parse the rgb format of the colors in the SVG file.
Unless otherwise indicated, all the visual aids in this report come from the CS184 Spring 2019 lecture slides.