光栅图形生成算法.ppt

《光栅图形生成算法.ppt》由会员分享，可在线阅读，更多相关《光栅图形生成算法.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Ch3 光栅图形生成算法光栅图形生成算法光栅显示器显示的图形是用一系列紧靠该图光栅显示器显示的图形是用一系列紧靠该图形路径的像素表示的。形路径的像素表示的。确定哪些像素能构成所确定哪些像素能构成所需图形的过程称为需图形的过程称为图形图形的光栅化的光栅化(也称也称光栅图光栅图形生成算法形生成算法)，或称为，或称为图形的扫描转换图形的扫描转换。本章讨论内容本章讨论内容uu直线生成算法直线生成算法uu圆和圆弧的程序设计圆和圆弧的程序设计uu区域填充算法区域填充算法uu字符生成字符生成uu反走样技术反走样技术直线生成算法直线生成算法uu直线是最基本的图元，曲线由一系列直线是最基本的图元，曲线由一系列直

2、线段逼近，复杂图形可看作是由无直线段逼近，复杂图形可看作是由无数直线段组成的。直线生成质量影响数直线段组成的。直线生成质量影响计算机图形设计的质量。因此，计算机图形设计的质量。因此，光栅光栅化直线生成算法化直线生成算法必须服从四条必须服从四条原则原则：直而光滑、端点准确、亮度均匀、速直而光滑、端点准确、亮度均匀、速度快。度快。直线生成算法直线生成算法uu逐点比较法逐点比较法 绘图仪常用的一种方法。在每次画图绘图仪常用的一种方法。在每次画图过程中过程中,绘图笔每画一笔，就与规定的图绘图笔每画一笔，就与规定的图形进行比较，形进行比较，然后决定下一步的走向，然后决定下一步的走向，用步步逼近的方法画出

3、规定的图形。用步步逼近的方法画出规定的图形。X XY YOOuu假设以坐标原点作假设以坐标原点作为直线起点，各象限为直线起点，各象限中画笔走向如图所示。中画笔走向如图所示。uu逐点比较法逐点比较法一般公式一般公式:要画的线段为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*xmX XY YOO

4、A(xA(xA A,y,yA A)M(xM(xMM,y,yMM)uu逐点比较法逐点比较法递推公式递推公式:上述公式要计算两次乘法上述公式要计算两次乘法,设法用前一设法用前一点的偏差来推算走步的方向以及走步后的偏差点的偏差来推算走步的方向以及走步后的偏差.（1）偏差计算）偏差计算笔的当前位置为笔的当前位置为Mi(xi,yi),此时此时Fi=yixa-yaxi.如果如果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=F

5、i-ya;如果 Fi0 则走+y一步,此时Fi+1=Fi+xa;uu逐点比较法逐点比较法 设步距为t,直线在x,y方向的增量分别为x 和y.按上述运算方法,绘图笔从直线的起点画到终点,在x方向应走|x/t|步,在y方向应走|y/t|步.取n=|x/t|+|y/t|作为终点判断的控制数,并将此数存入计数器内.在x或y方向上每走一步计数器减1,当计数器减到零时,作图停止.（2）终点判断）终点判断直线生成算法直线生成算法uuBresenham直线生成算法直线生成算法基本原理：沿某一计长方向上，每次变化一个单位步长，另一方向上的变化量通过计算获得。这种方法在计算判别式时，计算量很小，生成的直线光滑，因

6、而应用广泛。假设直线的斜率在01之间，k=y/x，x的变化率比y的变化率大，约定每次x方向变化一个像素单位，相应y方向的变化量为0或1个像素单位。Bresenham直线生成算法直线生成算法uu已知直线起点已知直线起点(x x1 1,y,y1 1)，终点终点(x x2 2,y,y2 2)；uu直线上第直线上第i i个像素为个像素为P(xP(xi i,y,yi i)，它是已经选定的离直线最近它是已经选定的离直线最近的当前像素。现在要决定下的当前像素。现在要决定下一个像素是一个像素是S(xS(xi i+1,y+1,yi i),),还是还是T(xT(xi i+1,y+1,yi i+1)?+1)?uu若

7、若st,s=t,s=t,则选择则选择T T。P(xi,yi)S(xi+1,yi)T(xi+1,yi+1)stQ(x,y)Q(x,y)uu计算判别式计算判别式计算判别式计算判别式:理论直线上点理论直线上点Q Q坐标为坐标为y=k(xy=k(xi i+1)+b;+1)+b;求求s s和和t:t:s=y-y s=y-yi i=k(x=k(xi i+1)+b-y+1)+b-yi i;t=(y t=(yi i+1)-y=(y+1)-y=(yi i+1)-k(x+1)-k(xi i+1)-b+1)-bstP(xi,yi)S(xi+1,yi)T(xi+1,yi+1)uu计算判别式计算判别式计算判别式计算判别

8、式:理论直线上点理论直线上点Q Q坐标为坐标为y=k(xy=k(xi i+1)+b;+1)+b;求求s s和和t:t:s=y-y s=y-yi i=k(x=k(xi i+1)+b-y+1)+b-yi i;t=(y t=(yi i+1)-y=(y+1)-y=(yi i+1)-k(x+1)-k(xi i+1)-b+1)-b则则 s-t=2k(xs-t=2k(xi+1)-2y+1)-2yi+2b-1+2b-1由于由于k=k=y yx,x,x=xx=x2-x-x1,y=yy=y2-y-y1,代入上式，得到代入上式，得到 x x (s-t)=2s-t)=2yxyxi-2-2xyxyi+(2+(2y-y-

9、x+2bx+2bx)x)(3-(3-1)1)记记d di=x x(s-t),s-t),x x0,d0,di与与(s-t)s-t)同号同号;d di值符号为选择下一值符号为选择下一个像素的判别因子。为得到个像素的判别因子。为得到d di的递推形式的递推形式,以以i+1i+1代入式代入式(3-1)(3-1)的的i i，得得 d di+1=2=2yxyxi+1-2-2xyxyi+1+(2+(2y-y-x+2bx+2bx)(3-2)x)(3-2)uu计算判别式计算判别式计算判别式计算判别式:将将(3-2)(3-2)减去减去(3-1),(3-1),且且x xi+1=x=xi+1+1，得得 d di+1=

10、d=di+2+2y-2y-2x(yx(yi+1-y-yi)(3-3)(3-3)其中其中,y yi+1-y-yi=0 0或或1 1取决于判别因子取决于判别因子d di值的符号。值的符号。如果如果d di0 0，取取S S为下一像素为下一像素,即即x xi+1=x=xi1,y1,yi+1=y=yi,有有 d di+1=d=di+2+2y (3-4)y (3-4)如果如果d di00，取取T T为下一像素为下一像素,即即x xi+1=x=xi+1,y+1,yi+1=y=yi+1,+1,有有 d di+1=d=di+2+2y-2y-2x (3-5)x (3-5)将将y y1=kx=kx1+b+b代入式

11、代入式(3-1),(3-1),得得d di初始值初始值:d d0=2=2y-y-x (3-6)x (3-6)Bresenham画线算法流程|m|m|1 1的的的的BresenhamBresenham画线算法画线算法画线算法画线算法1.1.输输输输入入入入线线线线的的的的两两两两个个个个端端端端点点点点，并并并并将将将将左左左左端端端端点点点点存存存存贮贮贮贮在在在在(x x0 0,y,y0 0)中；中；中；中；2.2.将将将将(x x0 0,y,y0 0)装入帧缓冲器，画第一个点；装入帧缓冲器，画第一个点；装入帧缓冲器，画第一个点；装入帧缓冲器，画第一个点；3.3.计计计计 算算算算 常常常常

12、 量量量量：x x、y y、2 2y y和和和和 2 2y-y-2 2x x，并得到决策参数的第一个值：并得到决策参数的第一个值：并得到决策参数的第一个值：并得到决策参数的第一个值：1.1.p p0 0=2=2yyx x；4.4.从从从从k=0k=0开开开开始始始始，在在在在沿沿沿沿线线线线的的的的每每每每个个个个x xk k处处处处，进进进进行行行行下列检测：下列检测：下列检测：下列检测：假如假如假如假如p pk k0 0，画下一个点画下一个点画下一个点画下一个点(x xk k+1+1，y yk k)，且：且：且：且：p pk k+1+1=p pk k+2+2y y；否则，下一个待画点否则，

13、下一个待画点否则，下一个待画点否则，下一个待画点(x xk k+1+1，y yk k+1+1)，且：且：且：且：p pk k+1+1=p pk k+2+2y-2y-2x x。5.5.k=k+1k=k+1；6.6.重复步骤重复步骤重复步骤重复步骤4 4，共，共，共，共x x次。次。次。次。像素生成过程屏幕显示过程 该算法仅涉及整数加法运算和乘该算法仅涉及整数加法运算和乘2(左移左移)操操作，运算效率高，易于硬件实现。作，运算效率高，易于硬件实现。与逐点比较法相比，生成的直线光滑。与逐点比较法相比，生成的直线光滑。若将该算法的范围扩大到整个平面，相应的若将该算法的范围扩大到整个平面，相应的d增量式

14、及其初始值增量式及其初始值,以及下一像素位置的取法以及下一像素位置的取法道理相似，请思考！道理相似，请思考！本章讨论内容本章讨论内容uu直线生成算法直线生成算法uu圆和圆弧的程序设计圆和圆弧的程序设计uu区域填充算法区域填充算法uu字符生成字符生成uu反走样技术反走样技术圆的生成算法圆的生成算法-中点圆生成算法中点圆生成算法uu以以单单位位间间隔隔取取样样并并在在每每个个步步长长中中确确定离指定圆最近的像素位置。定离指定圆最近的像素位置。uu对于给定半径对于给定半径r r和屏幕中心和屏幕中心(x xc c，y yc c)，运运用用平平移移：先先给给出出计计算算中中心心在在坐坐标标原原点点(0(

15、0，0)0)圆圆的的像像素素位位置置的的算算法法，然然后后通通过过将将x xc c加加到到x x和和y yc c加加到到y y而而把把每每个个计计算算出出的位置的位置(x x，y)y)移动到其适当的屏幕位置。移动到其适当的屏幕位置。运运用用对对称称：在在第第一一像像限限中中，圆圆弧弧段段从从x=0 x=0到到x=yx=y，曲曲线线的的斜斜率率从从0 0变变化化到到-1-1，因因此此，可可以以这这八八分分圆圆上上的的正正x x方方向向取取单单位位步步长长，并并使使用用决决策策参参数数来来确确定定每每一一步步中中两两个个可可能能的的y y位位置置中中更更接接近近于于圆圆的的位位置置，而而后后在在其

16、其它它七七个个八八分分圆圆中中的的位位置置可可由对称性得到。由对称性得到。候选低像素候选低像素候选高像素候选高像素前一像素前一像素候选像素中点候选像素中点x x2 2+y+y2 2-r-r2 2=0=0中点圆生成算法：算法原理算法原理uu定义圆函数：定义圆函数：f fcirclecircle(x(x，y)=xy)=x2 2+y+y2 2r r2 2 ，圆边界上任何具有半径圆边界上任何具有半径r r的点的点(x x，y)y)满足方程满足方程f fcirclecircle(x(x，y)=0y)=0。任何点任何点(x x，y)y)的相对位置可由对圆函数符号的检测来决定：的相对位置可由对圆函数符号的检

17、测来决定：l lf fcirclecircle(x(x，y)y)0 0，(x(x，y)y)位于圆边界内位于圆边界内;l lf fcirclecircle(x(x，y)y)0 0，(x(x，y)y)位于圆边界上位于圆边界上;l lf fcirclecircle(x(x，y)y)0 0，(x(x，y)y)位于圆边界外。位于圆边界外。uu在在中中点点算算法法中中圆圆函函数数是是决决策策参参数数，并并且且可可像像在在画画线线算算法法中中一一样为这个函数设置增量运算。样为这个函数设置增量运算。uu决策参数是圆函数在这两个候选像素的中点处求值：决策参数是圆函数在这两个候选像素的中点处求值：P Pk k=f

18、circle(x=fcircle(xk+1k+1，y yk k-1/2)-1/2)；根据决策参数判断：根据决策参数判断：假如假如p pk k0 0，这个中点在圆内，扫描线这个中点在圆内，扫描线y yk k上的像素上的像素(高像素高像素)接近圆边接近圆边界。界。假如假如p pk k00，中点位于圆外或在圆周边界上，选择扫描线中点位于圆外或在圆周边界上，选择扫描线y yk-1k-1的像素的像素(低低像素像素)。中点圆生成算法：决策参数决策参数uu下图示出了取样位置下图示出了取样位置x xk+1k+1处两候选像素间的中点，处两候选像素间的中点，假设假设(x xk k，y yk k)为前一像素，为前一

19、像素，需需要要决决定定下下列列哪哪个个像像素素：像像素素位位置置(x xk+1k+1，y yk k)，像像素素位位置置(x xk+1k+1，y yk-1k-1)更更接接近于圆？近于圆？注意：圆在第一像限，注意：圆在第一像限，y0y0，y y方向应取减量。方向应取减量。中点圆生成算法：生成过程中点圆生成算法：生成过程1.1.输输输输入入入入圆圆圆圆半半半半径径径径r r和和和和圆圆圆圆心心心心(x xc c，y yc c)，并并并并得得得得到到到到圆圆圆圆心心心心在在在在原原原原点点点点的的的的圆圆圆圆周周周周上上上上的的的的第第第第一一一一点点点点为为为为：(x x0 0，y y0 0)=(0

20、)=(0，r)r)2.2.计算决策参数的初始值为：计算决策参数的初始值为：计算决策参数的初始值为：计算决策参数的初始值为：p p0 0=5/4-r=5/4-r3.3.在每个在每个在每个在每个xkxk位置处，从位置处，从位置处，从位置处，从k=0k=0开始，完成下列检测：开始，完成下列检测：开始，完成下列检测：开始，完成下列检测：假如假如假如假如p pk k0 0，中心在中心在中心在中心在(0,0)(0,0)的圆的下一个点为的圆的下一个点为的圆的下一个点为的圆的下一个点为(x xk k+1+1,y yk k)，且：且：且：且：p pk k+1+1=p pk k+2x+2xk+1k+1+1+1；否

21、则，圆的下一点是否则，圆的下一点是否则，圆的下一点是否则，圆的下一点是(x xk k+1+1,y yk k-1)-1)，且：且：且：且：p pk k+1+1=p pk k+2x+2xk+1k+1+1-2y+1-2yk+1k+1。其中：其中：其中：其中：2 2x xk k+1+1=2x=2xk k+2+2，且且且且 2 2y yk k+1+1=2y=2yk k-2-2。4.4.确定在其它七个八分圆中的对称点。确定在其它七个八分圆中的对称点。确定在其它七个八分圆中的对称点。确定在其它七个八分圆中的对称点。5.5.将将将将每每每每个个个个计计计计算算算算出出出出的的的的像像像像素素素素位位位位置置置

22、置(x,y)x,y)移移移移动动动动到到到到中中中中心心心心在在在在(x xc c,y,yc c)的园路径上，并画坐标值：的园路径上，并画坐标值：的园路径上，并画坐标值：的园路径上，并画坐标值：x=x+xx=x+xc c，y=y+yy=y+yc c6.6.重复步骤重复步骤重复步骤重复步骤3 3到到到到5 5，直止，直止，直止，直止xyxy。本章讨论内容本章讨论内容uu直线生成算法直线生成算法uu圆和圆弧的程序设计圆和圆弧的程序设计uu区域填充算法区域填充算法uu字符生成字符生成uu反走样技术反走样技术区域填充区域填充uu区域区域是指一组相邻而又连通、具有相同属性的像素集。在区域内，生成某一属性

23、的实心或图案的过程称为区域填充区域填充。uu内点内点,边界和外点边界和外点:位于区域的点称为内点位于区域的点称为内点,与与内点相邻但又不属于该区域的像素组成了边界内点相邻但又不属于该区域的像素组成了边界,不不是内点和边界的像素是外点是内点和边界的像素是外点.uu光栅系统有两种区域填充算法：扫描线填充算法：扫描线填充算法：主要用于填充主要用于填充多边形、圆、椭圆以及其它简单多边形、圆、椭圆以及其它简单曲线所围成的封闭区域。曲线所围成的封闭区域。种子填充算法种子填充算法：适用于具有复杂：适用于具有复杂形状边界的区域填充。形状边界的区域填充。扫描线填充算法扫描线填充算法uu按顺序计算扫描线与多边形的

24、相交区域，用要求的颜色显示这些区间的像素，即完成填充工作。P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)u例如，y=6的扫描线与多边形有四个交点，显然，第1与第2、第3与第4间的区域落在多边形内，这些区间的像素填充预期的颜色。uu填充过程填充过程，对于一，对于一条扫描线，可以分成条扫描线，可以分成四个步骤：四个步骤：P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)(1)求交：求交：计算扫描线与多边形每个边的交点。(2)排序：排序：把所求出的交点按x递增的顺序排序。(3)交点配对：交点配对：第一与第二，第三与第四等

25、等，每对交点代表扫描线与多边形的一个相交区域。(4)区间填色：区间填色：把相交区域内的像素设置成多边形的颜色，把相交区域外的像素设置成背景色。解决两个特殊问题解决两个特殊问题扫描线与多边形的顶点相交，交点的取舍。P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)多边形边界上的像素的取舍问题。2 24 46 68 81 1个交点个交点0 0个交点，个交点，不填充不填充 2 2个交点，个交点，填充填充解决两个特殊问题解决两个特殊问题扫描线与多边形的顶点相交，交点的取舍。P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)多边

26、形边界上的像素的取舍问题。2 24 46 68 8种子填充算法种子填充算法 基本思想基本思想:从区域内部已定义新值的某像素从区域内部已定义新值的某像素(种子种子)开始开始,搜索与该种子相邻且位于区域内搜索与该种子相邻且位于区域内的像素的像素,该像素为新的种子；不断地递归搜索该像素为新的种子；不断地递归搜索,逐个像素填充所需颜色逐个像素填充所需颜色,直到填充完区域边界直到填充完区域边界内的所有像素为止。内的所有像素为止。区域分区域分四连通四连通区域和区域和八连通八连通区域区域:连通区域定义uu4 4连通区域：连通区域：任任取取区区域域内内两两点点，在在该该区区域域内内，允允许许通通过过上上、下、

27、左、右下、左、右四个方向四个方向的运动，这两点相互可达。的运动，这两点相互可达。uu8 8连通区域：连通区域：任任取取区区域域内内两两点点，在在该该区区域域内内，允允许许通通过过水水平平、垂垂直直、两两个个对对角角线线八八个个方方向向的的运运动动，这这两两点点相相互可达。互可达。连通区域定义uu由由定定义义可可知知：4 4连连通通区区域域也也可可以以看看作作是是8 8连连通通区区域域。但但它它作作为为4 4连连通通区区域域和和8 8连连通通区区域域的的边边界界是是不不同同的的(4(4连连通通比比8 8连连通通约束紧。左下图约束紧。左下图)：像素作为像素作为4 4连通区域连通区域，其，其边界只要

28、是连通边界只要是连通就可以了；就可以了；像像素素作作为为8 8连连通通区区域域，其其边边界界必必须须是是连连通通区区域域。否否则则，欠约束。欠约束。8 8连通区域能用来填充更复杂的图形连通区域能用来填充更复杂的图形(如下图所示如下图所示)。起始点起始点4连通连通区域边界区域边界8连通连通区域边界区域边界(1)边界填充算法边界填充算法 如如如如果果果果区区区区域域域域采采采采用用用用边边边边界界界界定定定定义义义义，即即即即边边边边界界界界上上上上的的的的所所所所有有有有像像像像素素素素具具具具有有有有某某某某个个个个相相相相同同同同的的的的特特特特定定定定值值值值(颜颜颜颜色色色色或或或或亮亮

29、亮亮度度度度)，区区区区域域域域内内内内部部部部所所所所有有有有像像像像素素素素均均均均具具具具有有有有非非非非新新新新值值值值的的的的某某某某个个个个给给给给定定定定值值值值；这这这这种种种种区区区区域内的种子填充算法又称边界填充算法。域内的种子填充算法又称边界填充算法。域内的种子填充算法又称边界填充算法。域内的种子填充算法又称边界填充算法。Boundary-fill-4(x,y,newcolor,boundarycolor)int x,y,newcolor,boundarycolor;int testcolor;testcolor=getpixel(x,y);if(testcolor!=b

30、oundarycolor)&(testcolor!=newcolor)putpixel(x,y,newcolor);boundary-fill-4(x,y+1,newcolor,boundarycolor);boundary-fill-4(x,y-1,newcolor,boundarycolor);boundary-fill-4(x+1,y,newcolor,boundarycolor);boundary-fill-4(x-1,y,newcolor,boundarycolor);(2)漫溢填充算法（泛滥）漫溢填充算法（泛滥）对对于于内内定定义义区区域域，其其区区域域内内部部所所有有像像素素均均

31、具具有有某某个个相相同同的的特特定定值值，区区域域外外的的所所有有像像素素具具有有其其它它不不同同的的值值，这这种种区区域域称称内内定定义义区区域域。对对内内定定义义区区域域采采用用的的种种子子填填充充算算法叫漫溢填充算法。法叫漫溢填充算法。区域填充属性区域填充属性uu区域填充属性区域填充属性是软件系统提供用户对是软件系统提供用户对已定义的图形区域已定义的图形区域(可包含边界可包含边界)填充填充自己所选择的图形内容的一种功能。自己所选择的图形内容的一种功能。uu一般区域填充属性包括一般区域填充属性包括填充模式填充模式填充颜色填充颜色填充图案填充图案(1)填充模式填充模式uu常见的有三种基本形式

32、：常见的有三种基本形式：空心的、实心的空心的、实心的和选定图案和选定图案。uTurbo C中由函数中由函数Setfillstyle(int pattern,int color)设置填充模式和填充颜色。设置填充模式和填充颜色。pattern定义填充模式类型定义填充模式类型Empty_Fill以背景色填充以背景色填充Solid_Fill以某一单色填充以某一单色填充Xhatch_Fill以斜网格填充以斜网格填充u填充函数：矩形填充函数：矩形bar(),多边形多边形fillpoly()等。等。(2)填充颜色填充颜色uucolor是定义区域边界或区域内部填充颜色是定义区域边界或区域内部填充颜色的参数，例

33、如，对于空心区域，只有在边的参数，例如，对于空心区域，只有在边界轮廓上显示所指定的填充颜色；对于实界轮廓上显示所指定的填充颜色；对于实心区域包括具有图案的区域，将以填充颜心区域包括具有图案的区域，将以填充颜色显示区域内部，也可包含其边界。色显示区域内部，也可包含其边界。本章讨论内容本章讨论内容uu直线生成算法直线生成算法uu圆和圆弧的程序设计圆和圆弧的程序设计uu区域填充算法区域填充算法uu字符生成字符生成uu反走样技术反走样技术字符的表示与输出uu国国际际字字符符编编码码：ASCIIASCII(American(American Standard Standard Code Code for

34、 for Information Interchange)Information Interchange)：7 7位位二二进进制制编编码码，共共128128个个字字符符。一一个个字字符符的的ASCIIASCII码码用用一一个个字字节节(8(8位位)表表示示，其其最最高高位位不不用用或作为奇偶校验位。或作为奇偶校验位。uu汉字编码汉字编码：国家标准信息交换编码国家标准信息交换编码GB2312-80GB2312-80汉字汉字67636763个、图形符号个、图形符号682682个。个。所所有有字字符符组组成成94949494矩矩阵阵表表示示，行行称称为为区区，用用区码标识，列称为位，用位码标识；区码

35、标识，列称为位，用位码标识；点阵字符uu点阵字符的存储点阵字符的存储点点阵阵字字符符是是由由一一个个位位图图表表示示：保保存存字字符符就就是是保保存存表表示示它它的的位位图图。字字型型7979、916916、16241624等等指指的的是是位位图图的的尺尺寸寸。一一个个汉汉字字需需要要1616x24=384x24=384位位，即即4848个个字字节节，而而常常用用汉汉字字有有67636763个个，从从而而存存储这种型号需要储这种型号需要676348324676348324K K字节。字节。在在实实际际应应用用中中需需要要多多种种字字体体(如如宋宋体体、揩揩体体等等)，每每种种字字体体又又有有十

36、十多多种种型型号号。因因此此汉汉字字字字库库所所占占的的存存储储空空间间是是相相当当庞大的，解决办法是采用压缩技术。庞大的，解决办法是采用压缩技术。111100000101000010100001100100100000010000001000000110010000000点阵字符uu点阵字符的显示点阵字符的显示从从给给定定的的字字符符编编码码到到在在屏屏幕幕上上将将它显示出来经历两个步骤：它显示出来经历两个步骤：第第一一步步（检检索索）是是从从字字库库中中将将它它的的位位图图检检索索出出来来，由由于于表表示示同同一一型型号号字字符符的的位位图图所所占占空空间间大大小小相相同同，可可以以直直接

37、接将将一一个个字字符符在在字字库库中的位置计算出来；中的位置计算出来；第第二二步步（显显示示）是是将将检检索索到到的的位位图图写写到到帧帧缓缓存存中中，这这可可以以利利用用光光栅系统的位拷贝功能。栅系统的位拷贝功能。矢量字符uu矢量字符的存储矢量字符的存储字符矢量表示中，记录的是字符的字符矢量表示中，记录的是字符的笔画信息笔画信息。l l首首先先选选一一个个正正方方形形网网格格作作为为字字符符的的局局部部坐坐 标标 空空 间间，网网 格格 的的 大大 小小 可可 取取 16161616、32323232、64646464等。等。l l对对一一个个字字符符来来说说，它它由由构构成成它它的的笔笔画

38、画组组成成，而而每每一一笔笔又又由由其其两两端端确确定定。对对于于每每一一个个端端点点，只只要要保保存存它它的的坐坐标标值值和和由由前前一端点到此端点一端点到此端点是否连线的标志是否连线的标志即可。即可。表表示示一一个个矢矢量量字字符符最最终终只只需需要要所所有有的的端端点点坐坐标信息及其是否连线的标志。标信息及其是否连线的标志。实实际际的的矢矢量量字字符符的的存存储储结结构构要要加加上上一一些些管管理理信息和字型信息等。信息和字型信息等。(63,63)P0P5P4P1P2P3x00001字符的编码字符的编码y0-111x1y1x2y2x3y3x4y4x5y5不连线不连线连线连线字符结束标志字

39、符结束标志矢量字符uu矢量字符的显示矢量字符的显示第第一一步步（检检索索）根根据据给给定定字字符符的的编编码码，在字库中检索出表示该字符的数据。在字库中检索出表示该字符的数据。l l由由于于各各个个字字符符的的笔笔画画不不一一样样多多，端端点点也也不不一一样样多多，造造成成存存储储各各个个字字符符的的记记录录所所占占字字节节数数也也不不同同，给给检检索索带带来来一一定定困困难难。为为了了提提高高检检索索效效率率，可以改变字符的存储结构。可以改变字符的存储结构。第第二二步步（变变换换）是是取取出出端端点点坐坐标标，对对其其进进行行适适当当的的几几何何变变换换，再再根根据据各各端端点的标志显示出字

40、符。点的标志显示出字符。(63,63)P0P5P4P1P2P3x00001字符的编码y0-111x1y1x2y2x3y3x4y4x5y5不连线连线字符结束标志点阵字符和矢量字符uu字符变换不同字符变换不同表表示示点点阵阵字字符符的的是是位位图图，对对点点阵阵字字符符的的变变换换要要对对位位图图中中的的每每一一个个像像素素进行，是图像变换，放大或旋转时会失真。进行，是图像变换，放大或旋转时会失真。表表示示矢矢量量字字符符的的是是端端点点坐坐标标，对对矢矢量量字字符符的的变变换换是是对对端端点点的的变变换换，是是图形的几何变换，不会影响显示效果。图形的几何变换，不会影响显示效果。uu占用空间不同占

41、用空间不同矢量字符占用空间较少，矢量字符占用空间较少，l l首先其单个字符占用较少空间；首先其单个字符占用较少空间；l l其其次次，矢矢量量字字符符只只需需保保存存一一套套字字符符，所所需需的的不不同同型型号号的的字字符符可可以以通通过过相相应的几何变换来产生。应的几何变换来产生。uu矢量字符美观矢量字符美观除除了了直直线线段段外外，还还可可以以用用二二次次曲曲线线段段、三三次次曲曲线线段段等等来来表表示示笔笔画画，使使字符更加美观。字符更加美观。矢矢量量字字符符占占用用空空间间小小、美美观观、变变换换方方便便等等优优点点得得到到越越来来越越广广泛泛的的应应用用，特别是在排版、软件和工程图软件

42、中它几乎已经完全取代了点阵字符特别是在排版、软件和工程图软件中它几乎已经完全取代了点阵字符。字符的显示字符的显示 图图形形标标准准或或一一般般的的软软件件系系统统通通常常都都用用各各自自统统一一的的函函数数提提供供字字符符显显示示，且且可可通通过过参参数数选选择择来来控控制制字字符的符的字体、大小、颜色、方向字体、大小、颜色、方向等属性等属性。例例 如如,在在 Turbo C图图 形形 模模 式式 下下，用用 函函 数数Settextstyle(font,direction,charsize)设设置置文文本本的的字字体体、方方向向及及大大小小；调调用用函函数数Outtext(*textstri

43、ng)或或Outtextxy(x,y,*textstring)在在屏屏幕幕上上以以当当前前前前景景色色在在当当前前位位置置或或指指定定的的(x,y)位位置置显显示示字字符符串串textstring所指定的文本所指定的文本.本章讨论内容本章讨论内容uu直线生成算法直线生成算法uu圆和圆弧的程序设计圆和圆弧的程序设计uu区域填充算法区域填充算法uu字符生成字符生成uu反走样技术反走样技术走样现象走样现象反走样方法反走样方法简单简单区域采样加权区域采样反走样技术走样现象走样：用离散量：用离散量(像素像素)表示连续的量表示连续的量(图形图形)而引起的失真，叫做而引起的失真，叫做走样走样。反走样方法uu

44、什么是反走样在图形显示过程中，用于减少或消在图形显示过程中，用于减少或消除走样现象的方法除走样现象的方法1）提高分辨率方法）提高分辨率方法 2）非加权区域采样）非加权区域采样 3）加权区域采样）加权区域采样 方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍时间。反走样方法uu提高分辨率的反走样方法 区域采样方法uu方法由来两点假设1 1、像像素素是是数数学学上上抽抽象象的的点点，它它的的面面积积为为0 0，它它的亮度由覆盖该点的图形的亮度所决定；的亮度由覆盖该点的图形的亮度所决定；2 2、直线段

45、是数学上抽象直线段，它的宽度为、直线段是数学上抽象直线段，它的宽度为0 0。现实l l像素的面积不为像素的面积不为0 0；l l直线段的宽度至少为直线段的宽度至少为1 1个像素；个像素；假设与现实的矛盾是导致走样出现的原因之一反走样基本方法uu非加权区域采样方法非加权区域采样方法l l将直线段看作是具有一定宽度的狭长矩形；将直线段看作是具有一定宽度的狭长矩形；l l当直线段与像素有交时，求出两者相交区域的面积；当直线段与像素有交时，求出两者相交区域的面积；l l根据相交的面积确定该像素的亮度等级；根据相交的面积确定该像素的亮度等级；直线段对一个像素亮度的贡献与两者相交面积成正比。直线段对一个像

46、素亮度的贡献与两者相交面积成正比。这样使线段上各相邻像素的亮度之间有一个平缓的过这样使线段上各相邻像素的亮度之间有一个平缓的过渡，淡化了锯齿现象。渡，淡化了锯齿现象。每个像素面积为单位面积；每个像素面积为单位面积；相相交交区区域域面面积积是是介介于于0 0，1 1之之间的实数；间的实数；用用它它乘乘以以像像素素可可设设置置的的最最大大亮亮度度值值，即即可可得得到到该该像像素素实实际显示的亮度值。际显示的亮度值。反走样基本方法uu加权区域采样方法加权区域采样方法l l将直线段看作是具有一定宽度的狭长矩形；将直线段看作是具有一定宽度的狭长矩形；l l当直线段与像素有交时，根据相交区域与像素中心的距

47、离来决当直线段与像素有交时，根据相交区域与像素中心的距离来决定其对象素亮度的贡献。定其对象素亮度的贡献。l l直线段对一个像素亮度的贡献正比于相交区域与像素中心的距直线段对一个像素亮度的贡献正比于相交区域与像素中心的距离。离。这种方法更符合人视觉系统对图像信息的处理方式，反走样效果更这种方法更符合人视觉系统对图像信息的处理方式，反走样效果更好。好。设设置置相相交交区区域域面面积积元元与与像像素素中中心心距距离离的的权权函函数数(如如高高斯斯函函数数等等)反反映映相相交交面面积积元元对对整整个像素亮度的贡献大小。个像素亮度的贡献大小。利利用用权权函函数数积积分分求求相相交交区区域域面面积积，用用

48、它它乘乘以以像像素素可可设设置置的的最最大大亮亮度度值值，即即可可得得到到该该像素实际显示的亮度值。像素实际显示的亮度值。直线段的过取样 uu过取样过取样(超放样超放样/后过滤后过滤)：在高分辩率下对对象取样，在较低分辨率上显示其结果。在高分辩率下对对象取样，在较低分辨率上显示其结果。基基本本思思想想：把把屏屏幕幕看看成成比比实实际际所所具具有有的的更更细细的的网网格格来来增增加加取取样样率率；再再沿这种更细网格使用取样点来确定每个屏幕像素的合适亮度等级。沿这种更细网格使用取样点来确定每个屏幕像素的合适亮度等级。uu从从多多个个点点对对一一个个像像素素总总体体亮亮度度的的贡贡献献来来得得到到该

49、该象素的亮度信息；象素的亮度信息；每每个个像像素素可可能能的的亮亮度度等等级级数数目目等等于于像像素素区区域域内内子子像像素素的的总总数数；总总的的线线亮亮度度在在更更多多的的像素上描述。像素上描述。这这样样，线线亮亮度度分分布布在在较较大大数数目目像像素素上上，并并且且通通过过在在阶阶梯梯状状台台阶阶附附近近显显示示有有些些模模糊糊的的线路径线路径使阶梯形状得到光顺。使阶梯形状得到光顺。亮度等级的数目取决于子像素的多少。亮度等级的数目取决于子像素的多少。直线段的过取样 uu考虑线宽度时，则将每个像素考虑线宽度时，则将每个像素亮度设置成正比于亮度设置成正比于线区域内的线区域内的子像素数目子像素

50、数目来完成过取样。来完成过取样。uu有颜色显示时：有颜色显示时：对子像素对子像素亮度进行平均亮度进行平均来得到像素来得到像素颜色设置。颜色设置。线亮度差的校正uu为减轻阶梯形效果，反走样线为另一种光栅效果提供校正。为减轻阶梯形效果，反走样线为另一种光栅效果提供校正。用用相相同同数数目目像像素素所所画画的的两两条条线线，对对角角线线还还是是比比水水平平线线长长，可可视视效效果果是是对角线显得比水平线要暗，因为对角线以更低的对角线显得比水平线要暗，因为对角线以更低的单位长度亮度单位长度亮度显示。显示。uu通过按照每条线的斜率来调整其亮度，就可对这种效果进行校正。通过按照每条线的斜率来调整其亮度，就