002计算机图形学之直线画线算法

002计算机图形学之直线画线算法

我们知道直线方程的斜截式是如下的样子:

y = kx +b

在显示器上显示直线的话,如果使用如上的方程,每描一个点

  1. 需要进行一次浮点乘法,一次浮点加法,和取整操作。

DDA算法 digital differential analyzer

对斜截式进行转换成如下:

$y_{k+1}=y_{k}+m$

由此我们可以根据起点依次推算到最后一个点,实现如下:

    inline int round(const float a) { return int(a + 0.5); }

    void lineDDA(int x0, int y0, int xEnd, int yEnd)
    {

        int dx = xEnd - x0, dy = yEnd - y0, steps, k;
        float xIncrement, yIncrement, x = x0, y = y0;

        if (fabs(dx) > fabs(dy))
          steps = fabs(dx);
        else
          steps = fabs(dy);

        xIncrement = float(dx) / float(steps);
        yIncrement = float(dy) / float(steps);

        //SetPixel(round(x), round(y));
        for (k = 0; k < steps; k++) {
          x += xIncrement;
          y += yIncrement;
          //SetPixel(round(x), round(y));
        }
    }

优点

取消了乘法,计算速度更快。

缺点

  1. 浮点增量连续增加,取证误差会积累
  2. 取整操作和浮点运算仍然十分耗时

Bresenham画线算法

主要思想是,由于我们在缓存区上画点,全部是整数。那么在画线的时候,当斜率k小于1的时候,下一个点是取(x+1,y+1)还是(x+1,y)取决于点(x+1,y+0.5)是在该直线的上方或者下方,从而将可以通过判断一个参数的的符号来得到下一个点的位置,提高了代码的效率。

算法可以表达为如下:

|m|<1 时的Bresenham画线算法

  1. 输入线段的两个端点,并将左端点存储在(x0,y0)中;

  2. 将(x0,y0)装入帧缓存,绘制第一个点;

  3. 计算常量△x, △y 2△y 和2△y-2△x,并得到决策参数的第一个值:

    $p_0 = 2△y - △x$

  4. 从k=0开始,如果pk<0,则下一个点是(/x_k+1,yk),并且

    $p_{k+1} = p_k + 2△y$

    否则,下一个绘制点是(xk+1,yk+1),并且

    $p_{k+1} = p_k+2△y-2△x$

  5. 重复步骤4,共△x-1次。

考虑到xy平面各种八分和四分区域的对称性,此算法对任意斜率的线段具有通用性。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 定点小数运算 来自:http://www.eepw.com.cn/article/17893.htm 在DSP世界...
    郝宇峰阅读 9,378评论 0 2
  • 关于CoreAnimation CoreAnimation是苹果提供的一套基于绘图的动画框架,下图是官方文档中给出...
    正谦阅读 3,505评论 3 15
  • 贪心算法 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上...
    fredal阅读 9,292评论 3 52
  • 有毒……刚才在机场见识了一位完美的“四头身”比例的妹妹(大姐?),四部分分别是 头,上身,腿,鞋跟…………鸡立鹤群...
    吴凡风之翼阅读 854评论 0 0
  • 林则徐诗
    书痴_33ee阅读 295评论 2 7