第5章 基本图形生成算法 提出问题如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。Date1华中理工大学计算机学院 陆枫 99- 7图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。 Date2华中理工大学计算机学院 陆枫 99- 75.1 直线的扫描转换直线的绘制要求： 1.直线要直 2.直线的端点要准确，即无定向性和断裂情况 3.直线的亮度、色泽要均匀 4.画线的速度要快 5.要求直线具有不同的色泽、亮度、线型等Date3华中理工大学计算机学院 陆枫 99- 75.1.1 数值微分法(DDA法)解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。直线的微分方程：Date4华中理工大学计算机学院 陆枫 99- 7DDA算法原理： =1/max(|x|,|y|) Date5华中理工大学计算机学院 陆枫 99- 7max(|x|,|y|)=|x|，即|k|1的情况：max(|x|,|y|)=|y|，此时|k|1：Date6华中理工大学计算机学院 陆枫 99- 7程序 注意： round(x)=(int)(x+0.5)Date7华中理工大学计算机学院 陆枫 99- 7特点： 增量算法 直观、易实现 不利于用硬件实现 Date8华中理工大学计算机学院 陆枫 99- 75.1.2 中点Bresenham算法直线的方程该直线方程将平面分为三个区域： 对于直线上的点，F(x,y)=0； 对于直线上方的点，F(x,y)0； 对于直线下方的点，F(x,y)0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。Date20华中理工大学计算机学院 陆枫 99- 7改进1：令e=d-0.5 e初=-0.5， 每走一步有e=e+k。 if (e0) then e=e-1Date21华中理工大学计算机学院 陆枫 99- 7算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。Date22华中理工大学计算机学院 陆枫 99- 7改进2：用2ex来替换e e初=-x， 每走一步有e=e+2y。 if (e0) then e=e-2x2018/7/2123华中科技大学计算机学院 陆枫算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。Date24华中理工大学计算机学院 陆枫 99- 7程序几种画线算法的比较Date25华中理工大学计算机学院 陆枫 99- 75.2 圆的扫描转换解决的问题：绘出圆心在原点，半径为整数R的圆x2+y2=R25.2.1 八分法画圆八分法画圆Date26华中理工大学计算机学院 陆枫 99- 7(y,x )(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)Date27华中理工大学计算机学院 陆枫 99- 7解决问题：Date28华中理工大学计算机学院 陆枫 99- 75.2.2 简单方程产生圆弧算法原理：利用其函数方程，直接离散计算 圆的函数方程为： Date29华中理工大学计算机学院 陆枫 99- 7圆的极坐标方程为： Date30华中理工大学计算机学院 陆枫 99- 75.2.3 中点Bresenham画圆构造函数F(x,y)=x2-y2-R2。 对于圆上的点，有F(x,y)=0； 对于圆外的点，F(x,y)0； 而对于圆内的点，F(x,y)0时，下一点取Pd(xi +1,yi-1)。M的坐标为：M(xi +1,yi-0.5)当F(xM,yM)0时，取Pd(xi +1,yi-1)当F(xM,yM)=0时，约定取Pu。构造判别式：Date33华中理工大学计算机学院 陆枫 99- 7误差项的递推d0： Date34华中理工大学计算机学院 陆枫 99- 7d0： Date35华中理工大学计算机学院 陆枫 99- 7判别式的初始值Date36华中理工大学计算机学院 陆枫 99- 7算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x0； 对于椭圆内的点，F(x,y)0，取Pd(xi+1,yi-1)Date45华中理工大学计算机学院 陆枫 99- 7误差项的递推 d10：Date46华中理工大学计算机学院 陆枫 99- 7d10： Date47华中理工大学计算机学院 陆枫 99- 7判别式的初始值 再来推导椭圆弧下半部分的绘制公式原理Date49华中理工大学计算机学院 陆枫 99- 7判别式 若d20，取Pl(xi,yi-1)若d20，取Pr(xi+1,yi-1)Date50华中理工大学计算机学院 陆枫 99- 7误差项的递推 d20：Date51华中理工大学计算机学院 陆枫 99- 7d20： Date52华中理工大学计算机学院 陆枫 99- 7注意： 上半部分的终止判别 下半部分误差项的初值算法步骤：1.输入椭圆的长半轴a和短半轴b。2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.绘制点(x,y)及其在四分象限上的另外三个对称点。Date53华中理工大学计算机学院 陆枫 99- 74.判断d的符号。若d0，则先将d更新为d+b2(2x+3)， 再将(x,y)更新为(x+1,y)；否则先将d更新为 d+b2(2x+3)+a2(-2y+2)，再将(x,y)更新为(x+1,y-1)。5.当b2(x+1)0时，重复步骤7和8。否则结束。程序Date55华中理工大学计算机学院 陆枫 99- 75.4 多边形的扫描转换与区域填充多边形的扫描转换主要是通过确定穿越区域的扫描线的覆盖区间来填充，区域填充是从给定的位置开始涂描直到指定的边界条件为止。Date56华中理工大学计算机学院 陆枫 99- 75.4.1 多边形的扫描转换顶点表示用多边形的顶点序列来刻划多边形点阵表示是用位于多边形内的象素的集合来刻划多边形扫描转换多边形或多边形的填充：从多边形顶点表示到点阵表示的转换。1. 什么是多边形的扫描转换Date57华中理工大学计算机学院 陆枫 99- 72. x-扫描线算法基本思想Date58华中理工大学计算机学院 陆枫 99- 7算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤：a.求交b.排序c.交点配对d.区间填色Date59华中理工大学计算机学院 陆枫 99- 7存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。Date60华中理工大学计算机学院 陆枫 99- 7解决：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。 Date61华中理工大学计算机学院 陆枫 99- 701 111022 2填充过程实例Date62华中理工大学计算机学院 陆枫 99- 73. 改进的有效边表算法（Y连贯性算法）改进原理： 处理一条扫描线时，仅对有效边求交 利用扫描线的连贯性 利用多边形边的连贯性Date63华中理工大学计算机学院 陆枫 99- 7有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点：x ymax 1/k nextDate64华中理工大学计算机学院 陆枫 99- 7边表（Edge Table）边表的构造：(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。Date65华中理工大学计算机学院 陆枫 99- 7(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x|ymin ymax 1/k NEXT(4)同一桶中若干条边按X|ymin由小到大排序，若X|ymax 相等，则按照1/m由小到大排序。Date66华中理工大学计算机学院 陆枫 99- 7解决顶点交点计为1时的情形：Date67华中理工大学计算机学院 陆枫 99- 7Date68华中理工大学计算机学院 陆枫 99- 7Date69华中理工大学计算机学院 陆枫 99- 7算法步骤：(1)初始化：构造边表，AET表置空；(2)将第一个不空的ET表中的边与AET表合并；(3)由AET表中取出交点对进行填充。填充之后删除 y=ymax的边；(4)yi+1=yi+1,根据xi+1=xi+1/m计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表；(5)AET表不为空则转(3)，否则结束。Date70华中理工大学计算机学院 陆枫 99- 75.4.2 边缘填充算法边缘填充算法算法简单，但对于复杂图型，每一象素可能被访问多次栅栏填充算法栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。Date71华中理工大学计算机学院 陆枫 99- 7边标志算法分为两个步骤：(1)打标记(2)填充当用软件实现本算法时，速度与改进的有效边表算法相当，但本算法用硬件实现后速度会有很大提高。Date72华中理工大学计算机学院 陆枫 99- 75.4.3 区域填充区域是指已经表示成点阵形式的填充图形，它是像素集合。4-邻接点和8-邻接点Date73华中理工大学计算机学院 陆枫 99- 74-连通区域和8-连通区域把位于给定区域的边界上的象素一一列举出来的方法称为边界表示法。边界填充算法（Boundary-fill Algorithm）。枚举出给定区域内所有象素的表示方法称为内点表示。泛填充算法（Flood-fill Algorithm） Date74华中理工大学计算机学院 陆枫 99- 71. 边界填充算法算法的输入：种子点坐标(x,y)，填充色和边界颜色。栈结构实现4-连通边界填充算法的算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的4-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。Date76华中理工大学计算机学院 陆枫 99-