Rasterizer

Overview

This project is a simple rasterizer that can take SVG files and render them to the screen. It explores the issues one faces in rendering, such as performance and aliasing, and demonstrates a variety of anti-aliasing techniques that can display faithful representations of the desired image while maintaining high performance. The rasterizer includes support for hierarchical transforms, texture mapping, and anti-aliasing by supersampling, nearest-neighbor sampling, bilinear filtering, and trilinear filtering using mipmaps.

Section I: Rasterization

Rasterization is the process of taking image data represented as geometric shapes and converting it into a series of pixel data that can more directly represent the image on a display. We'll start with the most basic polygon, the triangle.

Part 1: Rasterizing single-color triangles

Triangles are a fundamental modeling primitive in computer graphics. They can be used to break up more complex polygons and easily interpolate desired image data like color.

A single-color triangle can be represented with 3 (x,y) coordinates and a color, typically in RGB format. Given the coordinates, we can run point-in-triangle tests on each pixel location to see whether the pixel belongs inside the triangle. If it does, we can set the pixel to the specified color to be displayed on the screen.

A simple but effective optimization is to not test every pixel on the screen, but rather just the pixels in the bounding box of the triangle. We can do this by getting the minimum and maximum x and y coordinates of the triangle and simply traversing the pixel grid bounded by those values.

With this naive implementation of sampling 1 point per pixel, we get the images below. Notice that the rendered triangles fall noticeably short of an accurate representation, which would ideally have fully connected triangles with smooth sides. This is a phenomenon known as aliasing.

triangles zoomed in — An example of aliasing where the rendered pixels don't properly connect the triangle.

Part 2: Anti-aliasing triangles

Anti-aliasing refers to the techniques used to decrease the inaccuracies or artifacts due to aliasing. One way to anti-alias our triangle renders is a technique called supersampling. In supersampling, we take multiple samples per pixel and then average them out to get the final pixel color value to display. Since a pixel may only partly overlap our ideal triangles, we can set the pixel to be an appropriate blend of the triangle color and background color. This way, we can smooth out the edges with a more gradual change of color at pixel resolution.

zoom 1 — Anti-aliased triangles rendered by supersampling 16 points per pixel. The "jaggies" on the triangle pixels have been smoothed out.

zoom 2 — Antialiasing via supersampling properly connects the triangle.

Part 3: Transforms

Given our basic shapes, we are able to compose them to form more complex objects. One example of this is to specify object positions relative to parent objects using hierarchical transforms. Doing it in this manner makes it easy to manipulate the object. For example, to make the robot do a lively gesture in the figures below, we only need to specify the movements of the upper arm or leg instead of directly specifying the movement of every object contained by the limbs.

Section II: Sampling

Part 4: Barycentric coordinates

Moving beyond single color triangles, we can make use of barycentric coordinates to interpolate data across triangle vertexes. The barycentric coordinate system allows us to assign weights to each vertex relative to a given position on the triangle.

For example, if we label our triangle vertexes A, B, and C with corresponding barycentric coordinates (a, b, c), the coordinate (1, 0, 0) would correspond to the exact point A with weight 1, while the other points B and C have weight 0. If we move to the "center" of the triangle, we'd have coordinates (1/3, 1/3, 1/3) with each triangle vertex A, B, and C weighted equally.

As we move around the triangle, we can appropriately weight the triangle vertex colors using barycentric coordinates to get a sensible color value at a given position, resulting in a smooth interpolation across the entire triangle.

interpolated triangle — Linear interpolation using barycentric coordinates, given a single color per triangle vertex.

A smoothly interpolated color wheel consisting of smoothly interpolated triangles.

Part 5: "Pixel sampling" for texture mapping

Part 6: "Level sampling" with mipmaps for texture mapping

campanile, texture-mapped with aliasing — Warped image using texture mapping.

mipmap level visualization 2 — Zoomed out.

mipmap level visualization 3 — Zoomed in.

Visualization of mipmap levels. The brighter, cyan colored areas use increasingly downsampled versions of the original texture. This matches our expectation that the enlarged corners require more detail than along the shrinking diagonal. As we zoom in and out, the levels change.

trilinear — Trilinear sampling with mipmaps.