Tutorial - Introduction to Software-based Rendering: Triangle Rasterization
January 19, 2009
This article explains how to rasterize triangles. It contains sample C++ code and is accompanied by a demo program with full source code that uses SDL for display.
In our previous article, we implemented a function for drawing lines. This was adequate for drawing simple wireframes, such as the triangle consisting of three lines as displayed in the demo program, but now let's shift our attention to full triangle rasterization. This will enable us to draw fully shaded triangles with independent colors for each vertex. This is a bit more complicated than simple line drawing, but it will build on top of that knowledge.
There are basically three steps to triangle rasterization. First, let's break triangle drawing down into a few separate stages, as shown in the figures below (each figure represents a 20x20 grid of pixels):
The first figure shows the three points (represented by black dots) that are the three vertices of the triangle. The second figure shows the edges of the triangle; these are the three lines that connect the points and form an outline of the triangle. Last, we have the fully drawn triangle in the third figure, which is made up of horizontal lines of blue pixels that are within the boundaries of the triangle.
So the first step is to use the three points to determine the edges of the triangle. Next, we loop through the y axis boundaries of the triangle to calculate the horizontal spans that the triangle consists of; these are the horizontal lines that will form the triangle. Any row of pixels within the outline of the triangle is a span. Finally, we loop through the x axis boundaries of each span to draw each individual pixel.
Let's now dive into the code for doing all of this, starting with the first step: edge calculation.
First, we need a class to represent a single edge of a triangle. Here's the definition of the class:
This class contains color, x, and y values for the two points that an edge consists of. The only function is the constructor, which is shown below:
When we're looping through the y axis, we want to start with lower values and end with higher ones, so this constructor simply makes sure that the first point of the edge is the point with the lower y value of the two given.
Let's now take a look at the DrawTriangle() function of the Rasterizer class, which creates an array of edges from the three points given:
The first edge is from point one to point two, the second edge is from point two to point three, and the third edge is from point three to point one.
Let's refer back to the figures shown earlier in the article for a moment. Notice that one edge of the triangle (the vertical one on the left) spans the entire length of the triangle in the y axis, whereas the other two edges span roughly half of the length in the y axis. When we're drawing triangles, one edge will always have a length in the y axis greater than either of the other two edges (actually, it's possible that two edges have the same length in the y axis and the third has a 0 length, but our code will handle that situation as well); its length in the y axis will be the sum of the lengths of the other two edges.
The following bit of code is used to find the index of the tallest edge (the one with the greatest length in the y axis) in the edges array:
Next, we get the indices of the shorter edges, using the modulo operator to make sure that we stay within the bounds of the array:
Next, we pass the edges to the DrawSpansBetweenEdges() function, which will calculate the horizontal spans between two edges of the triangle and send them to another function for drawing indivudal spans; we call this function twice, passing in the tall edge along with each of the short edges, and the DrawTriangle() function is done:
As mentioned earlier, the tall edge's length in the y axis is the sum of the lengths in the y axis of the other two edges. Because the two short edges have different slopes, we take one short edge at a time to calculate the minimum/maximum x values of each span within the edge's boundaries. Let's now look at how we calculate the spans.
Just like we have a class to represent edges, we have one to represent spans. Here's the definition:
This is similar to the Edge class, but it has no y values because spans are always parallel to the x axis; the function for drawing a single span (shown later in the article) will take a single y value to draw at along with a span. The constructor of the Span class makes sure that the first point stored is the one with the lower x value:
Span calculation is performed by the DrawSpansBetweenEdges() function. This function first takes the differences between the y positions of the points for the given edges. If either of them is 0, there are no spans to render and the function simply returns:
Next, we also calculate the differences of the x positions and colors of the points for the given edges, as this will make it a little easier to interpolate x and color values for each span:
The last task before looping through each span is initializing factors for interpolating values between the two points of the given edges, and step values for increasing the factors each time the loop runs:
When this function is called, the first edge given must be the long edge and the second edge given must be one of the short ones. We're going to loop from the minimum y value of the second edge to the maximum y value of the second edge to calculate spans, since every span within the boundaries of the short edge will also be within the boundaries of the long edge. factor2 starts at 0 and is increased by factorStep2 until it reaches a value of 1 towards the end of the loop. factor1, however, may start with a value greater than 0 (if the long edge's starting y value is lower than the short edge's) or may end up at a value lower than 1 (if the long edge's ending y value is greater than the short edge's).
Here's the loop that calculates spans and passes them to the DrawSpan() function to draw them:
The x and color values for each span are interpolated from the first point of each edge to the second point, similarly to the line drawing function from our last tutorial. Once the loop finishes, the function is complete. Let's now take a look at the DrawSpan() function, which is where we draw each individual pixel of a span.
Span drawing is basically like drawing a one-dimensional line that exists only in the x axis. We loop from the minimum x value of the span to the maximum x value, interpolating the color and setting pixels along the way.
Here's how the DrawSpan() function starts. We calculate the differences between the starting/ending x/color values of the span and, if the x difference is 0, simply return because there are no pixels to draw:
Next, we initialize a factor for interpolating the color between the beginning and end of the span, and calculate a step value for incrementing the factor each time the loop runs:
Finally, we loop through each x position in the span and set pixels using the y value passed to this function and a calculated color value:
The function is finished, and with that, our triangle rasterization algorithm is complete. Here's a screenshot of the demo program: