第3章 基本图形光栅化.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机图形学,第,3,章,基本图形光栅化,主讲教师：尉秀梅,第,3,章 基本图形光栅化,3.1,直线的光栅化,3.2,圆的光栅化,3.3,区域填充,3.4,字符表示,3.5,反走样,3.1,直线的光栅化,在数学上，理想的直线是没有宽度的、由无数个点构成的集合。当我们对直线进行光栅化时，只能在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序对这些像素进行写操作，这就是通常所说的直线的扫描转换。,通常用于直线光栅化的算法有数值微分法（,DDA,）、中点画线法和,Bresenham,画线算法。,3.1.1DDA,算法,DDA,（,Digital Differential Analyzer,）,法是根据直线的微分方程来画直线的。,设直线的起点坐标为,Ps(xs,ys,),，终点坐标为,Pe(xe,ye,),，令,x,=,xe,-,xs,，,y,=,ye,-,ys,，则要绘制的直线的微分方程为,取时间步长为,1/t,，则可得上述微分方程数,值解的递推公式为,3.1.1DDA,算法,通常情况下，直线的方向分为,8,个不同的区域，每个区域的处理方法有所不同。,区域,dx,dy,1a,1,y/,x,1b,x/,y,1,2a,-1,y/,x,2b,-,x/,y,1,3a,-1,-,y/,x,3b,-,x/,y,-1,4a,1,-,y/,x,4b,y/,x,-1,3.1.1 DDA,算法,例：画直线段,P0(0,0)-P1(5,2),解：斜率,K=2/5=0.4,，所以,X,方向每次步长为,1,，,Y,方向递增,K.,初始点为（,0,，,0,）。,x int(y+0.5)y,000,100.4,210.8,311.2,421.6,522.0,3.1.2,中点画线法,为了讨论方便，假设直线的斜率在,0,到,1,之间，若直线在,x,方向上增加一个光栅单位，则在,y,方向上的增量只能在,0,到,1,之间。设,P,（,x,y,）,是直线上的一点，与,P,点最近的网格点为,（,x,i,y,i,）,那么，下一个与直线最近的像素只能是正右方的网格点,P,B,（,x,i,+1,y,i,）,或右上方的网格点,P,T,（,x,i,+1,y,i,+1,）,两者之一。再以点,M,（,x,i,+1,y,i,+0.5,）,表示,P,B,和,P,T,的中点，设,Q,是直线与垂直线,x=x,i,+1,的交点。显然，若,M,在,Q,的下方，则,P,T,离直线较近，应取,P,T,为下一个像素点，否则应取,P,B,做为下一个像素点，这就是中点画线算法的基本思想。,3.1.2,中点画线法,设直线的起点和终点分别为（,x,0,y,0,),和,(,x,1,y,1,),，则直线方程为,F(x,y,)=,ax+by+c,=0,其中,a=y,0,-y,1,，,b=x,1,-x,0,，,c=x,0,y,1,-x,1,y,0,。,构造,判别式,：采用增量计算,d=F(M)=F(x+1,y+0.5)=a(x+1)+b(y+0.5)+c,在,d0,的情况下，取正右方像素,P,B,，,判断下一像素应计算,d,1,=a(x+2)+b(y+0.5)+c=,d+,a,在,d0,的情况下，取右上方像素,P,T,，,判断下一像素应计算,d,2,=a(x+2)+b(y+1.5)=,d+,a+b,d,的初始值,d,0,=a+0.5b,3.1.2,中点画线法,由于我们使用的只是,d,的符号，而且,d,的增量都是整数，只是其初始值包含小数。因此，我们可以用,2d,代替,d,，来摆脱小数。,如果进一步把算法中,2*a,改为,a+a,等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。,3.1.3,Bresenham,画线算法,原理,:,过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。,若,st,，则,S,i,比较靠近理想直线，应选,S,i,;,若,st,，则,T,i,比较靠近理想直线，应选,T,i,。,设直线的起点和终点分别为,（,x,1,y,1,),和,(x,2,y,2,),，,则直线方程为,y=y,1,+dy/dx(x-x,1,),，其中,dx,=x,2,-x,1,，,dy,=y,2,-y,1,直线方程经变换后可表示为从（,0,，,0,）到,(dx,dy),，方程可简化为,y=dy/dx*x,s-t,=2*(x,i-1,+1)-2y,i-1,-1,s=*(x,i-1,+1)-y,i-1,t=(y,i-1,+1)-*(x,i-1,+1),dx(s-t,)=2(x,i-1,dy-2y,i-1,dx)+2dy-dx,3.1.3,Bresenham,画线算法,递推公式：,当,d,i,0,时，选,T,i,当,d,i,1,时，将,x,、,y,和,dx,、,dy,对换，即以,y,向作为增长方向，,y,总是增,1,（或减,1,），,x,是否增减,1,，则根据的符号判断：,d0,时,x,增,1,（或减,1,）；,d0,时，,x,不变。,（,2,）根据,dx,和,dy,的符号来控制,(,x,或,y,),增,1,还是减,1,。,双步算法,1987,年有人提出二步法，即每循环一次不是绘制一个象素，而是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。,下图为双步算法的四种情况,。,3.2,圆的光栅化,与直线的生成类似，圆的生成算法的好坏将直接影响到绘图的效率。本节仅讨论圆心位于坐标原点的圆弧生成算法，对于圆心为任意的圆弧，可以先将其平移到原点，然后光栅化，再平移到原来的位置。,3.2.1,中点画圆算法,假设圆的半径为,R,，则圆的方程为,当点（,x,y,）在圆内时，,F,（,x,y,）,0,;,当点（,x,y,）在圆上时，,F,（,x,y,）,=0,;,3.2.1,中点画圆算法,中点画圆算法的基本原理是：假设点,P,（,x,p,y,p,）,为圆弧上一点，如图,3-5,所示，那么，下一个与圆弧最近的像素点只能是正右方的点,P,1,（,x,p,+1,y,p,）,或右下方的点,P,2,(x,p,+1,y,p,-1),。令,M,为,P,1,和,P,2,的中点，易知,M,的坐标为,（,x,p,+1,y,p,-0.5,）,。显然，若,M,在圆内，则,P,1,离圆弧近，应取为下一个像素点；否则应取,P,2,作为下一个像素点。,判别式,d,：,d,的初始值为：,在,d0,的情况下，取右下方像素,P,2,，,在,d0,的情况下，取正右方像素,P,1,，,3.2.1,中点画圆算法,为了消除在计算判别式初始值产生的浮点数运算，将用,4d,来代替,d,。,3.2.1,中点画圆算法,下述程序使用中点画圆算法绘制一个,1/8,圆弧。,void,MidPointCircle(int,r,int,color),int,x,y,d,x=0;,y=r;,d=5-4r;,CirclePoint(x,y,color,);,while(x,=y),if(d,=0)d+=8x+12;,else d+=8(x-y)+20;y-;,x+;,CirclePoint(x,y,color,);,3.2.2,Bresenham,画圆算法,Bresenham,画圆算法是最有效的算法之一。,Bresenham,画圆算法的基本原理是如,下,图所示，若,P,i-1,（,x,i-1,y,i-1,）为已经选定的点，那么下一个可能的像素点为其正右方的点,S,i,或右下方的点,T,i,。,若,S,i,到圆弧的距离小于,T,i,到圆弧的距离，则取,S,i,，反之取,T,i,。,3.2.2,Bresenham,画圆算法,设,R,为圆弧的半径，记,P,（,x,y,）到原点的距离的平方与圆的半径的平方之差为,D,（,P,），即,3.2.2,Bresenham,画圆算法,当,d,i,0,时，点,S,i,做为下一个像素点,x,i+1,=x,i,+1,yi=y,i-1,故,当,d,i,0,时，点,T,i,做为下一个像素点,x,i+1,=x,i,+1,yi=y,i-1,-1,故,3.2.2,Bresenham,画圆算法,根据算法，可得,Bresenham,生成圆弧的程序如下：,void,bresenham_arc(int,R,int,color),int,x,y,d,;,x=0;y=R;,d=3-2*R;,while(x,y),putpixel(x,y,color,);,if(d,0),d+=4*x+6;,else,d+=4*(x-y)+10;,y-=1;,x+;,if(x,=y),putpixel(x,y,color,);,3.3,区域填充,区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。,3.3.1,多边形填充算法,1,多边形的表示方法,在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。,顶点表示是用多边形的顶点序列来描述多边形，用序列表示多边形。,点阵表示用位于多边形内的像素集合来描述多边形。,逐点判断法,多边形填充最简单的方法就是逐点判断，即逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。通常有两种方法：射线法，累计角度法。,1,）射线法,从,v,点发出射线与多边形,P,的边相交，若交点的个数为奇数，则,v,位于多边形,P,内；若为偶数，则,v,位于多边形,P,外部。,累计角度法,计算各边的夹角的和，若代数和为零，该点域外；若代数和为,2,，该点域内。,扫描线多边形填充算法,从前画的介绍已知，多边形填充给出一个多边形的边界，要求给多边形边界范围的所有像素单元赋予指定的颜色代码。要完成这个任务，一个首要的问题是判断一个像素是在多边形内还是在多边形外。数学上经常采用的方法是,“,扫描线交点的奇偶数判断,”,法：用一根水平扫描线自左而右通过多边形而与多边形的边界相交，扫描线与边界相交奇次数后进入该多边形，相交偶次数后走出该多边形。,扫描线多边形填充算法,顶点计数问题：,当顶点在多边形两边之下方时，该点计,2,次；,当顶点在多边形两边之上方时，该点计,0,次；,当顶点在多边形两边之间时，该点计,1,次；,对于多边形的水平边，不计它与扫描线的交点,扫描线多边形填充算法,扫描线多边形填充算法是按扫描顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作，多边形填充过程可以分为以下,4,个步骤：,（,1,）求交：计算扫描线与多边形各条边的交点；,（,2,）排序：把所有交点按,x,值递增顺序排序；,（,3,）配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边形的一个相交区间；,（,4,）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。,扫描线多边形填充算法,扫描线算法中采用了较灵活的数据结构，即边的分类表,ET,（,Edge Table,）和活化边表,AEL,（,Active Edge List,），两个表结构中的基本元素都是边结构。边结构的定义为：,Typedef,struct,int,ymax,;,float,x,deltax,;,struct,Edge*,nextEdge,;,Edge;,其中各变量的含义如下：,ymax,：,边的上端点的,y,坐标；,x,：,在,AEL,中表示当前扫描线与边的交点的,x,坐标，初值（即在,ET,中的值）为边的下端点的,x,坐标；,deltax,：,边的斜率的倒数；,nextEdge,：指向下一条边的指针；,扫描线多边形填充算法,边表一般是由一系列存储桶构成的，存储桶的数目与扫描线的数目一样多，按照扫描线递增（减）顺序存放。边表可以通过如下方法建立：先按照下端点的,y,坐标值对所有边进行分组，若某边的下低端点,y,值为,ymin,则该边就放在,ymin,所对应的桶中，按下端点的,x,坐标值递增的顺序将同一组中的边排列成行。,活化边表,AEL,由与当前扫描线相交的边组成，它记录了多边形的边和当前扫描线的所有交点的,x,坐标，并且随着扫描线的递增而不断变化。,扫描线多边形填充算法,扫描线多边形填充算法,ET,表,扫描线多边形填充算法,这样建立了边表,ET,后，扫描多边形填充算法可按如下步骤进行：,（,1,）初始化,AEL,，使之为空，取扫描线纵坐标,y,的初始值为,ET,中非空元素的最小序号。,（,2,）按从下到上的顺序对每条扫描线重复以下各步，直至,AEL,和,ET,为空。,1,）将,ET,中与当前,y,有关的结点加入至,AEL,，同时保存,AEL,中按,x,值从小到大实现的顺序序列。,2,）对于,AEL,中的扫描线,y,，在一对交点之间填充所需的像素值。,3,）从,AEL,中删掉,yymax,的结点。,4,）对于留在,AEL,中的每个结点，执行,xi+1=,xi+deltax,。,5,）对,AEL,中的各结点按,x,值从小到大排序。,6,）使,y=y+1,成为下一条扫描线的坐标。,扫描线多边形填充算法,AEL,表,3.3.2,边填充算法,边填充算法也称为正负相消法。该填充算法的基本原理是：对每一条扫描线，依次求与多边形各条边的交点，将该扫描线上交点右边的所有像素求补，并对多边形的每条边按一定的顺序（逆时针、顺时针均可）做此处理。,栅栏填充算法,栅栏填充算法的基本原理是：对于每条扫描线与多边形的交点，将交点与栅栏之间的扫描线上的像素取补，也就是说，若交点位于栅栏左边，则将交点之右、栅栏之左的所有像素取补；若交点位于栅栏之右，则将栅栏之右、交点之左的所有像素取补。,边标志算法,边标志算法分为两个步骤：,1,）对多边形的每条边进行直线扫描转换，即对多边形边界所经过的像素打上标志；,2,）填充，即对每条与多边形相交的扫描线，从左至右逐个访问该扫描线上的像素，使用一个布尔变量,inside,来指示当前的状态，若在多边形内，则,inside,为真；否则为假。,inside,的初始值为假，每当当前访问像素为被打上标志的点，就把,inside,取反，对未打上标志的点，,inside,不变。若访问当前像素时，对,inside,作必要操作后，,inside,为真，则把该像素置为多边形要填充的颜色。,3.3.3,种子填充算法,区域的表示方法：内点表示法（左图）、边界表示法（右图）,区域的连通性,区域按连通情况可分为四连通区域（左图）和八连通区域,（右图）,简单的种子填充算法,种子填充算法的基本思想是给定区域中一种子点（,x,y,）,首先判断该点是否是区域内的一点，如果是，则将该点填充成为新的颜色，然后将该点周围的,4,个点（四连通）或,8,个点（八连通）作为新的种子像素点进行同样的处理，通过这种扩散完成对整个区域的填充。,四连通区域的缺点是有时不能通过狭窄的区域，因此不能填满多边形。八连通区域的缺点有时会填出多边形的边界。由于填不满比涂出更容易补救，因此四连通算法比八连通算法用得更多,扫描线种子填充算法,扫描线种子填充算法的基本思想是：从给定的种子点开始，填充当前扫描线上种子点所在的区间，然后确定与这一区间相邻的上下两条扫描线上需要填充的区间，从这些区间上各取一个种子点并依次把他们保存起来，作为下次填充的种子点，反复进行这个过程，直到所保存的各区间都填充完毕。,借助于堆栈，扫描线种子填充算法可由以下,4,个步骤来实现。,1,）将算法设置堆栈置为空，将给定的种子点（,x,y,）压入堆栈；,2,）如果堆栈为空，算法结束；否则取栈顶元素（,x,y,）作为种子点；,3,）从种子点（,x,y,）开始，沿纵坐标为,y,的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充，直到边界为止。设区间两边界的横坐标为,x_left,x_right,。,4,）在与当前扫描线相邻的上下两条扫描线上，以区间,x_left,x_right,为搜索范围，求出需要填充的各个小区间，把各个小区间中最右边的点作为种子点压入堆栈中，转到步骤,2,）。,扫描线种子填充算法,3.4,字符表示,所讨论的字符是指字母、数字、汉字、标点等符号。计算机中，字符由一个数字编码唯一标识，它所对应的编码是什么由它所属的字符集决定。目前常用的字符有两种，一种是,ASCII,（,American Standard Code for Information Interchange,）码,-,美国信息交换用标准代码,。另外一种就是汉字字符，全称是“中华人民共和国国家标准信息交换编码”，代号为,GB3212-80,。,为了在显示器等输出设备上输出字符，必须要有每个字符的图形信息，这些信息保存在系统的字库中，字符的图形有两种表示方法：点阵表示和矢量表示。,3.4.1,点阵字符,在字符的点阵表示方法中，每个字符由一个位图来表示,。,3.4.2,矢量字符,与点阵字符不同，矢量字符记录字符的笔画信息而不是整个位图，具有存储空间小，美观、变换方便等优点。,3.5,反走样,对图形进行光栅化时，用离散的像素显示连续空间中定义的对象。这种用离散量表示连续量时引起的失真现象称为走样；用于减少或消除走样技术成为反走样。,3.5.1,光栅图形走样,用离散的像素表示连续的线段或多边形的边界时导致光栅图形走样，即光滑的线段变成了阶梯的形状。,阶梯形边界图,阶梯形线段,3.5.1,光栅图形走样,当在光栅显示器上显示如左图所示的细长的矩形时，由于光栅系统中表示图形的最小单位为像素，从而造成图形细节失真，原本细长的矩形被显示成了加宽的矩形。,3.5.1,光栅图形走样,一些狭小的多边形分布在两条扫描线之间，由于它们不覆盖任何一个像素中心，所以没有被显示出来，造成狭小图形的遗失。,3.5.2,常用反走样技术,1.,提高分辨率的反走样算法,显然，与低分辨率的光栅显示器相比，高分辨率的光栅图形显示器所显示的线段质量高，线形平直，阶梯形不明显，因此可通过提高分辨率的方法来改善图形质量，以达到反走样的效果。,提高硬件的分辨率可以得到高质量的图像，但是高分辨率的显示器价格昂贵，而且分辨率不能无限制提高，所以可以采用下面的软件方法，该方法的思想是高分辨率计算，低分辨率显示。,3.5.2,常用反走样技术,2.,线段反走样算法,线段反走样算法的基本思想是：因为线段是有宽度的，可以把线段看成是狭长的矩形，因而具有一定的面积，当线段通过某像素时，可以求出两者面积的交，之后根据每一像素与线段相交部分的面积值决定该像素的颜色值或灰度值。例如在单色图形中，最简单的方法是使像素的灰度值和线段交的面积成正比。,3.5.2,常用反走样技术,3.,多边形反走样算法,与线段反走样算法类似，多变性边界的反走样主要表现在对边界的处理上，可采用反走样线段的思想来改善多边形边界的显示质量。当像素与多边形区域相交时，求出两者相交的面积，然后以此面积值来决定该像素的颜色值或灰度值。,