# 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.

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.