Rasterization in One Weekend, Part I

Code for this part can be found here.

Hello, Triangle!

Mission statement: Given a set of three vertices which form a triangle, we want to rasterize the triangle onto our 2D screen.

Now how do we define those vertices? Two of the options are: raster(or pixel or screen)-space and normalized device coordinates space. In raster-space, vertex coordinates are defined in terms of actual screen resolution whereas NDC directly works with [-1, 1] range to simplify things; i.e. being independent from screen resolution and pixel density. Here’re the vertices of our first triangle:

```    // 2DH (x, y, w) coordinates of our triangle's vertices, in counter-clockwise order
glm::vec3 v0(-0.5, 0.5, 1.0);
glm::vec3 v1(0.5, 0.5, 1.0);
glm::vec3 v2(0.0, -0.5, 1.0);```

And now, we apply the viewport transformation such that vertices will be in screen-space before we rasterize them. Why do we even need this, you may ask. The reason is that you should always ensure not to mix values in different spaces in the same equations. This is sometimes tricky, because some values will magically work even if you are not careful about conversions, leading to the illusion that all the math is correct.

```// Apply viewport transformation
v0 = TO_RASTER(v0);
v1 = TO_RASTER(v1);
v2 = TO_RASTER(v2);```

Here’s the dumb macro to apply viewport transformation:

```// Transform a given vertex in NDC [-1,1] to raster-space [0, {w|h}]
#define TO_RASTER(v) glm::vec3((g_scWidth * (v.x + 1.0f) / 2), (g_scHeight * (v.y + 1.f) / 2), 1.0f)```

Next comes the part to set up a vertex matrix, which is a way of testing whether a given screen-space point is on our triangle or not:

```    // Base vertex matrix
glm::mat3 M =
{
{ v0.x, v1.x, v2.x},
{ v0.y, v1.y, v2.y},
{ v0.z, v1.z, v2.z},
};```

Wait, what? Why? It’s basically built upon the fact that all triangles can be defines as a weighted linear combination of their three vertices:

It follows that, alongside the three vertices we’re given, if we have three other values defined at each vertex, we can interpolate them at any point using the barycentric coordinates at a given pixel, granted that the point is inside our triangle. Now, that’s a really powerful property, but how do we find these three coefficients? What we’re trying to do here is basically to solve a system of linear equations:

Before we get into how we can solve such system, let’s clarify why we need them in the first place: They are the ingredients of one of the most fundamental equations in computer graphics, namely, edge functions.

An edge function, simply put, is a way of telling whether a point is to the left or right (or exactly on the edge) of a given edge. And how’s that useful? We have three edges and a point to test, which means that the point will be inside our triangle if and only if it’s to the same side of all three edges. The “same-sidedness” part is simply checking that each edge function has the same sign (depending on how you define your vertices’ winding order as +).

If what we just described was intuitive or makes sense a bit, let’s continue how we could get these findings to fit into our goal of solving the system of linear equations we’ve just set up above.

To solve the above-mentioned system of linear equations with 9 unknowns, we need 9 knowns. Utilizing edge functions we just set up, we can just do it! How, you say? Here’s how:

As you can probably hardly see (sorry for image quality!), each edge function will be constant and equal to 1 on one edge while it’ll be equal 0 on opposite edges. That’s three known values on each edge, which gives us the nice 9 known values we were after. Now, with our vertex matrix and interpolation constraints all set up, we are ready to solve the linear equations:

To compute alpha, beta and gamma for each vertex, we can now simply invert our vertex matrix on the left once per triangle and use these as edge equations. Note that (1, 0, 0), (0, 1, 0) and (0, 0, 1) values stem from edge functions being 1 on edge and 0 on the opposite ones.

```// Compute the inverse of vertex matrix to use it for setting up edge functions
M = inverse(M);

// Calculate edge functions based on the vertex matrix
glm::vec3 E0 = M * glm::vec3(1, 0, 0);
glm::vec3 E1 = M * glm::vec3(0, 1, 0);
glm::vec3 E2 = M * glm::vec3(0, 0, 1);```

And now the last part where we will simply walk along pixels in our frame buffer to check if they are inside our triangle and if so, output a color to see something resembling a triangle. I believe this is the least complicated part, let’s let the code speak:

```    // Start rasterizing by looping over pixels to output a per-pixel color
for (auto y = 0; y < g_scHeight; y++)
{
for (auto x = 0; x < g_scWidth; x++)
{
// Sample location at the center of each pixel
glm::vec3 sample = { x + 0.5f, y + 0.5f, 1.0f };

// Evaluate edge functions at every fragment
float alpha = glm::dot(E0, sample);
float beta = glm::dot(E1, sample);
float gamma = glm::dot(E2, sample);

// If sample is "inside" of all three half-spaces bounded by the three edges of our triangle, it's 'on' the triangle
if ((alpha >= 0.0f) && (beta >= 0.0f) && (gamma >= 0.0f))
{
frameBuffer[x + y * g_scWidth] = glm::vec3(1, 0, 0);
}
}
}```

If all went well, output of a single frame should be something like this:

And just like that, we completed our entree into the world of rasterization!  Stay tuned for Part II: Go 3D!, where we will have a little sense of 3D and depth.