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平面各种八分和四分区域的对称性,此算法对任意斜率的线段具有通用性。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏null的专栏

TensorFlow入门——Softmax Regression

下面的代码是利用TensorFlow实现的Softmax Regression的基本过程: ''' @author:zhaozhiyong @date:2017...

2775
来自专栏数据结构与算法

02:奇数单增序列 个人博客doubleq.win

 个人博客doubleq.win 02:奇数单增序列 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个长度为N(不...

3288
来自专栏小鹏的专栏

Tensorflow使用的预训练的resnet_v2_50,resnet_v2_101,resnet_v2_152等模型预测,训练

tensorflow 实现:Inception,ResNet , VGG , MobileNet, Inception-ResNet; 地址: https:/...

9888
来自专栏小樱的经验随笔

算法--枚举策略

枚举法的基本思想 枚举法的基本思想是根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。 枚举结构:循环...

5079
来自专栏尾尾部落

小白的机器学习实战——向量,矩阵和数组 小白的机器学习实战——向量,矩阵和数组

1294
来自专栏WeaponZhi

使用Octave来学习Machine Learning(二)

前言 上一篇我们介绍了 Octave 的一些基本情况,大家对 Octave 应该已经有了一个基本的了解,我相信看这篇文章的朋友已经在自己的电脑中安装好 Ocat...

3506
来自专栏人工智能

TensorFlow简介

TensorFlow是由Google开发的用于解决复杂数学问题的库。本篇介绍将简述TensorFlow示例,如何定义、使用张量执行数学运算,以及查看其他机器学习...

3.2K11
来自专栏林德熙的博客

C# 判断两条直线距离

d= \frac{ \left| C_1-C_2 \right|}{\sqrt{A^2+B^2}}

1162
来自专栏李智的专栏

Deep learning基于theano的keras学习笔记(1)-Sequential模型

《统计学习方法》中指出,机器学习的三个要素是模型,策略和优算法,这当然也适用于深度学习,而我个人觉得keras训练也是基于这三个要素的,先建立深度模型,然后选用...

951
来自专栏决胜机器学习

从机器学习学python(四) ——numpy矩阵基础

从机器学习学python(四)——numpy矩阵基础 (原创内容,转载请注明来源,谢谢) 一、numpy中matrix 和 array的区别 ...

4377

扫码关注云+社区