直线的光栅化算法

给定起点（ x₁ , y₁ ）和终点（ x₂ , y₂ ），直线的光栅化算法要找出哪些像素应该被着色。简单起见，这里假设 x₁ < x₂。

<strong>一、直观的方法</strong>

当直线的斜率 | k | = | ( y₂ - y₁ ) /( x₂ - x₁ ) | &lt; 1 时，直线在 y 向的变化速率小于在 x 方向上的变化速率，因此可以遍历 x₁ 到 x₂ 间的每一个 x ，计算对应的 y 值并将其四舍五入画点。算法伪代码如下：

<pre>k = ( y₂ - y₁ ) / ( x₂ - x₁ )
y = y₁
for x = x₁ to x₂
draw_point ( x, round ( y ) )
y += k</pre>

而当 | k | &gt; 1 时，必须交换 x 和 y 的地位——遍历 y 的取值，每次迭代计算对应的 x 。

<strong>二、Bresenham算法</strong>

假设 | k | &lt; 1 ，每当 x ← x + 1 时，对应的要绘制点的 要坐标要么保持不变，要么增加1或减小1（简单起见，这里假设 0 &lt; k &lt; 1 ，即只可能不变或增加1）。我们需要给出一个判断条件，判断什么时候该增加1、什么时候该保持不变。

常见的方法是使用中点进行比较（有一种所谓“中点画线法”，其原理和Bresenham算法本质上是相同的）。假设保持不变时绘制的点坐标为 ( m , n ) ，那么 y 增加1时坐标应为 ( m , n+1 ) ，容易知道连接这两个点的线段的中点为 ( m , n+0.5 ) 。现假设直线与 x = m 的交点坐标为 ( m , n' ) ，那么就可以将 ( m , n+0.5 ) 与之比较——若 n+0.5 &gt; n' ，就保持不变，否则增加1。这样判断的结果是我们总是选择离精确点更近的那个像素进行着色。

由于每一轮迭代中 x 的增量都是1，因此 n' 的增量是 k 。我们维护一个变量 d ，表示 n+0.5 - n' 的值。每次迭代 d 都减小 k ，一旦发现 d 小于零，就意味着应当使 n 增加1，对应地 d 的值也要加1。算法伪代码如下：

<pre>k = ( y₂ - y₁ ) / ( x₂ - x₁ )
d = 0.5
n = y₁
for m = x₁ to x₂
draw_point(m, n)
d -= k
if(d &lt; 0.0)
n += 1
d += 1</pre>

更进一步地，可以通过用 ( x₂ - x₁ )与之相乘的方法来消除上面的算法中与d有关的浮点操作，这样就彻底消灭了浮点运算而仅剩对整数的操作。即：

<pre>2_delta_y = 2 * ( y₂ - y₁ )
2_delta_x = 2 * ( x₂ - x₁ )
d = x₂ - x₁
n = y₁
for m = x1 to x₂
draw_point(m, n)
d -= 2_delta_y
if(d < 0)
d += 2_delta_x
n += 1</pre>

来源：<a href="https://www.cnblogs.com/AirGuanZ/p/6258253.html">AirGuanZ</a&gt;