直线的光栅化算法

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

一、直观的方法

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

k = ( y2 - y1 ) / ( x2 - x1 )
y =  y1
for x = x1 to x2
    draw_point ( x, round ( y ) )
    y += k

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

二、Bresenham算法

假设 | k | < 1 ，每当 x ← x + 1 时，对应的要绘制点的 要坐标要么保持不变，要么增加1或减小1（简单起见，这里假设 0 < k < 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 > n' ，就保持不变，否则增加1。这样判断的结果是我们总是选择离精确点更近的那个像素进行着色。

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

k = ( y2 - y1 ) / ( x2 - x1 )
d = 0.5
n = y1
for m = x1 to x2
    draw_point(m, n)
    d -= k
    if(d < 0.0)
        n += 1
        d += 1

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

2_delta_y = 2 * ( y2 - y1 )
2_delta_x = 2 * ( x2 - x1 )
d = x2 - x1
n = y1
for m = x1 to x2
    draw_point(m, n)
    d -= 2_delta_y
    if(d < 0)
        d += 2_delta_x
        n += 1

来源：AirGuanZ