光栅图形生成算法.ppt

Ch3 光栅图形生成算法,光栅显示器显示的图形是用一系列紧靠该图形路径的像素表示的。,确定哪些像素能构成所需图形的过程称为图形的光栅化(也称光栅图形生成算法)，或称为图形的扫描转换。,本章讨论内容,直线生成算法圆和圆弧的程序设计区域填充算法字符生成反走样技术,直线生成算法,直线是最基本的图元，曲线由一系列直线段逼近，复杂图形可看作是由无数直线段组成的。直线生成质量影响计算机图形设计的质量。因此，光栅化直线生成算法必须服从四条原则：直而光滑、端点准确、亮度均匀、速度快。,直线生成算法,逐点比较法 绘图仪常用的一种方法。在每次画图过程中,绘图笔每画一笔，就与规定的图形进行比较，然后决定下一步的走向，用步步逼近的方法画出规定的图形。,X,Y,O,假设以坐标原点作为直线起点，各象限中画笔走向如图所示。,逐点比较法,一般公式:要画的线段为OA，画笔的当前的位置为M。以OM，OA的斜率的大小来计算偏差。d=tg-tg=ym/xm-ya/xa=(ym*xa-ya*xm)/xm*xa；,（1）偏差计算（以第一象限为例）,当d=0时，表示笔在OA线段的上方，应该走+x一步。只判断d的正负,不管大小,第一象限xm,xa均为正。,第一象限偏差的判断公式:Fm=ym*xa-ya*xm,X,Y,O,A(xA,yA),M(xM,yM),逐点比较法,递推公式:上述公式要计算两次乘法,设法用前一点的偏差来推算走步的方向以及走步后的偏差.,（1）偏差计算,笔的当前位置为Mi(xi,yi),此时Fi=yixa-yaxi.,如果Fi0,应走+y一步到Mi+1,即:xi+1=xi,yi+1=yi+1;Mi+1处的偏差Fi+1=yi+1xa-yaxi+1=yixa+xa-yaxi=Fi+xa;,如果Fi=0,应走+x一步到Mi+1,即:xi+1=xi+1,yi+1=yi;Mi+1处的偏差Fi+1=yi+1xa-yaxi+1=yixa-yaxi-ya=Fi-ya;,如果 Fi=0 则走+x一步,此时Fi+1=Fi-ya;如果 Fi0 则走+y一步,此时Fi+1=Fi+xa;,逐点比较法,设步距为t,直线在x,y方向的增量分别为x 和y.按上述运算方法,绘图笔从直线的起点画到终点,在x方向应走|x/t|步,在y方向应走|y/t|步.取n=|x/t|+|y/t|作为终点判断的控制数,并将此数存入计数器内.在x或y方向上每走一步计数器减1,当计数器减到零时,作图停止.,（2）终点判断,直线生成算法,Bresenham直线生成算法,基本原理：沿某一计长方向上，每次变化一个单位步长，另一方向上的变化量通过计算获得。这种方法在计算判别式时，计算量很小，生成的直线光滑，因而应用广泛。假设直线的斜率在01之间，k=y/x，x的变化率比y的变化率大，约定每次x方向变化一个像素单位，相应y方向的变化量为0或1个像素单位。,Bresenham直线生成算法,已知直线起点(x1,y1)，终点(x2,y2)；直线上第i个像素为P(xi,yi)，它是已经选定的离直线最近的当前像素。现在要决定下一个像素是S(xi+1,yi),还是T(xi+1,yi+1)?若s=t,则选择T。,P(xi,yi),Q(x,y),计算判别式:理论直线上点Q坐标为y=k(xi+1)+b;求s和t:s=y-yi=k(xi+1)+b-yi;t=(yi+1)-y=(yi+1)-k(xi+1)-b,s,t,P(xi,yi),S(xi+1,yi),T(xi+1,yi+1),计算判别式:理论直线上点Q坐标为y=k(xi+1)+b;求s和t:s=y-yi=k(xi+1)+b-yi;t=(yi+1)-y=(yi+1)-k(xi+1)-b,则 s-t=2k(xi+1)-2yi+2b-1由于k=yx,x=x2-x1,y=y2-y1,代入上式，得到 x(s-t)=2yxi-2xyi+(2y-x+2bx)(3-1)记di=x(s-t),x0,di与(s-t)同号;di值符号为选择下一个像素的判别因子。为得到di的递推形式,以i+1代入式(3-1)的i，得 di+1=2yxi+1-2xyi+1+(2y-x+2bx)(3-2),计算判别式:,将(3-2)减去(3-1),且xi+1=xi+1，得 di+1=di+2y-2x(yi+1-yi)(3-3)其中,yi+1-yi=0或1取决于判别因子di值的符号。如果di0，取S为下一像素,即xi+1=xi1,yi+1=yi,有 di+1=di+2y(3-4)如果di0，取T为下一像素,即xi+1=xi+1,yi+1=yi+1,有 di+1=di+2y-2x(3-5)将y1=kx1+b代入式(3-1),得di初始值:d0=2y-x(3-6),Bresenham画线算法流程,|m|1的Bresenham画线算法输入线的两个端点，并将左端点存贮在(x0,y0)中；将(x0,y0)装入帧缓冲器，画第一个点；计算常量：x、y、2y和2y-2x，并得到决策参数的第一个值：p0=2yx；从k=0开始，在沿线的每个xk处，进行下列检测：假如pk0，画下一个点(xk+1，yk)，且：pk+1=pk+2y；否则，下一个待画点(xk+1，yk+1)，且：pk+1=pk+2y-2x。k=k+1；重复步骤4，共x次。,像素生成过程,该算法仅涉及整数加法运算和乘2(左移)操作，运算效率高，易于硬件实现。与逐点比较法相比，生成的直线光滑。若将该算法的范围扩大到整个平面，相应的d增量式及其初始值,以及下一像素位置的取法道理相似，请思考！,本章讨论内容,直线生成算法圆和圆弧的程序设计区域填充算法字符生成反走样技术,圆的生成算法-中点圆生成算法,以单位间隔取样并在每个步长中确定离指定圆最近的像素位置。对于给定半径r和屏幕中心(xc，yc)，运用平移：先给出计算中心在坐标原点(0，0)圆的像素位置的算法，然后通过将xc加到x和yc加到y而把每个计算出的位置(x，y)移动到其适当的屏幕位置。运用对称：在第一像限中，圆弧段从x=0到x=y，曲线的斜率从0变化到-1，因此，可以这八分圆上的正x方向取单位步长，并使用决策参数来确定每一步中两个可能的y位置中更接近于圆的位置，而后在其它七个八分圆中的位置可由对称性得到。,中点圆生成算法：算法原理,定义圆函数：fcircle(x，y)=x2+y2r2，圆边界上任何具有半径r的点(x，y)满足方程fcircle(x，y)=0。任何点(x，y)的相对位置可由对圆函数符号的检测来决定：fcircle(x，y)0，(x，y)位于圆边界内;fcircle(x，y)0，(x，y)位于圆边界上;fcircle(x，y)0，(x，y)位于圆边界外。在中点算法中圆函数是决策参数，并且可像在画线算法中一样为这个函数设置增量运算。决策参数是圆函数在这两个候选像素的中点处求值：Pk=fcircle(xk+1，yk-1/2)；根据决策参数判断：假如pk0，这个中点在圆内，扫描线yk上的像素(高像素)接近圆边界。假如pk0，中点位于圆外或在圆周边界上，选择扫描线yk-1的像素(低像素)。,中点圆生成算法：决策参数,下图示出了取样位置xk+1处两候选像素间的中点，假设(xk，yk)为前一像素，需要决定下列哪个像素：像素位置(xk+1，yk)，像素位置(xk+1，yk-1)更接近于圆？注意：圆在第一像限，y0，y方向应取减量。,中点圆生成算法：生成过程,1.输入圆半径r和圆心(xc，yc)，并得到圆心在原点的圆周上的第一点为：(x0，y0)=(0，r)2.计算决策参数的初始值为：p0=5/4-r3.在每个xk位置处，从k=0开始，完成下列检测：假如pk0，中心在(0,0)的圆的下一个点为(xk+1,yk)，且：pk+1=pk+2xk+1+1；否则，圆的下一点是(xk+1,yk-1)，且：pk+1=pk+2xk+1+1-2yk+1。其中：2xk+1=2xk+2，且 2yk+1=2yk-2。,4.确定在其它七个八分圆中的对称点。5.将每个计算出的像素位置(x,y)移动到中心在(xc,yc)的园路径上，并画坐标值：x=x+xc，y=y+yc6.重复步骤3到5，直止xy。,本章讨论内容,直线生成算法圆和圆弧的程序设计区域填充算法字符生成反走样技术,区域填充,区域是指一组相邻而又连通、具有相同属性的像素集。在区域内，生成某一属性的实心或图案的过程称为区域填充。内点,边界和外点:位于区域的点称为内点,与内点相邻但又不属于该区域的像素组成了边界,不是内点和边界的像素是外点.,光栅系统有两种区域填充算法：扫描线填充算法：主要用于填充多边形、圆、椭圆以及其它简单曲线所围成的封闭区域。种子填充算法：适用于具有复杂形状边界的区域填充。,扫描线填充算法,按顺序计算扫描线与多边形的相交区域，用要求的颜色显示这些区间的像素，即完成填充工作。,例如，y=6的扫描线与多边形有四个交点，显然，第1与第2、第3与第4间的区域落在多边形内，这些区间的像素填充预期的颜色。,填充过程，对于一条扫描线，可以分成四个步骤：,(1)求交：计算扫描线与多边形每个边的交点。(2)排序：把所求出的交点按x递增的顺序排序。,(3)交点配对：第一与第二，第三与第四等等，每对交点代表扫描线与多边形的一个相交区域。(4)区间填色：把相交区域内的像素设置成多边形的颜色，把相交区域外的像素设置成背景色。,解决两个特殊问题,扫描线与多边形的顶点相交，交点的取舍。,多边形边界上的像素的取舍问题。,2,4,6,8,解决两个特殊问题,扫描线与多边形的顶点相交，交点的取舍。,多边形边界上的像素的取舍问题。,2,4,6,8,种子填充算法,基本思想:从区域内部已定义新值的某像素(种子)开始,搜索与该种子相邻且位于区域内的像素,该像素为新的种子；不断地递归搜索,逐个像素填充所需颜色,直到填充完区域边界内的所有像素为止。,区域分四连通区域和八连通区域:,连通区域定义,4连通区域：任取区域内两点，在该区域内，允许通过上、下、左、右四个方向的运动，这两点相互可达。8连通区域：任取区域内两点，在该区域内，允许通过水平、垂直、两个对角线八个方向的运动，这两点相互可达。,连通区域定义,由定义可知：4连通区域也可以看作是8连通区域。但它作为4连通区域和8连通区域的边界是不同的(4连通比8连通约束紧。左下图)：像素作为4连通区域，其边界只要是连通就可以了；像素作为8连通区域，其边界必须是连通区域。否则，欠约束。8连通区域能用来填充更复杂的图形(如下图所示)。,(1)边界填充算法,如果区域采用边界定义，即边界上的所有像素具有某个相同的特定值(颜色或亮度)，区域内部所有像素均具有非新值的某个给定值；这种区域内的种子填充算法又称边界填充算法。,Boundary-fill-4(x,y,newcolor,boundarycolor)int x,y,newcolor,boundarycolor;int testcolor;testcolor=getpixel(x,y);if(testcolor!=boundarycolor),(2)漫溢填充算法（泛滥）,对于内定义区域，其区域内部所有像素均具有某个相同的特定值，区域外的所有像素具有其它不同的值，这种区域称内定义区域。对内定义区域采用的种子填充算法叫漫溢填充算法。,区域填充属性,区域填充属性是软件系统提供用户对已定义的图形区域(可包含边界)填充自己所选择的图形内容的一种功能。一般区域填充属性包括填充模式填充颜色填充图案,(1)填充模式,常见的有三种基本形式：空心的、实心的和选定图案。,Turbo C中由函数Setfillstyle(int pattern,int color)设置填充模式和填充颜色。pattern定义填充模式类型Empty_Fill以背景色填充Solid_Fill以某一单色填充Xhatch_Fill以斜网格填充,填充函数：矩形bar(),多边形fillpoly()等。,(2)填充颜色,color是定义区域边界或区域内部填充颜色的参数，例如，对于空心区域，只有在边界轮廓上显示所指定的填充颜色；对于实心区域包括具有图案的区域，将以填充颜色显示区域内部，也可包含其边界。,本章讨论内容,直线生成算法圆和圆弧的程序设计区域填充算法字符生成反走样技术,字符的表示与输出,国际字符编码：ASCII(American Standard Code for Information Interchange)：7位二进制编码，共128个字符。一个字符的ASCII码用一个字节(8位)表示，其最高位不用或作为奇偶校验位。汉字编码：国家标准信息交换编码GB2312-80汉字6763个、图形符号682个。所有字符组成9494矩阵表示，行称为区，用区码标识，列称为位，用位码标识；,点阵字符,点阵字符的存储点阵字符是由一个位图表示：保存字符就是保存表示它的位图。字型79、916、1624等指的是位图的尺寸。一个汉字需要16x24=384位，即48个字节，而常用汉字有6763个，从而存储这种型号需要676348324K字节。在实际应用中需要多种字体(如宋体、揩体等)，每种字体又有十多种型号。因此汉字字库所占的存储空间是相当庞大的，解决办法是采用压缩技术。,点阵字符,点阵字符的显示从给定的字符编码到在屏幕上将它显示出来经历两个步骤：第一步（检索）是从字库中将它的位图检索出来，由于表示同一型号字符的位图所占空间大小相同，可以直接将一个字符在字库中的位置计算出来；第二步（显示）是将检索到的位图写到帧缓存中，这可以利用光栅系统的位拷贝功能。,矢量字符,矢量字符的存储字符矢量表示中，记录的是字符的笔画信息。首先选一个正方形网格作为字符的局部坐标空间，网格的大小可取1616、3232、6464等。对一个字符来说，它由构成它的笔画组成，而每一笔又由其两端确定。对于每一个端点，只要保存它的坐标值和由前一端点到此端点是否连线的标志即可。表示一个矢量字符最终只需要所有的端点坐标信息及其是否连线的标志。实际的矢量字符的存储结构要加上一些管理信息和字型信息等。,矢量字符,矢量字符的显示第一步（检索）根据给定字符的编码，在字库中检索出表示该字符的数据。由于各个字符的笔画不一样多，端点也不一样多，造成存储各个字符的记录所占字节数也不同，给检索带来一定困难。为了提高检索效率，可以改变字符的存储结构。第二步（变换）是取出端点坐标，对其进行适当的几何变换，再根据各端点的标志显示出字符。,点阵字符和矢量字符,字符变换不同表示点阵字符的是位图，对点阵字符的变换要对位图中的每一个像素进行，是图像变换，放大或旋转时会失真。表示矢量字符的是端点坐标，对矢量字符的变换是对端点的变换，是图形的几何变换，不会影响显示效果。占用空间不同矢量字符占用空间较少，首先其单个字符占用较少空间；其次，矢量字符只需保存一套字符，所需的不同型号的字符可以通过相应的几何变换来产生。矢量字符美观除了直线段外，还可以用二次曲线段、三次曲线段等来表示笔画，使字符更加美观。矢量字符占用空间小、美观、变换方便等优点得到越来越广泛的应用，特别是在排版、软件和工程图软件中它几乎已经完全取代了点阵字符。,字符的显示 图形标准或一般的软件系统通常都用各自统一的函数提供字符显示，且可通过参数选择来控制字符的字体、大小、颜色、方向等属性。例如,在Turbo C图形模式下，用函数Settextstyle(font,direction,charsize)设置文本的字体、方向及大小；调用函数Outtext(*textstring)或Outtextxy(x,y,*textstring)在屏幕上以当前前景色在当前位置或指定的(x,y)位置显示字符串textstring所指定的文本.,本章讨论内容,直线生成算法圆和圆弧的程序设计区域填充算法字符生成反走样技术,走样现象反走样方法简单区域采样加权区域采样,反走样技术,走样现象,走样：用离散量(像素)表示连续的量(图形)而引起的失真，叫做走样。,反走样方法,什么是反走样在图形显示过程中，用于减少或消除走样现象的方法1）提高分辨率方法 2）非加权区域采样 3）加权区域采样,方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍时间。,反走样方法,提高分辨率的反走样方法,区域采样方法,方法由来两点假设1、像素是数学上抽象的点，它的面积为0，它的亮度由覆盖该点的图形的亮度所决定；2、直线段是数学上抽象直线段，它的宽度为0。现实像素的面积不为0；直线段的宽度至少为1个像素；假设与现实的矛盾是导致走样出现的原因之一,反走样基本方法,非加权区域采样方法将直线段看作是具有一定宽度的狭长矩形；当直线段与像素有交时，求出两者相交区域的面积；根据相交的面积确定该像素的亮度等级；直线段对一个像素亮度的贡献与两者相交面积成正比。这样使线段上各相邻像素的亮度之间有一个平缓的过渡，淡化了锯齿现象。,每个像素面积为单位面积；相交区域面积是介于0，1之间的实数；用它乘以像素可设置的最大亮度值，即可得到该像素实际显示的亮度值。,反走样基本方法,加权区域采样方法将直线段看作是具有一定宽度的狭长矩形；当直线段与像素有交时，根据相交区域与像素中心的距离来决定其对象素亮度的贡献。直线段对一个像素亮度的贡献正比于相交区域与像素中心的距离。这种方法更符合人视觉系统对图像信息的处理方式，反走样效果更好。,设置相交区域面积元与像素中心距离的权函数(如高斯函数等)反映相交面积元对整个像素亮度的贡献大小。利用权函数积分求相交区域面积，用它乘以像素可设置的最大亮度值，即可得到该像素实际显示的亮度值。,直线段的过取样,过取样(超放样/后过滤)：在高分辩率下对对象取样，在较低分辨率上显示其结果。基本思想：把屏幕看成比实际所具有的更细的网格来增加取样率；再沿这种更细网格使用取样点来确定每个屏幕像素的合适亮度等级。,从多个点对一个像素总体亮度的贡献来得到该象素的亮度信息；每个像素可能的亮度等级数目等于像素区域内子像素的总数；总的线亮度在更多的像素上描述。这样，线亮度分布在较大数目像素上，并且通过在阶梯状台阶附近显示有些模糊的线路径使阶梯形状得到光顺。亮度等级的数目取决于子像素的多少。,直线段的过取样,考虑线宽度时，则将每个像素亮度设置成正比于线区域内的子像素数目来完成过取样。有颜色显示时：对子像素亮度进行平均来得到像素颜色设置。,线亮度差的校正,为减轻阶梯形效果，反走样线为另一种光栅效果提供校正。用相同数目像素所画的两条线，对角线还是比水平线长，可视效果是对角线显得比水平线要暗，因为对角线以更低的单位长度亮度显示。通过按照每条线的斜率来调整其亮度，就可对这种效果进行校正。水平和垂直将以最低的亮度显示；而45线则以最高亮度显示；一旦反走样技术应用于显示，亮度就能自动校正。当考虑线的有限宽度时，调整亮度的结果是线以正比于其长度的整体亮度显示。,