<< Computer Graphics from scratch
<< 计算机图形学从无到有 pouei.com

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.
在上一章中，我们迈出了绘制简单图形的第一步--即直线段--仅使用 PutPixel 和基于简单数学的算法。在本章中，我们将重新使用一些数学知识来画一些更有趣的东西：一个填充的三角形。

Drawing Wireframe Triangles 绘制线框三角形

We can use the DrawLine method to draw the outline of a triangle:
我们可以用 DrawLine 的方法来画一个三角形的轮廓。

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.
这种轮廓被称为线框，因为它看起来像一个由线组成的三角形，正如你在图7-1中看到的。

Figure 7-1: A wireframe triangle with vertices (–200,–250), (200,50), and (20,250)
图7-1：一个具有顶点（-200,-250）、（200,50）和（20,250）的线框三角形。

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.
我们想画一个三角形，用我们选择的颜色填充。就像计算机图形学中经常出现的情况一样，有不止一种方法来处理这个问题。我们在画填充三角形时，可以把它们看作是一组水平线段的集合，这些线段画在一起时看起来像一个三角形。图7-2显示了一个这样的三角形，如果我们能看到各个线段的话，会是什么样子。

Figure 7-2: Drawing a filled triangle using horizontal segments
图7-2：用水平线段画一个填充的三角形

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} \leq y_{1} \leq y_{2}$ , then the range of values of $y$ occupied by the triangle is $[y_{0}, y_{2}]$ :
让我们从 "三角形的顶部和底部之间 "开始。一个三角形由它的三个顶点P 0 𝑃 0, P 1 𝑃 1, 和P 2 𝑃 2定义。如果我们按y𝑦的增加值对这些点进行排序，使y 0≤y 1≤y 2 𝑦 0≤𝑦 1≤𝑦 2，那么三角形所占y𝑦的数值范围是[ y 0 , y 2 ] [ 𝑦 0 , 𝑦 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.
这样对顶点进行排序使事情变得更容易：这样做之后，我们总是可以假设P 0 𝑃 0是三角形的最低点，P 2 𝑃 2是最高点，所以我们不必处理所有可能的排序。

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}$ .
接下来我们必须计算 x_left 和 x_right 数组。这稍微有点棘手，因为三角形有三条边，而不是两条。然而，只考虑y𝑦的值，我们总是有一条从P 0𝑃 0到P 2𝑃 2的 "高 "边，以及从P 0𝑃 0到P 1𝑃 1和P 1𝑃 1到P 2𝑃 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}$ .
有一种特殊情况，当y 0 = y 1 𝑦 0 = 𝑦 1或y 1 = y 2 𝑦 1 = 𝑦 2时，即当三角形的一条边是水平的。当这种情况发生时，另外两条边有相同的高度，所以任何一条都可以被认为是 "高 "边。我们应该选择右边还是左边？幸运的是，这并不重要；算法将支持从左到右和从右到左的水平线，所以我们可以坚持我们的定义，即 "高 "边是指从P 0 𝑃 0到P 2 𝑃 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:
0#的值要么来自高边，要么来自连接短边； x_left 的值将来自另一组。我们将首先计算三条边的x𝑥的值。由于我们要画水平线，我们希望y𝑦的每个值都有一个x𝑥的值；这意味着我们可以用 Interpolate 来计算这些值，y𝑦为自变量，x𝑥为因变量。

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
其中一边的x𝑥值在 x02 中；另一边的值来自 x01 和 x12 的连接。请注意，在 x01 和 x12 中有一个重复的值：y 1的x𝑥的值𝑦 1既是 x01 的最后一个值，又是

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:
的第一个值 x12 。我们只需要去掉其中一个（我们任意选择 x01 的最后一个值），然后将数组连接起来。

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.
最后我们有 x02 和 x012 ，我们需要确定哪个是 x_left ，哪个是 x_right 。要做到这一点，我们可以选择任何一条水平线（例如，中间那条），并比较其在 x02 和 x012 中的x𝑥值：如果 x02 中的x𝑥值小于 x012 中的，那么我们知道 x02 一定是 x_left ；否则，它一定是 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.
现在我们有了绘制水平段所需的所有数据。我们可以使用 DrawLine 来做这个。然而， DrawLine 是一个非常通用的函数，在这种情况下，我们总是在绘制从左到右的水平线，所以使用一个简单的 for 循环更为有效。这也让我们对所画的每个像素有了更多的 "控制"，这在后面的章节中会特别有用。

Listing 7-1 has the completed DrawFilledTriangle.
清单7-1有完成的 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)
        }
    }
}

Listing 7-1: A function to draw filled triangles
清单7-1：一个绘制填充三角形的函数

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 ❺.
让我们看看这里发生了什么。这个函数接收三角形的三个顶点作为参数，以任何顺序。我们的算法需要它们从下到上的顺序，所以我们以这种方式排序 ❶。接下来，我们计算三条边的每一个 y 值的 x 值，并将两条 "短 "边的数组连接起来 ❸。然后我们算出哪个是 x_left ，哪个是 x_right ❹。最后，对于三角形顶部和底部之间的每个水平段，我们得到它的左右 x 坐标，并逐个像素❺地画出这段。

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!
图7-3显示了结果；为了验证，我们先调用 DrawFilledTriangle ，然后调用 DrawWireframeTriangle ，其坐标相同，但颜色不同。尽可能地验证你的结果--这是发现代码中的错误的一个非常有效的方法!

Figure 7-3: A filled triangle, with wireframe edges for verification
图7-3：一个填充的三角形，有线框的边缘用于验证

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.
你可能会注意到三角形的黑色轮廓与绿色的内部区域不完全一致；这在三角形的右下角边缘尤其明显。这是因为 DrawLine 正在计算该边缘的y=f(x) 𝑦 = 𝑓 ( 𝑥 ) ，但 DrawTriangle 正在计算x=f(y) 𝑥 = 𝑓 ( 𝑦 ) ，由于舍入，这可能产生轻微的不同结果。这是我们愿意接受的近似误差，以使我们的渲染算法快速。

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.
在下一章，我们将扩展数学和算法，以绘制一个充满颜色渐变的三角形；数学和算法背后的推理将是本书所开发的其他功能的关键。