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

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.

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