计算机图形学课程论文 - 基本算法研究

1、湖北大学学生课程设计（论文）题 目：基本图形生成算法研究学 号：2012 2211 0421 0026姓 名：李 鹏 飞专业年级：12 计科一班教师姓名：余 敦 辉2015年 5 月 31日目 录摘 要3引言51.概论52.直线生成算法62.1直线数值微分算法62.1.1数值微分算法基本原理62.1.2数值微分算法描述与步骤72.1.3数值微分算法结果与分析82.1.4过程小结82.2直线中点画线算法82.2.1数值微分算法基本原理82.2.2数值微分算法描述与步骤92.2.3数值微分算法结果与分析102.2.4过程小结112.3直线Breseham画线算法112.3.1数值微分算法基本原理1

2、22.3.2数值微分算法描述与步骤132.3.3数值微分算法结果与分析142.3.4过程小结143.线段裁剪153.1线段裁剪算法基本原理153.2线段裁剪算法描述与步骤163.3线段裁剪算法结果与分析163.4过程小结174.二维图形变换174.1二维图形平移变换174.1.1二维图形平移变换基本原理184.1.2二维图形平移变换算法描述与步骤184.1.3二维图形平移变换算法结果与分析184.2二维图形缩放变换194.2.1二维图形缩放变换基本原理194.2.2二维图形缩放变换算法描述与步骤204.2.3二维图形缩放变换算法结果与分析204.3二维图形对称变换214.3.1二维图形对称变换

3、基本原理214.3.2二维图形对称变换算法描述与步骤234.3.3二维图形对称变换算法结果与分析234.4二维图形旋转变换234.4.1二维图形旋转变换基本原理244.4.2二维图形旋转变换算法描述与步骤244.4.3二维图形变换算法结果与分析245.图形填充算法255.1种子填充算法255.1.1种子填充算法基本步骤255.1.2种子填充算法结果与分析255.2边标志填充算法265.2.1边标志填充算法基本步骤与代码265.2.2边标志填充算法结果与分析275.3过程小结27总结与展望28附件29摘 要本论文结合实验，主要对计算机图形学的一些基础算法做了一些介绍和研究，主要包括直线生成算法、

4、线段裁剪、二维图形变换，在实现原先算法的基础上，针对实验结果，对相应的算法做出总结和评价。【关键词】直线生成算法 线段裁剪 二维图形变换AbstractThis paper with experiment mainly gives some introductions and researches to computer graphics algorithm which includes algorithm of the generating line, algorithm of cutting a line, two-dimensional graphics transformation.

5、And according to the result of experiment, we also give some summary and evaluation to these algorithms.【keywords】algorithm of cutting a line , algorithm of the generating line , two-dimensional graphics transformation引言计算机图形学(Computer Graphics，简称CG)是一种使用数学算法将二维或三维图形转化为计算机显示器的栅格形式的科学。简单地说，计算机图形学的主要研

6、究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。图形是客观物质世界在人大脑中的反映、图形蕴含信息密度大、易于理解接受，是当今信息社会中人们用于传递信息的重要手段。计算机技术和图形的结合使得图形在深度、广度和形式上都发生了深刻的变化，其应用也波及社会的各个领域，例如在商业广告、工业控制、科学计算可视化、仿真模拟、家庭娱乐以及影视业都得到了成功的应用，显示了计算机图形学的强大生命力。计算机图形学是计算机与应用专业的专业主干课，它的重要性体现在人们越来越强烈地需要和谐的人机交互环境：图形用户界面已经成为一个软件的重要组成部分，以图形的方式来表示抽象的概

7、念或数据（可视化）已经成为信息领域的一个重要发展趋势。在近几十年来，计算机图形学领域也有了很大发展，本文作为期末结课论文，将将重点介绍和研究几种最基本的计算机图形算法。1. 概论简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。本文从计算机图形学最基础的算法入手，主要研究基于线条的信息表示，通过实验将画直线、线段裁剪、二维图形变换、区域填充4种计算机图形学中最常见的图形算法展示出来。在计算机图形学领域，已经出现了很多优秀的算法，这些算法充分考虑

8、到计算机硬件资源的限制和图形的绘制效率，通过对算法的多次优化，达到了快速、准确绘制图形和尽量少耗计算机资源的目的。本文也多次参考了这些优秀的图形算法，并将这些算法运用到本次论文的实验中，通过实验数据来比较各种算法优劣。因此，本文最大的贡献在于，通过实验将画直线、线段裁剪、二维图形变换、区域填充4种图形算法集中展现出来，在对每种算法的原理和步骤做了简要分析后，同时也对算法过程进行了分析和总结。2. 直线生成算法直线生成算法是图形算法中最基础、也是最简单的算法，其主要解决的问题是：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。对于直线生成算法，主要从以下几个方面来评价算法的优劣

9、：n 画线直n 端点准确，即无定向性和断裂情况n 直线的亮度、色泽均匀并可具有具有不同的色泽、亮度、线型n 速度快，消耗计算机资源少2.1直线数值微分算法数值微分画线算法（DDA）法是直线生成算法中最简单的一种，它是一种单步直线生成算法。它的算法是这样的：首先根据直线的斜率确定是以X方向步进还是以Y方向步进，然后沿着步进方向每步进一个点（象素），就沿另一个坐标变量k，k是直线的斜率，因为是对点阵设备输出的，所以需要对每次计算出来的一对坐标进行圆整。2.1.1数值微分算法基本原理直线的微分方程：=1/max(|x|,|y|) 下面对|k|1和|k|1的情况分别分析：max(|x|,|y|)=|x

10、|，即|k|1的情况：max(|x|,|y|)=|y|，此时|k|1：以上两种情况绘出的直线如图：2.1-22.1.2数值微分算法描述与步骤算法描述：首先根据直线的斜率确定是以X方向步进还是以Y方向步进，然后沿着步进方向每步进一个点（象素），就沿另一个坐标变量k，k是直线的斜率，因为是对点阵设备输出的，所以需要对每次计算出来的一对坐标进行圆整。算法代码：见附件 数值微分算法代码2.1.3数值微分算法结果与分析点击程序中的菜单 画线 -> dda算法,拖动鼠标左键，出现结果如图2.1-1：图2.1-1分析：数值微分法（DDA法）产生的直线比较精确，而且逻辑简单，易于用硬件实现，但是步进量x

11、，y和k必须用浮点数表示，每一步都要对x或y进行四舍五入后取整，不利于光栅化或点阵输出。2.1.4过程小结数值微分算法是一种增量算法，最易于理解和接受。但由于运算为浮点运算，也较为消耗计算机资源。2.2直线中点画线算法2.2.1数值微分算法基本原理原理：假定直线斜率K<1，且已确定点亮象素点P（Xp ,Yp ）M为中点，Q为交点现需确定下一个点亮的象素。显然可得出如下结论：若M在Q的下方，选Pu，否则选Pd2.2.2数值微分算法描述与步骤算法描述： 假设直线的起点、终点分别为：（X0,Y0),(X1,Y1) 该直线方程可表示为： F(x,y)=a*x+b*y+c （1） 其中： a=Y0

12、-Y1, b=X1-X0, c=X0*Y1-X1*Y0 当： F(Xt,Yt) = 0 (Xt,Yt) 在直线上 F(Xt,Yt) < 0 (Xt,Yt) 在直线下方 F(Xt,Yt) > 0 (Xt,Yt) 在直线上方将中点M坐标代入（1）式，并判断其符号即可确定象素点的选取。构造如下判别式： d = F(M) =F(Xi+1,Yi+0.5) =a(Xi+1)+b(Yi+0.5)+c由上式可看出，d是x,y线性函数，可推导d的增量公式当d < 0 时， 取象素Pu，此时再下一个象素的判别式为：d= F(Xi+2,Yi+1.5) = a(Xi+2)+b(Yi+1.5)+c =

13、 a(Xi+1)+b(Yi+0.5)+c+a +b = d + a + b当d>= 0时，取象素Pd，此时再下一个象素的判别式为：d= F(Xi+2,Yi+0.5) = a(Xi+2)+b(Yi+0.5)+c = a(Xi+1)+b(Yi+0.5)+c +a = d + a;d的初始值可按下式计算： d0 = F(X0+1,Y0+0.5) = a(X0+1)+b(Y0+0.5)+c = F(X0,Y0)+a+0.5b = a+0.5b 由于只用d 的符号作判断，为了只包含整数运算, 可取2d代替 d，这样可得如下中点算法程序：当d < 0 时， 取象素Pu：d = d + 2*a

14、+2* b当d>= 0时，取象素Pd：d = d +2* a;d的初始值可按下式计算： d0 = 2*a+b算法代码：见附件 中点画线算法代码2.2.3数值微分算法结果与分析点击程序中的菜单 画线 -> MDP算法,拖动鼠标左键，出现结果如图2.2-1：图2.2-1分析：中点画线算法避免了浮点数的计算，使用迭代的思想求d，因而算法效率得到很大提高。2.2.4过程小结中点画线算法理解起来稍微复杂一些，用数学推导的方法省去了大量的计算。同时，在使用这个算法的时候要注意分象限讨论。详细请参考附件中的中点画线算法代码。2.3直线Breseham画线算法Bresenham算法由Bresenh

15、am在1965年提出的一种单步直线生成算法，是计算机图形学领域使用最广泛的直线扫描转换算法。Bresenham算法的基本原理就是将光栅设备的各行各列象素中心连接起来构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直方向网格线的交点，然后确定该列象素中与此交点最近的象素。2.3.1数值微分算法基本原理图2.3-1 直线Bresenham算法示意图如图2.3-1，每个交点就代表点阵设备上的一个象素点，当算法从一个点（Xi，Yi）沿着X方向向前步进到Xi+1时，Y方向的下一个位置只可能是Yi和Yi+1两种情况，到底是Yi还是Yi+1取决于它们与精确值y的距离d1和d2哪个更小。d1 = y

16、 - Yi                                  （等式 1）d2 = Yi+1 - y            

17、                    （等式 2）当d1-d2 > 0时，Y方向的下一个位置将是Yi+1，否则就是Yi。已知直线的斜率k和在y轴的截距b，可推导出Xi+1位置的精确值y如下：y = k Xi+1 + b              

18、60;                  （等式 3） 将等式3带入d1-d2，可得到等式4：d1-d2 = 2k Xi+1 - Yi - Yi+1 + 2b                   &#

19、160;（等式 4） 根据条件，k = dy / dx，Yi+1 = Yi + 1，Xi+1 =  Xi + 1，将此三个关系带入等式4，同时在等式两边乘以dx，整理后可得到等式5：dx(d1 d2) = 2dyXi + 2dy - 2dxYi + dx(2b - 1)       （等式 5） 另ei = dx(d1 d2)，则：ei = 2dyXi + 2dy - 2dxYi + dx(2b

20、- 1) 因为图2.3-1的dx是大于0的值，因此ei的符号与(d1 d2)一致，现在将初始条件带入可得到最初的第一个判断条件e1：e1 = 2dy dx 根据Xi+1与Xi，以及Yi+1与Yi的关系，可以推出ei的递推关系：ei+1 = ei + 2dy - 2dx(yi+1 - yi)由于yi+1可能是yi，也可能是yi + 1，因此，ei+1就可能是以下两种可能，并且和yi的取值是对应的：ei+1 = ei + 2dy    （Y方向保持原值）或ei+1 =

21、ei + 2(dy dx)  （Y方向向前步进1）2.3.2数值微分算法描述与步骤算法描述：当x2 > x1，y2 > y1时Bresenham直线生成算法的计算过程如下：1、画点(x1,   y1);  计算误差初值p1=2dy-dx；    2、求直线的下一点位置：       Xi+1 = Xi+1；       如果 pi > 0   则Yi

22、+1 = Yi + 1；      否则Yi+1 = Yi；       画点(Xi+1, Yi+1 )；      3、求下一个误差pi+1；       如果  pi>0   则pi+1 = pi+2(dy dx);      否则pi+1

23、 = pi+2dy；    4、如果没有结束，则转到步骤2；否则结束算法。以上算法只支持 x2 > x1，y2 > y1的情况，为了画出各种方向的直线，就要考虑斜率为负值的情况以及x1 > x2的情况。可通过坐标交换的方法来达到达到这个要求，改进后的算法见 附件 Bresenham画线算法代码。算法代码：见附件 Bresenham画线算法代码2.3.3数值微分算法结果与分析点击程序中的菜单 画线 -> Bresenham算法,拖动鼠标左键，出现结果如图2.3-2：图2.3-2分析：Bresenham算法只实用整数计算，少

24、量的乘法运算都可以通过移位来避免，因此计算量少，效率高2.3.4过程小结Bresenham算法其实和数值微分算法原理是一样的，差别在于Bresenham算法中确定Y方向下一个点的位置的判断条件的计算方式不一样。另外，值得一提的是，为了简化程序结构，本实验在代码设计上也较多的使用 m1=(x2>=x1)?1:0 形式的语句，使得程序较为简洁。3.线段裁剪线段裁剪的基本思想是：对每条直线段p1(x1,y1)p2(x2,y2)分三种情况处理(1) 直线段完全可见，“简取”之。(2) 直线段完全不可见，“简弃”之。(3) 直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进

25、行分段，分段后重复上述处理。3.1线段裁剪算法基本原理按以下方法对区域进行编码：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，CtCbCrCl，上下右左裁剪一条线段时，先求出端点p1和p2的编码code1和code2，然后：(1)若code1|code2=0，对直线段应简取之。(2)若code1&code20，对直线段可简弃之。(3)若上述两条件均不成立。则需求出直线段与窗口边界的交点。在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。3.2线段裁剪算法描述与步骤算法描述

26、：(1)输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。(2)对p1、p2进行编码：点p1的编码为code1，点p2的编码为code2。(3)若code1|code2=0，对直线段应简取之，转(6)；否则，若code1&code20，对直线段可简弃之，转(7)；当上述两条均不满足时，进行步骤(4)。(4)确保p1在窗口外部：若p1在窗口内，则交换p1和p2的坐标值和编码。(5)按左、右、上、下的顺序求出直线段与窗口边界的交点，并用该交点的坐标值替换p1的坐标值。也即在交点s处把线段一分为二，并去掉p1s这一段。考虑

27、到p1是窗口外的一点，因此可以去掉p1s。转(2)。(6)用直线扫描转换算法画出当前的直线段p1p2。(7)算法结束。算法代码：见附件 线段裁剪区域编码算法，矩形裁剪线段算法3.3线段裁剪算法结果与分析点击程序中的菜单 画线 -> dda算法,拖动鼠标左键，出现 图3.3-1结果；然后点击，菜单中的 裁剪 ->CS_Clip ,拖动鼠标左键，出现图3.3-3结果：图3.3-1图3.3-2图3.3-3分析：1）特点：用编码方法可快速判断线段-完全可见和显然不可见。 2）特别适用两种场合： 大窗口场合（完全可见）和窗口特别小的场合(显然不可见）3.4过程小结相比于其他的迭代算法，这种裁

28、剪方法计算量较少，提高了程序执行效率。4.二维图形变换二维图形变换主要包括：平移、缩放、对称、旋转和错切，这里，本实验只要讨论前4种。这些图形变换的计算主要通过矩阵的计算来实现。T=adgbehcfi cf 用于平移图形adbe用于缩放，旋转，对称，错切 i 用于对图形整体作缩放变换4.1二维图形平移变换4.1.1二维图形平移变换基本原理平移是指将p点沿直线路径从一个坐标位置移到另一个坐标位置的重定位过程。4.1.2二维图形平移变换算法描述与步骤算法描述：在对图形做平移变换的时候，只要将图形的关键点用图形平移算法计算出来就可以绘出整个平移后的图形，从而减少了计算。算法代码：见附件 平移变换矩阵

29、计算4.1.3二维图形平移变换算法结果与分析点击菜单中 画线 -> 绘制矩形，拖动鼠标左键，绘制原始矩形；然后点击 图形变换 -> 平移变换，拖动鼠标右键，出现如图4.1-1结果：图4.1-1分析：由于平移变换是一种比较简单的变换，因此除了采用矩阵运算的方法外，可以直接采取相对坐标运算的方法，即将图形的所有坐标点向某个方向同时平移若干个像素。用数组或链表存放所有需要平移的关键点即可。4.2二维图形缩放变换4.2.1二维图形缩放变换基本原理比例变换是指对p点相对于坐标原点沿x方向放缩Sx倍，沿y方向放缩Sy倍。其中Sx和Sy称为比例系数。讨论： (1) SxSy1 时 图形不变 (2

30、) SxSy > 1 时 图形沿两轴方向等比例放大 (3) SxSy < 1 时 图形沿两轴方向等比例缩小 (4) Sx < > Sy 时 图形沿两轴方向作非均匀比例变换4.2.2二维图形缩放变换算法描述与步骤算法描述：在对图形做缩放变换的时候，只要将图形的关键点用图形缩放算法计算出来就可以绘出整个平移后的图形。为了使缩放后的矩形位置保持不变，需先将原矩形平移至原点，然后放缩，再平移后原来位置。 算法代码：见附件 缩放变换矩阵计算4.2.3二维图形缩放变换算法结果与分析点击菜单中 画线 -> 绘制矩形，拖动鼠标左键，绘制原始矩形，出现如图4.2-1结果；然后点击

31、图形变换 -> 放缩变换，拖动鼠标右键，出现如图4.2-2结果： 图4.2-1图4.2-24.3二维图形对称变换4.3.1二维图形对称变换基本原理(1) bd0, a-1, e 1 时x* -x, y* y, 以y 轴对称(2) bd0, a1, e -1 时x* x, y* -y, 以x 轴对称(3) bd0, a e -1 时 x* -x, y* -y, 以原点对称(4) bd1, ae 0 时 x* y, y* x, 以y = x 直线对称(5) bd-1, a e 0 时 x* -y, y* -x, 以y = -x 直线对称以上方法只能实现关于坐标轴和关于y = x, y = -

32、x对称，而要实现关于任意直线的对称，进行以下讨论：1而参数A , B , C 可以根据线段的起始点求出。4.3.2二维图形对称变换算法描述与步骤算法描述：根据上述图形对称变换基本原理，可以画出关于坐标轴，关于y = x, y = -x对称或任意直线的对称点。算法代码：见附件 对称变换通用方法，点A关于点1，点2画出的直线对称算法4.3.3二维图形对称变换算法结果与分析点击菜单中 画线 -> 绘制矩形，拖动鼠标左键，绘制原始矩形；然后点击 图形变换 -> 对称变换，拖动鼠标右键，出现如图4.3-1结果：图4.3-14.4二维图形旋转变换4.4.1二维图形旋转变换基本原理二维旋转是指将

33、p点绕坐标原点转动某个角度（逆时针为正，顺时针为负）得到新的点p的重定位过程。4.4.2二维图形旋转变换算法描述与步骤算法描述：根据上述图形旋转变换基本原理，可以计算出旋转后的点。算法代码：见附件 旋转变换矩阵计算4.4.3二维图形旋转变换算法结果与分析点击菜单中 画线 -> 绘制矩形，拖动鼠标左键，绘制原始矩形；然后点击 图形变换 -> 旋转变换，拖动鼠标右键，出现如图4.4-1结果：图4.4-15.图形填充算法5.1种子填充算法5.1.1种子填充算法基本步骤算法步骤:假设在多边形区域内部有一象素已知，由此出发找到区域内的所有象素。四向连通搜索填充：从区域上任意一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素。算法代码：见附件 4联通种子填充算法5.1.2种子填充算法结果与分析点击菜单中 画线 -> 绘制矩形，拖动鼠标左键，绘制原始矩形；然后点击 图形变换 -> 平移变换，拖动鼠标右键，进行平移变换，如图5.1-1；接着点击 填充-> 向右边填充，出现如图5.1-2结果：图5.1-1图5.1-25.2边标志填充算法5.2.1边标志填充算法基本步骤与代码算法步骤:1. 对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作