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

1、武汉理工大学课程论文课程名称 开课学院 指导老师姓名 学生姓名 学生学号 学生专业班级计算机图形学基础计算机科学与技术学院软件0803班2010 2011学年 第2学期目录 TOC o 1-5 h z .课程设计目的 3.课程设计描述及要求3.系统开发环境3.直线的生成算法3. HYPERLINK l bookmark6 o Current Document 直线的DDA算法原理.3直线的中点算法原理4直线的 Bresenham算法原理6直线的生成运行结果.8.圆的生成算法9.圆的中点算法原理9.圆的 Bresenham算法原理9圆的DDA算法原理 10圆的生成运行结果11.多边形的绘制11.

2、二维图形的变换1.3平移1.4旋转1.4比例1.5对称1.5.区域填充16边填充1.6种子填充1.6.线段裁剪以及多边形裁剪 17线段裁剪1.7多边形裁剪1.8.总结.1911参考资料19计算机图形学课程设计报告本学期系统学习了计算机图形学的概论原理， 在学期期末按课程要求进行实 验。通过实验，进一步理解和掌握 DD顺法、Bresenham算法和中点算法，并掌 握以上算法生成圆和直线等图形的基本过程， 提高学生对计算机图形学的了解与 运用技巧，同时通过此次课程设计提高动手实践能力与学习分析能力。此次课程设计的课题为通过编程，实现圆和直线等基本图形的绘制。要求用 DDA算法、Bresenham算

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

4、直线的起点坐标为(Xs，Ys),终点坐标为(Xe，Ye),令：X Xe Xs, Y Ye Ys要生成直线的微分方程是：工Xdt也Ydt令： t =max ( X , Y )取时间步长为1 t , (1)式的数值解的递推公式为：X i 1 X i X / tYi 1 Yi Y / t根据式(2)可求得直线(Xs，Ys) (Xe,Ye)上的点，但由于显示时要用象素来表 示，这要用舍入法来找到最靠近直线的点。逐点比较法算法的基本思想：在绘制直线的过程中，每绘制一个点就与原直 线进行比较，根据比较结果决定下一步的走向， 这样一步一步逼近直线。过程如 下图所示:图(7)逐点比较法执行过程该算法执行中要使

5、得每一个绘制点尽可能靠近直线而不发生远离直线的趋向。由一点到下一个点的走向方法有：在 X,Y方向同时走一步，或只在X方向走步，或只在Y方向走一步。这里讨论规定每一次只在 X方向走一步，或只在Y方向走一步。假设要画直线为从O (0,0)到A ( Xa，Ya),即OA线段，如图(8)所示YY图(8)绘制OA线段绘制过程要考虑的问题如下：(1)如何计算偏差和判别偏差;YkYYkYaXkXaYkXAXkYAXkXA偏差计算公式：Fk= tg tg递推计算公式为：Fi 0时，走X方向一步，即:Xi 1 Xi 1Y i YFi 1 Fi YaFi 0时，走Y方向一步，即:Xi 1Xi 1XiY1 Y 1F

6、i 1Fi 1FiXa上面讨论的是斜率在第一象限的情况。 对于其他象限中的直线绘制算法的原 理仍然是逐点比较法的基本思想。图(9)给出了在其他象限绘制直线时画笔的 走向。表（10）给出了关于判别式的计算。由表（10）可见，不同象限的直线在绘 制时的偏差计算以及走步方向不相同，绘制直线时只要判别出直线的象限位置， 即可用相应的算法来生成直线。线段位置走步方向偏差值Fk0走步方向偏差值Fk0k第I象限+XFk 1Fk|Ya|+YFk 1FkXA第III象限-X-Y第II象限+YFk1Fk 区|-XFk1 Fk Ml第IV象限-Y+X表（10）判别式计算有关偏差计算公式以及判别问题已解决，下来考虑如

7、何判别终点。对于终点判别可采用计数方法。设在 X, Y方向的增量分别为 X和Y, 对于步长为一个象素来说，就是在生成直线过程中X方向走X步，Y方向走 Y 步，因此可选计数器值为max（ X, Y）在计长方向上每走一步计数器减 1,直到 计数器值为零，则结束直线算法。这种生成直线的算法与数值微分法类似，每次迭代在增量最大方向上均走一 步，其方向由增量的正负而定；另一方向上是否也走，取决于计算出来的误差项, 误差项所记录的方向同最大增量方向垂直。下面讨论误差项 ，如图（3）所示xm 1,xm 1,所以X为最大增量方向,yi i V m有x i-K=1,故有每点的坐标计算：(4)Xi 1 Xi 1因

8、此直线上点的显示坐标为xi ,round(yi),round( yi)表示最靠近y的整数。从图(3)可以看出，对于计算出来的(xi , yi)点，yi的取之为yi，r;计算出来的(Xi1,yi1)点,yi1的取值为y，。其根据就是因为更靠近yi，, y更靠近V 1,r o图(3)中A点为yi1，r与yi，r的中心点，计算BC长度，若值大于0.5,说明在A点之上，应取yi 1，r ,否则取yi，r值。设误差：(Xi yi 1 yi，r 0.5 (5)当(Xi 1) 0 , B点在A点上方，有yi廿yi，r 1；当(x “0, B点在A点下方，有yi廿y，r。由公式(4) (5)得：(xi 2)y

9、i 2yi 1,r0.5yi 1 m yi 1,r0.5yi iyi,r i m 0.5(xii)0yi iyi,rm 0.5(xii)0(x d ) i 1m 1(xii)0(x i 1m)(xii)0(6)运行结果如下:构造圆函数也-*。对于圆上的点，回）=口 ；对于圆外 的点；对于圆内的点圆硬攵。与中点画线法一样，构造判别式”网M） 7（。+ 1当 - 0 6 +1 再0-0.5）2 - Z若*口则应取P1为下一象素，而且再下一象素的判别式为八尸区十22-。如（十2）、3-03-交=2弓十3若之0_,则应取P2为下一象素，而且下一象素的判别式为, 旗十布二两无+ 2尸+,-1寸- R+2

10、（% -%）+5把Bresenham关于直线生成的基本思想用于圆弧生成上，把圆分成 8歌部分分 别生成。圆被定义为到给定中心位置（xc,yc）距离为r的点集。圆心位于原点的 圆有四条对称轴x=0,y=0, x=y ft x=-y 0若已知圆弧上一点（x,y）,可以得到其关 于四条对称轴的其它7个点，这种性质称为八分对称性。因此，只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集。假定直线斜率|k|1 o此时，只需考虑x方向每次递增1个单位，决定y方向 每次递增0或1。设直线的当前点为（xi, y）当前光栅点为（xi , yi）下一个直线的点 应为（xi+1, y+k）相应的光栅点或为右光栅点

11、（xi+1 , yi）（y方向递增量0）或为右上光栅点（xi+1 , yi+1） （y方向递增量1）记直线与它垂直方向最近的下光栅点 的误差为d,有：0& d0 1当d0.5: 下一个象素应取右上光栅点（xi+1 , yi+1）如果直线的（起）端点在整数点上，误 差项d的初值：d0=0 x坐标每增加1, d的值相应递增直线的斜率值 k,即：d =+卜一旦1,就把它减去1,保证d的相对性，即在0-1之间。令e=d-0.5,关于d的判别式和初值可简化成：e的初值e0= -0.5,增量亦为k;e0时，取当前象素（xi,yi）的右上方象素（xi+1 , yi+1）；e=0时，可任取上、下光栅点显示。因

12、为e是相对量，所以当e0时，表明e的计值将进入下一个参考点（上升一 个光栅点），此时须：e = e - 1dx dyRsintdt ydtRcostdt xdtdx dyRsintdt ydtRcostdt xdt设圆弧满足参数方程 y Rsint从而得到以上可用下面的差分方程来近似代替，即若点（x1yi）在圆弧上，令txiVxiV?yi?x而（x若点（x1yi）在圆弧上，令txiVxiV?yi?x而（xi 1,yi 1 ）近似地在圆弧上为了使xi,y)xi 1，yi 1）邻近，应该使22(xi 1 xi)(yi 1 yi)2/ 2(xiy2)2R22当 2n 1 R/J2 2n，可取n22

13、。但是，由于xi12yi 12222(xiV)(xiy2) (12)(x2y：),从而点(xi 1, V 1)将愈来愈偏离圆心2、 TOC o 1-5 h z 若令 x1 k y x 1 yi %1) xi (1)yi2222222有 Xi 1xi1 yi1yi1xixi yiyi,于是，如果(为,，)在乂 xy y R222222上，则点也在x xy y R上。这是一个非常接近圆x y R的椭圆。其长短半轴分别为=与/=。II1 J12.2运行结果如下:运行结果如下:文件旧物&旧堂面V旧面画算法乜)胆充舞法(F)解闲法图几便谶算法帮用(H)五?机| 45 LI 6 .）每法萩如即工友“ I山

14、三3片用斥方3I可颔吉工讲的但】 J LJ -和姓土彩而二串七1哂n MMU 塞着MHIWMC) 4M姆J IMP降同 MKMfftt 灿炳In iu 必寸 ix+ *: : :*+*+ *:通过这次课程设计，使我们加深了对 DD顺法、Bresenham算法和中点算法 的了解和应用。增强了我们的实践能力，对以后的学习和工作有很大帮助。.计算机图形学（第三版）罗笑南王若梅编著，中山大学出版社.计算机图形学基础 陈传波陆枫编著，电子工业出版社区域填充算法的探究摘要：本文旨在通过探究区域填充算法尤其是扫描线种子填充算法和种子填充算法近年来的发展状况，比较它们之间的优点与不足，对图形学的区域填充算法

15、有更深入的理解。在准备本报告的同时还加以实验环节， 选用扫描线填充算法和 扫描线种子填充算法来对算法加以验证、调试和理解。关键词：区域填充扫描线算法种子点1区域填充基本知识点介绍1. 1多边形扫描转换在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形，特点直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内， 故不能直 接用于面着色。点阵表示是用位于多边形内的像素集合来刻画多边形。这种表示 丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形 式。光栅图形的一个基本问题是把多边形的顶点表示

16、转换为点阵表示。这种转换称为多边形的扫描转换。区域填充算法这里的区域指已表示成点阵形式的填充图形，是像素的集合。区域有两种 表示形式：内点表示和边界表示，如图2-1所示。内点表示，即区域内的所有像 素有相同颜色；边界表示，即区域的边界点有相同颜色。区域填充指先将区域的 一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。图2-1区域的内点表示和边界表示图图2-1区域的内点表示和边界表示图2-2 4连通区域和8连通区域区域填充算法要求区域是连通的。区域可分为 4向连通区域和8向连通区 域，如图2-2所示。4向连通区域指的是从区域上一点出发，可通过四个方向， 即上、下、左、右移动的组合，在不越出

17、区域的前提下，到达区域内的任意像素； 8向连通区域指的是从区域内每一像素出发，可通过8个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。区域填充的扫描线算法算法的基本过程如下：给定种子点（x, y）,首先填充种子点所在扫描线 上给定区域的一个区段，然后确定与这一区段相连通的上、 下两条扫描线上位于 给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。区域填充的种子算法种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。 如果边界是以一种颜色指定 的，则种子填充算法可逐个像素地处理直到遇到边界颜色为

18、止。2扫描线种子填充算法首先填充当前扫描线上的位于给定区域内的一区段， 然后确定与这一区段相 邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段， 如果存在，则 依次把它们保存起来。反复这个过程，直到所保存的各区段都填充完毕。1、该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象 素，而是代表一个尚未填充的区段。2、进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象 素），这样解决了堆栈溢出的问题。3、种子出栈时，则填充整个区段。4、这样有机的结合：一边对尚未填充象素的登记（象素进栈），一边进行填 充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。由2 .1

19、的描述可以看出，对种子所在扫描线的填充与搜索新种子点的操作 是分别进行的，这就需要对大量的像素进行重复判读。 为了对当前的扫描线填充 和搜索新种子像素，需要对当前扫描线以及其相邻的上下扫描线等 3条扫描线进 行扫描，这就使得多数扫描线被重复扫描，即使该扫描线上的像素已经全部填充 也要被再次扫描。甚至扫描3次，大大降低了程序的效率和运行速度。另外，在 该算法中堆栈操作频繁，每搜到一个新的填充区间就要入栈， 对每一条扫描线至 少有一个区间入栈每次开始另一条扫描线搜索都要先出栈，这不仅占用了大量的储存空间，还降低了算法的效率。针对重复扫描的问题，根据当前扫描线与相邻扫描线间的位置关系以及区间 端点的

20、坐标大小减少了不必要的重复扫描， 缩小了重复扫描区间范围，但是所提 出的算法仍然将填充与搜索新种子点的操作分别进行，没有克服堆栈频繁操作的缺点，将种子点入栈改为新旧区间端点入栈，并将区间填充与搜索新区间合并进 行，进一步减少了重复扫描但是算法中并没有减少堆栈操作的频率，并且对每一条当前扫描线都要判断其相邻的两条扫描线是否需要重复扫描。种子算法的改进之一算法基本思想思路是：从链队列中获得一个像素点，判断其四连通像素点， 若没有填充，则填充它，并将它入队列，如此循环，直到队列空为止。对递归种 子填充算法的改进之处为：在递归种子填充算法中堆栈是系统预先设定的，具大小和存储区域已经 确定，这对填充的区

21、域大小有明显的限制，当堆栈溢出时，程序就会出错，若堆 栈设定很大，又会导致在填充区域不大的情况下， 浪费了很多计算机资源，本算 法不使用递归，而使用链队列，是因为链队列有两个特点：一是当链队列为空时， 它不占用存储空间，只有当数据入链队列时才分配存储空间给它。 二是由于在定 义链队列前没有限定它的大小，所以从理论上看，有多大的可使用存储空间，就 可以建立多大的链队列。 在递归种子填充算法中，采用的是先入栈，出栈后再填充，即当填充某 像素点时，不管它的四连通点是否已被填充， 都要进入堆栈，这会导致很多的冗 余像素点入栈，而本文算法采用的是先填充再入链队列， 在入队列之前要判断像 素点是否已被填充若已被填充才入队列否则不予考虑。这样将会减少入队列的 冗余像素，即每一个像素点只入队列一次。种子算法的改进之二以上算法的改进克服了递归种子填充算法由于一个像素点重复入栈操作而 导致速度很慢的问题，但经过研究发现以上改进之后，仍存在很多冗余的检测。 如图3-1所示，当像素P出队列时，要检测像素1, 3, 5, 7的颜色是否是填充 色或边