计算机图形学 第二章 二维基本图形的生成与二维区域的填充ppt课件

1、2020/11/20,1,第二章 二维基本图形的生成与区域填空,重点：掌握二维图元直线、圆、区域填充、字符的生成算法。 难点：理解二维图元生成的算法思想并且用C语言进行算法的实现。 课时安排：授课8学时（直线、圆：3学时；区域填充：4学时；字符：1学时）； 上机4学时（直线、圆：2学时；区域填充：2学时）。,2020/11/20,2,第二章 二维基本图形的生成与区域填空,图元生成算法的要求：准确、亮度均匀、速度快。 前面已经知道，矢量显示（随机扫描显示器）和光栅显示是两种完全不同的图形显示技术。,2020/11/20,3,第二章 二维基本图形的生成与区域填空,目前，光栅显示技术占主要地位。 原

2、因是： 1、光栅显示可以用颜色或图案来填充一个区域；2、光栅显示以象素为单位进行读写和存储，可以实现对物体细节的描述；3、图形的任意部分均可以被移动和复制。,2020/11/20,4,第二章 二维基本图形的生成与区域填空,在这一章里，主要介绍在光栅输出设备上，根据物体的坐标描述构造二维几何图形的方法。 在光栅显示器上，象素是屏幕的最小显示单位，因此二维图形的构造就是找出最靠近所描述几何图形的那些象素，将它们置入规定的颜色并放入帧缓存。 我们知道，一幅图是由点、直线、曲线、多边形填充区域以及字符串等组成。下面将讨论这些基本图元的生成技术和算法。,2020/11/20,5,2.1 直线的扫描转换,

3、一、数学直线 在数学上，理想的直线是一条由无穷多个无限小的连续的点组成。 数学直线,2020/11/20,6,2.1 直线的扫描转换,二、光栅平面显示的直线 但在光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻像素的坐标值是阶梯的而不是连续的。,2020/11/20,7,2.1 直线的扫描转换,光栅直线,2020/11/20,8,2.1 直线的扫描转换,三、直线的扫描转换 直线的扫描转换，就是要找出显示平面上最佳逼近理想直线的那些象素的坐标值，并将这些象素置成所要求的

4、颜色。 直线的扫描转换 由于一幅图中可能包含成千上万条直线，所以要求绘制算 法应该： 1、最接近数学上的直线；,2020/11/20,9,2.1 直线的扫描转换,2、沿着线段分布的象素应均匀 不均匀的例子如下图所示，对同样长的线段，如果进行图中的扫描转换，就会因为斜率的不同，产生的象素个数不相等，这样将导致象素亮度分布不均匀。 3、画线速度尽可能的快,2020/11/20,10,2.1.1 生成直线的DDA算法,数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法 一、直线DDA算法描述： 设(x1，y1)和(x2，y2)

5、分别为所求直线的起点和终点坐标，由直线的微分方程得 = m =直线的斜率 (21),2020/11/20,11,2.1.1 生成直线的DDA算法,可通过计算由x方向的增量x引起y的改变来生成直线：xi+1=xi+x (22) yi+1=yi+y=yi+xm (23) 也可通过计算由y方向的增量y引起x的改变来生成直线：yi+1=yi+y (24) xi+1=xi+x=xi+y/m (25) 式(22)至(25)是递推的。,2020/11/20,12,2.1.1 生成直线的DDA算法,二、直线DDA算法思想： 选定x2x1和y2y1中较大者作为步进方向(假设x2x1较大)，取该方向上的增量为一个

6、象素单位(x=1)，然后利用式(21)计算另一个方向的增量(y=xm=m)。通过递推公式(22)至(25)，把每次计算出的(xi+1，yi+1)经取整后送到显示器输出，则得到扫描转换后的直线。 之所以取x2x1和y2y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。,2020/11/20,13,2.1.1 生成直线的DDA算法,另外，算法实现中还应注意直线的生成方向，以决定x及y是取正值还是负值。,2020/11/20,14,2.1.1 生成直线的DDA算法,三、直线DDA算法实现： 1、已知直线的两端点坐标：(x1，y1)，(x2，y2)2、已知画线的颜色：colo

7、r3、计算两个方向的变化量：dx=x2x1 dy=y2y14、求出两个方向最大变化量的绝对值： steps=max(|dx|，|dy|),2020/11/20,15,2.1.1 生成直线的DDA算法,5、计算两个方向的增量(考虑了生成方向)： xin=dx/steps yin=dy/steps6、设置初始象素坐标：x=x1,y=y17、用循环实现直线的绘制：for(i=1；i=steps；i+) putpixel(x，y，color)；/*在(x，y)处，以color色画点*/x=x+xin； y=y+yin；,2020/11/20,16,2.1.1 生成直线的DDA算法,四、直线DDA算法特

8、点： 该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。 五、直线DDA算法程序： 下面给出考虑不同斜率、不同方向直线的DDA画线算法程序：,2020/11/20,17,2.1.1 生成直线的DDA算法,void DDAline(int x0,int y0,int x1,int y1,int color) int x; float dx,dy,y,k; dx=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;x=x1;x+)putpixel(x，int(y+0.5)，color); /在(x，y)处，以color色画点y=y+k;,202

9、0/11/20,18,2.1.2 生成直线的Bresenham算法,从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。 在生成直线的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一种基于误差判别式来生成直线的方法。 一、直线Bresenham算法描述： 它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。,2020/11/20,19,2.1.2 生成直线的Bresenham算法,我们首先讨论m=y/x，当0m1且x1x2时的Bresenham算法

10、。从DDA直线算法可知这些条件成立时，公式(2-2)、(2-3)可写成： xi+1=xi+1 (26) yi+1=yi+m (27) 有两种Bresenham算法思想，它们各自从不同角度介绍了Bresenham算法思想，得出的误差判别式都是一样的。,2020/11/20,20,2.1.2 生成直线的Bresenham算法,二、直线Bresenham算法思想之一 由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(xi，yi)，它是直线上点(xi，yi)的最佳近似，并且xi=xi(假设m1），如下图所示。那么，直线上下一个象素点的可能位置是(xi+1，yi)或(xi+1，yi

11、+1)。,2020/11/20,21,2.1.2 生成直线的Bresenham算法,2020/11/20,22,2.1.2 生成直线的Bresenham算法,由图中可以知道，在x=xi+1处，直线上点的y值是y=m(xi+1)+b，该点离象素点(xi+1，yi)和象素点(xi+1，yi+1)的距离分别是d1和d2： d1=y-yi=m(xi+1)+b-yi (28) d2=(yi+1)-y=(yi+1)-m(xi+1)-b (29) 这两个距离差是 d1-d2=2m(xi+1)-2yi2b-1 (210),2020/11/20,23,2.1.2 生成直线的Bresenham算法,我们来分析公式

12、(2-10)：(1)当此值为正时，d1d2，说明直线上理论点离(xi+1，yi+1)象素较近，下一个象素点应取(xi+1，yi+1)。(2)当此值为负时，d1d2，说明直线上理论点离(xi+1，yi)象素较近，则下一个象素点应取(xi+1，yi)。(3)当此值为零时，说明直线上理论点离上、下两个象素点的距离相等，取哪个点都行，假设算法规定这种情况下取(xi+1，yi+1)作为下一个象素点。,2020/11/20,24,2.1.2 生成直线的Bresenham算法,因此只要利用(d1-d2)的符号就可以决定下一个象素点的选择。为此，我们进一步定义一个新的判别式： pi=x(d1-d2)=2yxi

13、-2xyi+c (211)式(2-11)中的x=(x2-x1)0，因此pi与(d1-d2)有相同的符号； 这里y=y2-y1，m=y/x；c=2y+x(2b-1)。 下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c。,2020/11/20,25,2.1.2 生成直线的Bresenham算法,将式(2-11)中的下标i改写成i+1，得到： pi+1=2yxi+1-2xyi+1+c (212)将式(2-12)减去(2-11)，并利用xi+1=xi+1，可得： pi+1= pi+2y-2x(yi+1-yi) (213) 再假设直线的初始端点恰好是其象素点的坐标，即满足： y1=

14、mx1+b (214),2020/11/20,26,2.1.2 生成直线的Bresenham算法,由式(2-11)和式(2-14)得到p1的初始值： p1=2y-x (215) 这样，我们可利用误差判别变量，得到如下算法表示： 初始 p1=2y-x (216) 当pi0时： yi+1=yi+1,xi+1=xi+1，pi+1=pi+2(y-x) 否则：yi+1=yi,xi+1=xi+1， pi+1=pi+2y,2020/11/20,27,2.1.2 生成直线的Bresenham算法,从式(2-16)可以看出，第i+1步的判别变量pi+1仅与第i步的判别变量pi、直线的两个端点坐标分量差x和y有关

15、，运算中只含有整数相加和乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。 三、直线Bresenham算法思想之二 由于象素坐标的整数性，数学点(xi，yi)与所取象素点(xi，yir)间会引起误差(i)，当xi列上已用象素坐标(xi，yir)表示直线上的点(xi，yi)，下一直线点B(xi+1，yi+1)，是取象素点C(xi+1，yir )，还是D(xi1，y(i+1)r)呢？,2020/11/20,28,2.1.2 生成直线的Bresenham算法,设A为CD边的中点，正确的选择： 若B点在A点上方，选择D点； 否则，选C点。 用误差式描述为： (xi+1)=BC

16、-AC=(yi+1-yir)-0.5 (28),2020/11/20,29,2.1.2 生成直线的Bresenham算法,求递推公式： (xi+2)=(yi+2-y(i+1)r)-0.5 = yi+1+m-y(i+1)r-0.5 (29) 当(xi+1)0时，选D点，y(i+1)r = yir+1 (xi+2)= yi+1+m-yir-1-0.5=(xi+1)+m-1 (210) 当(xi+1)0时，选C点，y(i+1)r = yir (xi+2)= yi+1+myir-0.5=(xi+1)+m (211),2020/11/20,30,2.1.2 生成直线的Bresenham算法,初始时： (

17、xs+1)=BC-AC=m-0.5 (212),2020/11/20,31,2.1.2 生成直线的Bresenham算法,为了运算中不含实型数，同时不影响不等式的判断，将方程两边同乘一正整数。 令方程两边同乘2x，即p=2x，则： 初始时： p = 2y-x (213)递推式： 当p0时： p=p+2(yx)；y+；x+；否则： p=p+2y；x+； (214),2020/11/20,32,2.1.2 生成直线的Bresenham算法,四、直线Bresenham算法实现 条件：0m1且x1x2 1、输入线段的两个端点坐标和画线颜色：x1，y1，x2，y2，color；2、设置象素坐标初值：x=

18、x1，y=y1；3、设置初始误差判别值：p=2y-x；4、分别计算：x=x2-x1、y=y2-y1；,2020/11/20,33,2.1.2 生成直线的Bresenham算法,5、循环实现直线的生成：for(x=x1；x=0) y=y+1；p=p+2(y-x)；else p=p+2y； ,2020/11/20,34,2.1.2 生成直线的Bresenham算法,五、直线Bresenham算法完善 现在我们修正(2-16)公式，以适应对任何方向及任何斜率线段的绘制。如下图所示，线段的方向可分为八种，从原点出发射向八个区。由线段按图中所示的区域位置可决定xi+1和yi+1的变换规律。 容易证明：当

19、线段处于、区时，以|x|和|y|代替前面公式中的x和y，当线段处于、区时，将公式中的|x|和|y|对换，则上述两公式仍有效。,2020/11/20,35,2.1.2 生成直线的Bresenham算法,在线段起点区分线段方向,2020/11/20,36,2.1.2 生成直线的Bresenham算法,七、直线Bresenham算法特点 由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。 八、直线Bresenham算法程序 void Bresenhamline (int x1,int y1,int x2,int y2,int color)int x, y, dx, dy, s1,

20、s2, p, temp, interchange, i;x=x1;y=y1;dx=abs(x2-x1);dy=abs(y2-y1);if(x2x1)s1=1;elses1=-1;,2020/11/20,37,2.1.2 生成直线的Bresenham算法,if(y2y1)s2=1;elses2=-1;if(dydx)temp=dx;dx=dy;dy=temp;interchange=1;elseinterchange=0;p=2*dy-dx;,2020/11/20,38,2.1.2 生成直线的Bresenham算法,for(i=1;i=0)if(interchange= =0)y=y+s2;el

21、sex=x+s1;p=p-2*dx;if(interchange= =0)x=x+s1; elsey=y+s2;p=p+2*dy;,2020/11/20,39,2.1 直线的生成习题,1.DDA法生成直线的基本原理是什么？,2020/11/20,40,2.2 圆的生成,这里仅讨论圆心位于坐标原点的圆的扫描转换算法，对于圆心不在原点的圆，可先用平移变换，将它的圆心平移到原点，然后进行扫描转换，最后再平移到原来的位置。 有几种较容易的方法可以得到圆的扫描转换，但是效率都不高。例如：直角坐标法和极坐标法： 1、直角坐标法 圆的直角坐标方程为 x2+y2=R2若取x作为自变量，解出y，得到,2020/

22、11/20,41,2.2 圆的生成,(217) 我们可以先扫描转换四分之一的圆周。让自变量x从0到R以单位步长增加，在每一步时可解出y，然后调用画点函数即可逐点画出圆。但这样做，由于有乘方和平方根运算，并且都是浮点运算，算法效率不高。而且当x接近R值时(圆心在原点)，在圆周上的点（R，0）附近，由于圆的斜率趋于无穷大，使得圆周上有较大的间隙。,2020/11/20,42,2.2 圆的生成,2、极坐标法 假设圆周上一点P（x，y）处的半径与x轴的夹角为，则圆的极坐标方程为 x=Rcos (218) y=Rsin 利用下面将要介绍的圆周上点的对称性，那么自变量的取值范围就是(0，45)。这个方法涉

23、及三角函数计算和乘法运算，计算量较大。因此，也不是一种有效的方法。,2020/11/20,43,2.2.1 圆的八分对称性,圆心位于原点的圆有四条对称轴x=0、y=0、x=y和x=y，见下图。从而若已知圆弧上一点P(x，y)，就可以得到其关于四条对称轴的七个对称点，这种性质称为八分对称性。因此只要能画出八分之一的圆弧，就可以利用对称性的原理得到整个圆弧。下面的函数CirclePoints()用来显示P(x，y)及其七个对称点。,2020/11/20,44,2.2.1 圆的八分对称性,void CirclePoints(x,y,color)int x,y,color;putpixel(x,y,c

24、olor);putpixel(x,y,color);putpixel(x,y,color);putpixel(x,y,color);putpixel(y,x,color);putpixel(y,x,color);putpixel(y,x,color);putpixel(y,x,color);,2020/11/20,45,2.2.1 圆的八分对称性,圆的八分对称性 注意： 当圆心不在原点时，只须在putpixel()函数中加上平移量x0、y0（圆心坐标）即可。,2020/11/20,46,2.2.1 圆的八分对称性,例如 当 x0=300，y0=200时，则： putpixel(x0+x，y0+

25、y，color)；putpixel(x0+x，y0-y，color)；putpixel(x0-x，y0+y，color)；putpixel(x0-x，y0-y，color)；putpixel(x0+y，y0+x，color)；putpixel(x0+y，y0-x，color)；putpixel(x0-y，y0+x，color)；putpixel(x0-y，y0-x，color)；,2020/11/20,47,2.2.2 中点算法生成圆,中点画圆算法在一个方向上取单位间隔，在另一个方向的取值由两种可能取值的中点离圆的远近而定。实际处理中，用决策变量的符号来确定象素点的选择，因此算法效率较高。 一

26、、中点画圆算法描述 设要显示圆的圆心在原点(0，0)，半径为R，起点在(0，R)处，终点在( , )处，顺时针生成八分之一圆，利用对称性扫描转换全部圆。 为了应用中点画圆法，我们定义一个圆函数 F(x，y)=x2+y2-R2 (219),2020/11/20,48,2.2.2 中点算法生成圆,任何点(x，y)的相对位置可由圆函数的符号来检测： 0点(x，y)位于数学圆外,2020/11/20,49,2.2.2 中点算法生成圆,如下图所示，图中有两条圆弧A和B，假定当前取点为Pi(xi，yi)，如果顺时针生成圆，那么下一点只能取正右方的点E(xi+1，yi)或右下方的点SE(xi+1，yi-1)

27、两者之一。 中点画线算法,2020/11/20,50,2.2.2 中点算法生成圆,假设M是E和SE的中点，则： 1、当F(M)0时，M在圆外(圆弧B)，表明SE点离圆更近，应取SE点；3、当F(M)=0时，在E点与SE点之中随便取一个即可，我们约定取SE点。,2020/11/20,51,2.2.2 中点算法生成圆,二、中点画圆算法思想 因此，我们用中点M的圆函数作为决策变量di，同时用增量法来迭代计算下一个中点M的决策变量di+1。 (221) 下面分两种情况来讨论在迭代计算中决策变量di+1的推导。 1、见图（a），若di0，则选择E点，接着下一个中点就是 ，这时新的决策变量为： (222)

28、,2020/11/20,52,2.2.2 中点算法生成圆,（a）(di0) 中点画线算法,2020/11/20,53,2.2.2 中点算法生成圆,式(222)减去(221)得： di+1=di+2xi+3 (223) 2、见图（b），若di0，则选择SE点，接着下一个中点就是 ，这时新的决策变量为： (224),2020/11/20,54,2.2.2 中点算法生成圆,（b）(di0) 中点画线算法 式(224)减去(221)得： di+1=di+2(xi-yi)+5 (225),2020/11/20,55,2.2.2 中点算法生成圆,我们利用递推迭代计算这八分之一圆弧上的每个点，每次迭代需要两

29、步处理：（1）用前一次迭代算出的决策变量的符号来决定本次选择的点。（2）对本次选择的点，重新递推计算得出新的决策变量的值。 剩下的问题是计算初始决策变量d0，如下图所示。对于初始点(0，R)，顺时针生成八分之一圆，下一个中点M的坐标是 ，所以：,2020/11/20,56,2.2.2 中点算法生成圆,(226） 生成圆的初始条件和圆的生成方向,2020/11/20,57,2.2.2 中点算法生成圆,三、中点画圆算法实现 1、输入：圆半径r、圆心(x0，y0)；2、确定初值：x=0，y=r、d=5/4-r；3、While(x=y)利用八分对称性，用规定的颜色color画八个象素点(x，y)； 若

30、d0y=y-1；d=d+2(x-y)+5；否则d=d+2x+3；x=x+1；,2020/11/20,58,2.2.2 中点算法生成圆,四、中点画圆算法完善 在上述算法中，使用了浮点数来表示决策变量d。为了简化算法，摆脱浮点数，在算法中全部使用整数，我们使用e=d-1/4代替d。显然，初值d0=5/4-r对应于e0=1-r。决策变量d0对应于e-1/4。算法中其它与d有关的式子可把d直接换成e。又由于e的初值为整数，且在运算过程中的迭代值也是整数，故e始终是整数，所以e-1/4等价于e0。因此，可以写出完全用整数实现的中点画圆算法。要求：写出用整数实现的中点画圆算法程序，并上机调试，观看运行结果

31、。,2020/11/20,59,2.2.2 中点算法生成圆,五、中点画圆算法程序 void MidpointCircle(int x0,int y0,int r,int color)int x,y;float d;x=0;y=r;d=5.0/4-r;,2020/11/20,60,2.2.2 中点算法生成圆,while(x=y)putdot(x0,y0,x,y,color);if(d0)d+=x*2.0+3;elsed+=2.0*(x-y)+5;y-; x+;,2020/11/20,61,2.2.2 中点算法生成圆,putdot(x0,y0,x,y,color)putpixel(x0+x,y0+

32、y,color);putpixel(x0+x,y0-y,color);putpixel(x0-x,y0+y,color);putpixel(x0-x,y0-y,color);putpixel(x0+y,y0+x,color);putpixel(x0+y,y0-x,color);putpixel(x0-y,y0+x,color);putpixel(x0-y,y0-x,color);,2020/11/20,62,2.2.3 正负算法生成圆,正负法是利用平面曲线将平面划分成正负区域，对当前点产生的圆函数进行符号判别，利用负反馈调整以决定下一个点的产生来直接生成圆弧。 一、正负画圆算法描述 设要显示圆

33、的圆心在原点(0，0)，半径为R，初始点的坐标为(0，R)，顺时针生成八分之一圆，令：F(x，y)=x2+y2-R2 则圆的方程为： F(x，y)=0 (2-27) 当点(x，y)在圆内时，则F(x，y)0；当点(x，y)在圆上时，则F(x，y)=0；,2020/11/20,63,2.2.3 正负算法生成圆,二、正负画圆算法思想 现以下图的AB弧为例，来说明正负画圆法(顺时针生成圆)。,2020/11/20,64,2.2.3 正负算法生成圆,假设当前点为Pi(xi，yi)，取下一个点Pi+1(xi+1，yi+1)的原则是： 1、当F(xi，yi)0时：取xi+1= xi+1，yi+1= yi。

34、即向右走一步，从圆内走向圆外。对应图(a)中的从Pi到Pi+1。2、当F(xi，yi)0时：取xi+1= xi，yi+1= yi-1。即向下走一步，从圆外走向圆内。对应图(b)中的从Pi到Pi+1。 由于向圆内或向圆外走取决于F(xi，yi)的正负，因此称为正负法。 下面分两种情况求出F(xi，yi)的递推公式：,2020/11/20,65,2.2.3 正负算法生成圆,(1) 当F(xi，yi)0时，向右走，取xi+1=xi+1，yi+1=yi，则 F(xi+1，yi+1)=F(xi+1，yi)=(xi+1)2+yi2-R2=(xi2+yi2-R2)+2xi+1= F(xi，yi)+2xi+1

35、 (2-28),2020/11/20,66,2.2.3 正负算法生成圆,(2) 当F(xi，yi)0时，向下走，取xi+1=xi，yi+1=yi-1，则 F(xi+1，yi+1)=F(xi，yi-1)=xi2+(yi-1)2-R2=(xi2+yi2-R2)-2yi+1= F(xi，yi)-2yi+1 (2-29),2020/11/20,67,2.2.3 正负算法生成圆,初始时，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30) 公式(2-28)、(2-29)和(2-30)就构成正负画圆算法的核心。 给象素坐标(x，y)及F赋初始值后，进入循环画点； 画点后，根据F的符号进

36、行F值的递推和下一个点的获取，直到xy为止。 同前面介绍的一样，利用圆的八分对称性，循环一次，画八个点。,2020/11/20,68,2.2.3 正负算法生成圆,三、正负画圆算法实现 注意：初值不同、圆的生成方向不同时，当前点和下一个点的获取原则是不同的，见下图。 例如，初始点(R，0)，逆时针生成圆，从图（b）可知： 若当前点Pi在圆内，则下一点Pi+1(xi，yi+1)，即向上走一步；若当前点Pi在圆外，则下一点Pi+1(xi-1，yi)，即向左走一步；,2020/11/20,69,2.2.3 正负算法生成圆,(a) 顺时针生成圆(b) 逆时针生成圆,2020/11/20,70,2.2.3

37、 正负算法生成圆,四、正负画圆算法特点 物理意义清楚，程序中只含整数运算，因此算法速度快。 五、正负画圆算法程序 / 顺时针生成圆void PNARC(int x0,int y0,int r,int color)int x=0,y=r,f=0;,2020/11/20,71,2.2.3 正负算法生成圆,while(x=y)putdot(x0,y0,x,y,color);if(f=0)f=f+2*x+1;x+;elsef=f-2*y+1;y-;,2020/11/20,72,2.2 圆的生成习题,1. 用自己的语言描述中点画圆算法。,2020/11/20,73,2.3 区域填充,前面介绍的直线和圆都

38、属于线划图，然而，光栅显示的一个重要特点是能进行面着色，区域填充就是在一个闭合区域内填充某种颜色或图案。 区域填充一般分两类：多边形填充和种子填充。 一、多边形填充 1、填充条件 多边形的顶点序列(Pi，i=0，1，n)、填充色。 2、多边形内点的判别准则 对多边形进行填充，关键是找出多边形内的象素。在顺序给定多边形顶点坐标的情况下，如何判明一个象素点是处于多边形的内部还是外部呢？,2020/11/20,74,2.3 区域填充,从测试点引出一条伸向无穷远处的射线(假设是水平向右的射线)，因为多边形是闭合的，那么： 若射线与多边形边界的交点个数为奇数时，则该点为内点(例：图中测试点4引出的射线)

39、；反之，交点个数为偶数时，则该点为外点。(例：测试点2引出的射线)。,2020/11/20,75,2.3 区域填充,多边形内点的判别准则和奇异点,2020/11/20,76,2.3 区域填充,3、奇异点的处理 上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它们应该是内点，但实际上却是外点。 而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。,2020/11/20,77,2.3 区域填充,综合以上情况，我们将多边形的顶点分为两大类： (1) 局部极值点：如图中的点P1、

40、P2、P4和P6。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的同一侧。(2)非极值点：如图中的点P3、P5。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的两侧。 处理奇异点规则： （1）对于局部极值点，应看成两个点； （2）对于非极值点，应看成一个点。,2020/11/20,78,2.3 区域填充,4、逐点判别算法步骤： (1)求出多边形的最小包围盒：从Pi(xi，yi)中求极值，xmin、ymin、xmax、ymax。 (2)对包围盒中的每个象素引水平射线进行测试。 (3)求出该射线与多边形每条边的有效交点个数。 (4)如果个数为奇数：该点置为填充色。

41、(5)否则：该点置为背景色。 逐点判别算法虽然简单，但不可取，原因是速度慢。它割断了各象素之间的联系，孤立地考虑问题，由于要对每个象素进行多次求交运算，求交时要做大量的乘除运算，从而影响了填充速度。,2020/11/20,79,2.3 区域填充,二、种子填充 种子填充是将区域内的一点(种子)赋予给定的颜色，然后将这种颜色扩展到整个区域内的过程。 1、填充条件 区域内一点的坐标即种子坐标、边界色、填充色。 2、连通方式 区域是互相连通着的象素的集合，连通方式可分为四连通和八连通。,2020/11/20,80,2.3 区域填充,四连通：从区域内一点出发，可通过四个方向：上、下、左、右到达该区域内部

42、的任意象素。 八连通：区域内部从一个象素到达另一个象素的移动路径，除了上、下、左、右四个方向外，还允许沿着对角线方向。,2020/11/20,81,2.3 区域填充,注意： （1） 八连通区域中，既然区域内的两个象素可以通过对角线相通，那么，区域边界上的象素则不能通过对角线相连，否则填充就会溢出到区域外，因此，八连通区域的边界线必须是四连通的，见下图(a)； （2）而四连通区域，其边界象素是四连通和八连通的都可以，见下图(b)。,2020/11/20,82,2.3 区域填充,(a) 八连通区域四连通边界(b) 四连通区域八连通(或四连通)边界,2020/11/20,83,2.3 区域填充,3、

43、内点(x,y)的检测条件 (1) if(getpixel(x,y)!=边界色 y= ymax;y+) 合并当前扫描线y的ET表； 将y桶中每个记录按x项升序排列； 在当前y值下，将两两记录的x值之间的象素进行填充； 删除y=ymax的边记录； 修改边记录x=x+1/m； ,2020/11/20,96,2.3.1 边相关扫描线多边形填充算法,五、边相关扫描线填充算法特点 该算法充分利用多边形的边相关性和扫描线的相关性，使用ET表对多边形的非水平边进行登记；用AET表的建立和更新来支持填充，大大地减少了求交点的计算量，有效地提高了填充速度。,2020/11/20,97,2.3.2 扫描线种子填充算

44、法,该算法属于种子填充算法，它是以扫描线上的区段为单位进行操作。所谓区段，就是一条扫描线上相连着的若干内部象素的集合。 一、扫描线种子填充算法思想 扫描线种子填充算法的基本思想是：首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存起来。反复这个过程，直到所保存的各区段都填充完毕。,2020/11/20,98,2.3.2 扫描线种子填充算法,二、扫描线种子填充算法实现 借助于堆栈，上述算法实现步骤如下： 1、初始化堆栈。2、种子压入堆栈。3、while（堆栈非空） (1)从堆栈弹出种子象素。(2)

45、如果种子象素尚未填充，则： a.求出种子区段：xleft、xright; b.填充整个区段。,2020/11/20,99,2.3.2 扫描线种子填充算法,c.检查相邻的上扫描线的xleftxxright区间内,是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright范围内的最右边的象素，作为新的种子象素依次压入堆栈。 d.检查相邻的下扫描线的xleftxxright区间内，是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright范围内的最右边的象素，作为新的种子象素依次压入堆栈。 ,2020/11/20,100,2.3.2 扫描线种子填充算法,四

46、、扫描线种子填充算法特点 1、该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象素，而是代表一个尚未填充的区段。 2、进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。 3、种子出栈时，则填充整个区段。 4、这样有机的结合：一边对尚未填充象素的登记（象素进栈），一边进行填充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。,2020/11/20,101,2.3.3 边标志填充算法,在光栅显示平面上，多边形是封闭的，它是用某一边界色围成的一个闭合区域，填充是逐行进行的，即用扫描线逐行对多边形求交，在交点对之间填充。边标志填充算法就是在逐

47、行处理时，利用边界色作为标志来进行填充的。例如某扫描线从左到右扫描时碰到边界色，立刻改变标志的状态，接下来再根据标志的状态决定某象素点是否填充。,2020/11/20,102,2.3.3 边标志填充算法,一、边标志填充算法思想 扫描线具有连贯性，这种连贯性只有在扫描线与多边形相交处才会发生变化，而每次的变化结果：无非是在前景色和背景色之间相互“切换”。 边标志填充算法正是基于这一发现，先在屏幕上生成多边形轮廓线，然后逐条扫描处理。处理中：逐点读取象素值，若为边界色，则对该象素值进行颜色切换。,2020/11/20,103,2.3.3 边标志填充算法,二、边标志填充算法实现 1、用边界色画出多边

48、形轮廓线，也就是将多边形边界所经过的象素打上边标志。 2、为了缩小范围，加快填充速度，须找出多边形的最小包围盒：xmin、ymin、xmax、ymax。如下图所示。,2020/11/20,104,2.3.3 边标志填充算法,边标志填充算法 3、逐条扫描线进行处理，对每条扫描线依从左往右的顺序，逐个访问该扫描线上的象素。每遇到边界象素，标志取反。然后，按照标志是否为真，决定象素是否为填充色。,2020/11/20,105,2.3.3 边标志填充算法,三、边标志填充算法特点 该算法思想简单，实现容易。既不需要求交点、交点排序、边的登记，也不需要使用链表、堆栈等数据结构。 四、边标志填充算法程序 E

49、dgeMarkFill(int p2,int n,int boundarycolor,int newcolor),2020/11/20,106,2.3.3 边标志填充算法,int i, x,y,flag,xmin,xmax,ymin,ymax;setcolor(boundarycolor); /*设置画笔色*/ for(i=0 ;in;i+) line(pi0,pi1,p(i+1)%n0,p(i+1)%n)1); /*画出多边形的n条边*/用求极值的算法，从多边形顶点数组p中，求出xmin,xmax,ymin,ymax;,2020/11/20,107,2.3.3 边标志填充算法,for(y=y

50、min;y=ymax;y+) flag=-1; for(x=xmin;x=xmax;x+) if(getpixel(x,y)=boundarycolor) flag=(-1) *flag;if(flag=1)putpixel(x,y, newcolor); ,2020/11/20,108,2.3.3 边标志填充算法,五、边标志填充算法错误处理 1、该算法虽然简单，但程序运行后会出现局部错误。从下图可以发现，对于多边形顶点为局部极值点时，扫描线与多边形的相交次数不再是偶数，而是奇数，填充时会出现“抽丝”现象。即某扫描线上不该填充的区段填上色，而应该填充的区段却没有填上色。解决的办法：判断多边形顶

51、点的性质，如果是局部极值点，那么扫描线碰上它则不改变标志。,2020/11/20,109,2.3.3 边标志填充算法,2、特别当心多边形边界的扫描转换。在这里就不能考虑：不同的斜率产生的直线要亮度均匀，如下图(a)所示。否则当扫描线y遇到斜率小于1的边界线时，碰到几个边界点，会引起标志的无序改变，将导致填充的错误。 解决的办法：对于不同斜率的边界，都要使用斜率大于1的直线扫描转换方法：每次y方向增长一步，x方向增长1/m步距，以保证扫描线y遇到斜率小于1的边界时，只能遇到一个点。请看下图(b)。,2020/11/20,110,2.3.3 边标志填充算法,在边标志填充算法中要注意多边形边界的扫描

52、转换,2020/11/20,111,2.3.4 图案填充,前面介绍的区域填充算法，都是把区域内部的象素全部置成同一种颜色。但在实际应用中，有时需要用图案来填充平面区域。这可以将前面的填充算法中写象素的那部分代码稍加修改来实现: 在确定了区域内点后，不是马上对该象素填色，而是先将该象素映射到图案位图的对应位置。根据图案该位置的象素值，决定填充颜色。,2020/11/20,112,2.3.4 图案填充,一、图案填充方式： 1、透明方式:若是以透明方式填充图案，则当图案位图的对应位置为1时，用前景色写象素，否则，不改变该象素的值。 2、不透明方式: 而若是以不透明方式填充图案，则当图案位图的对应位置

53、为1时，用前景色写象素，否则，用背景色写象素。,2020/11/20,113,2.3.4 图案填充,二、图案定位法： 1、相对定位法:把图案原点与填充区域边界或内部的某点对齐。这样，当被填充的多边形移动时，图案也跟着移动，看起来比较自然。 对于多边形，可取边界上最左边的顶点，而对于圆和椭圆这样具有光滑边界的区域，则最好取区域内部某一点，如取中心与图案原点对齐。,2020/11/20,114,2.3.4 图案填充,2、绝对定位法：把图案原点与屏幕原点对齐。该方法可以将整个屏幕看成被要填充的图案布满，只是要填充的区域是透明的，可以让图案显露出来，其它区域对此图案却是不透明的，图案被全部挡住。 这种

54、方法比较简单，并且在相邻区域用同一图案填充时，可以达到无缝连接的效果。但它有一个潜在的毛病，即当区域移动时，图案不会跟着移动。其效果是区域内的图案变了。,2020/11/20,115,2.3.4 图案填充,三、图案填充算法实现 下面讨论在第二种绝对定位法下用不透明方式对平面区域填充图案： 假设填充图案是一个MN的位图，用MN的数组存放。M、N一般比需要填充区域的尺寸小得多（88、1616、3232），所以图案总是设计成周期性的，使之能通过重复使用来构成任意尺寸的图案。当确定了区域内点p（x,y）后，则图案位图上的对应位置为p（x%M，y%N），其中%为C语言整除取余运算符,然后取出图案位图该位

55、置的象素进行填充。,2020/11/20,116,2.3.4 图案填充,四、图案填充算法程序 / 采用不透明方式绝对定位法填充图案的程序伪代码: maskpixel(int x,int y,int newcolor,int backgroundcolor) int xx,yy;int maskcode88= 0,0,0,0,1,0,0,0,/*砖缝图案*/ 0,0,0,0,1,0,0,0, 0,0,0,0,1,0,0,0, 1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1;,2

56、020/11/20,117,2.3.4 图案填充,xx=x%8; /*多边形区域内点坐标x映射到图案坐标xx*/yy=y%8; /*多边形区域内点坐标y到图案坐标yy*/if(maskcodeyyxx)putpixel(x,y, newcolor); /* newcolor 为前景色*/elseputpixel(x,y, backgroundcolor); /* backgroundcolor为背景色*/,2020/11/20,118,2.4.1 点阵字符,我们讨论的字符是指字母、数字、汉字、标点等符号。计算机中，字符由一个数字编码唯一标识，对于一个字符来说，它所对应的编码是由它所属的字符集决

57、定。 1、ASCII码 目前，国际上普遍采用的字符编码是ASCII码（American Standard Code for Information Interchange）美国信息交换标准代码。它是用七位二进制数进行编码，共能表示128个字符，其中编码031表示控制字符（不可显示），编码32127表示英文字母、数字、标点符号等可显示字符。 一个字符的ASCII码用一个字节（8位）表示，其最高位不用或者作为奇偶校验位。,2020/11/20,119,2.4.1 点阵字符,2、国标码 我国除了采用ASCII码外，还制定了汉字编码的国家标准字符集:中华人民共和国国家标准信息交换编码，代号为“GB23

58、1280”。该字符集共收录常用汉字6763个，图形符号682个。 它规定所有汉字和图形符号组成一个9494的矩阵，在此方阵中，每一行称为“区”，用区码来标识；每一列称为“位”，用位码来标识，一个符号由一个区码和一个位码共同标识。 区码和位码分别需要7个二进制位，同样，为了方便，各采用一个字节表示。所以在计算机中，汉字（符号）国标码占用两个字节。,2020/11/20,120,2.4.1 点阵字符,3、两种编码的区别 那么，给定一个字节，如何来确定它代表的是ASCII码，还是国标码的区码和位码呢？通常采用字符中冗余的最高位来标识： 最高位为0时，表示ASCII码；最高位为1时，表示汉字编码的区码（高位字节）或位码（低位字节）。 4、机内码 机内码： 计算机内表示字符的编码 1、西文字符 西文字符的机内码就是ASCII码。2、中文字符国标码为：2020H+区位码的十六进制表示机内码为：8080H+国标码 即：A0A0H+区位码的十六进制表示,2020/11/20,121,2.4.1 点阵字符,3、举例“啊”字的区位码为1601，转换为十六进制表示应为1001H（区码16转为10H，位码01转为01H）。于是，“啊”