Filled Triangles

In the previous chapter, we took our first steps toward drawing simple shapes—namely, straight line segments—using only PutPixel and an algorithm based on simple math. In this chapter, we’ll reuse some of the math to draw something more interesting: a filled triangle.

Drawing Wireframe Triangles

We can use the DrawLine method to draw the outline of a triangle:

DrawWireframeTriangle (P0, P1, P2, color) {
    DrawLine(P0, P1, color);
    DrawLine(P1, P2, color);
    DrawLine(P2, P0, color);
}

This kind of outline is called a wireframe, because it looks like a triangle made of wires, as you can see in Figure 7-1.

This is a promising start! Next we’ll explore how to fill that triangle with a color.

Drawing Filled Triangles

We want to draw a triangle filled with a color of our choice. As is often the case in computer graphics, there’s more than one way to approach this problem. We’ll draw filled triangles by thinking of them as a collection of horizontal line segments that look like a triangle when drawn together. Figure 7-2 shows what one such triangle would look like if we could see the individual segments.

The following is a very rough first approximation of what we want to do:

for each horizontal line y between the triangle's top and bottom
    compute x_left and x_right for this y
    DrawLine(x_left, y, x_right, y)

Let’s start with “between the triangle’s top and bottom.” A triangle is defined by its three vertices \(P_0\), \(P_1\), and \(P_2\). If we sort these points by increasing value of \(y\), such that \(y_0 \le y_1 \le y_2\), then the range of values of \(y\) occupied by the triangle is \([y_0, y_2]\):

if y1 < y0 { swap(P1, P0) }
if y2 < y0 { swap(P2, P0) }
if y2 < y1 { swap(P2, P1) }

Sorting the vertices this way makes things easier: after doing this, we can always assume \(P_0\) is the lowest point of the triangle and \(P_2\) is the highest, so we won’t have to deal with every possible ordering.

Next we have to compute the x_left and x_right arrays. This is slightly tricky, because the triangle has three sides, not two. However, considering only the values of \(y\), we always have a “tall” side from \(P_0\) to \(P_2\), and two “short” sides from \(P_0\) to \(P_1\) and \(P_1\) to \(P_2\).

There’s a special case when \(y_0 = y_1\) or \(y_1 = y_2\)—that is, when one of the sides of the triangle is horizontal. When this happens, the two other sides have the same height, so either could be considered the “tall” side. Should we choose the right side or the left side? Fortunately, it doesn’t matter; the algorithm will support both left-to-right and right-to-left horizontal lines, so we can stick to our definition that the “tall” side is the one from \(P_0\) to \(P_2\).

The values for x_right will come either from the tall side or from joining the short sides; the values for x_left will come from the other set. We’ll start by computing the values of \(x\) for the three sides. Since we’ll be drawing horizontal segments, we want exactly one value of \(x\) for each value of \(y\); this means we can compute these values by using Interpolate, with \(y\) as the independent variable and \(x\) as the dependent variable:

x01 = Interpolate(y0, x0, y1, x1)
x12 = Interpolate(y1, x1, y2, x2)
x02 = Interpolate(y0, x0, y2, x2)

The \(x\) values for one of the sides are in x02; the values for the other side come from the concatenation of x01 and x12. Note that there’s a repeated value in x01 and x12: the \(x\) value for \(y_1\) is both the last value of x01 and the

first value of x12. We just need to get rid of one of them (we arbitrarily choose the last value of x01), and then concatenate the arrays:

remove_last(x01)
x012 = x01 + x12

We finally have x02 and x012, and we need to determine which is x_left and which is x_right. To do this, we can choose any horizontal line (for example, the middle one) and compare its \(x\) values in x02 and x012: if the \(x\) value in x02 is smaller than the one in x012, then we know x02 must be x_left; otherwise, it must be x_right.

m = floor(x02.length / 2)
if x02[m] < x012[m] {
    x_left = x02
    x_right = x012
} else {
    x_left = x012
    x_right = x02
}

Now we have all the data we need to draw the horizontal segments. We could use DrawLine for this. However, DrawLine is a very generic function, and in this case we’re always drawing horizontal, left-to-right lines, so it’s more efficient to use a simple for loop. This also gives us more “control” over every pixel we draw, which will be especially useful in the following chapters.

Listing 7-1 has the completed DrawFilledTriangle.

DrawFilledTriangle (P0, P1, P2, color) {
   ❶// Sort the points so that y0 <= y1 <= y2
    if y1 < y0 { swap(P1, P0) }
    if y2 < y0 { swap(P2, P0) }
    if y2 < y1 { swap(P2, P1) }

   ❷// Compute the x coordinates of the triangle edges
    x01 = Interpolate(y0, x0, y1, x1)
    x12 = Interpolate(y1, x1, y2, x2)
    x02 = Interpolate(y0, x0, y2, x2)

   ❸// Concatenate the short sides
    remove_last(x01)
    x012 = x01 + x12

   ❹// Determine which is left and which is right
    m = floor(x012.length / 2)
    if x02[m] < x012[m] {
        x_left = x02
        x_right = x012
    } else {
        x_left = x012
        x_right = x02
    }

   ❺// Draw the horizontal segments
    for y = y0 to y2 {
        for x = x_left[y - y0] to x_right[y - y0] {
            canvas.PutPixel(x, y, color)
        }
    }
}

Let’s see what’s going on here. The function receives the three vertices of the triangle as arguments, in any order. Our algorithm needs them to be in bottom-to-top order, so we sort them that way ❶. Next, we compute the x values for each y value of the three sides ❷, and concatenate the arrays from the two “short” sides ❸. Then we figure out which is x_left and which is x_right ❹. Finally, for each horizontal segment between the top and the bottom of the triangle, we get its left and right x coordinates, and draw the segment pixel by pixel ❺.

Figure 7-3 shows the results; for verification purposes, we call DrawFilledTriangle and then DrawWireframeTriangle with the same coordinates but different colors. Verify your results whenever you can—this is a very effective way to find bugs in the code!

Source code and live demo >>

You may notice the black outline of the triangle doesn’t exactly match the green interior region; this is especially visible in the lower-right edge of the triangle. This is because DrawLine is computing \(y = f(x)\) for that edge but DrawTriangle is computing \(x = f(y)\), and this can produce slightly different results due to rounding. This is the kind of approximation error we’re willing to accept in order to make our rendering algorithms fast.

Summary

In this chapter, we’ve developed an algorithm to draw a filled triangle on the canvas. This is a step up from drawing line segments. We’ve also learned to think of triangles as a set of horizontal segments that we can work with individually.

In the next chapter, we’ll extend the math and the algorithm to draw a triangle filled with a color gradient; the math and the reasoning behind the algorithm will be key to the rest of the features developed in this book.