《光栅图形学》PPT课件.ppt

1,光栅图形学,2,本章主要内容,2.1直线的生成2.2圆的生成2.3椭圆的生成2.4多边形扫描转换与区域填充2.5字符的生成,3,光栅化,扫描转换确定像素集,基本图形的生成与显示,图元属性颜色、宽度,4,2.1 直线光栅化显示算法,线条应该显得笔直：由连续点组成的直线要显示在离散网格的平面上，一定会有不经过网格的点。在这种情况下，必须选择靠近直线的网格点来逼近这条直线。,绘制直线的要求,理想的绘制,5,绘制直线的要求,直线端点位置应该准确：画出的线段如果不准确，往往会使两条线之间不能很好的镶接,直线浓度应该均匀：线段的浓度与单位线段中所显示的点数成正比。要保持线段的灰度均匀端点应该等距分布。要取得均匀的线段灰度，应该保持每单位长度的点数是个常数,6,直线的扫描转换:确定最佳逼近于该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作。三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。,直线的微分方程：,直线的方程：,7,直线的方程：,直线增量的方程：,1.数值微分法（DDA）,栅格交点表示像素点位置,已知过端点Ps(xs,ys),Pe(xe,ye)的直线段L：y=kx+b，直线斜率为：,基本思想：,当x=1时,算法的实质是：每一步的x,y值是用前一个的值加上一个增量获得的；为了在显示器上显示，需要对其作取整处理。,计算yi+1=yi+kx 当x=1;yi+1=yi+k 即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1,y最多增加1。当 k 1时，y每增加1,x增加1/k。,算法分析,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。,DDA算法特点 这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算，不利于用硬件实现。,算法实现,void CMyView:OnDdaline()CDC*pDC=GetDC();/获得设备指针int x0=100,y0=100,x1=300,y1=200,c=RGB(255,0,0);/定义直线两端点和直线颜色（红色）float x,y,i;float dx,dy,k;dx=(float)(x1-x0);dy=(float)(y1-y0);k=dy/dx;y=y0;x=x0;if(abs(k)SetPixel(x,int(y+0.5),c);y=y+k;if(abs(k)=1)for(;ySetPixel(int(x+0.5),y,c);x=x+1/k;ReleaseDC(pDC);/释放设备指针,例1：画直线段P0(0,0)-P1(5,2),x y+0.5 int(y+0.5),0 0+0.5 0,1 0.4+0.5 0,2 0.8+0.5 1,3 1.2+0.5 1,4 1.6+0.5 2,5 2.0+0.5 2,优点：在同一坐标上,不可能连续停留两次。缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,算法特点:,非整数端点的修正,任意方向直线的算法分析,|k|1，|xe-xs|ye-ys|，则：,|k|1，|xe-xs|ye-ys|，则：,2.中点画线法,原理：,假定直线斜率0K1，且已确定点亮象素点P（xi,yi）,则下一个与直线最接近的像素只能是Pu点或Pd点。设M为中点，Q为交点,现需确定下一个点亮的象素。,当M在Q的下方 Pu离直线更近取Pu M在Q的上方 Pd离直线更近更近取PdM与Q重合，Pu、Pd任取一点。,问题：如何判断M与Q点的关系？,算法原理,假设起点为Ps(xs,ys),终点为Pe(xe,ye)的直线方程为：F(x,y)=ax+by+c=0,其中a=ys-ye,b=xe-xs,c=xsye-xeys，则：,欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,16,构造判别式：d=F(M)=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c当d0，M在直线(Q点)上方，取下方Pd；当d=0，选Pu或Pd均可，约定取Pd；能否采用增量算法呢？,17,若d0;取Pd;则再取下一个像素的判别式为：d1=F(xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+c=a(xi+1)+b(yi+0.5)+c+a=d+a；增量为a,18,若d0;取Pu;则再取下一个像素的判别式为：d2=F(xi+2,yi+1.5)=a(xi+2)+b(yi+1.5)+c=a(xi+1)+b(yi+0.5)+c+a+b=d+a+b；增量为ab,19,确定判断式初值：设：画线从(x0,y0)开始，d的初值 d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b,整数化判断式：即设：d0 2a+b d1=2a d2=2(a+b),例2：用中点画线法P0(0,0)至 P1(5,2)，a=y0-y1=-2 b=x1-x0=5d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6,I xi yi d,1 0 0 1,2 1 0-3,3 2 1 3,4 3 1-1,5 4 2 5,6 5 2 1,void CMyView:OnMidpointline()CDC*pDC=GetDC();int x0=100,y0=100,x1=400,y1=300,c=RGB(0,0,0);/黑色直线float a,b,d1,d2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b;d1=2*a;d2=2*(a+b);x=x0;y=y0;pDC-SetPixel(x,y,c);while(xSetPixel(x,y,c);ReleaseDC(pDC);,算法程序,3.Bresenham算法,基本思想:由直线的斜率确定选择在x方向或y方向上每次递增（减）1个单位，另一变量的递增（减）量为0或1，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5,然后根据误差项的符号确定该列像素中与此交点最近的像素。,基本算法,23,假定：直线斜率0k1；只需考虑x方向每次递增1个单位，则决定y方向每次递增0或1,记直线与它垂直方向最近的下光栅点的误差为d,0d1,d0.5：下一个像素应取右光栅点(xi+1,yi),d0.5：下一个像素应取右上光栅点(xi+1,yi+1),若直线的起点在整数点上，则d00,当d0.5，则xi+1=xi+1,di+1=di+k,当d0.5，则yi+1=yi+1,di+1=di+k-1,令e=d-0.5，e0=-0.5,e0时，取当前像素(xi,yi)的右上方像素(xi+1,yi+1)e=0时，可任取上、下光栅点显示,当e0，则xi+1=xi+1,ei+1=ei+k,当e0，则yi+1=yi+1,ei+1=ei+k-1,算法实现,void CTestView:OnBresenhamline()CDC*pDC=GetDC();int x1=100,y1=200,x2=600,y2=800,color=RGB(0,0,255);int i,x,y,dx,dy;float k,e;dx=x2-x1;dy=y2-y1;k=dy/dx;e=-0.5;x=x1;y=y1;for(i=0;iSetPixel(x,y,color);x+;e=e+k;if(e=0)y+;e=e-1;,例3：利用Bresenham算法绘制直线:P0(0,0),P1(5,2),e x y,-0.5 0 0,-0.1 1 0,0.3 2 1,-0.3 3 1,0.1 4 2,-0.5 5 2,解：k=dy/dx=0.4,e0=-0.5,当e0，则xi+1=xi+1,ei+1=ei+k,当e0，则yi+1=yi+1,ei+1=ei+k-1,28,则整数Bresenham画线算法可描述为：,整数Bresenham算法,为了便于硬件操作,令:,当e0，则xi+1=xi+1,ei+1=ei+2dy,当e0，则yi+1=yi+1,ei+1=ei+2dy-2dx,优点：无乘除法(计算坐标时)；在同一坐标上不可能连续停留两次。,思考讨论：斜率不同时：以上讨论的是 0 k 1 的情况，即 0yx 的情况；若是 0 xy 的情况，则需将 x 和 y 的位置交换。方向不同时：若y0或x0时，要将算法中的 yy1换成yy1、xx1换成xx1。,改进的Bresenham算法,30,2.2 圆光栅化显示算法,假设圆的方程为：,以下仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。,圆的特征:八对称性。只要扫描转换八分之一圆弧，就可以求出整个圆弧的像素集,其参数方程为：,解决问题：,1.简单方程产生圆弧,算法原理：利用其函数方程，直接计算离散点,隐式方程,特点：思路清晰，计算量大；当x 沿0R增加时，y值变化不均匀,参数式：,特点：计算量大；当变量角度的增量太小时，像素会重叠,2.中点画圆法,利用圆的对称性，只须讨论1/8圆：P为当前点像素，那么，下一个显示的像素可能是T(Xp+1，Yp）或B（Xp+1，Yp-1),设d是点p(x,y)到圆心的距离，则：,有如下结论：F（M）0 M在圆内取T F（M）0 M在圆外取B,d0,则T 为下一个像素，那么再下一个像素的判别式为：d1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3 即d 的增量为 2xp+3,算法原理,d 0,则B 为下一个像素，那么再下一个像素的判别式为：d2=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2xp 2yp+5即d 的增量为 2xp 2yp+5,d的初值:x0=0,y0=R d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R,void CTestView:OnMindpointcircle()CDC*pDC=GetDC();int x=100,y=200,r=150,color=RGB(0,0,255);float d;x=0;y=r;d=1.25-r;pDC-SetPixel(x,y,color);while(xSetPixel(x,y,color);,算法程序,将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用D=d-0.25代替d，则算法如下：,中点圆整数算法,39,X=0,y=R,d=1-R,Yx?,显示点（x,y,属性）,d0?,d=d+2x+3,d=d+2(x+y)+5,y=y-1,X=X+1,END,该算法以点(0,r)为起点，按顺时针方向生成圆时，从x=0开始，xi+1=xi+1直到y=x结束。相当于在第一象限内，所以 y 是 x 的单调递减函数。,3.Bresenham画圆法,令d1、d2分别为yi到y、yi-1到y的距离,41,42,当P为当前被选择的最靠近圆的显示点，则圆可能穿越的下一显示点的情况有5种：,蓝色表示为通过光栅点,选择与圆的距离达到最小值,则取下一点的判断准则为：,43,当圆穿越T上方时：,当圆穿越B下方时：,44,当圆在T和B之间时：,（3）判别式的初值。初始点为（0，R），则：,结论：,（1）如果di0，则y=yi，即选择当前像素的正右方作为下一个像素，递推公式为：,（2）如果di0，则y=yi-1，即选择当前像素的右下方作为下一个像素,递推公式为：,算法实现,void CMyView:OnBresenhamcircle()CDC*pDC=GetDC();int x0=100,y0=100,x,y,r=80,c=0;/黑色圆弧float e,d;e=3-2*r;x=0;y=r;while(xSetPixel(x+x0,y+y0,c);pDC-SetPixel(-x+x0,y+y0,c);pDC-SetPixel(-x+x0,-y+y0,c);pDC-SetPixel(x+x0,-y+y0,c);pDC-SetPixel(y+x0,x+y0,c);pDC-SetPixel(-y+x0,x+y0,c);pDC-SetPixel(-y+x0,-x+y0,c);pDC-SetPixel(y+x0,-x+y0,c);ReleaseDC(pDC);,2.3 椭圆光栅化算法,椭圆的特征,椭圆函数:,对于椭圆上的点，有F(x,y)=0；对于椭圆外的点，F(x,y)0；对于椭圆内的点，F(x,y)0。,解决第1象限问题：以弧上切线斜率为1的点作为分界将第一象限椭圆弧分为上下两部分。,区域中，x1,区域中，y-1,引理：若在当前的中点（xm,ym），法向量的y分量比x分量大，即：,而在下一个中点，不等号改变方向，则说明椭圆弧从上部分转入下部分。,法向量,上部分算法推导,判别式:,若di0，取Pu(xi+1,yi)若di 0，取Pd(xi+1,yi-1),当di0，则：,增量：,算法推导,MT,52,当di0，则：,判别式的初始值：,增量为：,下部分算法推导,y-1,判别方法：,若di0，取Pl(xi,yi-1)若di0，取Pr(xi+1,yi-1),算法推导,当di0，则：,增量：,当di0，则：,增量：,中点椭圆算法小结,第象限内椭圆弧的中点算法可以概括为：,算法实现,void CTestView:OnMidpointellispe()CDC*pDC=GetDC();int a=100,b=300,x,y,color=50;float d1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);pDC-SetPixel(x,y,color);pDC-SetPixel(-x,-y,color);pDC-SetPixel(-x,y,color);pDC-SetPixel(x,-y,color);while(b*b*(x+1)a*a*(y-0.5)if(d1=0)d1+=b*b*(2*x+3);x+;else d1+=b*b*(2*x+3)+a*a*(-2*y+2);x+;y-;,pDC-SetPixel(x,y,color);pDC-SetPixel(-x,-y,color);pDC-SetPixel(-x,y,color);pDC-SetPixel(x,-y,color);/*while上半部分*/d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;while(y0)if(d2SetPixel(x,y,color);pDC-SetPixel(-x,-y,color);pDC-SetPixel(-x,y,color);pDC-SetPixel(x,-y,color);,59,2.4 多边形填充,1.区域的表示及类型,顶点表示也称为几何表示，是用多边形的顶点序列来表示区域。,顶点表示,点阵表示,点阵表示也称像素表示，是用位于多边形内的像素集合来刻画多边形,60,多边形区域填充：将区域内的一点（种子点）赋予给定的颜色，然后将该颜色扩展到整个区域内的过程。,区域的表示：边界（闭合的线段）+填充（灰度或色彩）,多边形的扫描转换：将多边形的顶点表示转换为点阵表示，即从多边形给定边界出发，求出位于其内部的各个像素，并给帧缓存区的各个对应元素设置相应的灰度。,61,点阵表示的两种要素：内点表示和边界表示,在内点表示中，区域内所有像素具有同一颜色，区域以外的所有像素是另外一种颜色,在边界表示中，区域边界上的所有像素具有特定的颜色（可以是填充颜色），在区域(内)、外的所有像素均不能具有这种颜色。,区域填充算法要求区域是连通的，因为只有在连通区域中，才能将种子点的颜色扩充到区域内的其他点。,2.多边形扫描转换法,逐点扫描：交点内点（区间着色）,基本思想 对每一条扫描线，计算扫描线与多边形边界交点，再用要求的颜色对扫描线上在多边形区域内的每两个相邻交点间的全部像素一次显示,当奇点在多边形两边之下方时，该点计为2个点，如图中的P1、P3和P5点。当奇点在多边形两边之上方时，该点计为0个点，如图中的P2、P4和P6点。当奇点在多边形两边之间时，该点计为1个点，如图中的P7点。,交点的异常处理,当扫描线与多边形顶点相交时，称该交点为奇点,y=8的区域:(1,2)(2,3)(3,4),则(1,2),(3,4)区域为内点区域,0,1,1,1,1,0,2,2,2,对一条扫描线填充的过程可分为四个步骤：求交、排序、交点配对、区间填色,算法步骤：,确定多边形顶点坐标生成多边形完成多边形扫描转换,确定多边形所占有的最大扫描线数，得到多 边形顶点的最小和最大y值（ymin和ymax）从y=ymin到y=ymax，每次用一条扫描线进行填充。,3.有效边表扫描转换,原理：处理一条扫描线时，仅对有效边求交利用扫描线的连贯性利用多边形边的连贯性,有效边表的扫描转换算法，充分利用了相邻像素之间的连贯性，避免了对像素的逐点判断和反复求交的运算，达到了减少计算量和提高速度的目的，利用和开发相邻像素之间的连贯性是光栅图形算法研究的重要内容。,有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（Active Edge Table,AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。,基本概念,边表(Edge Table,ET)：存放多边形边（除了水平边）的信息的表,区域的连贯性：可类推各梯形关于P的内外关系,设多边形P的顶点Pi(xi,yi),i=0,1,n,又设yi0，yi1，yin 是各顶点Pi的纵坐标yi的递减数列,两条扫描线之间的长方形被多边形P分割为若干梯形（三角形是底边为0的梯形）具有如下性质：,梯形两底边分别在两条扫描线上,梯形分为两类：一类在位于多边形P内部，一类在外部,两类梯形在长方形区域内相间地排列，即相邻两梯 形中必有一个在多边形P之内，一个在P之外,扫描线的连贯性 相邻两条扫描线与各边的焦点顺序基本一致,设e为一整数yi0 e yin，若扫描线y=e与多边形P的边Pi1Pi相交，则其交点的横坐标为xei 又设xei0，xei1，xeil 是该扫描线与P的边界各交点横坐标的递增序列,此交点序列有如下性质：l是偶数在该扫描线上，只有区间段（xeik，xeik+1）k=1,3,l-1 位于多边形P内，其余线段在P外,某条边与当前扫描线相交，与下一条也可相交,边的连贯性：,设e、d为整数,d=e-1yi0 y yin，若位于扫描线y=d上的交点序列为:xdj0，xdj1，xdjk,若多边形P的边Pr1Pr与扫描线y=e，y=d都相交，则两序列中对应的元素：,又设xei0，xei1，xeil 是位于y=e上的交点递增序列,其中：mr是边Pr1Pr的斜率,两序列元素个数相等点（xeir，e）与（xdjr，d）位于多边形P的 同一边上，即ir=jr,于是：,当存在一整数k，0 k n-1使得yik e、d yik+1成立,则由区域连贯性可知两序列之间有如下关系：,其中：mjr是边Pr1Pr的斜率,有效边表的构造,设边的直线方程为：y=kx+b，则：,有效边表的数据结构为：,Ymax:边的上端点的y值；x/ymin:边的下端点对应的x值；x：边斜率的倒数；next:指向下一条边的指针,其中：边与两扫描线相交,每条边的数据形成一个结点。同一桶中若干条边按x由小到大排序，若x相等，则x由小到大排序。,将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。即某边最低端点的x坐标放进相应扫描线桶中。,首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。,边的分类表ET,边的活化表链表AET,算法步骤：,初始化：构造边表ET，AET表置空，将扫描线纵坐标y的初值置为ET中非空元素的最小序号,如上图中，y=1,将ET中与当前y有关的结点加入至AET，同时存AEL中按x值从小到大实现的排列序列；,按从下到上的顺序对每条扫描线重复以下各步，直至ET和AET都为空。,若对于当前扫描线，边的活化链表AET非空，则将AEL中的边两两一次配对，每一对边与当前扫描线的交点多构成的区域位于多边形内，一次对这些像素点按多边形属性着色；,76,在AET中删掉yymax的结点。,对于留在AET中的每个结点，执行 xi+1=xi+1/k；,yi+1=yi+1成为下一条扫描线的坐标，根据计算并修改AET表，形成新的AET表,对AET中的各结点按x值从小到大排序；,结论：该算法的数据结构与程序结构远比逐点判断算法复杂，但由于充分利用了多边形的区域、扫描线和边的连贯性，从而避免了反复球交点的大量运算，因此速度要快,3.边填充算法,该填充算法的基本原理是：对每一条扫描线，依次求与多边形各边的交点，将该扫描线上交点右边的所有像素求补。,步骤：,将位于扫描线y=e上的所有像素都着色M,对位于扫描线y=e上的横坐标 xxi,(i=1,2,n)的像素求补,注意：通过求补免去建立AEL需要对多边形的 边进行的排序工作,78,完成第一步骤，着白色,从x1开始向右求补,从x2开始向右求补,从x3开始向右求补,从x4开始向右求补,4.种子填充算法,该填充算法的基本原理是：将区域内的一点（种子点）赋予给定的颜色，然后将这种颜色扩展到整个区域的过程。,区域：是指已经表示成点阵形式的填充图形，它是像素集合。根据填充方向分4-连通区 域和8-连通区域。,边界表示：把位于给定区域的边界上的像素一一列举出来的方法。区域的边界点有相同颜色,内点表示：枚举出给定区域内所有象素的表示方法。即区域内的所有象素有相同的颜色。,边界表示的四连通区域种子填充算法,用栈结构来实现该算法，种子像素入栈，当栈非空时，重复执行如下操作：栈顶像素出栈；将出栈像素置成多边形填充的颜色；按“左上右下”的顺序检查与出栈像素相邻的四个 像素，若其中某个像素不在边界上且未置成多边形 色，则把该像素入栈。,基本思想：从多边形内部任一点像素出发，按照“左上右下”的顺序判断相邻像素，若不是边界像素且没有被填充过，则对其填充，并重复上述过程，直到所有像素填充完毕。（递归）,1,算法功能：按顺序重新着色顺序：上下左右思考：如果是左上右下顺序呢？请填写右下图序号,2,3,4,6,5,其它颜色,1,1,2,46,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,P,递归填充算法（上下左右）：Void Fill(int x,int y,int bcolor,int ncolor)int color；color=GetPixel(x,y)；if(color!=bcolor)&(color!=ncolor)PutPixel(x,y,ncolor)；Fill(x,y+1,bcolor,ncolor)；Fill(x,y-1,bcolor,ncolor)；Fill(x-1,y,bcolor,ncolor)；Fill(x+1,y,bcolor,ncolor)；思考：如果换成左上右下的顺序呢？,可以使用栈结构来实现该算法，种子像素入栈，当栈非空时，重复执行如下操作：（与边界表示类似）栈顶像素出栈；将出栈像素置成多边形填充的颜色；按“左上右下”的顺序检查与出栈像素相邻的四个像 素，若其中某个像素不在边界上且未置成多边形色，则把该像素入栈。,内点表示的四连通区域种子（泛）填充算法,基本思想：从多边形内部任一点像素出发，按照“左上右下”的顺序判断相邻像素，如果是区域内的像素，则对其填充，并重复上述过程，直到所有像素填充完毕.,总结：P31,当以边界表示时，四连通边界填充算法只能填充四连通区域，八连通边界填充算法也只能填充八连通区域。但当以内部点表示时，八连通区域填充算法可以填充八连通区域，也可以填充四连通区域。然而四连通区域的填充算法仍只能填充四连通区域。,86,2.5 字符与汉字显示,1.基本概念,字符 计算机在文本方式下能够在屏幕上显示的符号,字节最高位0ASC,字节最高位1汉字编码,ASC码(American Standard Code for Information Interchange),国标码中华人民共和国国家标准信息交换编码，代号GB231280，每个字符由一个区码与一个位码共同标识,字库：储存每个字符的形状信息,2.点阵字符,点阵字符是由一个位图表示的，保存字符就是保存表示它的位图；,点阵字符的显示：首先从字库中将它的位图检索出来，然后将检索得到的位图写到桢缓存中，进行显示。,3.矢量字符,字符由构成它的笔画组成，每一笔画由其两端确定；每一端点，保存它的坐标值和由前一端点到此端点是否连线的标志即可；,矢量字符的显示：首先检索表示该字符的数据，然后取出端点坐标，几何转换，根据各端点的标志进行显示；,采用矢量序列表示字符的各笔划轮廓,矢量式字符将字符表达为点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻画。右图用矢量式表示的字符“B”。“B”是由顶点序列a,b,c,d,e,f,e,g,h,i,j,k,j,a,l的坐标表达。,矢量式表示字符“B”,矢量字符的端点存储方式,矢量字符方向编码及存储,方向编码式字符用有限的若干种方向编码来表达一个字符。左下图给出了8个方向的编码为07。右下图(a)示出字母“B”的方向矢量构成。这样，“B”就表示为8方向编码0000123444000123444406666。方向编码式字符很容易被填入帧暂存寄存器中予以显示(右下图(b)，方向编码所占的空间比较小，它也能接受一些特定的变换操作。,字符的8方向编码,方向编码式字符的实例,91,2.6 反走样（Anti-liasing）,1.图形走样,走样 用离散量表示连续量引起的图形失真,反走样 减少或克服走样效果的技术,92,走样现象 产生阶梯或锯齿状 细节或纹理绘制的失真 狭小图形的丢失 实时动画的或隐或现、闪烁跳跃,93,2.超采样(supersampling),反走样技术 提高设备分辨率；提高采样频率满足采样定理；不同位置的像素以不同的权重亮度；,超采样 采用高分辨率计算，低分辨率显示.即将较低的显示分辨率划分为若干子分辨率，进行取样计算，对各子像素的颜色值何等属性采用平均或加权平均算法，返回在较低的显示分辨率的光栅图形设备上显示。,94,简单区域取样（平均）,加权矩阵:,如果一个像素点完全被直线覆盖，则该店的灰度值为黑色，如果该像素点被部分覆盖，则该点的灰度值为覆盖区域的份额,加权区域取样,输出像素的灰度值不仅与覆盖的面积有关，而且与所覆盖的面积据像素中心点的距离有关,95,96,上机作业：,1.在Illustrator中，用两种方法实现某一事件的统 计图表（说明步骤），并简述其生成的原理,97,作业：,1.基本概念的解释：走样，反走样；区域表示 的类型以及含义；超采样。2.解释多边形扫描转换以及多边形区域填充的 概念。3.简述点阵字符与矢量字符的显示4.请指出用中点算法和Bresenham算法扫描转换 像素点（8，6）到（1，1）的线段的像素位置（有计算，并用方格图表示）5.推导出椭圆中点显示的算法（框图）,98,作业：,6.请分析多边形扫描转换、边界填充、种子填充算法的特点7.按照左上右下的顺序作以边界表示的四连通区域种子填充，填写下图序号,1,其它颜色,99,练习：,一、选择题,1下列各项中不是计算机图形学应用范围的是 D。A.计算机艺术 B.医疗诊断C.办公自动化 D.卫星遥感中资源勘测2.用数学方式描述几何对象的数目和相互位置关系是图形的 D。A.几何信息B.非几何属性 C.描述属性D.拓扑信息3.阴极射线管CRT由电子枪、荧光屏、加速器、聚焦系统和 B 组成。A.锥体系统 B.偏转系统 C.管颈系统 D.显示适配器,100,4.下列各项中不是计算机图形输入设备的是 D。A.跟踪球B.图像扫描仪C.光笔D.绘图仪5.屏幕的刷新频率称为 A。A.场频B.行频C.会聚D.平衡度6.利用惰性气体放电时所产生的紫外线来激发彩色荧光粉发光的显示器是 B。A.液晶显示器B.等离子体显示器C.CRT显示器D.发光二极管显示器7.关于直线生成算法的叙述中那种说法是正确的 A。A.Bresenhan算法是每次决定一个像素的走法B.Bresenhan算法是对中点画线算法的改进C.DDA算法是Bresenhan算法的改进D.DDA算法利用了光栅的特点，故其运行效率高,101,8.在中点画圆算法中，那些说法是错误的 B。A.中点画圆算法是一个增量算法B.为了减轻画圆的工作量，该算法利用了圆的四对称性C.中点画圆算法只用到了整数的加减法和左移运算，故 效率高，适合硬件实现。D.该算法与中点画线类似，用一个函数值选择两个像素点中最逼近圆弧的像素点。9.下例哪一种现象不是图像走样 B。A.狭小图形的丢失B.颜色轮廓重现C.线条锯齿D.细节丢失10.多边形区域的表示方法有 A 和顶点表示。A.点阵表示 B.直线表示 C.颜色表示 D.路径表示,102,二、填空题,1.字符的图形表示可以分为点阵和矢量两种形式。2.常见的直线生成算法有DDA增量、中点画线和B-。3.扫描线的连贵性、区域性和边的连贯性三者之间的联系是线、边连贯性是区域连贯性在线和边上的体现。4.直线的属性包括端点、线宽和颜色。5.GKS称为图形核心系统，提供应用程序与图形输入输出设备之间与语言无关的功能接口。6.帧缓冲存储器也称为 帧缓存是内存中一块连续的区域，用来存储屏幕上需要刷新的图像信息.7.有3个位平面、分辨率是10241024像素的显示器，需要的显存大小为 3M。8.多边形扫描转换法的基本思想是对每一条扫描线，计算扫描线与多边形边界交点，再用要求的颜色对扫描线上在多边形区域内的每两个相邻交点间的全部像素一次显示。,103,三、综合题,1.用框图写出中点画线法的算法，并给出参数公式,2.按照上下左右的顺序作以边界表示的四连通区域种子填充，填写下图序号,1,其它颜色,104,用中点算法 像素点（8，6）到（1，1）的线段的像素位置（有计算，并用方格图表示）解：x0=8,x1=1;y0=6,y1=1;,105,x0=8,x1=1;y0=6,y1=1;a=y1-y0=1-6=-5;b=x0-x1=8-1=7;d0=-(2a+b)=3;d1=-2(a+b)=-4;d2=-2a=10;,987654321,1 2 3 4 5 6 7 8 9,106,Bresenham算法扫描转换 像素点（8，6）到（1，1）的线段的像素位置（有计算，并用方格图表示）,解：x0=8,x1=1;y0=6,y1=1;dx=-7,dy=-5,e=-(2dy-dx)=3,当e0，则xi+1=xi-1,ei+1=ei-2dy,当e0，则yi+1=yi-1,ei+1=ei-2dy+2dx,107,推导出椭圆中点显示的算法（框图）,d=b2-a2(b-0.25),x=0,y=b,显示点（x,y),a2(y-0.5)b2(x+1)?,d0,d+=b2(2x+3),d+=b2(2X+3)+a2(-2y+2),y-,x+,d=b2(x+0.5)2+a2(y-1)2-a2b2,Y=0,d0,d+=2b2(x+1)a2(3-2y),Exit,x+,d+=a2(3-2y),y-,108,课堂作业：,1.利用Bresenham算法绘制直线P1P2,其中P1（1，0），P2到（9，4）（有计算，并用方格图表示像素点）2.分辨率为1024*768像素的真彩色光栅显示系统的帧缓存量至少是多少兆？,