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

Lines

In Part I of this book, we studied raytracing extensively and developed a raytracer that could render our test scene with accurate lighting, material properties, shadows, and reflection using relatively simple algorithms and math. This simplicity comes at a cost: performance. While non-real-time performance is fine for certain applications, such as architectural visualization or visual effects for movies, it’s not enough for other applications, such as video games.
在本书的第一部分中，我们广泛地研究了光线追踪，并开发了一个光线追踪器，它可以使用相对简单的算法和数学来渲染我们的测试场景，并具有准确的照明、材料属性、阴影和反射。这种简单性是有代价的：性能。虽然非实时性能对于某些应用来说是没有问题的，比如建筑可视化或电影的视觉效果，但对于其他应用，比如视频游戏，它是不够的。

In this part of the book, we’ll explore an entirely different set of algorithms that favor performance over mathematical purity.
在本书的这一部分，我们将探索一套完全不同的算法，这些算法偏重于性能而不是数学的纯洁性。

Our raytracer starts from the camera and explores the scene through the viewport. For every pixel of the canvas, we answer the question, “Which object of the scene is visible here?” Now we’ll follow an approach that is, in some sense, the opposite: for every object in the scene, we’ll try to answer the question “In which parts of the canvas will this object be visible?”
我们的光线追踪器从摄像机开始，通过视口探索场景。对于画布上的每一个像素，我们都要回答这样一个问题："这里可以看到场景中的哪个物体？"现在，我们将采用一种在某种意义上相反的方法：对于场景中的每个物体，我们将尝试回答 "这个物体在画布的哪些部分是可见的？"

It turns out we can develop algorithms that answer this new question much faster than raytracing could, as long as we’re willing to make some accuracy trade-offs. Later, we’ll explore how to use these fast algorithms to achieve results with a quality comparable to that of a raytracer.
事实证明，我们可以开发出比光线追踪更快地回答这个新问题的算法，只要我们愿意做出一些精度上的折衷。稍后，我们将探讨如何使用这些快速的算法来实现与光线追踪的质量相当的结果。

We’ll start from scratch again: we have a canvas of dimensions $C_{w}$ and $C_{h}$ , and we can set the color of individual pixels with PutPixel(), but nothing else. Let’s explore how to draw the simplest possible element on the canvas: a line between two points.
我们再从头开始：我们有一个尺寸为C w 𝐶 𝑤和C h 𝐶 ℎ的画布，我们可以用 PutPixel() 设置单个像素的颜色，但没有其他功能。让我们探讨一下如何在画布上绘制最简单的元素：两点之间的直线。

Describing Lines 描述线条

Suppose we have two canvas points, $P_{0}$ and $P_{1}$ , with coordinates $(x_{0}, y_{0})$ and $(x_{1}, y_{1})$ respectively. How can we draw the straight line segment between $P_{0}$ and $P_{1}$ ?
假设我们有两个画布点，P 0 𝑃 0和P 1 𝑃 1，其坐标分别为( x 0 , y 0 ) ( 𝑥 0 , 𝑦 0 ) 和( x 1 , y 1 ) ( 𝑥 1 , 𝑦 1 ) 。如何画出P 0 𝑃 0与P 1 𝑃 1之间的直线段？

Let’s start by representing a line with parametric coordinates, just as we did with rays before (in fact, you can think of “rays” as lines in 3D). Any point $P$ on the line can be obtained by starting at $P_{0}$ and moving some distance along the direction from $P_{0}$ to $P_{1}$ :
让我们先用参数坐标来表示一条线，就像我们之前对射线所做的那样（事实上，你可以把 "射线 "看成是三维中的线）。线上的任何一点P𝑃都可以通过从P 0𝑃 0开始，沿P 0𝑃 0到P 1𝑃 1的方向移动一段距离得到。

P = P_{0} + t (P_{1} - P_{0})P = P 0 +t( P 1 - P 0 ) 𝑃 = 𝑃 0 + 𝑡 ( 𝑃 1 - 𝑃 0 )

We can decompose this equation into two, one for each coordinate:
我们可以把这个方程分解成两个，每个坐标都有一个。

x = x_{0} + t \cdot (x_{1} - x_{0})x = x 0 +t\cdot( x 1 - x 0 ) 𝑥 = 𝑥 0 + 𝑡 \cdot ( 𝑥 1 - 𝑥 0 )

y = y_{0} + t \cdot (y_{1} - y_{0})y= y 0 +t\cdot( y 1 - y 0 ) 𝑦 = 𝑦 0 + 𝑡 \cdot ( 𝑦 1 - 𝑦 0 )

Let’s take the first equation and solve for $t$ :
让我们从第一个方程出发，求解t 𝑡。

x = x_{0} + t \cdot (x_{1} - x_{0})x = x 0 +t\cdot( x 1 - x 0 ) 𝑥 = 𝑥 0 + 𝑡 \cdot ( 𝑥 1 - 𝑥 0 )

x - x_{0} = t \cdot (x_{1} - x_{0})x- x 0 =t\cdot( x 1 - x 0 ) 𝑥 - 𝑥 0 = 𝑡 \cdot ( 𝑥 1 - 𝑥 0 )

\frac{x - x_{0}}{x_{1} - x_{0}} = tx- x 0 x 1 - x 0 =t 𝑥 - 𝑥 0 ubli 1 - ubli 0 ubli 1 - ubli 0 = 𝑡

We can now plug this expression for $t$ into the second equation:
现在我们可以把t 𝑡的这个表达式插入第二个方程。

y = y_{0} + t \cdot (y_{1} - y_{0})y= y 0 +t\cdot( y 1 - y 0 ) 𝑦 = 𝑦 0 + 𝑡 \cdot ( 𝑦 1 - 𝑦 0 )

y = y_{0} + \frac{x - x_{0}}{x_{1} - x_{0}} \cdot (y_{1} - y_{0})y = y 0 + x- x 0 x 1 - x 0 \cdot( y 1 - y 0 ) 𝑦 = 𝑦 0 + 𝑥 - 𝑥 0 \cdot( 𝑦 1 -𝑦 0 )

Rearranging it a bit: 重新安排一下。

y = y_{0} + (x - x_{0}) \cdot \frac{y_{1} - y_{0}}{x_{1} - x_{0y= y 0 +(x- x 0 )⋅ y 1 - y 0 x 1 - x 0 𝑦 = 𝑦 0 + ( 𝑥 - 𝑥 0 ) ⋅ 𝑦 1 - 𝑦 0 𝑥 1 - 𝑥 0}}

Notice that $\frac{y_{1} - y_{0}}{x_{1} - x_{0}}$ is a constant that depends only on the endpoints of the segment; let’s call it $a$ . So we can rewrite the equation above as
请注意，y 1 - y 0 x 1 - x 0 𝑦 1 - 𝑦 0 𝑥 1 - 𝑥 0 是一个常数，只取决于线段的端点；我们称之为𝑎。因此，我们可以将上面的方程改写为

y = y_{0} + a \cdot (x - x_{0})y = y 0 +a\cdot(x- x 0 ) 𝑦 = 𝑦 0 + 𝑎 \cdot ( 𝑥 - 𝑥 0 )

What is $a$ ? According to the way we’ve defined it, it measures the change in the $y$ coordinate per unit change in the $x$ coordinate; in other words, it’s a measure of the slope of the line.
什么是𝑎？根据我们的定义，它衡量的是y𝑦坐标在x𝑥坐标中每一单位的变化；换句话说，它是对直线斜率的衡量。

Let’s go back to the equation. Distributing the multiplication:
让我们回到方程中去。分布乘法。

y = y_{0} + a x - a x_{0y = y 0 +ax-a x 0 𝑦 = 𝑦 0 + 𝑎 𝑥 - 𝑎 0}

Grouping the constants: 对常数进行分组。

y = a x + (y_{0} - a x_{0})y=ax+( y 0 -a x 0 ) 𝑦 = 𝑎 𝑥 + ( 𝑦 0 - 𝑎 𝑥 0 )

Again, $(y_{0} - a x_{0})$ depends only on the endpoints of the segment; let’s call it $b$ . Finally we get
同样，( y 0 -a x 0 ) ( 𝑦 0 - 𝑎 𝑥 0 ) 只取决于线段的端点，我们称之为b 𝑏。最后我们得到

y = a x + by=ax+b 𝑦= 𝑎 𝑥+ 𝑏

This is the standard formulation of a linear function, which can be used to represent almost any line. When we solved for $t$ , we added a division by $x_{1} - x_{0}$ without thinking what happens if $x_{1} = x_{0}$ . We can’t divide by zero, which means this formulation can’t represent lines with $x_{1} = x_{0}$ —that is, vertical lines.
这是线性函数的标准表述，几乎可以用来表示任何线。当我们求解t𝑡时，我们加入了除以x 1 - x 0 𝑥 1 - 𝑥 0，而没有考虑到如果x 1 = x 0 𝑥 1 = 𝑥 0会怎样。

To work around this issue, we’ll just ignore vertical lines for now and figure out how to deal with them later.
为了解决这个问题，我们现在先不考虑垂直线，以后再想办法处理它们。

Drawing Lines 画线

We now have a way to get the value of $y$ for each value of $x$ we’re interested in. This gives us a pair $(x, y)$ that satisfies the equation of the line.
现在我们有办法得到我们感兴趣的每个x𝑥的y𝑦的值。这样我们就得到了一对满足直线方程的(x,y) ( 𝑥 , 𝑦 )。

We can now write a first approximation of a function that draws a line segment from $P_{0}$ to $P_{1}$ . Let x0 and y0 be the $x$ and $y$ coordinates of $P_{0}$ , respectively, and x1 and y1 those of $P_{1}$ . Assuming $x_{0} < x_{1}$ , we can go from $x_{0}$ to $x_{1}$ , computing the value of $y$ for each value of $x$ , and drawing a pixel at these coordinates:
现在我们可以写出一个函数的第一近似值，即从P 0 𝑃 0到P 1 𝑃 1画一条线段。让 x0 和 y0 分别为P 0𝑃0的x𝑥和y𝑦坐标，以及 x1 和 y1 为P 1𝑃1的坐标。假设x 0 < x 1 𝑥 0 < 𝑥 1，我们可以从x 0 𝑥 0到x 1 𝑥 1，计算x 𝑥每个值的y 𝑦值，并在这些坐标上画一个像素。

DrawLine(P0, P1, color) {
    a = (y1 - y0) / (x1 - x0)
    b = y0 - a * x0
    for x = x0 to x1 {
        y = a * x + b
        canvas.PutPixel(x, y, color)
    }
}

Note that the division operator / is expected to perform real division, not integer division. This is despite $x$ and $y$ being integers in this context, as they represent coordinates of pixels on the canvas.
请注意，除法运算符 / 被期望执行实数除法，而不是整数除法。尽管x𝑥和y𝑦在这里是整数，因为它们代表画布上的像素坐标。

Also note that we consider for loops to include the last value of the range. In C, C++, Java, and JavaScript, among others, this would be written as for (x = x0; x <= x1; ++x). We will be using this convention throughout this book.
还要注意的是，我们认为 for 循环包括范围的最后一个值。在C、C++、Java和JavaScript等语言中，这将被写成 for (x = x0; x <= x1; ++x) 。我们将在本书中使用这一约定。

This function is a direct, naive implementation of the equation above. It works, but can we make it faster?
这个函数是上述方程的一个直接的、天真的实现。它是有效的，但我们可以使它更快吗？

We aren’t calculating values of $y$ for any arbitrary $x$ . On the contrary, we’re calculating them only at integer increments of $x$ and we’re doing so in order. Right after calculating $y (x)$ , we calculate $y (x + 1)$ :
我们不是在计算任意x𝑥的y𝑦的值。相反，我们只在x𝑥的整数增量上计算它们，而且是按顺序计算的。在计算完y(x) 𝑦 ( 𝑥) 之后，我们再计算y(x+1) 𝑦 ( 𝑥 + 1 ) 。

y (x) = a x + b

y (x + 1) = a \cdot (x + 1) + b

We can manipulate that second expression a bit:
我们可以对第二个表达式进行一些操作。

y (x + 1) = a x + a + by(x+1)=ax+a+b 𝑦 ( 𝑥 + 1 ) = 𝑎 𝑏 + ᵄ

y (x + 1) = (a x + b) + ay(x+1)=(ax+b)+a 𝑦 ( 𝑥+1 ) = ( 𝑎 𝑥+ 𝑏 ) + 𝑎

y (x + 1) = y (x) + a

This shouldn’t be surprising; after all, the slope $a$ is the measure of how much $y$ changes when $x$ increases by 1, which is exactly what we’re doing here.
这并不令人惊讶；毕竟，斜率a𝑎是衡量x𝑥增加1时y𝑦的变化程度，这正是我们在这里所做的。

This means we can compute the next value of $y$ just by taking the previous value of $y$ and adding the slope; no per-pixel multiplication is needed, which makes the function faster. At the beginning there’s no “previous value of $y$ ,” so we start at $(x_{0}, y_{0})$ . Then we keep adding $1$ to $x$ and $a$ to $y$ until we get to $x_{1}$ .
这意味着我们可以计算出y𝑦的下一个值，只需取y𝑦的前一个值并加上斜率；不需要每像素的乘法，这使得函数更快。一开始没有 "y𝑦的前值"，所以我们从( x 0 , y 0 ) ( 𝑥 0 , 𝑦 0 ) 开始。然后，我们不断地在x𝑥添加1 1，在y𝑦添加a 𝑎，直到我们得到x 1𝑥1。

Again assuming that $x_{0} < x_{1}$ , we can rewrite the function as follows:
再次假设x 0 < x 1𝑥 0 < 𝑥 1，我们可以将该函数改写如下。

DrawLine(P0, P1, color) {
    a = (y1 - y0) / (x1 - x0)
    y = y0
    for x = x0 to x1 {
        canvas.PutPixel(x, y, color)
        y = y + a
    }
}

So far we’ve been assuming that $x_{0} < x_{1}$ . There’s an easy workaround to support lines where that doesn’t hold: since the order in which we draw the pixels doesn’t matter, if we get a right-to-left line, we can just swap P0 and P1 to transform it into the left-to-right version of the same line, and draw it as before:
到目前为止，我们一直假设x 0 < x 1 𝑥 0 < 𝑥 1。有一个简单的变通方法来支持不成立的线条：由于我们绘制像素的顺序并不重要，如果我们得到一条从右到左的线条，我们可以将 P0 和 P1 交换，将其转化为同一线条的从左到右的版本，然后像以前一样绘制它。

DrawLine(P0, P1, color) {
    // Make sure x0 < x1
    if x0 > x1 {
        swap(P0, P1)
    }
    a = (y1 - y0) / (x1 - x0)
    y = y0
    for x = x0 to x1 {
        canvas.PutPixel(x, y, color)
        y = y + a
    }
}

Let’s use our function to draw a couple of lines. Figure 6-1 shows the line segment $(- 200, - 100) - (240, 120)$ , and Figure 6-2 shows a close-up of the line.
让我们用我们的函数来画几条线。图6-1显示了线段(-200,-100)-(240,120) ( - 200 , - 100 ) - ( 240 , 120 ) ，图6-2显示了该线段的特写。

Figure 6-2: Zooming in on the straight line
图6-2：扩大直线的范围

The line appears jagged because we can only draw pixels on integer coordinates, and mathematical lines actually have zero width; what we’re drawing is a quantized approximation of the ideal line from $(- 200, - 100) - (240, 120)$ . There are ways to draw prettier approximations of lines (you may want to look into MSAA, FXAA, SSAA, and TAA as possible entry points to an interesting set of rabbit holes). We won’t go there for two reasons: (1) it’s slower, and (2) our goal is not to draw pretty lines but to develop some basic algorithms to render 3D scenes.
线条出现锯齿状是因为我们只能在整数坐标上绘制像素，而数学线条的宽度实际上为零；我们所绘制的是一条从（-200,-100）-（240,120）（-200 , -100）-（240 , 120）的理想线条的量化近似。有一些方法可以画出更漂亮的近似线（你可能想研究一下MSAA、FXAA、SSAA和TAA，作为进入一组有趣的兔子洞的可能入口）。我们不会去那里，原因有二：（1）它比较慢，（2）我们的目标不是要画出漂亮的线条，而是要开发一些渲染3D场景的基本算法。

Let’s try another line, $(- 50, - 200) - (60, 240)$ . Figure 6-3 shows the result and Figure 6-4 shows the corresponding close-up.
让我们试试另一条线，(-50,-200)-(60,240) ( - 50 , - 200 ) - ( 60 , 240 ) 。图6-3是结果，图6-4是相应的特写。

Figure 6-3: Another straight line with a higher slope
图6-3：另一条斜率较高的直线

Figure 6-4: Zooming in on the second straight line
图6-4：放大第二条直线

Oops. What happened? 哎呀。发生了什么事？

The algorithm did exactly what we told it to; it went from left to right, computed one value of $y$ for each value of $x$ , and painted the corresponding pixel. The problem is that it computed one value of $y$ for each value of $x$ , while in this case we actually need several values of $y$ for some values of $x$ .
该算法完全按照我们的要求去做；它从左到右，为每个x𝑥的值计算一个y𝑦的值，并画出相应的像素。问题是，它为每个x𝑥的值计算了一个y𝑦的值，而在这种情况下，我们实际上需要为x𝑥的一些值计算几个y𝑦的值。

This happens because we chose a formulation where $y = f (x)$ ; in fact, it’s the same reason why we can’t draw vertical lines—an extreme case where all the values of $y$ correspond to the same value of $x$ .
这是因为我们选择了一个y=f(x) 𝑦 = 𝑓 ( 𝑥 ) 的公式；事实上，这也是我们无法画出垂直线的原因--在这种极端情况下，y 𝑦的所有数值都对应于x 𝑥的相同数值。

Drawing Lines with Any Slope
绘制任意斜度的直线

Choosing $y = f (x)$ was an arbitrary choice; we could equally have chosen to express the line as $x = f (y)$ . Reworking all the equations by exchanging $x$ and $y$ , we get the following algorithm:
选择y=f(x) 𝑦 = 𝑓 ( 𝑥 ) 是一个任意的选择；我们同样可以选择将这条线表达为x=f(y) 𝑥 = 𝑓 ( 𝑦 ) 。通过交换x𝑥和y𝑦，重修所有的方程，我们得到以下算法。

DrawLine(P0, P1, color) {
    // Make sure y0 < y1
    if y0 > y1 {
        swap(P0, P1)
    }
    a = (x1 - x0)/(y1 - y0)
    x = x0
    for y = y0 to y1 {
        canvas.PutPixel(x, y, color)
        x = x + a
    }
}

This is identical to the previous DrawLine, except the $x$ and $y$ computations have been exchanged. This one can handle vertical lines and will draw $(0, 0) - (50, 100)$ correctly; but of course, it can’t handle horizontal lines at all, or draw $(0, 0) - (100, 50)$ correctly! What to do?
这与之前的 DrawLine 相同，只是交换了x𝑥和y 𝑦的计算。这个函数可以处理垂直线，并且可以正确地画出(0,0)-(50,100) ( 0 , 0 ) - ( 50 , 100 ) ；但当然，它完全不能处理水平线，也不能正确地画出(0,0)-(100,50) ( 0 , 0 ) - ( 100 , 50 )!怎么办呢？

We can just keep both versions of the function and choose which one to use depending on the line we’re trying to draw. And the criterion is quite simple; does the line have more different values of $x$ than different values of $y$ ? If there are more values of $x$ than $y$ , we use the first version; otherwise, we use the second.
我们可以保留两个版本的函数，根据我们要画的线来选择使用哪一个。这个标准很简单，线的x𝑥的不同值是否比y𝑦的不同值多？如果x𝑥的数值多于y𝑦的数值，我们就使用第一个版本；否则，我们就使用第二个版本。

Listing 6-1 shows a version of DrawLine that handles all the cases.
清单6-1显示了一个处理所有情况的 DrawLine 的版本。

DrawLine(P0, P1, color) {
    dx = x1 - x0
    dy = y1 - y0
    if abs(dx) > abs(dy) {
        // Line is horizontal-ish
        // Make sure x0 < x1
        if x0 > x1 {
            swap(P0, P1)
        }
        a = dy/dx
        y = y0
        for x = x0 to x1 {
            canvas.PutPixel(x, y, color)
            y = y + a
        }
    } else {
        // Line is vertical-ish
        // Make sure y0 < y1
        if y0 > y1 {
            swap(P0, P1)
        }
        a = dx/dy
        x = x0
        for y = y0 to y1 {
            canvas.PutPixel(x, y, color)
            x = x + a
        }
    }
}

Listing 6-1: A version of DrawLine that handles all the cases
清单6-1：一个处理所有情况的 DrawLine 的版本

This certainly works, but it isn’t pretty. There’s a lot of code duplication, and the logic for selecting which function to use, the logic to compute the function values, and the pixel drawing itself are all intertwined. Surely we can do better!
这当然是可行的，但它并不漂亮。有很多代码重复，选择使用哪个函数的逻辑，计算函数值的逻辑，以及像素绘制本身都是相互交织的。当然，我们可以做得更好!

The Linear Interpolation Function
线性内插函数

We have two linear functions $y = f (x)$ and $x = f (y)$ . To abstract away the fact that we’re dealing with pixels, let’s write it in a more generic way as $d = f (i)$ , where $i$ is the independent variable, the one we choose the values for, and $d$ is the dependent variable, the one whose value depends on the other and which we want to compute. In the horizontal-ish case, $x$ is the independent variable and $y$ is the dependent variable; in the vertical-ish case, it’s the other way around.
我们有两个线性函数 y=f(x) 𝑦 = 𝑓 ( 𝑥 ) 和 x=f(y) 𝑥 = 𝑓 ( 𝑦 ) 。为了抽象出我们在处理像素的事实，让我们用更通用的方式来写，即d=f(i) 𝑑 = 𝑓 ( 𝑖 )，其中i 𝑖是自变量，即我们选择数值的变量，而d 𝑑是因变量，即其数值取决于其他变量，我们想计算的变量。在横向的情况下，x𝑥是自变量，y𝑦是因变量；在纵向的情况下，情况正好相反。

Of course, any function can be written as $d = f (i)$ . We know two more things that completely define our function: the fact that it’s linear and two of its values—that is, $d_{0} = f (i_{0})$ and $d_{1} = f (i_{1})$ . We can write a simple function that takes these values and returns a list of all the intermediate values of $d$ , assuming as before that $i_{0} < i_{1}$ :
当然，任何函数都可以写成d=f(i) 𝑑 = 𝑓 ( 𝑖 ) 。我们还知道两件事，它们完全定义了我们的函数：它是线性的，以及它的两个值--即d 0 =f( i 0 ) 𝑑 0 = 𝑓 ( 𝑖 0 ) ，d 1 =f( i 1 ) 𝑑 1 = 𝑓 ( 𝑖 1 ) 。我们可以写一个简单的函数，接受这些值并返回d𝑑的所有中间值的列表，如前所述，假设i 0 < i 1 𝑖 0 < 𝑖 1。

Interpolate (i0, d0, i1, d1) {
    values = []
    a = (d1 - d0) / (i1 - i0)
    d = d0
    for i = i0 to i1 {
        values.append(d)
        d = d + a
    }
    return values
}

This function has the same “shape” as the first two versions of DrawLine, but the variables are called i and d instead of x and y, and instead of drawing pixels, this one stores the values in a list.
这个函数的 "形状 "与前两个版本的 DrawLine 相同，但变量被称为 i 和 d ，而不是 x 和 y ，而且这个函数不是绘制像素，而是将值存储在一个列表中。

Note that the value of $d$ corresponding to $i_{0}$ is returned in values[0], the value for $i_{0} + 1$ in values[1], and so on; in general, the value for $i_{n}$ is returned in values[i_n - i_0], assuming $i_{n}$ is in the range $[i_{0}, i_{1}]$ .
请注意，i 0𝑖 0对应的d𝑑值在 values[0] 中返回，i 0+1𝑖 0+1的值在 values[1] 中返回，以此类推；一般来说，i n 𝑖𝑛的值在 values[i_n - i_0] 中返回，假设i n 𝑖𝑛在[ i 0 , i 1 ] [ 𝑖 0 , 𝑖 1 ] 范围内。

There’s a corner case we need to consider: we may want to compute $d = f (i)$ for a single value of $i$ —that is, when $i_{0} = i_{1}$ . In this case we can’t even compute $a$ , so we’ll treat it as a special case:
我们需要考虑一个角落的情况：我们可能想要计算d=f(i) 𝑑 = 𝑓 ( 𝑖 ) 对于i𝑖的单一值--也就是说，当i 0 = i 1 𝑖 0 = 𝑖 1。在这种情况下，我们甚至无法计算出一个𝑎，所以我们将把它作为一个特例。

Interpolate (i0, d0, i1, d1) {
    if i0 == i1 {
       return [ d0 ]
    }
    values = []
    a = (d1 - d0) / (i1 - i0)
    d = d0
    for i = i0 to i1 {
        values.append(d)
        d = d + a
    }
    return values
}

As an implementation detail, and for the remainder of this book, the values of the independent variable $i$ are always integers, as they represent pixels, while the values of the dependent variable $d$ are always floating point values, as they represent values of a generic linear function.
作为一个实现细节，在本书的其余部分，自变量i𝑖的值总是整数，因为它们代表像素，而因变量d𝑑的值总是浮点值，因为它们代表一个通用线性函数的值。

Now we can write DrawLine using Interpolate.
现在我们可以用 Interpolate 来写 DrawLine 。

DrawLine(P0, P1, color) {
    if abs(x1 - x0) > abs(y1 - y0) {
        // Line is horizontal-ish
        // Make sure x0 < x1
        if x0 > x1 {
            swap(P0, P1)
        }
        ys = Interpolate(x0, y0, x1, y1)
        for x = x0 to x1 {
            canvas.PutPixel(x, ys[x - x0], color)
        }
    } else {
        // Line is vertical-ish
        // Make sure y0 < y1
        if y0 > y1 {
            swap(P0, P1)
        }
        xs = Interpolate(y0, x0, y1, x1)
        for y = y0 to y1 {
            canvas.PutPixel(xs[y - y0], y, color)
        }
    }
}

Listing 6-2: A version of DrawLine that uses Interpolate
清单6-2：一个使用 Interpolate 的 DrawLine 版本

This DrawLine can handle all cases correctly (Figure 6-5).
这个 DrawLine 可以正确处理所有情况（图6-5）。

Figure 6-5: The refactored algorithm handles all cases correctly.
图6-5：重构后的算法能正确处理所有情况。

Source code and live demo >>
源代码和现场演示 >>

While this version isn’t much shorter than the previous one, it cleanly separates the computation of the intermediate values of $y$ and $x$ from the decision of which is the independent variable and from the pixel-drawing code itself.
虽然这个版本并不比前一个版本短多少，但它将y𝑦和x𝑥的中间值的计算与决定哪个是自变量以及与像素绘制代码本身干净地分开。

It might come as a surprise that this line algorithm is not the best or the fastest there is; that distinction probably belongs to Bresenham’s Algorithm. The reason to present this algorithm is twofold. First, it is easier to understand, which is an overriding principle in this book. Second, it gave us the Interpolate function, which we will use extensively in the rest of this book.
这条线的算法并不是最好的或最快的，这一点可能会让人感到惊讶；这个区别可能属于Bresenham的算法。提出这个算法的原因有两个方面。首先，它更容易理解，这也是本书的一个首要原则。第二，它为我们提供了 Interpolate 函数，我们将在本书的其余部分广泛使用它。

Summary

In this chapter, we’ve taken the first steps to building a rasterizer. Using the only tool we have, PutPixel, we’ve developed an algorithm that can draw straight line segments on the canvas.
在这一章中，我们已经迈出了建立光栅器的第一步。使用我们唯一的工具， PutPixel ，我们开发了一种算法，可以在画布上绘制直线段。

We have also developed the Interpolate helper method, a way to efficiently compute values of a linear function. Make sure you understand it well before proceeding, because we’ll be using it a lot.
我们还开发了 Interpolate 辅助方法，这是一种有效计算线性函数值的方法。在继续学习之前，请确保你能很好地理解它，因为我们会经常使用它。

In the next chapter, we’ll use Interpolate to draw more complex and interesting shapes on the canvas: triangles.
在下一章，我们将使用 Interpolate 在画布上画出更复杂、更有趣的形状：三角形。