Triangles often serve as the building block for computer graphics. We often use meshes of triangles as our building block for rasterization - the process of converting an image into pixels that can be displayed on a screen.

Why do we use triangles? They're the most basic polygon, they're guaranteed to planar, they have a well-defined interior, and they have a well-defined method for interpolating values at vertices over the triangle (barycentric interpolation).

Rasterization is the process of drawing a triangle to the frame buffer (a 2D array that represents our screen). To start our discussion of rasterization, let's consider what pixel values approximate a triangle.

Our goal is to transform a triangle, which can be defined as three vertices with X/Y coordinates, into values on a frame buffer (2D array) that represent the triangle. To do so, we start with a simple approach: sampling.

Our goal is to transform a triangle, which can be defined as three vertices with X/Y coordinates, into values on a frame buffer (2D array) that represent the triangle. To do so, we start with a simple approach: sampling.

Sampling is the process of evaluating a function at a point. We can convert a continuous signal into a discrete function using periodic sampling.

for (int x = 0; x < xmax; x++): output[x] = f(x)

In computer graphics, we'll sample time (1D), area (2D), volume (3D), and even N-dimensional or infinite-dimensional functions.

For now, let's consider sampling our continuous triangle function in an effort to draw it on our frame buffer. In this case, we define a binary function inside(t, x, y) that returns true if a point (x, y) is in the triangle, and false otherwise. Then, we can iterate through all (x, y) coordinate pairs and identify which pixels to activate. Note that for a particular coordinate, we can evaluate the continuous function using f(x + 0.5, y + 0.5) to consider the midpoint of the pixel.

We evaluate at every point in the 2D frame buffer.

We evaluate inside(tri, x, y) at every point in the 2D frame buffer.

Now, let's consider how we evaluate inside(tri, x, y). We can think of a triangle as the intersection of three half-planes, where each half plane is represented as a line equation and an inequality. Using this representation, we first identify how to define what side of a half-plane a point falls on; then, we use that to define what points lie inside a particular triangle.

We can define a line in the form of . To determine whether a point is above or below the line, we can evaluate the inequality directly.

We can define a line in the form of Ax + By + C = L(x, y). To determine whether a point is above or below the line, we can evaluate the inequality directly.

Here's another way to identify whether a point lies within a triangle, or, in this case, on a particular side of a half-plane. We can define a normal vector, , and a vector from a point on the line to the point . In this case, we apply our inequality comparisons to the dot product .

Here's another way to identify whether a point P lies within a triangle, or, in this case, on a particular side of a half-plane. We can define a normal vector, N, and a vector V from a point on the line to the point P. In this case, we apply our inequality comparisons to the dot product V • N.

To summarize our point-in-triangle test, we can define a function that evaluates the implicit line equation for each vertex (0, 1, 2) and ensures the sample point falls inside the triangle.

To summarize our point-in-triangle test, we can define a function inside(sx, sy) that evaluates the implicit line equation for each vertex (0, 1, 2) and ensures the sample point (sx, sy) falls inside the triangle.

Note that our method of evaluating has to consider edge cases. OpenGL and Direct3D classify a point as within a triangle if the edge that it falls on is a "top edge" or a "left edge."

Note that our method of evaluating inside(sx, sy) has to consider edge cases. OpenGL and Direct3D classify a point as within a triangle if the edge that it falls on is a "top edge" or a "left edge."

Now that we know how to rasterize a triangle by iterating through each point on the grid, let's consider alternative approaches.

Incremental triangle traversal is a method that starts at a vertex of the triangle, and proceeds in the direction of points that fall within the triangle. It may be faster...

Incremental triangle traversal is a method that starts at a vertex of the triangle, and proceeds in the direction of points that fall within the triangle. It may be faster...

Tiled triangle traversal (modern approach) uses parallelism on GPU's to perform the point-in-triangle test on a group of pixels at a time. This is typically much faster than incremental traversal.

Tiled triangle traversal (modern approach) uses parallelism on GPU's to perform the point-in-triangle test on a group of pixels at a time. This is typically much faster than incremental traversal.

When we send the display (via our frame buffer) our sampled triangle signal, we encounter a staircase-like phenomenon with our rendered image: jaggies. Intuitively, we could think about simply adding more pixels to create a smoother image - in other words, taking more samples & increasing the size of our frame buffer. This isn't usually the best approach, however, often due to physical limitations.

Jaggies are fundamentally caused by a finite sampling rate - we're taking a high-frequency image and sampling it at a lower frequency. We'll see how to counteract this in Note 3.

Jaggies are fundamentally caused by a finite sampling rate - we're taking a high-frequency image and sampling it at a lower frequency. We'll see how to counteract this in Note 3.