HTML5 Canvas 提高班（二） —— 光栅图形学（2）Bresenham算法画直线

豆豆狗

<div id="cnblogs_post_body">    上次的随笔介绍了如何用中点画圆的算法提高Canvas绘图性能，感觉大家还是比较感兴趣的。
    本节借助HTML5 canvas 强大的像素处理能力，重点给大家介绍计算机图形中-光栅学Bresenham算法；并实现两点画直线的程序。
光栅图形学（2）Bresenham算法画直线

    Bresenham算法是计算机图形学典型的直线光栅化算法，其历史可以追溯到上个世界，由 Jack E. Bresenham 1962年在IBM工作时提出。算法的历史这里就不做更多的介绍了，有兴趣的同学可以看这个wikipedia的链接，里面有很详细的介绍，我们现在就关注其实现的理论。
    1.Bresenham 算法的实现原理

    用通俗的方法解释Bresenham 算法：由于计算机屏幕的特殊性，像素不可能有小数的显示，比如：我们无法显示0.5像素在屏幕上。这样我们可以假设一条线段的斜率为k，当这条直线在X方向增加（或减少）1个像素的同时；其Y方向只可能增加（或减少）1或是0，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5。有了感性的认识，下面我们在数学的世界中计算这个Y方向的改变量。
    Bresenham 算法的数学实施：（为了能理解下面的内容可能需要一些基本的数学概念，如果已经忘了也没有关系我会尽可能简单的说明）
    1。假设空间中有两点P1和P2，则我们可以求得斜率k，假设0<k<1，这样我们只需要考虑x方向每次递增1，y的方向每次是递增1或是0。
    2。设:  直线方程为：y = kx + b。
               直线当前点为(xi, y) —— 此点是未经过离散后的点。
               直线当前光栅点为(xi, yi) —— 此点是经过离散后的点。
        则： 下一个直线的点应为(xi+1, k(xi + 1) + b)，
              由于光栅点只可能位于yi，或yi+1的位置，我们用变量 d_upper 表示真实点的坐标与（yi + 1）离散点坐标的距离：d_upper = (yi + 1) - (k(xi + 1) + b)；用d_lower 表示真实点的坐标与（yi）离散度坐标的距离：d_lower = (k(xi + 1) + b) - yi。
　　　　　这样一来我们就可以明确该如何选择点：如果d_upper > d_lower，则表示真实点距yi的位置更近我就选择yi为下一离散点的y坐标；反之选择yi + 1。
        所以我们程序中需要求： d_lower - d_upper = 2k(xi + 1) - 2yi + 2b -1（化简后的结果，如果大家不相信可以自己算算哈）。（1）
        设：p1,p2之间x方向的距离为 dx，y方向的距离为dy，则斜率k = dy / dx；
        我们将所求的的算式（1）乘以系数dx，命名为变量 Pi（第i步的决策参数） = dx（d_lower - d_upper） = 2*dy*xi - 2*dx*yi + c 。（2）(c=2*dy + dx(2b - 1)，c为一常数在程序计算时会省去)。
        通过算式（2）我们可以得出Pi+1(第i + 1时的决策参数) = 2 * dy * Xi+1 - 2*dx * Yi+1 + c （3）
        将算式（3）与算式（2）做差并化简后得 ：
         （4）（呼呼，终于推倒出我们要的算式了，不知道大家看懂推导过程了没，其实都很简单就是步骤多了些）
        可以通过算式（2）得出p0 = 2 dy - dx。
    之后我们就递归的调用计算决策参数的算法就可以啦，通过互换x、y的位置和坐标的位置可将其算法扩展到任意象限。
    2.Bresenham的程序实现

<div class="cnblogs_code">// 使用 Bresenham 算法画任意斜率的直线（包括起始点，不包括终止点）function Line_Bresenham(x1, y1, x2, y2, color){    var  x = x1;    var y = y1;    var dx = Math.abs(x2 - x1);    var dy = Math.abs(y2 - y1);    var s1 = x2 > x1 ? 1 : -1;    var s2 = y2 > y1 ? 1 : -1;        var interchange = false;    // 默认不互换 dx、dy    if (dy > dx)                // 当斜率大于 1 时，dx、dy 互换    {        var temp = dx;        dx = dy;        dy = temp;        interchange = true;    }        var p = 2 * dy - dx;    for(var i = 0; i < dx; i++)    {        putpixel(x, y, color);        if (p >= 0)        {            if (!interchange)        // 当斜率 < 1 时，选取上下象素点                y += s2;            else                    // 当斜率 > 1 时，选取左右象素点                x += s1;            p = p + 2 * dy - 2 * dx;        }        if (!interchange)            x += s1;                // 当斜率 < 1 时，选取 x 为步长        else            y += s2;                // 当斜率 > 1 时，选取 y 为步长        p += 2 * dy;    }}