计算机图形学 学习笔记（一）：概述，直线扫描转换算法：DDA，中点画线算法，Bresenham算法

本笔记基于 http://www.icourse163.org/learn/CAU-45006?tid=1001746004#/learn/announce

感谢中国农大 赵明老师的分享~

现在我要为我自己走向游戏编程打下基石~

《计算机图形学》是计算机、地理信息系统、应用数学、机械、建筑等专业本科教学中的一门重要的专业基础课

如图像处理、模式识别、多媒体技术、计算机视觉等的基础

在CAD/CAM、计算机动画、系统环境模拟、地理信息系统、计算机艺术、真实感图形显示、科学计算的可视化、3D打印的等领域都有重要的应用

该门课程使学生了解计算机图形学的发展、掌握图形学的基本原理、算法和实现技术。学会基本的图形软件开发技术，为进一步学习后续课程打下良好的基础。

参考书籍：

简单来说，计算机图形是计算机产生的图像。

定义：计算机图形学就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法

如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法，构成了计算机图形学的主要研究内容。

图形硬件：研究图形要有基本的支撑硬件，包括图形加速卡、显示器、图形输出设备等等。

一般来说，要在计算机上生成一副表示物体的图形，有三个步骤

造型技术 在计算机中建立索要生成图像的物体的模型，即给出表示该物体的集合数据和拓扑关系。

光照模型 自然光照现象是由一些物理学定律所决定的，而这些物理学定律又非常复杂 所以，希望用一些简单的数学模型来近似、代替那些物理学的模型，为模拟物体表面的光照物理现象的数学模型叫光照模型

绘制（渲染）技术 第三步是选择适当的绘制算法来把这个场景画（渲染）出来。就是将模型真实性显示在屏幕上。 渲染一幅三维物体图像所涉及的知识、实际上就是计算机图形中每个像素看上去应该是什么颜色的问题。这很大程度上取决于不同的光照模型。 计算机屏幕是由像素构成的，像素作为构成图形的基本单位。为了在屏幕上显示一幅图形，就必须研究在哪些像素上生成图形，就必须有一套针对光栅显示器生成图形的算法。

要了解一门学科的发展，最好的就是了解它的发展历史 （百度去吧少年们）

随着光栅显示器的出现，为了在计算机上处理、显示图形，需要发展一套与之相适应的算法：光栅图形学算法。

光栅图形算法多数属于计算机图形的底层算法，很多图形学的基本概念和思想都在这一章。

光栅图形学算法的研究内容

在数学上，直线上的点有无穷多个。但当在计算机光栅显示器屏幕上表示这条直线时需要做一些处理（因为光栅显示器是由一个个像素点构成的，而像素又是有限的）

为了在光栅显示器上用有限的点逼近无限的点构成的直线，需要知道这些像素点的x,y坐标

如何把数学上的一个点扫描转换成一个频幕像素点？（因为像素点都是整数，所以我要对点进行取整处理，x和y都要是整数）

y=kx+b

直线是最基本的图形，一个动画或真实感图形往往需要调用成千上万次画线程序，因此直线算法的好坏与效率将直接影响图形的质量和显示速度。

回顾一下刚才的算法：

y=kx+b（直线斜截式方程）

这个算法，有乘法运算和加法运算，还有后期的取整运算。

为了提高效率，把计算量减下来，关键问题就是如何把乘法取消？（因为计算机中加减乘除，加法的运算效率最快）

为了提高效率，把乘法取消。我们需要学习三个著名的常用算法。

直线绘制的三个著名的常用算法

一、数值微分法DDA

引进图形学中一个很重要的思想—增量思想。

注：之所以能写成是因为数学上的点要转换成像素点，因此x和y都是整数，而像素最小的单位为1，直线肯定的点与点之间肯定不会隔多远，因此默认相隔一个像素

这样也就是说

例子：

【思考题】 DDA画直线算法：x每递增1，y递增斜率k。是否适合任意斜率的直线？

（1） | k | 1 时， 如果K>1，会导致光栅点太稀了！

除开起点和终点，中间只有1个点，而1个点完全无法表达直线的趋势。

那么如何解决K>1时的直线扫描算法呢？

采用增量思想的DDA算法，直观、易实现，每计算一个像素坐标，只需计算一个加法。

这个算法是否最优呢？若非最优，如何改进？

（我们在2.1中已经知道DDA不适合于斜率k>1的情况）

（1）改进效率 这个算法每步只做一个加法，能否再提高效率呢？

计算机运行最快的就是加法。

但是加法分为整数加法和浮点加法。

一般情况下k与k都是小数，而且每一步运算都要对y进行四舍五入后取整。

唯一改进的途径就是把浮点运算变成整数加法。

（2）改善直线方程类型 这样就引出了中点画线算法~~~

直线的一般式方程：

这个方程把屏幕分成3部分

思想：每次在最大位移方向（最大位移发现就是+1，到达屏幕的另一部分）上走一步，而另一个方向是走还是不走要取决于中点误差项的判断（两个方向就x和y）。

假定：0