计算机图形学图形生成技术PPT课件

1、3.1 直线图形3.2 二次曲线3.3 字 符3.4 区域填充第第3章章 二维图形生成技术二维图形生成技术第1页/共85页3.1 直线图形第2页/共85页3.1 直线图形直线图形 扫描转换直线段就是计算出落在直线段上或充分靠近它的一串象素，并以此象素近似代替原连续直线段在屏幕上显示的过程。本节介绍画线的三个常用算法：数值微分法，中点画线法和Bersenham法。 为了简化算法，给出两点假设： 直线段的宽度为1； 直线段的斜率|k| 1；对于斜率 |k| 1 的直线段的生成方法可对算法做适当改变得到。第3页/共85页DDA算法算法 DDA是数值微分法（Digital Differential A

2、nalyzer）的缩写。设直线起点（x1,y1），终点（x2,y2），则斜率m（|m| 1） 为： y=mx+b；b = (y2x1 - y1x2)/(x2 - x1) m=dy/ dx； dy=y2-y1；dx=x2-x1； 画直线算法: 给定直线的两个端点坐标后，求得m和b；然后在x1xx2范围内对x取整数，利用公式进行浮点乘法和加法运算，求得y值后再取整数值，即可得到需要的直线上的像素点。 计算方法的缺点是计算量大。3.1直线图形直线图形第4页/共85页 直线图形上的点是由有先后顺序的一列像素点构成的，相邻的两点应满足: m= (yi+1-yi ) / (xi+1-xi ) 于是有： y

3、i+1 = yi + m(xi+1-xi ) 其中(xi,yi)是第i步求得的像素点坐标，(xi+1, yi+1)是第i + 1步求得的像素点坐标。据前面的分析，应要求：| xi+1-xi | 1 | yi+1-yi | 1并要求较大者为1。即如果|m| 1 ，则要求 | xi+1-xi | 1 | yi+1-yi | 1那么，当|m| 1 时，则要求 | xi+1-xi |1 | yi+1-yi |1DDA算法算法第5页/共85页于是，画直线的DDA算法可分两种情况描述为:a.|m| 1 当x2-x1 0时： xi+1 xi 1； yi+1 yi m 当x2-x1 0时： xi+1 xi 1

4、； yi+1 yi mb.|m| 1 当y2-y1 0时： yi+1 yi 1；xi+1 xi 1/m； 当y2-y1 0时： yi+1 yi 1；xi+1 xi 1/m；DDA算法算法第6页/共85页象限|dx|dy| ?DxDy1a1m1b1/m12a-1m2b-1/m13a-1-m3b-1/m-14a1-m4b1/m-1DDA算法算法假设：xi+1 - xi Dxyi+1 - yi Dy Dy = m Dx 则有：xi+1 xi + Dxyi+1 yi +Dy Dy = m Dx第7页/共85页DDA算法算法研究表中的数据，可以发现两个规律：1、当|dx|dy|时 |Dx|=1， |Dy

5、|=m； 当|dx|= -1 & k = 1) y=y1; for(x=x1;x=x2;x+) putpixel(int)x,(int)(y+0.5),color); y+=k; else k=1/k; x=x1; for(y=y1;y0F(x,y)0F(x,y)0假定已经求得像素（xi,yi,r），由四舍五入取整原则可知（下图） 21y,21yyr ,ir ,ii由于P0P1的斜率在0,1之间，故x = xi +1和P0P1的交点的纵坐标： 23y,21yyr , ir , i1i在直线x = xi +1 上，区间内存在两个像素，NE和E。 23y,21yr , ir , iNEM（

6、xi,yi,r）（xi,yi）E（xi+1,yi+1）x=xix=xi+1P0P1第16页/共85页中点画线法中点画线法 NEM（xi,yi,r）（xi,yi）E（xi+1,yi+1）x=xix=xi+1 根据取整原则，当Q(xi+1,yi+1)在中点M（ xi+1,yi,r+0.5 ）上方时，取像素NE，否则取像素E，即：而“(xi+1,yi+1) 在M上方”等价于“F(M)0di=0第19页/共85页void MidpointLine (int x0,int y0,int x1, int y1,int color) int y , x , d1, d2, d, x, y; y = y1 -

7、 y0; x =x1-x0; d= x - 2*y; d1=-2*y ; d2=-2* (y -x ); x=x0; y=y0; putpixel(x, y, color); while (xx1) if (d0，则yi+1=yi+1，否则yi+1=yi。因此算法的关键在于简便地求出d1-d2的符号。Bresenham画线法画线法第25页/共85页 d1-d2 =2y-2yi-1=2 (xi+1)-2yi+2b-1 用dx乘等式两边，并令Pi=dx(d1-d2)代入上述等式，得：Pi=2xidy-2yidx+2dy+dx(2b-1) (1) d1-d2是我们用以判断符号的误差。由于在1a象限，

8、dx总大于0，所以Pi仍旧可以用作判断符号的误差。用Pi+1- Pi得： Pi+1 =Pi+2dy-2dx(yi+1-yi) 其中yi+1-yi=0或1；(2) 若Pi0 ，则d1d2， yi+1-yi=1； Pi+1 =Pi+2dy-2dx 若Pi0 ，则d10 then yi+1=yi+1 else yi+1=yi；3、画点（xi+1, yi+1）；4、求下一个误差Pi+1： if Pi0 then Pi+1=Pi+2dy-2dx else Pi+1=Pi+2dy；5、i=i+1; if i|dy|为分支，并分别将2a, 3a象限的直线和3b, 4b象限的直线变换到1a, 4a和2b, 1

9、b方向去，以求得程序处理的简洁。Bresenham画线法画线法第29页/共85页Bersenham程序程序void line (x1, y1, x2, y2, c)int x1, y1, x2, y2, c; int dx，dy，x，y，p，const1，const2，inc，tmp； dx=x2-x1; dy=y2-y1; if (dx*dy=0) inc=1; else inc=-1; /*准备x或y的单位递变值*/ if (abs(dx)abs(dy) if(dx0) /*将2a,3a象限方向的直线变换到1a,4a象限方向去*/ tmp=x1; x1=x2;x2=tmp;tmp=y1;y

10、1=y2; dx=-dx; dy=-dy; p=2*dy-dx; const1=2*dy; const2=2*(dy-dx); /*注意此时误差的变化参数取值*/ x=x1; y=y1; set_pixel(x, y, c); 第30页/共85页Bersenham程序程序 while (xx2) x+; if (p0) p+=const1; else y+=inc; p+=const2; set_piexl(x, y, c); else /*将3b,4b象限方向的直线变换到2b, 1b象限方向去*/ if (dy0) tmp=x1; x1=x2;x2=tmp;tmp=y1;y1=y2； dx=

11、-dx; dy=-dy; p=2*dx-dy; /*注意此时误差的变化参数取值*/ const1=2*dx; const2=2*(dy-dx); x=x1; y=y1; set_pixel (x, y, c); 第31页/共85页Bersenham程序程序 while (yy2) y+; if (p0) p+=const1; else x+=inc; p+=const2; set_pixel (x, y, c); 第32页/共85页3.2 二次曲线二次曲线第33页/共85页3.2 二次曲线二次曲线v 圆弧拟合法 给出圆心坐标xc， yc和半径r，逐点画出圆的公式有两种：1、直角坐标法：(x-x

12、c)2+(y-yc)2=r2，导出 当x-xc从-r到r作加1递增时，可以求出对应的圆周点的y坐标。但是这样求出的圆周上的点是不均匀的；|x-xc|越大，对应生成圆周点之间的圆周距离也就越长。2、极坐标法： x=xc+rcos y=yc+rsin 从0,360 作加1递增时，由此式便可求出圆周上均匀分布的360个点的x, y坐标。22c)xx(ryyc 第34页/共85页3.2.1 圆弧的中点算法 本节考虑圆的圆心在原点的圆弧的扫描转换算法，对于圆心为任意点的圆可通过平移再扫描转换，再平移到原来的位置。(xc,yc)rv 圆的八对称性 圆心位于原点的圆有四条对称轴： x0； y0； xy； x

13、y 如图若已知圆弧上一点(x,y)，就可以得到其关于四条对称轴的七个对称点，这种性质称为圆的八对称性。为了求出表示整个圆弧的象素集，只要扫描转换1/8圆弧就可以了。第35页/共85页圆弧的中点算法圆弧的中点算法写出圆弧的隐函数方程形式：0),(222RyxyxF则圆弧F(x,y)=0具有正负划分性，如图: 圆弧外的点：F(X，Y)0 圆弧内的点：F(X，Y)0 圆弧上的点：F(X，Y)=0第36页/共85页 讨论1b象限内的1/8圆弧段，假定计算出象素（xi，yi,r）由四舍五入的取整原则得： 在圆弧段内，圆弧上各点的切线斜率k满足-1,0，竖直线x=xi+1和圆弧的交点的纵坐标满足 P(xi

14、+1,yi,r-0.5)圆弧的中点算法圆弧的中点算法 21y,21yyr , ir , ii 21y,23yyr , ir , i1i第37页/共85页)M(Fdi 则变为：P(xi+1,yi,r-0.5)圆弧的中点算法即为生成圆弧的中点判别方法。 0d1y0dyyir , iir , ir ,1i当当当当 0d5)yx(2d0d3x2d0dR1)21y(2)21y(1)1x(2)1x(0dR)21y(1)1x(2)1x(0dR)23y(1)1x(2)1x(0dR)21y(1)1x(2)1x(R)21y()2x()21y, 2x(Fdir , iiiiiii2r , i2r , ii2ii22

15、r , ii2ii22r , ii2ii22r , ii2i22r ,1i2ir ,1ii1i 欲判断M点是在交点上方还下方，只需把M代入F(x,y),并检查它的符号。判别式：第38页/共85页圆弧的中点算法判别式和di+1构成了完整的中点算法，这两个递推式的初值条件为：x,y的初值：(x0,y0,r)=(0，R) d 的 初 值: d0=F(x0+1, y0,r-0.5) = F(1, R-0.5) = 1+(R-0.5)2-R 2 = 1.25-R 算法中有浮点数，用e=d-0.25代替，初始化运算d0 = 1.25 R 对应于 e0= 1- R，判别式 d 0 对应于 e -0.25；

16、e的初值e0为整数，运算过程中的分量为整数，故e始终为整数所以： e -0.25 等价于 d 0。第39页/共85页程序如下（完全用整数实现）MidpointCircle(int r, int color) int x,y,d; x = 0; y = r; d = 1-r; putpixel(x,y,color); while( x y) if (d 0) d += 2*x+3; x+; else d += 2*(x-y)+5; x+ ; y-; putpixel(x,y,color); 第40页/共85页 考虑圆心在原点，圆弧在第1b象限的1/8圆弧，圆的半径为R。假定像素点Pi-1是x=x

17、i-1时最靠近圆周的像素点，那么在x=xi-1+1时要得到的最靠近圆周的像素点只可能是：Hi 或Li。因为这一段圆弧曲(xi-1,yi-1)(xi-1+1,yi-1)(xi-1+1,yi-1-1)x=xi-1x=xi线随x的增加，y单调减小，且 x 方向改变量大于y方向的改变量。由于x方向改变量为1，y方向的改变量只能在0和1之间， 因此取整后 y 坐标的改变量只能是 0 或 1。设x = xi-1+1时圆周上点的y坐标为 y，则必有下列3种关系之一成立： y yi-1 - 1或yi-1-1 y yi-1。3.2.2 Bresenham圆弧算法圆弧算法第41页/共85页(xi-1,yi-1)(

18、xi-1+1,yi-1)(xi-1+1,yi-1-1)x=xi-1x=xi 01yyd0yyd21i2L221iH为x = xi-1+1时圆周上点的y坐标为分别与Li和Hi点的y坐标平方之差，注意R2 =(xi-1+1)2+y2，则有 21i21i2L21i221iH1y1xRd1xRyd(1). 当yi-1-1 y yi-1时，圆弧从Hi或Li两点间穿过，定义dH,dL两个量的几何意义是从圆心到H(或L)距离的平方与到圆周距离的平方之差。如果dH dL，则Li比Hi更接近于实际的圆。反之，dHdL，则Hi比Li更接近于实际的圆。故我们把判别变量定义为dH和dL的差，用pi表示：pi = dH

19、-dL = 2(xi-1+1)2+ yi-12 + (yi-1-1)2 - 2R2当pi 0时选择像素点为Hi，否则选择像素点为Li。3.2.2 Bresenham圆弧算法圆弧算法第42页/共85页3.2.2 Bresenham圆弧算法圆弧算法 21i21i2L21i221iH1y1xRd1xRyd总之，无论哪种情况成立，判别规则都是一致的，即当pi 0时选择的像素点为Hi；否则选择的像素点为Li 。(xi-1,yi-1)(xi-1+1,yi-1)(xi-1,yi-1 -1)(2). 当y 0；(3). 当y yi-1时，此时圆弧曲线从Hi和Li两点上方通过，显然 的选择是Hi和Li中y坐标为

20、yi-1的点，即Hi。此时上式中定 义的dH 0，dL0 ，故同时有pi 0。pi = dH-dL第43页/共85页3.2.2 Bresenham圆弧算法圆弧算法pi = 2(xi-1+1)2+ yi-12 + (yi-1-1)2 - 2R2要决定下一个像素点，就要求出下一步的判别式pi+1。Pi+1 = 2(xi+1)2+ yi2 + (yi-1)2 - 2R2如果Pi0时，取Hi，xi=xi-1+1，yi=yi-1，得Pi+1 = Pi+4xi-1+6如果Pi 0时，取Li，xi=xi-1+1，yi=yi-1-1，得Pi+1 = Pi+4(xi-1- yi-1)+10算法每次从p1开始，以

21、后则按照上式计算下一个判别变量。把点(x0，y0) =(0，R)代人式，可得到 p1=2+R2+(R-1)2-2R2=3-2R第44页/共85页根据上面的推导，圆周生成算法思想为：1 求误差初值，p1=3-2R；i=1；画点(0, R)；2 求下一个光栅位置：xi+1=xi+1；if (pi0) 则 yi+1=yi； 否则 yi+1=yi-1；3 画点（xi+1, yi+1）4 计算下一个误差： if pi0 则 pi+1=pi+4xi-1+6； 否则 pi+1=pi+4(xi-1-yi-1)+10；5 i=i+1; if x=y则end；否则返2。Bresenham算法思想第45页/共85页

22、circle (xc, yc, radius, c) int x, y, p; x=0; y=radius; p=3-2*radius; while (xy) plot_circle_points(xc, yc, x, y, c); if (p0) p=p+4*x+6; else p=p+4*(x-y)+10; y-=1; x+=1; if (x= =y) plot_circle_points(xc, yc, x, y, c);plot_circle_points(xc, yc, x, y, c) set_pixel(xc+x, yc+y, c); set_pixel(xc-x, yc+y,

23、c); set_pixel(xc+x, yc-y, c); set_pixel(xc-x, yc-y, c); set_pixel(xc+y, yc+x, c); set_pixel(xc-y, yc+x, c); set_pixel(xc+y, yc-x, c); set_pixel(xc-y, yc-x, c);Bresenham算法程序第46页/共85页3.2.3 圆弧的正负法v 原 理： 设圆的方程： F(x,y)=x2 + y2 - R2=0;假设求得Pi的坐标为(xi,yi)：则当Pi在圆内时， F(xi,yi) 向右- 向圆外 当Pi在圆外时， F(xi,yi)0 - 向下- 向

24、圆内pipiv 求得Pi点后选择下一个象素点Pi+1的规则 当F(xi,yi) 0 取xi+1 = xi+1，yi+1 = yi； 当F(xi,yi) 0 取xi+1 = xi， yi+1 = yi-1； 用于表示圆弧的点均在圆弧附近，且使(xi,yi) 时正时负，故称正负法。 快速计算的关键是F(xi,yi) 的计算，能否采用增量算法？第47页/共85页圆弧的正负法若已知F(xi,yi) ，计算F(xi+1,yi+1) 可分两种情况：v当F(xi,yi)0时 xi+1 = xi+1，yi+1 = yi F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 = (xi+1)

25、2+ yi2 -R2 = F(xi,yi) +2xi +1v当F(xi,yi)0时 xi+1 = xi，yi+1 = yi -1 F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2 = xi2+(yi 1)2-R2 = F(xi,yi) - 2yi +1第48页/共85页 利用曲线可用折线来逼近，每段折线越短曲线逼近越好，但执行时间也越长。 假设圆弧的起始和终止角分别为ts和te，半径为R，用折线代替圆弧容许的最大误差为，如果用n段等长折线来逼近圆弧，则每段圆弧曲线对应的圆弧角度为& =（ te - ts ）/n。当&充分小时，圆弧和对应弦的最大误差是：e

26、=R1-cos(&/2)=2Rsin2(&/4) (1/8)R&2为了使e= ，把&代人上式后得到： 该式表明半径越大，要求的误差越小，则所用的折线段数也越多。2R2ttnse 3.2.4 圆的内接正多边形逼近法第49页/共85页 假设要画一个半圆弧，其半径R = 256个像素点单位，于是圆弧的角度为te-ts = 。若要求误差不超过两个像素点单位，即= 2 ，则所需要的折线段数n为：1342562n 即用13段折线来逼近这个半圆弧。圆的内接正多边形逼近法第50页/共85页圆的内接正多边形逼近法v思 想 当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即

27、 因此，在允许的误差范围内，可以用正多边形代替圆。v圆的参数方程圆边正内接多边形） (nlimn 0,2tRsintyRcostx 对圆弧来说，参数t ts , te，而每一折线端点处的参数为 ti = ts + i&, i = 0, 1, 2, , n因此，各折线段的端点坐标为 0,2tRsintyRcostxiii ti&xy第51页/共85页 直接利用公式求出折线的端点的计算是很费时的，为此我们根据相邻折线段的端点间的递推关系来递推地计算折线段的端点： 0,2tRsintyRcostxiii 在这个公式中, 三角函数值cos &，sin &是常量。于是可以

28、从x0 =Rcos ts和y0 = Rsin ts 开始进行逐点递推计算，并且在递推计算的过程中每计算一个端点，只需要四次乘法和两次加法，因而计算速度比较快，但缺点是计算过程中的前面的舍入误差却随着递推的过程逐步向后传递, 使得越靠后的点误差会越大。圆的内接正多边形逼近法第52页/共85页3.2.5 椭圆的扫描转换 对于一个标准椭圆1byax2222 可用如下隐函数形式的方程表示：F(x,y) = b2x2 + a2y2 - a2b2 = 0v 椭圆的四对称性 中心点位于原点的椭圆有两条对称轴： x0； y0； 如图若已知椭圆弧上一点(x,y)，就可以得到其关于两条对称轴的三个对称点，这种性质

29、称为四对称性。为了求出表示整个圆弧的象素集，需要转换位于第一象限的四分之一椭圆，其它部分可利用四对称性获得。（x,y）（-x,y）（-x,-y）（x,-y）yx第53页/共85页 在第1象限的1/4椭圆弧当x从0变到a时，椭圆弧的变化率是变化的，从0到-1，从-1到-，因此基于变化率为-1的点将第1象限的1/4椭圆弧分成两部分，确定边界上的像素点。椭圆弧上任一点(x,y)的法向量为： 第一象限内变化率为-1的点应满足：1ya2xb21yyxFxyxF22 ),(),(结合椭圆方程，求得此Q点的坐标是： 222222babbaa,3.2.5 椭圆的扫描转换 当0 xxq时，椭圆弧曲线上x方向的变

30、化大于y方向的变化，令x = 1，求解y；当xqxa时，则令y =-1，求解x。Q ya2xb2yyxFxyxF22,),(,),( 第54页/共85页 当0 xxq时，如果当前点是P(xi,yi)，下一点(xi+1, yi+1)的选择方法为：xi+1 = xi+1，取整后的y的改变量是0或1，下一个要选择的点是H(xi+1,yi)或L(xi+1,yi -1)。根据H 和L之间中点的函数值进行判别，如果F(xi+1,yi1/2) 0，表明中点位于椭圆内部，则点H靠近椭圆，应选择点H；反之则选择点L。3.2.5 椭圆的扫描转换法向量两分量相等上半部分下半部分M1M2PP/HLL/H/ 当xqxa

31、时，如果当前点是P/(xi,yi)，下一点(xi+1, yi+1)的选择方法为：yi+1= yi1,取整后的x的改变量是0或1,下一个要选择点是L/(xi, yi1)或H/(xi+1,yi1)。根据H/和L/之间中点的函数值进行判别,如果F(xi+1/2, yi1) 0，表明中点位于椭圆内部，则点H/靠近椭圆，应选择点H/ ；反之则选择点L/ 。Q第55页/共85页基于中点判别规则，比较容易区分0 xxq成立否，即： b2 (xp+1) a2 (yp-0.5)其中(xp, yp )为当前椭圆弧像素点。而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分。3.2.5 椭圆的扫描转换在上半

32、部分,法向量的y分量大在下半部分,法向量的x分量大法向量两分量相等上半部分下半部分M1M2PPQ第56页/共85页椭圆的中点画法 与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点。圆弧的上部分，(xp,yp)中点(xp+1,yp-0.5)： d1= F(xp+1,yp-0.5) = b2(xp+1)2+a2(yp-0.5)2-a2b2法向量两分量相等上半部分下半部分M1M2PP/HLL/H/第57页/共85页 根据d1的符号决定下一点是取正右方点，还是右下方点。 若d10，中点在椭圆内，取H点，判别式更新为： d1=F(xp+2,yp-

33、0.5)=d1+b2(2xp+3) d1的增量为b2(2xp+3) 若d10，中点在椭圆外，取L点，判别式更新为： d1=F(xp+2,yp-1.5)=d1+b2(2xp+3)+a2(-2yp+2) d1的增量为b2(2xp+3)+a2(-2yp+2)v d1的初始条件 椭圆弧起点为(0，b)，第一个中点为(1，b-0.5) 初始判别式：d10=F(1,b-0.5) = b*b+a*a(-b+0.25)椭圆的中点画法第58页/共85页v 转入椭圆弧下部分，根据d2的符号决定下一点是正下方或右下方，此时判别式要初始化d2 = F(xp+0.5,yp-1) = b2(xp+0.5)2+a2(yp-

34、1)2-a2b2 若若d2 0，中点在椭圆内，取H/点，判别式更新为： d2/ = F(xp+1.5,yp-2) = d2 + b2(2xp+2)+a2(-2yp+3) 若若d20，中点在椭圆外，取L/点，判别式更新为： d2/ = F(xp+0.5,yp-2) = d2 + a2(-2yp+3) 下半部分弧的终止条件为 y = 0椭圆的中点画法第59页/共85页 MidpointEllipse(a,b, color) int a,b,color, int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); putpixel(x,y

35、,color); while( b*b*(x+1) a*a*(y-0.5) if (d10) if (d2 0) d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x+; y-； else d2 += a*a*(-2*y+3); y-; putpixel(x,y,color); 中点画椭圆的程序第60页/共85页3.3 字字 符符第61页/共85页 在计算机图形学中，字符可以用不同的方式表达和生成。常用的方法有点阵式、矢量式和编码式。3.3 字符的生成字符的生成 点阵式字符将字符表示为一个矩形点阵，由点阵中点的不同值表达字符的形状。常用的点阵大小有7 9、 916 、 1624等。

36、矩阵中每个元素是一位二进制数。如图示，当点阵位图(a) 中为1的位,表示字符笔划经过此位,对应到图 (b) 所示的象素图案中为字符颜色；为 0 的位表示字符笔划不经过此位置，对应此位的象素图案中字符颜色应置为背景色。 点阵式字符第62页/共85页a 标准字符b 粗体c 旋转d 斜体粗体字的算法是：当字符原型中每个象素被写入帧缓存寄存器的指定 位置（xi, yi）时，同时被写入（xi+1, yi）。旋转90的算法是：把字符原型中每个象素的x, y坐标彼此交换，并使y 值改变符号后，再写入帧缓存寄存器的指定位置。斜体字的算法是：从底到顶逐行拷贝字符，每隔n行，左移一单元。3.3 字符的生成字符的生

37、成第63页/共85页 在笔式绘图仪上采用矢量型字符比较合适，矢量式字符具有和图形相一致的数据结构。 矢量式字符 矢量式字符将字符表达为点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻画。用矢量式表示字符“B”，由顶点序列a，b，c，d，e，f，e，g，h，i，j，k，j，f，a，l的坐标表达。kjihgedcbalf3.3 字符的生成字符的生成第64页/共85页 方向编码式字符 方向编码既可用于字符的显示，也可用于字符的绘图机输出。 方向编码式字符用有限的若干种方向编码来表达一个字符，常用的8个方向的编码0-7，其中编码为偶数的线段的固定长度为1，奇数的线段的固定长度为 。则一个字

38、符就用一连串方向码表示。2kjihgedcbalf0 0 0 0 1 2 3 4 4 4 0 0 0 1 2 3 4 4 4 4 0 6 6 6 6 307512463.3 字符的生成字符的生成第65页/共85页3.4 区域填充区域填充第66页/共85页3.4 区域填充算法区域填充算法 一个区域是一组相互连通的像素点集合。区域的建立和定义通常采用2种方式：内部定义区域：区域内部的所有像素具有同一种颜色值。边界定义区域：由多边形轮廓线定义的内部区域。边界线上所有 的像素具有特定的颜色值。通常区域本身部分的 像素点具有不同于边界上的像素点的值。内部定义区域内部定义区域边界定义区域边界定义区域v 区

39、域的定义第67页/共85页像素点之间的连通方式可分为如下两类：3.4 区域填充算法区域填充算法v 区域的连通方式四连通：两个像素点是上下或左右相连的，则 称其为四连通的。 即一个像素点最多 与上、下、左和右四个相邻像素点具 有连通关系。八连通：两个像素点是上下或左右相连的，或 者对角线方向相连的，则称其为八连 通的。即一个像素点最多与上、下、 左和右四个及四个对角点共八个相邻 像素点具有连通关系。第68页/共85页3.4 区域填充算法区域填充算法 区域填充：给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码。填色算法分为两大类： 种子填充（Seed Filling） 扫描线转

40、换填充（Scan-Line Filling）算法v 区域填充第69页/共85页种子填充算法种子填充算法种子填充算法思想： 假设某点(x , y ) 是已知的，将它作为种子，对相邻像素进行搜索。如果相邻像素在填充区域内且又没有改为新颜色值，则作为新的种子继续递归搜索下去。如果相邻像素已不在填充区内，则说明已经达到边界。选取区域内一点为种子种子压栈弹出种子给种子着新色color2分别判断（x-1，y）, （x，y -1 ）, （x+1，y）, （x，y +1 ）相邻像素的颜色边界颜色color1且相邻像素的颜色新色color2?作为新种子压栈栈非空吗？结 束非边界或已填充区域内像素且未填充边界定义

41、填充算法YNYN选取区域内一点为种子种子压栈弹出种子给种子着新色color2分别判断（x-1，y）, （x，y -1 ）, （x+1，y）, （x，y +1 ）相邻像素的颜色=color1?作为新种子压栈栈非空吗？结 束非区域内像素区域内像素内定义填充算法第70页/共85页四相邻种子填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799缺点？第71页/共85页void seed_filling (x, y, fill_color, boundary_color)int x, y, fill_color, bo

42、undary_color; int c; c=inquire_color(x, y); if(c boundary_color) & (c fill_color) putpixel(x, y, fill_color); seed_filling(x+1, y, fill_color, boundary_color); seed_filling(x-1, y, fill_color, boundary_color); seed_filling(x, y+1, fill_color, boundary_color); seed_filling(x, y-1, fill_color, bou

43、ndary_color); 四邻法种子边界填色算法描述四邻法种子边界填色算法描述第72页/共85页void FloodFill4(int x,int y,int fillColor,int oldColor) int c; c=inquire_color(x, y); if (c = oldColor) putpixel(x, y, fillColor); FloodFill4(x+1, y, fillColor, oldColor); FloodFill4(x-1, y, fillColor, oldColor); FloodFill4(x, y+1, fillColor, oldColor

44、); FloodFill4(x, y-1, fillColor, oldColor); 四邻法种子内定义填色算法描述四邻法种子内定义填色算法描述第73页/共85页四连通区域边界填充算法的填充结果八连通区域边界填充算法的填充结果区域连通方式对填充结果的影响第74页/共85页v 缺点缺点： (1) 有些象素会入栈多次，降低算法效率；栈结构占空间。 (2) 递归执行，算法简单，但效率不高，区域内每一象素 都引起一次递归，进、出栈，费时费内存。v 改改进算法，减少递归次数，提高效率。种子填充算法种子填充算法第75页/共85页多边形扫描转换填充算法 该算法适应边界定义区域的填充。其基本思想：用水平扫描线从上到下扫描由点线段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照 x 坐标进行分类，将分类后的交点成对取出，作两个端点，以所需要填的颜色画水平直线。多边形扫描完毕，填充完成。 左、右顶点处理 水平边处理 扫描线与边的求交方法 活性边表第76页/共85页左、右顶点处理 扫描线与多边形的每个顶点相交时，会同时产生两个交点，这是因为一个顶点同属于多边形两条边的端点。 左顶点2：y1y2y2y3其中y1, y2, y3是三个相邻的顶点的y坐标。对多边形的所有左、右顶点作如下处理:左、右顶点的入边（以顶点为终点的边），即1, 2边之终点删去。即：左顶点：入边（x1