Bresenham 直线算法

计算机图形图像

简介Bresenham 算法

在计算机图形图像中，因为屏幕是一个一个的像素点。所以在屏幕上展示的直线也是一个一个的点组成的，这个很好理解。生活中的电视屏幕，电脑显示屏像素点都比较小，可能不直观，但是我们可以看见户外那些一个个LED灯组成的LED广告牌，就会明白这个事情。Bresenham 算法就是将连续的线段计算为一个个连续的点，然后绘制在屏幕上的。

事实上Bresenham算法现在应用非常广泛，基于它的改进算法已经应用到很多其他地方，比如画圆，比如硬化到硬件芯片。

2. 线的光栅化

我们假设每条线的起始点已经给定了，我们的目标就是通过给定的起始点计算这条线的其他点，起点为(x1,y1),终点为(x2,y2)。

2.1 Digital Differential Analyzer (DDA 算法)

线光栅化算法里最简答的算法,叫做Digital Differential Analyzer （DDA），事实上是使用 y = m*x + c，其中m是斜率,m = dy/dx。 dy = y2-y1， 同理dx = x2-x1。如下图所示。

第一步，我们通过比较dx和dy的大小来确定那一条线比较长。如下图所示现在是dx > dy ，因为dx比较长，所以设置length = dx。

第二步我们通过 x = x + dx/length 和 y = y + dy/length 从第一个点开始一步一步的计算出线每一个的位置。实际我们是计算了点(x1,y1)与点(x2,y2)之间的插值，具体计算如下图右边所示。

SimpleexampleofDDAalgorithm

不知道大家理解没有，虽然是很简单的东西，反正直接通过文字我没理解，但我是结合下面的代码理解的。说一下我的理解：

中心思想就是：将 x，y方向的差值分别平均分成n份，然后从起点往终点的方向，x += x/n, y += y/n。

首先这个算法是一个像素一个像素的计算，所以具体循环里面计算几次，是由length 也就是上面的n决定，也就是dx，dy中大的部分，这样就能保证一个像素一个像素的计算。
因为选差值小的那个方向的话，在具体的计算过程中就会出现差值较大的那个方向出现一个大于一个像素的情况，这要是出现了，那么多出的像素该放到哪里？

说了length的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function DDA(int x1, int y1, int x2, int y2)
{
    if (|x2 – x1|) >= (|y2 – y1|)
        len = |x2 – x1|;
    else
        len = |y2 – y1|;

    // 计算每次的加在x，y方向的增长值
    // 注意了 dx或者dy会有一个为1，另外一个为斜率的倒数
    dx = (x2 – x1) / len;
    dy = (y2 – y1) / len;

    // 起始点
    float x = x1;
    float y = y1;

    for (int i = 0; i < len; i++)
    {
        plot(round(x), round(y));
        x = x + dx;
        y = y + dy;
    }
    // 绘制终点
    plot(x2, y2);
}

在这里我们调用了一个plot(int x, int y)函数，这个函数表示在屏幕的（x,y）坐标上绘制一个像素。后面的其他算法，我们也会调用到这个函数。
round()函数将所给的浮点数转化为最靠近的整数。如果你想使用floor()获取整数的话，你需要稍微修改下代码。

一个更好的解决方案是使用下面的代码实现。

1
2
float x = x1 + 0.5 * ( (dx > 0) ? 1 : -1);
float y = y1 + 0.5 * ( (dy > 0) ? 1 : -1);

上面的DDA算法里面也可以修改for循环 里面的 i < len 为 i <= len 从而避免最后一个像素的绘制，但是这个也取决于取整函数round或者floor()的具体实现,总而言之这都是一些比较小的细节，大家注意就是了。

上面的伪代码是DDA算法的实现，这个算法依赖于方向和斜率，在前面的长度检测中使用了绝对值，所以显而易见适用于任何类型的直线。
上面的是光栅化线最简单的算法，x，y需要为整数。说完这些现在让我们来看看另外一个算法的原理以及实现。

2.2 直线光栅化的Bresenham算法 (浮点数版本)

在这一章我们假设直线在第一象限，同时直线的角度在0度～45度之间，也就是说斜率在0～1之间。也就是说现在两个点（x1，y1），（x2，y2）有x2 > x1,y2 > y1，并且 0 <= dy <= dx 在 章节 2.3我们或取消这些限制，讨论更加通用的情况。

Bresenham 算法 通过以下的算法，试着去得到锯齿更加少的直线。具体每个点是在x轴方向还是在y轴方向处理，由一个在区间[-0.5 ~ 0.5]之间的 e 值来决定。如果e > 0的话，那么我们在y轴方向上处理直线，同时e的值减1，如果e < 0 的话。那么我们在x轴上处理直线。
初始化的时候e的值取决于斜率，e的值和斜率大小成正比。如下图所示展示了e的值与点之间的关系。
Relationoferrorvalueeandlineproceeding
当然了这个图解释了e值的与点的选择之间的关系，只是解释了怎么去根据e的值去计算x的y值这个操作的步骤，但是作者并没有解释出为什么这么做，也就是为什么这样去计算e的值。

至少我没明白其中的原理，所以我查阅了其他的资料，解释了为什么这么计算的原理。下面我们将介绍下其中的原理。
bres1
第一步：如上图我么初始化e的值，其实就是斜率dy/dx。一开始第一个点是(x-1,y) 那么下一个点要么是(x,y)要么是（x，y+1）。然后y+e < y+0.5 也就是说 点（x,y+e）在点(x,y) 和点（x，y+1）之间离着(x,y) 更加近一些。

第二步：然后继续我们将x 移向x+1的时候，要么选择(x+1,y+1)要么选择(x+1,y)如上图可见y + e + m > y + 0.5 (e+m为累计误差)所以我们现在选择点(x+1,y+1) 因为选择这个点的话相对来说产生的误差更加小一些。

总结一下第一步第二步，意思就是说 误差值e的累计与y的和小于 y+0.5，也就是e+y < 0.5+y。操作就是选择x轴上前进一步,e+y > 0.5+y 我们就在y轴上前进一步。

在知道了如何绘制了新的点之后，现在我们来看看如何更新误差值e_new了。

第一步：我们在x轴上前进了一步所以(x-1,y)->(x,y) 下一个点的实际值y = y+e+m，实际选择的是计算的误差值 e_new = e + m;
第二步：x轴上前进了一步，y轴也前进一步(x,y)->(x+1,y+1) e_new = (e + m) - 1（注：因为这里是第二步了 e+m 应该作为累计误差的整体e ）;
e = m = dy/dx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void BresenhamFloat(int x1, int y1, int x2, int y2)
{
    int x = x1;
    int y = y1;
    int dx = x2 – x1;
    int dy = y2 – y1;
    // 初始化的e
    float e = ((float)dy/(float)dx);
    for (int i = 1; i <= dx; i++)
    {
        plot(x, y);
        // 比较误差，为什么这里是while不是if？？
        while (e >= 0.5)
        {
            y = y + 1;
            e = e – 1;
        }
        x = x + 1;
        e = e + (float)dy/(float)dx;
    }
}

2.3 直线光栅化的Bresenham算法 (整数版本)

在本章节我们要解决两个问题
a)上面的算法为浮点数计算
b)上般的算法只是在第一象限能够运行

因为上面的算法涉及到很多的浮点数计算，所以效率是比较低的（特别是一些嵌入式的系统，比如DSP系统一个周期能完成两次乘法，但是一个浮点计算却要上百个周期）

本文主要翻译自:
RasterisingLinesCircles
The Bresenham Line-Drawing Algorithm