1、第五章第五章 基本图形生成算法基本图形生成算法12p 如何在指定的输出设备上根据坐标描述构造基如何在指定的输出设备上根据坐标描述构造基本二维几何图形本二维几何图形p 直线、圆直线、圆p 多边形域多边形域p 字符串字符串p 相关属性相关属性主要内容主要内容3o 图形的生成：是在指定的图形的生成：是在指定的输出设备上，根据坐标描输出设备上，根据坐标描述构造二维几何图形。述构造二维几何图形。o 图形的扫描转换图形的扫描转换：在光栅：在光栅显示器等数字设备上确定显示器等数字设备上确定一个最佳逼近于图形的象一个最佳逼近于图形的象素集的过程。素集的过程。图图5.1 用象素点集逼近直线用象素点集逼近直线图形
2、生成的概念图形生成的概念4直线段的扫描转换直线段的扫描转换直线段的绘制要求直线段的绘制要求DDA算法算法中点中点Bresenhan算法算法改进的改进的Bresenhan算法算法12345直线的扫描转换直线的扫描转换o 直线的绘制要求直线的绘制要求n 直线要直；直线要直；n 直线的端点要准确，无定向性无断裂；直线的端点要准确，无定向性无断裂；n 直线的亮度、色泽要均匀；直线的亮度、色泽要均匀；n 画线的速度要快；画线的速度要快；n 具有不同的色泽、亮度、线型等。具有不同的色泽、亮度、线型等。6直线的扫描转换直线的扫描转换o解决的问题解决的问题：给定直线两端点给定直线两端点P0(x0,y0)和和P
3、1(x1,y1)，画出该直线。画出该直线。o 数值微分法数值微分法o 中点中点Bresenhan算法算法o 改进的改进的Bresenhan算法算法7直线段的扫描转换直线段的扫描转换直线段的绘制要求直线段的绘制要求DDA算法算法中点中点Bresenhan算法算法改进的改进的Bresenhan算法算法12348数值微分法数值微分法(DDA法法)11yyyxxxiiii直线的微分方程：直线的微分方程：kxxyyxydxdy0101=1/max(|x|,|y|)图图5.2 DDA算法原理算法原理o max(|x|,|y|)=|x|，即即|k|1的情况：的情况：p max(|x|,|y|)=|y|，此时
4、此时|k|1：11111kyyxyyyyxxxxxxxiiiiiiii 111111iiiiiiiiyyyyyyykxxyxxxx10o 增量算法增量算法o 直观、易实现直观、易实现o 不利于用硬件实现不利于用硬件实现 数值微分法数值微分法(DDA法法)特点特点11直线段的扫描转换直线段的扫描转换直线段的绘制要求直线段的绘制要求DDA算法算法中点中点Bresenhan算法算法改进的改进的Bresenhan算法算法123412中点中点Bresenham算法算法o 直线的方程直线的方程 ,0),(0101xxyyxykbkxyyxF其中图图5.3 直线将平面分为三个区域直线将平面分为三个区域13中
5、点中点Bresenham算法算法p 算法原理：根据直线的斜率确定或选择变量在算法原理：根据直线的斜率确定或选择变量在x或或y方向上每次递增一个单位，而另一方向方向上每次递增一个单位，而另一方向的增量为的增量为1或或0，它取决于实际直线与相邻象，它取决于实际直线与相邻象素点的距离，这一距离称为素点的距离，这一距离称为误差项误差项。假定假定0k1，即即0 y/x 1，x是最大位移方向是最大位移方向图图5.4 Brensemham算法生成直线的原理算法生成直线的原理判别式：判别式：)1(5.0)5.0,1(),(bxkyyxFyxFdiiiiMM则有：则有：)0()0(1111dydyyxxiiii
6、i图图5.5 Brensemham算法生成直线的原理算法生成直线的原理d的意义的意义：)1(5.0)5.0,1(),(bxkyyxFyxFdiiiiMMQMQQMMQQMMyybkxybkxyyxFyxFd)(),(),(QMQMQMyydyydyyd000图图5.6 Brensemham算法生成直线的原理算法生成直线的原理d0(xi,yi)(xi+1,yi+0.5)(xi+2,yi+1.5)误差项的递推（误差项的递推（d=0(xi,yi)(xi+1,yi+0.5)(xi+2,yi+0.5)bxkyyxFdiiii)1(5.0)5.0,1(1kdkbxkydii12)1(5.0图图5.8 误差
7、项递推误差项递推19初始值初始值d的计算的计算kkbkxybxkyyxFd5.0 5.0 )1(5.0 )5.0,1(0000000(x0,y0)(x0+1,y0+0.5)中点中点Bresenham算法算法图图5.9 计算初值计算初值20改进：用改进：用2dx代替代替d,令令D2dx 则：则：yDkdxxdDDdyxDyxxdkdxxdDDdyxkxxdD2)(220022222)1(22002)5.0(2200中点中点Bresenham算法算法改进改进21o 输入直线的两端点输入直线的两端点P0(x0,y0)和和P1(x1,y1)。o 计算初始值计算初始值x、y、D=x-2y、x=x0、y=
8、y0。o 绘制点绘制点(x,y)。判断判断D的符号。若的符号。若D0)then e=e-10.5)(d 0.5)(d 1 111iiiiiyyyxx误差项的计算误差项的计算 d初初=0，每走一步：每走一步：d=d+k if(e0)then d=d-1改进改进2：用：用E=2ex来替换来替换e e初初=-0.5 每走一步有每走一步有e=e+k if(e0)then e=e-1 E初初=-0.5*2x=-x 每走一步有每走一步有E=(e+k)*2x=E+2y if(e0)then E=(e-1)*2x=E-2x281.输入直线的两端点输入直线的两端点P0(x0,y0)和和P1(x1,y1)。2.计
9、算初始值计算初始值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。否则结束。否则结束。改进的改进的Bresenham算法算法算法步骤算法步骤29圆的扫描转换圆的扫描转换八分法画圆八分法画圆简单方程生成圆弧简单方程生成圆弧中点中点Bresenhan算法画圆算法画圆12330圆的扫描转换圆的扫描转换o解决的问题：解决的问题：绘
10、出圆心在原点，半径为整数绘出圆心在原点，半径为整数R的圆的圆x2+y2=R2。(x,y)yy=-xy=x(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)图图5.11 八分法画圆八分法画圆32解决问题：解决问题：圆的扫描转换圆的扫描转换图图5.12 1/8圆弧圆弧33圆的扫描转换圆的扫描转换八分法画圆八分法画圆简单方程生成圆弧简单方程生成圆弧中点中点Bresenhan算法画圆算法画圆12334简单方程产生圆弧简单方程产生圆弧算法原理算法原理：利用其函数方程，直接离散计算。：利用其函数方程，直接离散计算。圆的函数方程为：圆的函数方程为：222Ryx7)-(5
11、)(2R0,x121211iiiixRroundyxx35圆的圆的极坐标方程极坐标方程为：为：sincosRyRx)sin()cos()(11111iiiiiiRroundyRroundx为一固定角度步长简单方程产生圆弧简单方程产生圆弧36圆的扫描转换圆的扫描转换八分法画圆八分法画圆简单方程生成圆弧简单方程生成圆弧中点中点Bresenhan算法画圆算法画圆12337构造函数构造函数F(x,y)=x2+y2-R2。o 对于圆上的点，有对于圆上的点，有F(x,y)=0；o 对于圆外的点，对于圆外的点，F(x,y)0；o 而对于圆内的点，而对于圆内的点，F(x,y)0时，下一点取时，下一点取Pd(x
12、i+1,yi-1)。构造判别式：构造判别式：222)5.0()1()5.0,1(),(RyxyxFyxFdiiiiMM中点中点Bresenham画圆画圆误差项的递推（误差项的递推（d0）2222)5.0()2()5.0,2(RyxyxFdiiii32)5.0(32)1()5.0()11(12222222iiiiiixdRyxxRyxd图图5.14 d0的情况的情况2222)5.1()2()5.1,2(RyxyxFdiiii5)(25)(2)5.0()1(1)5.0(2)5.0(32)1()15.0()11(1222222222iiiiiiiiiiiiyxdyxyxRyyxxRyxd误差项的递推
13、（误差项的递推（d0）图图5.15 d 0的情况的情况42判别式的初始值判别式的初始值RRRRFyxFd25.1 )5.0(1 )5.0,1()5.0,1(22000中点中点Bresenham画圆画圆改进：用改进：用d-0.25代替代替d此时有：此时有：Rddyxdddxddiii125.05)(225.0320025.0025.0dddd441.输入圆的半径输入圆的半径R。2.计算初始值计算初始值d=1-R、x=0、y=R。3.绘制点绘制点(x,y)及其在八分圆中的另外七个对称点。及其在八分圆中的另外七个对称点。4.判断判断d的符号。若的符号。若d0，则先将则先将d更新为更新为d+2x+3，
14、再将再将(x,y)更新为更新为(x+1,y)；否则先将否则先将d更新为更新为d+2(x-y)+5，再将再将(x,y)更新为更新为(x+1,y-1)。5.当当xy时，重复步骤时，重复步骤3和和4。否则结束。否则结束。程序演示程序演示中点中点Bresenham画圆画圆算法步骤算法步骤45多边形的扫描转换与区域填充多边形的扫描转换与区域填充多边形的扫描转换多边形的扫描转换区域填充区域填充多边形扫描转换与区域填充的比较多边形扫描转换与区域填充的比较相关概念相关概念123446多边形的扫描转换与区域填充多边形的扫描转换与区域填充o 多边形的扫描转换多边形的扫描转换主要是通过确定穿越区域的主要是通过确定穿
15、越区域的扫描线的覆盖区间来填充。扫描线的覆盖区间来填充。o 区域填充区域填充是从给定的位置开始涂描直到指定的是从给定的位置开始涂描直到指定的边界条件为止。边界条件为止。47多边形的扫描转换多边形的扫描转换o 顶点表示顶点表示用多边形的顶点序列来刻划多边形。用多边形的顶点序列来刻划多边形。o 点阵表示点阵表示是用位于多边形内的象素的集合来刻是用位于多边形内的象素的集合来刻划多边形。划多边形。o 扫描转换多边形扫描转换多边形：从多边形的顶点信息出发，：从多边形的顶点信息出发，求出位于其内部的各个象素，并将其颜色值写求出位于其内部的各个象素，并将其颜色值写入帧缓存中相应单元的过程。入帧缓存中相应单元
16、的过程。48多边形的扫描转换多边形的扫描转换o X扫描线算法扫描线算法o 改进的有效边表算法改进的有效边表算法o 边缘填充算法边缘填充算法49o 基本思想：按扫描线基本思想：按扫描线顺序，计算扫描线与顺序，计算扫描线与多边形的相交区间，多边形的相交区间，再用要求的颜色显示再用要求的颜色显示这些区间的所有象素。这些区间的所有象素。X扫描线算法扫描线算法原理原理图图5.16 x-扫描线算法填充多边形扫描线算法填充多边形501.确定多边形所占有的最大扫描线数，得到多边形确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大顶点的最小和最大y值（值（ymin和和ymax）。）。2.从从y=ymin
17、到到y=ymax，每次用一条扫描线进行填充。每次用一条扫描线进行填充。3.对一条扫描线填充的过程可分为四个步骤：对一条扫描线填充的过程可分为四个步骤：求交；排序；交点配对；区间填色。求交；排序；交点配对；区间填色。X扫描线算法扫描线算法算法步骤算法步骤51p 交点的取整规则：使生成的像素全部位于多边交点的取整规则：使生成的像素全部位于多边形之内。（用于直线等图元扫描转换的四舍五形之内。（用于直线等图元扫描转换的四舍五入原则可能导致部分像素位于多边形之外，从入原则可能导致部分像素位于多边形之外，从而不可用）。而不可用）。p 假定非水平边与扫描线假定非水平边与扫描线y=e相交，交点的横坐标相交，交
18、点的横坐标为为x，规则如下：，规则如下：X扫描线算法扫描线算法取整规则取整规则p规则规则1：X为小数，即交点落于扫描线上两个相邻像为小数，即交点落于扫描线上两个相邻像素之间时：素之间时：n交点位于左边界之上，向右取整；交点位于左边界之上，向右取整；n交点位于右边界之上，向左取整；交点位于右边界之上，向左取整；图图5.17 取整规则取整规则1p 规则规则2：边界上象素的取舍问题，避免填充扩大化。：边界上象素的取舍问题，避免填充扩大化。规定落在右边边界上的象素不予填充。（具体实现规定落在右边边界上的象素不予填充。（具体实现时，只要对扫描线与多边形的相交区间左闭右开）时，只要对扫描线与多边形的相交区
19、间左闭右开）图图5.18 取整规则取整规则2o 规则规则3：当扫描线与多边形顶点相交时，交点：当扫描线与多边形顶点相交时，交点的取舍，保证交点正确配对。的取舍，保证交点正确配对。图图5.19 取整规则取整规则355解决方法解决方法：当扫描线与多边形的顶点相交时，当扫描线与多边形的顶点相交时，p 若共享顶点的两条边分别落在扫描线的两边，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；交点只算一个；p 若共享顶点的两条边在扫描线的同一边，这若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。时交点作为零个或两个。X扫描线算法扫描线算法取整规则取整规则56实际处理实际处理：只要检查：只
20、要检查顶点的两条边的另外顶点的两条边的另外两个端点的两个端点的Y值，两个值，两个Y值中大于交点值中大于交点Y值的值的个数是个数是0，1，2，来，来决定取决定取0，1，2个交个交点。点。图图5.20 取整规则取整规则3X扫描线算法扫描线算法取整规则取整规则57填充过程实例填充过程实例图图5.21 与扫描线相交的多边形顶点的交点数与扫描线相交的多边形顶点的交点数X扫描线算法扫描线算法取整规则取整规则58改进的有效边表算法（改进的有效边表算法（Y连贯性算法）连贯性算法）改进原理：改进原理：p处理一条扫描线时，仅对处理一条扫描线时，仅对有效边求交。有效边求交。p利用扫描线的连贯性。利用扫描线的连贯性。
21、p利用多边形边的连贯性。利用多边形边的连贯性。图图5.22 与多边形边界相交的两条与多边形边界相交的两条连续扫描线交点的相关性连续扫描线交点的相关性59o 有效边（有效边（Active Edge）：）：指与当前扫描线相指与当前扫描线相交的多边形的边，也称为活性边。交的多边形的边，也称为活性边。o 有效边表（有效边表（Active Edge Table,AET）：）：把把有效边按与扫描线交点有效边按与扫描线交点x坐标递增的顺序存放坐标递增的顺序存放在一个链表中，此链表称为有效边表。在一个链表中，此链表称为有效边表。o 有效边表的每个结点：有效边表的每个结点：x ymax 1/k next改进的有
22、效边表算法（改进的有效边表算法（Y连贯性算法）连贯性算法）60o 首先构造一个纵向链表，链表的长度为多边形首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。为一个桶，则对应多边形覆盖的每一条扫描线。o 将每条边的信息链入与该边最小将每条边的信息链入与该边最小y坐标（坐标（ymin）相对应的桶处。也就是说，若某边的较低端点相对应的桶处。也就是说，若某边的较低端点为为ymin，则该边就放在相应的扫描线桶中。则该边就放在相应的扫描线桶中。改进的有效边表算法改进的有效边表算法构造边表构造边表
23、61o 每条边的数据形成一个结点，内容包括：该扫每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点描线与该边的初始交点x（即较低端点的即较低端点的x值），值），1/k，以及该边的最大以及该边的最大y值值ymax。x|ymin ymax 1/k NEXTo 同一桶中若干条边按同一桶中若干条边按X|ymin由小到大排序，若由小到大排序，若X|ymax 相等，则按照相等，则按照1/k由小到大排序。由小到大排序。改进的有效边表算法改进的有效边表算法构造边表构造边表解决顶点交点计为解决顶点交点计为1 1时的情形：时的情形：图图5-23 将多边形的某些边缩短以分离那些应计为将多边形的某些边缩短以
24、分离那些应计为1个交点的顶点个交点的顶点36-1/3p3p2353/4p3p485-1/2p5p4891/2p5p61122/5p2p1712-1p0p1795p0p6图图5.24 多边形多边形P0P1P2P3P4P5P6123456789101112桶(c)边表3-1/3353/485-1/2891/2p3p2p3p4p5p4p5p661122/5712-1795p2p1p0p1p0p6图图5.24 多边形多边形P0P1P2P3P4P5P665(1)初始化：构造边表，初始化：构造边表，AET表置空；表置空；(2)将第一个不空的将第一个不空的ET表中的边与表中的边与AET表合并；表合并；(3)
25、由由AET表中取出交点对进行填充。填充之后删除表中取出交点对进行填充。填充之后删除y=ymax的边；的边；(4)yi+1=yi+1,根据根据xi+1=xi+1/k计算并修改计算并修改AET表，同表，同时合并时合并ET表中表中y=yi+1桶中的边，按次序插入到桶中的边，按次序插入到AET表中，形成新的表中，形成新的AET表；表；(5)AET表不为空则转表不为空则转(3)，否则结束。，否则结束。改进的有效边表算法改进的有效边表算法算法步骤算法步骤66边缘填充算法边缘填充算法o 基本思想基本思想：按任意顺序处理多边形的每条边。：按任意顺序处理多边形的每条边。处理时，先求出该边与扫描线的交点，再对扫处
26、理时，先求出该边与扫描线的交点，再对扫描线上交点右方的所有象素取反。描线上交点右方的所有象素取反。o 算法简单，但对于复杂图型，每一象素可能被算法简单，但对于复杂图型，每一象素可能被访问多次访问多次67栅栏填充算法栅栏填充算法o 栅栏指的是一条过多边形顶点且与扫描线垂直栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。的直线。它把多边形分为两半。o 基本思想基本思想：按任意顺序处理多边形的每一条边，：按任意顺序处理多边形的每一条边，但处理每条边与扫描线的交点时，将交点与栅但处理每条边与扫描线的交点时，将交点与栅栏之间的象素取反。栏之间的象素取反。o 这种算法尽管减少了被重复访
27、问象素的数目，这种算法尽管减少了被重复访问象素的数目，但仍有一些象素被重复访问。但仍有一些象素被重复访问。68边标志算法边标志算法o 基本思想基本思想：先用特殊的颜色在帧缓存中将多边：先用特殊的颜色在帧缓存中将多边形的边界勾画出来，然后将着色的象素点依形的边界勾画出来，然后将着色的象素点依x x坐标递增的顺序配对，再把每一对象素构成的坐标递增的顺序配对，再把每一对象素构成的区间置为填充色。区间置为填充色。o 分为两个步骤：打标记；填充。分为两个步骤：打标记；填充。o 当用软件实现本算法时，速度与改进的有效边当用软件实现本算法时，速度与改进的有效边表算法相当，但本算法用硬件实现后速度会有表算法相
28、当，但本算法用硬件实现后速度会有很大提高。很大提高。69多边形的扫描转换与区域填充多边形的扫描转换与区域填充多边形的扫描转换多边形的扫描转换区域填充区域填充多边形扫描转换与区域填充的比较多边形扫描转换与区域填充的比较相关概念相关概念123470区域填充区域填充o 基本概念基本概念o 区域的表示方法区域的表示方法o 区域的分类区域的分类o 区域填充算法区域填充算法71基本概念基本概念o 区域填充区域填充是指从区域内的某一个象素点（种子是指从区域内的某一个象素点（种子点）开始，由内向外将填充色扩展到整个区域点）开始，由内向外将填充色扩展到整个区域内的过程。内的过程。o 区域区域是指已经表示成点阵形
29、式的填充图形，它是指已经表示成点阵形式的填充图形，它是相互连通的一组像素的集合。是相互连通的一组像素的集合。图图5-25 区域的概念区域的概念73o 边界表示法边界表示法：把位于给定区域的边界上的象素：把位于给定区域的边界上的象素一一列举出来的方法。一一列举出来的方法。o 边界表示法中，由于边界由特殊颜色指定，填边界表示法中，由于边界由特殊颜色指定，填充算法可以逐个象素地向外处理，直到遇到边充算法可以逐个象素地向外处理，直到遇到边界颜色为止，这种方法称为边界填充算法界颜色为止，这种方法称为边界填充算法（Boundary-fill Algorithm）。）。区域的表示方法区域的表示方法p内点表示
30、：枚举出给定区域内所有象素的表示方内点表示：枚举出给定区域内所有象素的表示方法。以内点表示法为基础的区域填充算法称为泛填法。以内点表示法为基础的区域填充算法称为泛填充算法（充算法（Flood-fill Algorithm）。图图5-26 区域的表示方法区域的表示方法75p 4-连通区域，连通区域，8-连通区域连通区域区域的分类区域的分类图图5-27 4邻接点与邻接点与8邻接点邻接点（a）4邻接点邻接点 （b）8邻接点邻接点76o 4-连通区域连通区域：从区域上的一点出发，通过访问：从区域上的一点出发，通过访问已知点的已知点的4-邻接点，在不越出区域的前提下，邻接点，在不越出区域的前提下，遍历区
31、域内的所有象素点。遍历区域内的所有象素点。o 8-连通区域连通区域：从区域上的一点出发，通过访问：从区域上的一点出发，通过访问已知点的已知点的8-邻接点，在不越出区域的前提下，邻接点，在不越出区域的前提下，遍历区域内的所有象素点。遍历区域内的所有象素点。区域的分类区域的分类图图5-28 4连通与连通与8连通区域连通区域78o 连通性：连通性：4连通可看作连通可看作8连通区域，但对边界连通区域，但对边界有要求。有要求。o 对边界的要求。对边界的要求。4连通与连通与8连通区域的区别连通区域的区别图图5-29 4连通与连通与8连通区域连通区域79区域填充算法区域填充算法p 区域填充算法（边界填充算法
32、和泛填充算法）区域填充算法（边界填充算法和泛填充算法）是根据区域内的一个已知象素点（种子点）出是根据区域内的一个已知象素点（种子点）出发，找到区域内其他象素点的过程，所以把这发，找到区域内其他象素点的过程，所以把这一类算法也成为一类算法也成为种子填充算法种子填充算法。80区域填充算法区域填充算法边界填充算法边界填充算法o 算法的输入算法的输入：种子点坐标：种子点坐标(x,y)，填充色以及边填充色以及边界颜色。界颜色。o 利用堆栈实现简单的种子填充算法利用堆栈实现简单的种子填充算法 算法从种子点开始检测相邻位置是否是边界算法从种子点开始检测相邻位置是否是边界颜色，若不是就用填充色着色，并检测该象
33、素颜色，若不是就用填充色着色，并检测该象素点的相邻位置，直到检测完区域边界颜色范围点的相邻位置，直到检测完区域边界颜色范围内的所有象素为止。内的所有象素为止。81栈结构实现栈结构实现4-连通边界填充算法的连通边界填充算法的算法步骤算法步骤为：为：种子象素入栈；当栈非空时重复执行如下三步种子象素入栈；当栈非空时重复执行如下三步操作：操作：(a)栈顶象素出栈；栈顶象素出栈；(b)将出栈象素置成填充色；将出栈象素置成填充色；(c)检查出栈象素的检查出栈象素的4-邻接点，若其中某个象素点不邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。是边界色且未置成多边形色，则把该象素入栈。区域
34、填充算法区域填充算法边界填充算法边界填充算法82栈结构实现栈结构实现8-8-连通边界填充算法的连通边界填充算法的算法步骤算法步骤为：为：种子象素入栈；当栈非空时重复执行如下三步操作：种子象素入栈；当栈非空时重复执行如下三步操作：(a)a)栈顶象素出栈；栈顶象素出栈；(b)b)将出栈象素置成填充色；将出栈象素置成填充色；(c)c)检查出栈象素的检查出栈象素的8-8-邻接点，若其中某个象素点不邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。是边界色且未置成多边形色，则把该象素入栈。区域填充算法区域填充算法边界填充算法边界填充算法83区域填充算法区域填充算法边界填充算法边界填充算
35、法p 可以用于填充带有内孔的平面区域。可以用于填充带有内孔的平面区域。p 把太多的象素压入堆栈，降低了效率，同时需把太多的象素压入堆栈，降低了效率，同时需要较大的存储空间。要较大的存储空间。p 递归执行，算法简单，但效率不高，区域内每递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进一象素都引起一次递归，进/出栈费时费内存。出栈费时费内存。p 通过沿扫描线填充水平象素段，来代替处理通过沿扫描线填充水平象素段，来代替处理4-邻接点和邻接点和8-邻接点。邻接点。84区域填充算法区域填充算法边界填充算法边界填充算法o 扫描线种子填充算法：扫描线种子填充算法：扫描线通过在任意不扫描线通过
36、在任意不间断扫描线区间中只间断扫描线区间中只取一个种子象素的方取一个种子象素的方法使堆栈的尺寸极小法使堆栈的尺寸极小化。不间断区间是指化。不间断区间是指在一条扫描线上的一在一条扫描线上的一组相邻象素。组相邻象素。图图5-30 扫描线种子填充算法扫描线种子填充算法85区域填充算法区域填充算法边界填充算法边界填充算法p 基本过程：当给定种子点时，首先填充种子点基本过程：当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反位
37、于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。复这个过程，直到填充结束。图图5-31 扫描线种子填充算法过程扫描线种子填充算法过程87区域填充算法区域填充算法泛填充算法泛填充算法o 算法的输入：种子点坐标算法的输入：种子点坐标(x,y)，填充色和内部填充色和内部点的颜色。点的颜色。o 算法原理：算法从指定的种子算法原理：算法从指定的种子(x,y)开始，用所开始，用所希望的填充颜色赋给所有当前为给定内部颜色希望的填充颜色赋给所有当前为给定内部颜色的象素点。的象素点。88o 种子象素入栈；栈非空时重复执行如下三步操作：种子象素入栈；栈非空时重复执行如下三步操作：(1)栈顶象素出栈
38、；栈顶象素出栈；(2)将出栈象素置成填充色；将出栈象素置成填充色；(3)检查出栈象素的检查出栈象素的8-邻接点，若其中某个象邻接点，若其中某个象素点不是给定内部点的颜色且未置成新的填充色，素点不是给定内部点的颜色且未置成新的填充色，则把该象素入栈。则把该象素入栈。区域填充算法区域填充算法泛填充算法泛填充算法89o 当以边界表示时，当以边界表示时，4-连通边界填充算法只能填连通边界填充算法只能填充充4-连通区域，连通区域，8-连通边界填充算法也只能填连通边界填充算法也只能填充充8-连通区域。连通区域。o 当以内点表示时，当以内点表示时，8-连通泛填充算法可以填充连通泛填充算法可以填充8-连通区域
39、也可以填充连通区域也可以填充4-连通区域，当然连通区域，当然4-连通泛填充算法还是只能填充连通泛填充算法还是只能填充4-连通区域。连通区域。区域填充算法区域填充算法泛填充算法泛填充算法90多边形的扫描转换与区域填充多边形的扫描转换与区域填充多边形的扫描转换多边形的扫描转换区域填充区域填充多边形扫描转换与区域填充的比较多边形扫描转换与区域填充的比较相关概念相关概念123491相同点：相同点：n 都是光栅图形面着色，用于真实感图形显示。都是光栅图形面着色，用于真实感图形显示。n 可相互转换。可相互转换。多边形扫描转换与区域填充方法比较多边形扫描转换与区域填充方法比较92多边形扫描转换与区域填充方法
40、比较多边形扫描转换与区域填充方法比较o 基本思想不同基本思想不同：前者将顶点表示转换成点阵表：前者将顶点表示转换成点阵表示，而后者只改变区域内填充颜色，没有改变示，而后者只改变区域内填充颜色，没有改变表示方法。表示方法。o 对边界的要求不同对边界的要求不同：前者只要求扫描线与多边：前者只要求扫描线与多边形边界交点个数为偶数。后者则要求区域封闭，形边界交点个数为偶数。后者则要求区域封闭，防止递归填充跨界。防止递归填充跨界。o 基本的条件不同基本的条件不同：前者是从边界顶点信息出发，：前者是从边界顶点信息出发，而后者从区域内种子点开始算法。而后者从区域内种子点开始算法。93多边形的扫描转换与区域填
41、充多边形的扫描转换与区域填充多边形的扫描转换多边形的扫描转换区域填充区域填充多边形扫描转换与区域填充的比较多边形扫描转换与区域填充的比较相关概念相关概念123494相关概念相关概念内外测试内外测试图图532 不自交的多边形与自相交的多边形不自交的多边形与自相交的多边形95o 奇奇-偶规则偶规则（Odd-even RuleOdd-even Rule）从任意位置从任意位置p p作一条射线，若与该射线相交作一条射线，若与该射线相交的多边形边的数目为奇数，则的多边形边的数目为奇数，则p p是多边形内部是多边形内部点，否则是外部点。点，否则是外部点。相关概念相关概念内外测试内外测试96非零环绕数规则非零
42、环绕数规则（Nonzero Winding Number Rule）o 首先使多边形的边变为矢量。首先使多边形的边变为矢量。o 将环绕数初始化为零。将环绕数初始化为零。o 再从任意位置再从任意位置p作一条射线。当从作一条射线。当从p点沿射线方向移动点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加的边从右到左穿过射线时，环绕数加1，从左到右时，从左到右时，环绕数减环绕数减1。o 处理完多边形的所有相关边之后，若环绕数为非零，处理完多边形的所有相关边之后，若环绕数为非零，则则p为内部点，否则，为内部点，否则
43、，p是外部点。是外部点。相关概念相关概念内外测试内外测试97o 两种规则的比较两种规则的比较相关概念相关概念内外测试内外测试98字符处理字符处理点阵字符点阵字符矢量字符矢量字符1299字符处理字符处理o A S C I I 码：码：“美 国 信 息 交 换 用 标 准 代 码美 国 信 息 交 换 用 标 准 代 码集集”(American Standard Code for Information Interchange)，简称简称ASCII码。码。o 国际码：国际码：“中华人民共和国国家标准信息交换中华人民共和国国家标准信息交换编码，简称为国际码，代号编码，简称为国际码，代号GB23128
44、0。o 字库：字库中储存了每个字符的图形信息。字库：字库中储存了每个字符的图形信息。o 矢量字库和点阵字库。矢量字库和点阵字库。100o 在点阵表示中，每个字符由一个点阵位图来在点阵表示中，每个字符由一个点阵位图来表示。表示。o 显示时：形成字符的象素图案。显示时：形成字符的象素图案。字符处理字符处理点阵字符点阵字符图图5-33 字符字符A的点阵表示的点阵表示101特点：特点：（1）定义和显示直接、简单。）定义和显示直接、简单。（2）存储需要耗费大量空间。）存储需要耗费大量空间。解决方法：解决方法：（1）从一组点阵字符生成不同尺寸和不同字体）从一组点阵字符生成不同尺寸和不同字体的其他字符。的其
45、他字符。（2）采用压缩技术）采用压缩技术字符处理字符处理点阵字符点阵字符102字符处理字符处理点阵字符点阵字符矢量字符矢量字符12103o 矢量字符采用直线和曲线段来描述字符形状，矢量字符采用直线和曲线段来描述字符形状，矢量字符库中记录的是笔划信息。矢量字符库中记录的是笔划信息。o 显示时：解释字符的每个笔划信息。显示时：解释字符的每个笔划信息。字符处理字符处理矢量字符矢量字符图图5-34 字符字符A的矢量表示的矢量表示104o 常用的矢量字符表示：轮廓字型法常用的矢量字符表示：轮廓字型法o 轮廓字型法采用直线或二、三次曲线的集合来轮廓字型法采用直线或二、三次曲线的集合来描述一个字符的轮廓线，
46、轮廓线构成了一个或描述一个字符的轮廓线，轮廓线构成了一个或若干个封闭区域，显示时只要填充这些区域就若干个封闭区域，显示时只要填充这些区域就可产生相应的字符。可产生相应的字符。o 显示时可以显示时可以“无极放缩无极放缩”o 占用空间少，美观，变换方便占用空间少，美观，变换方便字符处理字符处理矢量字符矢量字符105属性处理属性处理线性和线宽线性和线宽字符属性字符属性区域填充属性区域填充属性123106o 图素或图段的外观由其属性决定。图素或图段的外观由其属性决定。o 图形软件中实现属性选择的方法是提供一张系图形软件中实现属性选择的方法是提供一张系统统当前属性值表当前属性值表，通过调用标准函数提供属
47、性，通过调用标准函数提供属性值表的设置和修改。进行扫描转换时，系统使值表的设置和修改。进行扫描转换时，系统使用属性值表中的当前属性值进行显示和输出。用属性值表中的当前属性值进行显示和输出。属性处理属性处理107o 线型的显示可用象素段方法实现线型的显示可用象素段方法实现o 针对不同的线型，画线程序沿路径输出一些连针对不同的线型，画线程序沿路径输出一些连续象素段，在每两个实心段之间有一段中间空续象素段，在每两个实心段之间有一段中间空白段，他们的长度（象素数目）可用象素模板白段，他们的长度（象素数目）可用象素模板(pixel mask)指定。指定。o 存在问题：如何保持任何方向的划线长度近似存在问
48、题：如何保持任何方向的划线长度近似地相等地相等线型处理线型处理108o 可根据线的斜率来调整实心段和中间空白段的可根据线的斜率来调整实心段和中间空白段的象素数目象素数目线型处理线型处理图图5-35109o 线刷子和方刷子处理线宽线刷子和方刷子处理线宽o 线刷子：垂直刷子、水平刷子线刷子：垂直刷子、水平刷子线宽处理线宽处理线刷子线刷子图图5-36110特点：特点：o 实现简单、效率高。实现简单、效率高。o 斜线与水平斜线与水平(或垂直或垂直)线不一样粗。线不一样粗。o 当线宽为偶数个象素时，线的中心将偏移半个象当线宽为偶数个象素时，线的中心将偏移半个象素。素。o 利用线刷子生成线的始末端总是水平
49、或垂直的，利用线刷子生成线的始末端总是水平或垂直的，需要添加需要添加“线帽（线帽（line cap）”线宽处理线宽处理线刷子线刷子111o 方帽：调整端点位置，使粗线的显示具有垂直于方帽：调整端点位置，使粗线的显示具有垂直于线段路径的正方形端点。线段路径的正方形端点。o 凸方帽：简单将线向两头延伸一半线宽并添加方凸方帽：简单将线向两头延伸一半线宽并添加方帽。帽。o 圆帽：通过对每个方帽添加一个填充的半圆得到圆帽：通过对每个方帽添加一个填充的半圆得到线宽处理线宽处理线刷子线刷子112线宽处理线宽处理线刷子线刷子图图5-37 线帽线帽113o 当比较接近水平的线与比较接近垂直的线汇合当比较接近水平
50、的线与比较接近垂直的线汇合时，汇合处外角将有缺口时，汇合处外角将有缺口线宽处理线宽处理线刷子线刷子图图5-38 线刷子产生的缺口线刷子产生的缺口114o 解决：斜角连接（解决：斜角连接（miter join）、）、圆连接（圆连接（round join）、）、斜切连接（斜切连接（bevel join）线宽处理线宽处理线刷子线刷子图图5-39 解决线刷子产生的缺口解决线刷子产生的缺口115o方方刷子绘制的线条（斜线）比用刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些线刷子所绘制的线条要粗一些o方刷子绘制的斜线与水平（或垂方刷子绘制的斜线与水平（或垂直）线不一样粗直）线不一样粗o方刷子绘制的线
