Filled triangles

We can use the DrawLine method to draw the outline of a triangle. This kind of outline is called wireframe, because it looks like a triangle made of wires:

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

Here’s the result:

Can we fill the triangle with some color?

As usually happens in Computer Graphics, there are many ways to accomplish this. We’ll draw filled triangles by thinking of them as a collection of horizontal line segments that look like a triangle when drawn together. The following is a very rough first approximation of what we want to do:

for each horizontal line y occupied by the triangle
    compute x_left and x_right for this y
    DrawLine(x_left, y, x_right, y)

Let’s start with “each horizontal line occupied by the triangle”. A triangle is given 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) }

Then we have to compute x_left and x_right. This is slightly tricky, because the triangle has three sides, not two. However, in terms of values of \(y\), we always have a “long” side from \(P_0\) to \(P_2\), and two “short” sides from \(P_0\) to \(P_1\) and \(P_1\) to \(P_2\) 1. So the values for x_right will come either from the long side or from both short sides; and 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 will be drawing horizontal segments, we want exactly one value of \(x\) for each value of \(y\); this means we can get the values in a straightforward way with Interpolate, using \(y\) as the independent value and \(x\) as the dependent value:

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

x02 will be either x_left or x_right; the other one will be the concatenation of x01 and x12.

Note that there’s a repeated value in these two lists: 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.

remove_last(x01)
x012 = x01 + x12

Finally, we have x02 and x012, and we need to determine which is x_left and which is x_right. We do this by looking at the values of \(x\) for one of the lines, for example the middle one:

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

Now the only thing left is to draw the horizontal segments. For reasons that will become clearer later, we won’t use DrawLine for this; instead we’ll draw the pixels individually.

Here’s 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 = 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)
        }
    }
}

Here are the results; for verification purposes, we call DrawFilledTriangle and then DrawWireframeTriangle with the same coordinates but different colors:

Source code and live demo >>

You may notice the black outline of the triangle doesn’t match the green interior region exactly; 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)\). This is the kind of approximation we’re willing to pay in order to achieve high-performance rendering.

<< Lines · Shaded triangles >>
Computer Graphics from scratch · Introduction · Table of contents · Common concepts
Part I: Raytracing · Basic ray tracing · Light · Shadows · Reflection · Arbitrary camera · Beyond the basics · Raytracer pseudocode
Part II: Rasterization · Lines · Filled triangles · Shaded triangles · Perspective projection · Scene setup · Clipping · Hidden surface removal · Shading · Textures
Found an error? Everything is in Github.


  1. There’s a special case when \(y_0 = y_1\) or \(y_1 = y_2\), that is, when the triangle has a horizontal side; in these cases, there are two sides that can be considered the “long” side. Fortunately, it doesn’t matter which one we choose, so we’ll stick to that definition.