!!html_class cgfs !!html_title Filled Triangles - Computer Graphics from Scratch
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.
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.
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.
{#fig:filled_triangle_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
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
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
There's a special case when
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 Interpolate
, with
x01 = Interpolate(y0, x0, y1, x1)
x12 = Interpolate(y1, x1, y2, x2)
x02 = Interpolate(y0, x0, y2, x2)
The 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 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 x02
and x012
: if the 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!
{#fig:filled_triangle_with_edges}
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 DrawTriangle
is computing
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.