《计算机图形学chap5基本图形生成算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算机图形学chap5基本图形生成算法ppt课件.ppt（158页珍藏版）》请在三一办公上搜索。
1、计算机图形学基础,华东理工大学计算机系 谢晓玲,2,如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。,第五章 基本图形生成算法,3,图形生成的概念直线段的扫描转换圆的扫描转换多边形的扫描转换与区域填充属性处理反走样技术在OpenGL中绘制图形,第五章 基本图形生成算法,4,图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。,图5.1 用象素点集逼近直线,图形生成的概念,5,5.1 直线的扫描转换,线画图元的扫描转换计算出落在线段上或充分靠近它
2、的一串像素，并以此像素集近似代替连续直线在屏幕上显示的过程。直线的绘制要求 （1）直线要直； （2）直线的端点要准确，无定向性无断裂； （3）直线的亮度、色泽要均匀； （4）画线的速度要快； （5）具有不同的色泽、亮度、线型等。,6,直线的扫描转换,解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。数值微分法（Digital Differential Analyzer, DDA）中点Bresenhan算法改进的Bresenhan算法,数值微分法数值微分法即DDA(Digital Differential Analyzer)算法，是根据直线的微分方程来计算x或y生成直
3、线的扫描转换算法。 在一个坐标轴上以单位间隔对线段取样, 以决定另一个坐标轴方向上最靠近理想线段的整数值。数值微分法的本质，是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。,数值微分法(DDA法),8,数值微分法(DDA法),直线的微分方程：,=1/max(|x|,|y|),图5.2 DDA算法原理,max(|x|,|y|)=|x|，即|k|1的情况：,max(|x|,|y|)=|y|，此时|k|1：,数值微分法步骤：给定：两个端点P0(x0,y0)和P1(x1,y1)，则：dx=(x1-x0)；dy=(y1-y0);根据|dx|、|dy|，哪个大，哪个为步长参
4、数：当|dx|dy|，即|m|x1，即直线从右到左，则x=-1， y=-m当|dx|dy|，即|m|1时， 若x0 x1，即直线从右到左，则y=-1， x=-1/m,数值微分法(DDA法),void DDA_Line(int x0,int y0,int x1,int y1,int color) int i； float dx, dy, length,x,y; if (fabs(x1-x0)=fabs(y1-y0)length=fabs(x1-x0); elselength=fabs(y1-y0); dx = (x1-x0)/length; dy=(y1-y0)/length; i=1;x= x
5、0;y= y0; while(i=length) PutPixel (int(x+0.5), int(y+0.5), color); x=x+dx; y=y+dy; i+; ,x int(y+0.5) y+0.50 0 0+0.51 0 0.4+0.52 1 0.8+0.53 1 1.2+0.54 2 1.6+0.55 2 2.0+0.5,直线段的DDA扫描转换,举例: 线段P0(0,0)和P1(5,2)的DDA方法扫描转换。,12,增量算法：加法+取整直观、易实现x与dx、y与dy用浮点数表示，每一步要进行四舍五入后取整，不利于硬件实现。,数值微分法(DDA法)特点,13,中点Bresenh
6、am算法,算法原理：根据直线的斜率确定或选择变量在x或y方向上每次递增一个单位，而另一方向的增量为1或0，它取决于实际直线与相邻象素点的距离，这一距离称为误差项。,14,中点Bresenham算法,直线的方程,图5.4 直线将平面分为三个区域,假定0k1，即0 y/ x 1，x是最大位移方向，则每次x加1，若M在Q下放，y加1（取Pu)；若M在Q上放，取y加0（取Pd)。,图5.5 Brensemham算法生成直线的原理,判别式：,则有：,图5.5 Brensemham算法生成直线的原理,d的意义：d=F(xM,yM)=F(xi+1,yi+0.5)=yi+0.5-k(xi+1)-b =yi+0
7、.5-k(xi+1)+b =yM-yQ 这里：yQ= k(xi+1)+b、yM = yi+0.5,图5.5 Brensemham算法生成直线的原理,误差项的递推（d10）,图5.6 误差项递推(a),误差项的递推（d10）,图5.6 误差项递推(b),20,初始值d的计算,中点Bresenham算法,图5.9 计算初值,21,改进：用2dx代替d ,令D2dx 则：,中点Bresenham算法改进,22,输入直线的两端点P0(x0,y0)和P1(x1,y1)。计算初始值x、y、D=x-2y、x=x0、y=y0。绘制点(x,y)。判断D的符号。若D0，则(x,y)更新为(x+1,y+1)，D更新
8、为D+2x-2y；否则(x,y)更新为(x+1,y), D更新为D-2y。当直线没有画完时，重复上一步骤，否则结束。0K1时Bresenham算法程序演示,中点Bresenham算法算法步骤,例：已知：P0（0,0) P1（5,2)dy= y1-y0=2, dx= x1-x0 = 5d0 =dx-2dy = 1, 令：d1=2dy =4, d2=2(dx - dy)=6i(xi,yi) di (xi+1,yi+1 ) di+10(0,0) 1 (1,0) di-d1=-31(1,0) -3 (2,1) di+d2=32(2,1) 3 (3,1) di-d1=-13(3,1) -1 (4,2)
9、di+d2=54(4,2) 5 (5,2),中点Bresenham算法,思考讨论：斜率不同时： 以上讨论的是 0 k 1 的情况，即 0yx 的情况； 若是 0 xy （即k 1）的情况，则需将 x 和 y 的位置交换。方向不同时： 若y0，将算法中的 yy1换成yy1； 若x0，将算法中的 xx1换成xx1。,中点Bresenham算法,25,改进的Bresenham算法,假定直线段的0k1,图5.8 改进的Brensemham算法绘制直线的原理d：交点与网格线之间的误差,改进的Bresenham算法,27,误差项的计算d初=0， 每走一步：d=d+k 一旦y方向上走了一步，d=d-1,改进
10、的Bresenham算法原理,改进1：令e=d-0.5,e初=-0.5，每走一步有e=e+k。if (e0) then e=e-1;y+,误差项的计算d初=0，每走一步：d=d+k if (d0.5) then d=d-1;y+;,仍然存在小数和除法计算k。,改进2：用E=2ex来替换e,e初=-0.5每走一步有e=e+kif (e0) then e=e-1;y+;,E初=-0.5*2x=-x每走一步有E=(e+k)*2x=E+2y if (e0) then E=(e-1)*2x=E-2x;y+;,30,1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-x
11、、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算法算法步骤,例：已知：P0（0,0) P1（5,2)dy= y1-y0=2, dx= x1-x0 = 5e0 =-dx = -5, 令：2dy =4, 2dx=10i(xi,yi) ei e+2dy (xi+1,yi+1 ) e-2dx0(0,0) -5 -1 (1,0)1(1,0) -1 3 (2,1) -7 2(2,1) -7 -3
12、 (3,1) 3(3,1) -3 1 (4,2) -94(4,2) -9 -5 (5,2),改进的Bresenham算法,32,5.2 圆的扫描转换,为了方便起见，只考虑圆心中心在原点、半径为整数R的圆x2+y2=R2 。,图5.9 八分法画圆,Void cirput(int x0,int y0,int x,int y,int color) PutPixel(x0+x,y0+y,color); PutPixel(x0+y,y0+x,color); PutPixel(x0+y,y0-x,color); PutPixel(x0+x,y0-y,color); PutPixel(x0-x,y0-y,c
13、olor); PutPixel(x0-y,y0-x,color); PutPixel(x0-y,y0+x,color); PutPixel(x0-x,y0+y,color);,34,解决问题：只要扫描转换八分之一圆弧（从(0,R)顺时针到(R/2,R/2) ），就可以求出整个圆弧的象素集。,圆的扫描转换,图5.10 1/8圆弧,35,圆的扫描转换,简单方程生成圆弧中点Bresenham算法,36,简单方程产生圆弧,算法原理：利用其函数方程，直接离散计算。,圆的函数方程为：,37,圆的极坐标方程为：,简单方程产生圆弧,38,构造函数F(x,y)=x2+y2-R2。对于圆上的点，有F(x,y)=0
14、；对于圆外的点，F(x,y)0；而对于圆内的点，F(x,y)0。,给定圆心在原点，半径为整数R的圆，其方程为,中点Bresenham画圆,图5.11 中点Bresenham画圆的原理,当F(M)0，M在圆外，取Pd(xi+1,yi-1);当F(M)=0，M在圆上，取Pu或Pd;,40,当d0时，下一点取Pu(xi +1,yi)；当d0时，下一点取Pd(xi +1,yi-1)。,构造判别式：,中点Bresenham画圆,误差项的递推（d10）,图5.12 d0的情况,误差项的递推（d10）,43,判别式的初始值：有浮点运算,中点Bresenham画圆,改进：用d-0.25代替d，则：d0=1-R
15、当di0 di+1=F(xi+2,yi-1.5) =(xi+2)2+(yi-1.5)2-R2 =(xi+1)2+(yi-0.5)2-R2+2xi+3+(-2yi+2) =di+2(xi-yi)+5,45,1.输入圆的半径R。2.计算初始值d=1-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.当xy时，重复步骤3和4。否则结束。程序演示,中点Bresenham画圆算法步骤,设圆半径R=10，初始点(0
16、,10)，d0=1-R=-9idi下一个点 di+10 -9 (1,10) =di+2Xi+1+1=-6-6 (2,10) =di+2Xi+1+1=-1-1 (3,10) =di+2Xi+1+1=66 (4,9) =di+2Xi+1-2Yi-1+1=-3-3 (5,9) =di+2Xi+1+1=88 (6,8) =di+2Xi+1-2Yi-1+1=55 (7,7),中点Bresenham画圆,47,5.4 多边形的扫描转换与区域填充,多边形的扫描转换主要是通过确定穿越区域的扫描线的覆盖区间来填充。区域填充是从给定的位置开始涂描直到指定的边界条件为止。,48,多边形的扫描转换与区域填充,多边形的
17、扫描转换边缘填充算法区域填充相关概念,49,多边形的扫描转换,顶点表示用多边形的顶点序列来刻划多边形，几何意义强，但不适合着色。 点阵表示是用位于多边形内的象素的集合来刻划多边形，没有几何意义，但适合着色扫描转换多边形：从多边形的顶点信息出发，求出位于其内部的各个象素，并将其颜色值写入帧缓存中相应单元的过程。,多边形扫描转换顶点表示 点阵表示,50,多边形的扫描转换,X扫描线算法改进的有效边表算法,51,基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的所有象素。,X扫描线算法原理,图5.23 x-扫描线算法填充多边形,52,1.确定多边形所占有的最大扫描线数，
18、得到多边形顶点的最小和最大y值（ymin和ymax）。2.从y=ymin到y=ymax，每次用一条扫描线进行填充。3.对一条扫描线填充的过程可分为四个步骤：求交：计算扫描线与多边形所有边的交点；排序：按x轴排序所有交点；交点配对：每对交点代表扫描线与多边形的一个相交区域；区间填色：根据相交区域填色。,X扫描线算法算法步骤,图 多边形域的填充,求交：扫描线6与多边形的边界线交于A、 B、 C、 D。得到的各交点的横坐标分别为2、 4、 8、 11；排序：按递增排序：2、 4、 8、 11；配对：相交区间为2, 4、8, 11；填色：这两个区间的像素置成多边形色, 把相交区间外的像素置成背景色。,
19、X扫描线算法算法步骤,54,交点的取整规则：使生成的像素全部位于多边形之内。（用于直线等图元扫描转换的四舍五入原则可能导致部分像素位于多边形之外，从而不可用）。假定非水平边与扫描线y=e相交，交点的横坐标为x，规则如下：,X扫描线算法取整规则,规则1：如X为小数，即交点落于扫描线上两个相邻像素之间时：交点位于左边界之上，向右取整；交点位于右边界之上，向左取整；,图 取整规则1,规则2：如X为整数，即交点落于扫描线上某像素上时，按照“左闭右开” 原则处理交点：交点处于左边界之上，交点不变；交点处于右边界之上，交点的x坐标减1；,图 取整规则2,当扫描线与多边形顶点相交时，交点的取舍，保证每一条扫
20、描线与多边形的交点个数为偶数，使交点正确配对。规则3：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。,图 取整规则3,X扫描线算法取整规则,填充过程实例,58,实际处理：只要检查顶点的两条边的另外两个端点的Y值，按这二个y值中大于交点y值的个数是0、1、2来决定交点个数是0个、1个、还是2个。,X扫描线算法取整规则,图5.25 与扫描线相交的多边形顶点的交点数,59,改进的有效边表算法（Y连贯性算法）,x-扫描线算法需要与多边形所有边求交，效率低下。改进原理：处理一条扫描线时，仅对有效边求交。利用
21、扫描线的连贯性。利用多边形边的连贯性。 当扫描线Yi与某一条边的交点坐标为Xi，那么下一条扫描线Yi+1与该边的交点Xi+1的计算，只需加上一个增量即可：Xi+1= Xi+1/k,60,边表（Edge Table,ET）：多边形的所有边放在一个表中。有效边（Active Edge）：与当前扫描线相交的多边形的边，也称为活性边。有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点： x ymax 1/k next,改进的有效边表算法（Y连贯性算法）,有效边链表结点的数据结构x：当前扫描线与边的交点
22、坐标Ymax：该边所交的最高扫描线号Ymax 1/k：从当前扫描线到下一条扫描线间x的增量边的连贯性，扫描线的联贯性； 只需对当前扫描线的有效边表稍作修改，就可以得到下一条扫描线的有效边表。,改进的有效边表算法（Y连贯性算法）,62,首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。,改进的有效边表算法构造边表,63,每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x
23、值），1/k，以及该边的最大y值ymax。x|ymin ymax 1/k NEXT同一桶中若干条边按X|ymin由小到大排序，若X|ymax 相等，则按照1/k由小到大排序。,改进的有效边表算法构造边表,解决顶点交点计为1时的情形：,图5.28 将多边形的某些边缩短以分离那些应计为1个交点的顶点下闭上开：检测是否存在某边的ymax等于另一边的ymin，假如有，则将ymax的边缩短（ymax=ymax-1）如图5.28 (b)，以保证顶点交点计数为1 。,图5.27 多边形P0P1P2P3P4P5P6,图5.27 多边形P0P1P2P3P4P5P6,67,初始化：构造边表，AET表置空；将第一个
24、不空的ET表中的边与AET表合并；由AET表中取出交点对进行填充。填充之后删除y=ymax的边；yi+1=yi+1,根据xi+1=xi+1/k计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表；AET表不为空则转，否则结束。,改进的有效边表算法构造有效边表,进一步改进，使得无须缩短任何边：建新边表ET将扫描线坐标Y的初值置为ET中非空元素的最小序号置AET为空执行以下步骤，直至ET和AET都为空把ET中Y信息与AET合并，同时保存AET中按X值实现的排序序列对于扫描线Y，在一对交点之间填充所需要的像素值从AET中删除Yi+1Ymax的项对于仍留在
25、AET中的每一项，用x+1/m代替x检查并保存AET中的各项，按X值排序使Y增1，成为下一条扫描线的坐标,各扫描线的新边表 NET,特点：利用边的连贯性，加速交点的计算 利用AET，排除盲目求交 利用扫描线的连贯性，避免逐点判别缺点：涉及表的维护和排序，不适合硬件。,改进的有效边表算法,求余运算假定A是给定的正数，则M得余数定义为M=A-M边缘填充法当计算机内用n位二进制表示M，A=2n-1， 则M=A-M=A-(A-M)=M。 即对M作偶次求余，运算结果是M； 对M作奇次求余，运算结果是M。,边缘填充算法,73,边缘填充算法,（逐边向右求补）基本思想：按任意顺序处理多边形的每条边。处理时，先
26、求出该边与扫描线的交点，再对扫描线上交点右方的所有象素取反。算法简单，但对于复杂图型，每一象素可能被访问多次,74,栅栏填充算法,栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。（逐边向栅栏求补）基本思想：按任意顺序处理多边形的每一条边，但处理每条边与扫描线的交点时，将交点与栅栏之间的象素取反。这种算法尽管减少了被重复访问象素的数目，但仍有一些象素被重复访问。,75,边标志算法,基本思想：先用特殊的颜色在帧缓存中将多边形的边界勾画出来，然后将着色的象素点依x坐标递增的顺序配对，再把每一对象素构成的区间置为填充色。象素仅访问一次，但需要逐条扫描线对帧缓存中的像素进行搜索和比较
27、。,76,边标志算法,分为两个步骤：打标记 对多边形的每条边做直线扫描转换，并对所得的像素点打标记，按照“下闭上开”原则，局部最低点处理为两个重叠交点；局部最高点处理为零个重叠交点。2.填充 对每一条与多边形相交的扫描线，按“左闭右开”原则，从自左到右顺序对扫描线上的像素点进行填色。,77,区域填充,基本概念区域的表示方法区域的分类区域填充算法,78,基本概念,区域填充是指从区域内的某一个象素点（种子点）开始，由内向外将填充色扩展到整个区域内的过程。区域是指已经表示成点阵形式的相互连通的一组象素的集合。通常由内点表示和边界表示两种形式。,79,边界表示法：把位于给定区域的边界上的象素一一列举出
28、来的方法，要求边界上的像素颜色是相同色，与区域内外不同，而区域内外可以颜色相同或不同。如兰圆点为边界表示。边界表示法中，由于边界由特殊颜色指定，填充算法可以逐个象素地向外处理，直到遇到边界颜色为止，这种方法称为边界填充算法（Boundary-fill Algorithm）。,区域的表示方法,图 边界表示的区域,内点表示法：枚举出给定区域内所有象素的表示方法，要求区域内的像素颜色是相同色，与区域外颜色不同。如绿圆点为内点表示。 以内点表示法为基础的区域填充算法称为泛填充算法（Flood-fill Algorithm）。,图 内点表示的区域,区域的表示方法,81,区域可分4-连通区域，8-连通区域
29、。,区域的分类,图5-33 4邻接点与8邻接点,（a） 4邻接点 （b）8邻接点,四连通区域 八连通区域,4-连通区域4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。8-连通区域从区域内每一像素出发，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。,区域的分类,图5-28 4连通,图5-28 8连通区域,蓝圆点像素集为边界表示的区域；绿圆点像素集为内点表示的区域；,84,连通性： 4连通可看作8连通区域，但对边界有要求。对边界的要求。,4连通与8连通区域的区别,图5-34 园点构成
30、的边界是4-连通；园点、三角点构成的边界才是8-连通区域,85,区域填充算法,区域填充算法（边界填充算法和泛填充算法）是根据区域内的一个已知象素点（种子点）出发，找到区域内其他象素点的过程，所以把这一类算法也成为种子填充算法。,86,区域填充算法边界填充算法,算法的输入：种子点坐标(x,y)，填充色以及边界颜色。利用堆栈实现简单的种子填充算法 算法从种子点开始检测相邻位置是否是边界颜色，若不是就用填充色着色，并检测该像素点的相邻位置，直到检测完区域边界颜色范围内的所有像素为止。,87,栈结构实现4-连通边界填充算法的算法步骤为： 种子象素入栈；当栈非空时重复执行如下三步操作： (a)栈顶象素出
31、栈； (b)将出栈象素置成填充色； (c)检查出栈象素的4-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。,区域填充算法边界填充算法,88,栈结构实现8-连通边界填充算法的算法步骤为： 种子象素入栈；当栈非空时重复执行如下三步操作： (a)栈顶象素出栈； (b)将出栈象素置成填充色； (c)检查出栈象素的8-邻接点，若其中某个像素点不是边界色且未置成多边形色，则把该像素入栈。,区域填充算法边界填充算法,89,区域填充算法边界填充算法,可以用于填充带有内孔的平面区域。未考虑像素的相关性，把太多的像素压入堆栈，降低了效率，同时需要较大的存储空间。递归执行，算法简单，但效率不高
32、，区域内每一像素都引起一次递归，进/出栈费时费内存。通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。,90,区域填充算法边界填充算法,扫描线种子填充算法：扫描线通过在任意不间断扫描线区间中，只取一个种子像素的方法使堆栈的尺寸极小化。不间断区间是指在一条扫描线上的一组相邻像素。,图5-35 扫描线种子填充算法,91,区域填充算法边界填充算法,基本过程：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段；然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，分别将它们的最左端像素作为种子点保存下来；反复这个过程，直到填充结束。,扫描线区域填充算法
33、（扫描线种子填充算法）：(1)初始化：堆栈置空。将种子点(x，y)入栈。(2)出栈：若栈空则结束。否则取栈顶元素(x，y)，以y作为当前扫描线。(3)填充并确定种子点所在区段：从种子点(x，y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为XL和XR 。(4)确定新的种子点：在区间XL，XR中检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最左端的像素作为种子点压入堆栈，返回第(2)步。,区域填充算法边界填充算法,出栈：4栈：7，3，1出栈：7栈：3，1出栈：3栈：1出栈：1栈：,扫描线区域填充算法（扫描线种子填充算
34、法）初始化栈：s,出栈：s栈：2，1出栈：2栈：5，4，3，1出栈：5栈：6，4，3，1出栈：6栈：4，3，1,图5-31 扫描线种子填充算法过程,95,区域填充算法泛填充算法,算法的输入：种子点坐标(x,y)，填充色和内部点的颜色。算法原理：算法从指定的种子(x,y)开始，用所希望的填充颜色赋给所有当前为给定内部颜色的象素点。,96,种子象素入栈；栈非空时重复执行如下三步操作： (1)栈顶象素出栈； (2)将出栈象素置成填充色； (3)检查出栈象素的8-邻接点，若其中某个象素点是给定内部点的颜色且未置成新的填充色，则把该象素入栈。,区域填充算法泛填充算法,97,当以边界表示时，4-连通边界填
35、充算法只能填充4-连通区域，8-连通边界填充算法也只能填充8-连通区域。当以内点表示时，8-连通泛填充算法可以填充8-连通区域也可以填充4-连通区域，当然4-连通泛填充算法还是只能填充4-连通区域。,区域填充算法泛填充算法,98,相关概念内外测试,图536 不自交的多边形与自相交的多边形,不自相交的多边形多边形的边除共享顶点外，没有其他交点；多边形的内部、外部可以直观地划分。自相交的多边形多边形的边除共享顶点外，还有其他交点；多边形的内部、外部不能一目了然。,99,奇-偶规则（Odd-even Rule） 从任意位置P作一条射线，该射线不与任何多边形边与边的交点（包括共享顶点和交点）相交，若与
36、该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。,相关概念内外测试,100,非零环绕数规则（Nonzero Winding Number Rule）首先按逆时针对多边形顶点排序，使多边形的边变为矢量。将环绕数初始化为零。再从任意位置p作一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点。,相关概念内外测试,101,两种规则的比较,相关概念内外测试,102,相交计算中包含了非线性边界。对于简单曲线： （1）计算曲线
37、相对两侧的两个扫描线交点 （2）简单填充在曲线两侧上的边界点间的水平象素区间。,相关概念曲线边界区域填充,103,5.5 字符处理,ASCII码：“美国信息交换用标准代码集”(American Standard Code for Information Interchange)，简称ASCII码。国际码：“中华人民共和国国家标准信息交换编码，简称为国际码，代号GB231280。字库：字库中储存了每个字符的图形信息。矢量字库和点阵字库。,104,在点阵表示中，每个字符由一个点阵位图来表示。显示时：形成字符的像素图案。,字符处理点阵字符,图5-33 字符A的点阵表示,105,定义和显示直接、简单。
38、 存储需要耗费大量空间。 从一组点阵字符生成不同尺寸和不同字体的其他字符。 采用压缩技术。,字符处理点阵字符,106,矢量字符采用直线和曲线段来描述字符形状，矢量字符库中记录的是笔划信息。显示时：解释字符的每个笔划信息。,字符处理矢量字符,图5-34 字符A的矢量表示,107,字符处理矢量字符,轮廓字型法采用直线或二、三次曲线的集合来描述一个字符的轮廓线，轮廓线构成了一个或若干个封闭区域，显示时只要填充这些区域就可产生相应的字符。显示时可以“无极放缩”。占用空间少，美观，变换方便。,108,图素或图段的外观由其属性决定。图形软件中实现属性选择的方法是提供一张系统当前属性值表，通过调用标准函数提
39、供属性值表的设置和修改。进行扫描转换时，系统使用属性值表中的当前属性值进行显示和输出。,5.6 属性处理,109,线型与线宽区域填充属性,属性处理,110,线型与线宽线型,线型的显示可用象素段方法实现：针对不同的线型，画线程序沿路径输出一些连续象素段，在每两个实心段之间有一段中间空白段，他们的长度（象素数目）可用象素模板(pixel mask)指定。存在问题：如何保持任何方向的划线长度近似地相等。,可根据线的斜率来调整实心段和中间空白段的像素数目。,图5-35 相同数目象素显示的不等长划线,112,线刷子：垂直刷子、水平刷子,线型与线宽线宽,图5-36 线刷子,113,实现简单、效率高。斜线与
40、水平(或垂直)线不一样粗。当线宽为偶数个象素时，线的中心将偏移半个象素。利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。解决：添加“线帽（line cap）”,线型与线宽线型,方帽：调整端点位置，使粗线的显示具有垂直于线段路径的正方形端点。凸方帽：简单将线向两头延伸一半线宽并添加方帽。圆帽：通过对每个方帽添加一个填充的半圆得到。,图5-37 线帽,115,当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口。,线型与线宽线型,图5-38 线刷子产生的缺口,解决：斜角连接（miter join）、圆连接（round join）、斜切连接（bevel join）,图5-39 线
41、刷子产生的缺口,方刷子,特点：方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些。方刷子绘制的斜线与水平（或垂直）线不一样粗。方刷子绘制的线条自然地带有一个“方线帽”。,图5-40 方刷子,118,区域填充改变刷子形状,线型与线宽线型,图5-41 利用像素模板进行线宽处理,119,线型：可采用像素模板的方法。,线型与线宽曲线的线型和线宽,图5-42 利用模板110进行圆的线型处理,120,从一个八分象限转入下一个八分象限时要交换象素的位置，以保持划线长度近似相等。在沿圆周移动时调整画每根划线的像素数目以保证划线长度近似相等。改进：可以采用沿等角弧画像素代替用等长区间的像素模板来生成等长划线
42、。,线型与线宽曲线的线型和线宽,121,线宽：线刷子：经过曲线斜率为1和1处，必须切换刷子。 曲线接近水平与垂直的地方，线条更粗。方刷子：接近水平垂直的地方，线条更细 要显示一致的曲线宽度可通过旋转刷子方向以使其在沿曲线移动时与斜率方向一致圆弧刷子采用填充的办法。,线型与线宽曲线的线型和线宽,122,区域填充属性选择包括颜色、图案和透明度。,区域填充属性,图5-43 利用图案模板进行三角形的填充,根据图案和透明度属性来填充平面区域的基本思想是：首先用模板定义各种图案。然后，修改填充的扫描转换算法：在确定了区域内一像素之后，不是马上往该像素填色而是先查询模板位图的对应位置。若是以透明方式填充图案
43、，则当模板位图的对应位置为1时，用前景色写像素，否则，不改变该像素的值。若是以不透明方式填充图案，则视模板位图对应位置为1或0来决定是用前景色还是背景色去写像素。,124,确定区域与模板之间的位置关系（对齐方式）,区域填充属性,图5-44 利用图案模板进行三角形的填充,125,用离散量表示连续量引起的失真，就叫做走样（Aliasing）。,5.7 反走样,图5-45 绘制直线时的走样现象,126,产生原因： 数学意义上的图形是由无线多个连续的、面积为零的点构成；但在光栅显示器上，用有限多个离散的，具有一定面积的象素来近似地表示他们。,反走样,127,走样现象：一是光栅图形产生的阶梯形。一是图形
44、中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁。,反走样,例子,图5-46 丢失细节与运动图形的闪烁,用于减少或消除这种效果的技术，称为反走样（antialiasing，图形保真）。一种简单方法：,过取样（supersampling），或后滤波 区域取样（area sampling），或前滤波,图5-47 分辨率提高一倍，阶梯程度减小一倍,130,过取样：在高于显示分辨率的较高分辨率下用点取样方法计算，然后对几个象素的属性进行平均得到较低分辨率下的象素属性。,反走样过取样（super sampling）,简单过取样 在x，y方向把分辨率都提高一倍，
45、使每个象素对应4个子象素，然后扫描转换求得各子象素的颜色亮度，再对4个象素的颜色亮度进行平均，得到较低分辨率下的象素颜色亮度。,图5-48 简单的过取样方式,重叠过取样：为了得到更好的效果，在对一个像素点进行着色处理时，不仅仅只对其本身的子像素进行采样，同时对其周围的多个像素的子像素进行采样，来计算该点的颜色属性。,图5-49 重叠过取样,基于加权模板的过取样：前面在确定像素的亮度时，仅仅是对所有子像素的亮度进行简单的平均。更常见的做法是给接近像素中心的子像素赋予较大的权值，即对所有子像素的亮度进行加权平均。,图5-50 常用的加权模板,134,反走样简单的区域取样,在整个像素区域内进行采样，
46、这种技术称为区域取样。又由于像素的亮度是作为一个整体被确定的，不需要划分子像素，故也被称为前置滤波。,图5-53 有宽度的直线段,135,如何计算直线段与像素相交区域的面积？,反走样简单的区域取样,图5-54 重叠区域面积的计算,136,可以利用一种求相交区域的近似面积的离散计算方法： (1)将屏幕像素分割成n个更小的子像素， (2)计算中心落在直线段内的子像素的个数m， (3)m/n为线段与像素相交区域面积的近似值。直线段对一个像素亮度的贡献与两者重叠区域的面积成正比。相同面积的重叠区域对像素的贡献相同。,反走样简单的区域取样,137,过取样中，我们对所有子像素的亮度进行简单平均或加权平均来
47、确定像素的亮度。在区域取样中，我们使用覆盖像素的连续的加权函数（Weighting Function）或滤波函数(Filtering Function)来确定像素的亮度。,反走样加权区域取样,加权区域取样原理 加权函数W(x,y)是定义在二维显示平面上的函数。对于位置为(x,y)的小区域dA来说，函数值W(x,y)（也称为在(x,y)处的高度）表示小区域dA的权值。将加权函数在整个二维显示图形上积分，得到具有一定体积的滤波器（Filter），该滤波器的体积为1。将加权函数在显示图形上进行积分，得到滤波器的一个子体，该子体的体积介于0到1之间。用它来表示像素的亮度。,图5-55 盒式滤波器的加权
48、区域取样,图5-56 常用的滤波函数,141,特点：接近理想直线的象素将被分配更多的灰度值；相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。,反走样加权区域取样,142,5.8 在OpenGL中绘图,点的绘制直线的绘制多边形面的绘制OpenGL中的字符函数OpenGL中的反走样,143,点的绘制,点的绘制 glBegin(GL_POINTS)； glVertex3f(0.0f, 0.0f, 0.0f); glVertex3f(10.0f, 0.0f, 0.0f); glEnd()；点的属性（大小） void glPointSize(GLfloat size)；,144,直线的绘制
49、,直线的绘制模式GL_LINESGL_LINE_STRIPGL_LINE_LOOP,（a）GL_LINES画线模式 （b）GL_LINE_LOOP画线模式 （c）GL_LINE_STRIP画线模式图5-57 OpenGL画线模式,145,直线的绘制,直线的属性线宽 void glLineWidth(GLfloat width)线型 glEnable(GL_LINE_STIPPLE)； glLineStipple(GLint factor，GLushort pattern)；,146,直线的绘制,图5-58 画线模式用于构造线段,147,多边形面的绘制,三角形面的绘制GL_TRIANGLESGL
50、_TRIANGLE_STRIPGL_TRIANGLE_FAN四边形面的绘制GL_QUADSGL_QUADS_STRIP多边形面的绘制（GL_POLYGON）,148,多边形面的绘制,多边形面的绘制规则所有多边形都必须是平面的。多边形的边缘决不能相交，而且多边形必须是凸的。解决：对于非凸多边形，可以把它分割成几个凸多边形（通常是三角形），再将它绘制出来。,149,多边形面的绘制,问题：轮廓图形状态会看到组成大表面的所有小三角形。处理OpenGL提供了一个特殊标记来处理这些边缘，称为边缘标记。 glEdgeFlag（True） glEdgeFlag（False）,150,多边形面的属性,多边形面的
