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)-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 raster-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 we’ll use for testing whether a given screen-space point is inside our triangle or not. 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 this! 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:

After initializing our base vertex matrix, to compute alpha, beta and gamma for each vertex, we will simply invert our vertex matrix (on leftmost)  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 one on edge and zero on the opposite ones.

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

// Compute the inverse of base 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.

Advertisements

One thought on “Rasterization in One Weekend, Part I

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s