计算机图形学基础课程设计说明书

《计算机图形学基础课程设计说明书》由会员分享，可在线阅读，更多相关《计算机图形学基础课程设计说明书（22页珍藏版）》请在装配图网上搜索。

1、武汉理工大学计算机图形学基础课程设计说明书武汉理工大学课程论文课 程 名 称 计算机图形学基础 开 课 学 院 计算机科学与技术学院 指导老师姓名 学 生 姓 名 学 生 学 号 学生专业班级 软件0803班 2010 2011学年 第 2学期目录1.课程设计目的22.课程设计描述及要求33.系统开发环境34.直线的生成算法34.1 直线的DDA算法原理34.2直线的中点算法原理44.3直线的Bresenham算法原理64.4直线的生成运行结果85.圆的生成算法85.1圆的中点算法原理85.2圆的Bresenham算法原理95.3圆的DDA算法原理105.4圆的生成运行结果116.多边形的绘制

2、117.二维图形的变换127.1平移137.2旋转137.3比例147.4对称148.区域填充158.1边填充158.2种子填充159.线段裁剪以及多边形裁剪169.1线段裁剪169.2多边形裁剪1710.总结1811.参考资料18计算机图形学课程设计报告1.课程设计目的本学期系统学习了计算机图形学的概论原理，在学期期末按课程要求进行实验。通过实验，进一步理解和掌握DDA算法、Bresenham算法和中点算法，并掌握以上算法生成圆和直线等图形的基本过程，提高学生对计算机图形学的了解与运用技巧，同时通过此次课程设计提高动手实践能力与学习分析能力。2.课程设计描述及要求此次课程设计的课题为通过编程

3、，实现圆和直线等基本图形的绘制。要求用DDA算法、Bresenham算法和中点算法实现圆和直线等基本图形的绘制，并各自比较算法精度与效率的差别，实现二维图形的变换（包括平移，放缩，旋转，错切以及复合变换），用区域填充算法实现区域填充以及实现线段裁剪和多边形裁剪，并给出代码和结果截图。3.系统开发环境开发工具：VC 6.0 开发环境：MFC操作系统：Microsoft Windows 74.直线的生成算法4.1 直线的DDA算法原理这是一种用微分方程生成直线的方法。基本思想是：在生成直线的某点上增加一个同X和Y的一阶导数成比例的小步长，在这种情况下的一阶导数是连续的，而且对于和是成比例的。数值微

4、分法（Digital Differential Analyzer ,又称DDA法）推导如下：设直线的起点坐标为，终点坐标为，令： 要生成直线的微分方程是： （1） 令： =max（，）取时间步长为 ，（1）式的数值解的递推公式为： （2）根据式(2)可求得直线 上的点，但由于显示时要用象素来表示，这要用舍入法来找到最靠近直线的点。4.2直线的中点算法原理逐点比较法算法的基本思想：在绘制直线的过程中，每绘制一个点就与原直线进行比较，根据比较结果决定下一步的走向，这样一步一步逼近直线。过程如下图所示：是否结束开始 图（7） 逐点比较法执行过程该算法执行中要使得每一个绘制点尽可能靠近直线而不发生远离

5、直线的趋向。由一点到下一个点的走向方法有：在X,Y方向同时走一步,或只在X方向走一步，或只在Y方向走一步。这里讨论规定每一次只在X方向走一步，或只在Y方向走一步。假设要画直线为从O（0，0）到A（），即OA线段，如图（8）所示。OAXY图（8） 绘制OA线段绘制过程要考虑的问题如下： （1）如何计算偏差和判别偏差；（2）如何判别绘制到终点以结束算法。偏差计算公式：= = = 递推计算公式为：（1）时，走X方向一步，即：（2）时，走Y方向一步，即：上面讨论的是斜率在第一象限的情况。对于其他象限中的直线绘制算法的原理仍然是逐点比较法的基本思想。图（9）给出了在其他象限绘制直线时画笔的走向。 图（9

6、）各象限画笔走向表（10）给出了关于判别式的计算。由表（10）可见，不同象限的直线在绘制时的偏差计算以及走步方向不相同，绘制直线时只要判别出直线的象限位置，即可用相应的算法来生成直线。 线段位置 走步方向偏差值走步方向偏差值第 I 象限+X+Y第III象限 -X -Y第II 象限 +Y -X第IV 象限 -Y +X 表（10） 判别式计算有关偏差计算公式以及判别问题已解决，下来考虑如何判别终点。对于终点判别可采用计数方法。设在X，Y方向的增量分别为和，对于步长为一个象素来说，就是在生成直线过程中X方向走步，Y方向走步，因此可选计数器值为在计长方向上每走一步计数器减1，直到计数器值为零，则结束直

7、线算法。4.3直线的Bresenham算法原理 这种生成直线的算法与数值微分法类似，每次迭代在增量最大方向上均走一步，其方向由增量的正负而定；另一方向上是否也走，取决于计算出来的误差项，误差项所记录的方向同最大增量方向垂直。下面讨论误差项，如图（3）所示。DBCA图（3） 误差项计算示意图设图（3）中直线满足：0，即：0，所以X为最大增量方向，有-=1,故有每点的坐标计算： （4）因此直线上点的显示坐标为,round(),round()表示最靠近y的整数。从图（3）可以看出，对于计算出来的（，）点，的取之为；计算出来的（ ,）点，的取值为。其根据就是因为更靠近，更靠近。图（3）中A点为与的中心

8、点，计算BC长度，若值大于0.5，说明在A点之上，应取，否则取值。设误差： （5） 当，B点在A点上方，有；当0，B点在A点下方，有。由公式（4）（5）得： （6）4.4直线的生成运行结果运行结果如下：5.圆的生成算法5.1圆的中点算法原理构造圆函数 。对于圆上的点， ；对于圆外的点 ；对于圆内的点 。与中点画线法一样，构造判别式若 则应取P1为下一象素，而且再下一象素的判别式为 若 则应取P2为下一象素，而且下一象素的判别式为5.2圆的Bresenham算法原理把Bresenham关于直线生成的基本思想用于圆弧生成上，把圆分成8歌部分分别生成。圆被定义为到给定中心位置（xc,yc）距离为r的

9、点集。圆心位于原点的圆有四条对称轴x=0,y=0, x=y和x=-y。若已知圆弧上一点（x,y）,可以得到其关于四条对称轴的其它7个点，这种性质称为八分对称性。因此，只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集。假定直线斜率|k|1 。此时，只需考虑x方向每次递增1个单位，决定y方向每次递增0或1。设直线的当前点为(xi，y)当前光栅点为(xi，yi)下一个直线的点应为(xi+1，y+k)相应的光栅点或为右光栅点(xi+1，yi)（y方向递增量0）或为右上光栅点(xi+1，yi+1)（y方向递增量1）记直线与它垂直方向最近的下光栅点的误差为d，有：0d1当d0.5：下一个象素应取右光栅

10、点(xi+1，yi)当d0.5：下一个象素应取右上光栅点(xi+1，yi+1)如果直线的（起）端点在整数点上，误差项d的初值：d00 x坐标每增加1，d的值相应递增直线的斜率值k，即：dd+k一旦d1，就把它减去1，保证d的相对性，即在0-1之间。令e=d-0.5，关于d的判别式和初值可简化成：e的初值e0= -0.5，增量亦为k;e0时，取当前象素(xi,yi)的右上方象素(xi+1，yi+1)；e=0时，可任取上、下光栅点显示。 因为e是相对量，所以当e0时，表明e的计值将进入下一个参考点（上升一个光栅点），此时须：e = e 15.3圆的DDA算法原理 设圆弧满足参数方程从而得到以上可用

11、下面的差分方程来近似代替，即若点（）在圆弧上，令，则而（）近似地在圆弧上。为了使（）与（）邻近，应该使，当，可取。但是，由于，从而点（）将愈来愈偏离圆心。若令，有，于是，如果（）在上，则点也在上。这是一个非常接近圆的椭圆。其长短半轴分别为与。5.4圆的生成运行结果运行结果如下：6.多边形的绘制运行结果如下：7.二维图形的变换7.1平移7.2旋转7.3比例7.4对称8.区域填充8.1边填充8.2种子填充9.线段裁剪以及多边形裁剪9.1线段裁剪9.2多边形裁剪10.总结通过这次课程设计，使我们加深了对DDA算法、Bresenham算法和中点算法的了解和应用。增强了我们的实践能力，对以后的学习和工作

12、有很大帮助。11.参考资料1.计算机图形学（第三版）罗笑南 王若梅 编著，中山大学出版社2.计算机图形学基础 陈传波 陆枫 编著，电子工业出版社区域填充算法的探究摘要：本文旨在通过探究区域填充算法尤其是扫描线种子填充算法和种子填充算法近年来的发展状况，比较它们之间的优点与不足，对图形学的区域填充算法有更深入的理解。在准备本报告的同时还加以实验环节，选用扫描线填充算法和扫描线种子填充算法来对算法加以验证、调试和理解。关键词：区域填充扫描线算法种子点区域填充基本知识点介绍多边形扫描转换在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形，特点直

13、观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于面着色。点阵表示是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。.2区域填充算法这里的区域指已表示成点阵形式的填充图形，是像素的集合。区域有两种表示形式：内点表示和边界表示，如图2-1所示。内点表示，即区域内的所有像素有相同颜色；边界表示，即区域的边界点有相同颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。

14、 图2-1 区域的内点表示和边界表示 图2-2 4连通区域和8连通区域区域填充算法要求区域是连通的。区域可分为4向连通区域和8向连通区域，如图2-2所示。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；8向连通区域指的是从区域内每一像素出发，可通过8个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。.2.1区域填充的扫描线算法算法的基本过程如下：给定种子点（x，y），首先填充种子点所在扫描线上给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来

15、。反复这个过程，直到填充结束。.2.2区域填充的种子算法种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。扫描线种子填充算法.1扫描线种子填充算法的基本思想首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存起来。反复这个过程，直到所保存的各区段都填充完毕。.扫描线种子填充算法的特点1、该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象素，而是代

16、表一个尚未填充的区段。2、进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。3、种子出栈时，则填充整个区段。4、这样有机的结合：一边对尚未填充象素的登记（象素进栈），一边进行填充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。.基于扫描线种子填充算法的改进 由.1的描述可以看出，对种子所在扫描线的填充与搜索新种子点的操作是分别进行的，这就需要对大量的像素进行重复判读。为了对当前的扫描线填充和搜索新种子像素，需要对当前扫描线以及其相邻的上下扫描线等3条扫描线进行扫描，这就使得多数扫描线被重复扫描，即使该扫描线上的像素已经全部填充也要被再次扫描。甚

17、至扫描3次，大大降低了程序的效率和运行速度。另外，在该算法中堆栈操作频繁，每搜到一个新的填充区间就要入栈，对每一条扫描线至少有一个区间入栈每次开始另一条扫描线搜索都要先出栈，这不仅占用了大量的储存空间，还降低了算法的效率。针对重复扫描的问题，根据当前扫描线与相邻扫描线间的位置关系以及区间端点的坐标大小减少了不必要的重复扫描，缩小了重复扫描区间范围，但是所提出的算法仍然将填充与搜索新种子点的操作分别进行，没有克服堆栈频繁操作的缺点，将种子点入栈改为新旧区间端点入栈，并将区间填充与搜索新区间合并进行，进一步减少了重复扫描但是算法中并没有减少堆栈操作的频率，并且对每一条当前扫描线都要判断其相邻的两条

18、扫描线是否需要重复扫描。.种子算法的改进.1 种子算法的改进之一 算法基本思想思路是：从链队列中获得一个像素点，判断其四连通像素点，若没有填充，则填充它，并将它入队列，如此循环，直到队列空为止。对递归种子填充算法的改进之处为： 在递归种子填充算法中堆栈是系统预先设定的，其大小和存储区域已经确定，这对填充的区域大小有明显的限制，当堆栈溢出时，程序就会出错，若堆栈设定很大，又会导致在填充区域不大的情况下，浪费了很多计算机资源，本算法不使用递归，而使用链队列，是因为链队列有两个特点：一是当链队列为空时，它不占用存储空间，只有当数据入链队列时才分配存储空间给它。二是由于在定义链队列前没有限定它的大小，

19、所以从理论上看，有多大的可使用存储空间，就可以建立多大的链队列。 在递归种子填充算法中，采用的是先入栈，出栈后再填充，即当填充某像素点时，不管它的四连通点是否已被填充，都要进入堆栈，这会导致很多的冗余像素点入栈，而本文算法采用的是先填充再入链队列，在入队列之前要判断像素点是否已被填充 若已被填充才入队列 否则不予考虑。这样将会减少入队列的冗余像素，即每一个像素点只入队列一次。.2 种子算法的改进之二 以上算法的改进克服了递归种子填充算法由于一个像素点重复入栈操作而导致速度很慢的问题，但经过研究发现以上改进之后，仍存在很多冗余的检测。如图3-1所示，当像素P出队列时，要检测像素1，3，5，7的颜

20、色是否是填充色或边界色。而当像素1出队列时显然P像素已经被填充，而仍要检测像素P的颜色。同理，当像素3，5，7出队列时分别也要检测像素P的颜色，这样也会浪费一些时间。所以我们在改进一的基础上进一步提出改进二的算法。改进的思路是这样的，设置4个链队列分别记录向上、向下、向左、向右4个方向的填充新种子像素点.若当正在出队的像素点是来自于记录向上的那个队列，不要检测它的下面那个像素点，则在处理某个像素点时只要检测3个连通像素点。这里设置了4个链队列，是否增加了程序的存储开销呢？答案是否定的。因为采用的是链队列，只有当像素入队列时才会占用存储空间。经过对程序的测试可得，第一次改进时，每个像素只入队列一

21、次，同样设4个链队列，每个像素点也只入一次队列，所以总的入队列次数是一样的。第一次改进后的像素监测 程序运行调试作为本次区域填充算法探究的实践部分我选择扫描线种子填充算法和扫描线算法进行调试观测，经过查阅纸质资料、互联网相关内容，最终调试运行成功。结束语通过查阅大量的图形学区域填充相关资料，总结了近年来在区域填充方面一些算法，并且阐述各自的优劣。分别以扫描线种子填充算法和种子填充算法两条主线探究图形学方面的专家逐步改善区域填充算法提高算法效率的过程。经过对区域填充算法的进一步学习、整理和总结，更加熟悉了算法本身以及大家一直在试图改善算法的入手点。参考文献【1】 余腊生，沈德耀扫描线种子填充算法的改进【2】 谢克明.压入新旧区段的区域填充扫描线算法【3】 郭文平，龙帮强扫描线种子填充算法的改进【4】 张荣国，刘焜新区入栈的区域填充扫描线算法【5】 陈元琰，陈洪波一种基于链队列的种子填充法22