本模块内容绝大部分是在慕课上看中国农业大学网客时的笔记，因此算作转载，在此鸣谢赵明、李振波两位老师，感谢他们录制该门课程供大家学习！

Bresenham算法

前两种算法把效率提高到了整数加法级别，只讲效率，基本已经可以说是最快了。但是，两者均严重依赖直线方程，那么，有没有算法在保证算法效率的同时能够扩大使用范围，将画线算法适用的范围变得更加广泛呢？（曲线等）——即是下面要介绍的Bresenham算法。

算法思想

Bresenham早在1962年就发表了该算法，该算法结合DDA与中点画线法的优势，它的思路是构造一个由各行各列象素中心构造一组虚拟的网格线，按照直线起点到终点的顺序，计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列像素中与此交点最近的像素。

假设按照如下图的方向步进、判断，x每次++，y是否递增取决于直线与最近像素点中心的距离，也即以0.5为界，与d=d+k比较，判断直线具体在哪个像素点内。另外，一旦d>=1，就执行d-=1操作，以保证d的相对性，使它在0,1之间

图形学（3）光栅图形学的直线绘制（下）

基于该算法的改进

由于前面的算法已经可以把直线绘制效率提高到整数加法级别了，因此虽然这个思路有优势，但如果不把它也提高到相同级别，也还是白搭。下面是对其效率提高的探索。

改进1

令e=d-0.5，这样判断条件就从d与0.5这个浮点数比较，变为了e与0比较大小。此时e的初值是-0.5，每走一步有e+=k，要保持e不要太大可以有:if(e>0)e-=1 *这里没有用e>0.5作判断条件，也是因为想避免浮点数的出现。理解时可以举个例子试一下，效果跟e>0.5是一样的。

改进2

根据斜率的定义，k=（y2-y1）/（x2-x1），由于现在判断条件不等式的一边是0，因此可以同乘一下把e化为整数，即使用2*e*(x2-x1)替换原来的e，而e初值中的浮点数也一并化为了整数。 *这里根据前面的假设默认x2>x1

改进后的算法步骤

读取两点坐标
计算初始值△x=x2-x1，△y=y2-y1，e=-△x，x=x1，y=y1......依然假设x2>x1，在实际编程中需要判断一下
绘制点（x，y）
e+=2*△y，判断e的正负决定要描的像素点
循环3,4直到绘制完成

程序如下

public class Bresenham extends JFrame {
    private int x1 , x2 , y1 , y2 , e;

    public Bresenham( int x1 , int y1  , int x2 , int y2 ){
        super();
        setTitle("Bresham直线绘制算法");
        setSize(800,600);
        setVisible(true);
        this.x1 = x1;
        this.x2 = x2;
        this.y1 = y1;
        this.y2 = y2;
        bresenhamDrawLine(x1 , y1 , x2 , y2 );
    }
    private void bresenhamDrawLine(int x1 , int y1 , int x2 , int y2){
        if (abs(x2-x1)>abs(y2-y1)){         //按x方向递增
            if (x1 > x2){
                int temp = x1;
                x1 = x2;
                x2 = temp;
                temp = y1;
                y1 = y2;
                y2 = temp;
            }
            e = x1 - x2;
            drawPixel(x1,y1);
            for (int i = x1 , j = y1 ; i < x2 ; i++){
                e += 2*(y2 - y1);
                if (e > 0){
                    j++;
                    drawPixel(i,j);
                }
                else {
                    drawPixel(i,j);
                }
            }
        }else {
            if (y1 > y2){
                int temp = y1;
                y1 = y2;
                y2 = temp;
                temp = x1;
                x1 = x2;
                x2 = temp;
            }
            e = y1 - y2;
            drawPixel(x1,y1);
            for (int j = y1 , i = x1 ; j < y2 ; j++){
                e += 2*(y2 - y1);
                if (e>0){
                    i++;
                    drawPixel(i,j);
                }else {
                    drawPixel(i,j);
                }
            }
        }
    }

通过以上我们可以看出，Bresenham算法并没有去求k，b亦或是A，B，C，仅仅是通过两点坐标去绘制直线，不限定直线方程类型，集合DDA与中点画线法优势，应用更广泛。

小结

读过这三种算法，我们经历了一个算法不断优化，精益求精的过程，领略了图形学的魅力所在。这些算法中所蕴含的思想是值得我们用心揣摩、领悟的，这对于以后的学习会有很大帮助，比如从二维到三维的直线绘制等。另外，我们可以看得出，算法中永远没有“最优”，只有不断的改进。我们要勤于思考，发散思维，发现算法的不足并思考改进方案。
下面是一些可以大致读得懂的知网论文，笔者只看过一篇，感兴趣大家可以去看一看作为扩展
图形学（3）光栅图形学的直线绘制（下）

秒客网