CG第3章基本图形生成算法C课件.ppt

1、2022-8-81第5章 基本图形生成算法 图形生成图形生成:是是在指定的输出设备上根据坐标描述构在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。对于光栅显示器形域、字符串及其相关属性等）。对于光栅显示器来说，将屏幕看作像素矩阵来说，将屏幕看作像素矩阵，在该矩阵上在该矩阵上。确定一确定一个像素集合来逼近图形。个像素集合来逼近图形。2022-8-825.1 直线的扫描转换The lines of this objectappear continuousHowever,they aremade o

2、f pixels2022-8-83图5-1 用一系列的象素点来逼近直线图形的扫描转换图形的扫描转换 在光栅显示器等设备上确定一个在光栅显示器等设备上确定一个最佳逼近于图形象素集的过程，如下图所示最佳逼近于图形象素集的过程，如下图所示：5.1 直线的扫描转换直线的扫描转换2022-8-845.1 直线的扫描转换 直线的绘制要求：直线的绘制要求：1.1.直线要直直线要直2.2.直线的端点要准确，直线的端点要准确，即无定向性和断裂情况即无定向性和断裂情况3.3.直线的亮度、色泽要均匀直线的亮度、色泽要均匀4.4.画线的速度要快画线的速度要快5.5.直线具有不同的色泽、亮度、线型等直线具有不同的色泽、

3、亮度、线型等直线绘制算法有直线绘制算法有：逐点比较法、正负法、逐点比较法、正负法、数值微分法和中点数值微分法和中点BreshenhamBreshenham算法等算法等。2022-8-85数值微分法（数值微分法（DDA方法，方法，Digital Differential Analyzer）要解决的问题：给定直线两端点要解决的问题：给定直线两端点P0(x0,y0)和和P1(x1,y1)，画出该直线。画出该直线。直线的方程为直线的方程为1010,(constant)yydyymdxxxx111(1)iiiiixxym xbym,(01)ym xbm注：注：1、仅需要计算一次、仅需要计算一次m；2、x

4、每增加一个单位，每增加一个单位，y只需加上一个只需加上一个m，回避了乘法运算，提高了运算效率。回避了乘法运算，提高了运算效率。1,x取2022-8-86问题：若问题：若|m|1,?x与与y互换；互换；m与与1/m互换互换x=x+1y=y+12022-8-87若直线为参数方程表示：若直线为参数方程表示：,01ssxxx ttyyy t 其中：其中：,;esesxxxyyy 令：令：max,nxy则则t 的每次增量为：的每次增量为：1/.tn 故，第故，第 i 步时：步时：,isiisixxx tyyy t 于是：于是：11(),()isiiisiixxxttxx tyyyttyy t 其中：其中

5、：均为常数，上式即给出了一个迭代算法。均为常数，上式即给出了一个迭代算法。,xyt2022-8-88特别地：当特别地：当 max(|x|,|y|)=|x|，即即|m|1时：时：11111iiiiiixxxxxyyyymx 当当 max(|x|,|y|)=|y|，即即|m|1时时：111111iiiiiixxxxymyyyyy 2022-8-89 DDA是一种增量算法是一种增量算法,直观、易实现；直观、易实现；但其中的但其中的x，y，m都要用浮点数，计算较大都要用浮点数，计算较大,且要对且要对x，y作取整运算，费时且不利于用硬件实现。作取整运算，费时且不利于用硬件实现。图5-3 DDA算法生成直

6、线段(xi,yi)(xi+1,round(yi+m)(round(xi+1/m),yi+1)2022-8-810Bresenham算法（算法（Bresenhams algorithm(1965)）J.E.Bresenham,Algorithm for computer control of a digital plotter,IBM Systems Journal,1965,3,pp.25-30.该算法仅使用整数运算，运算速度大大提高，该算法仅使用整数运算，运算速度大大提高，是最有效的算法之一。是最有效的算法之一。核心思想：核心思想：分析直线与网格线的交点与分析直线与网格线的交点与网格点的距离

7、。网格点的距离。该距离与该距离与1/2的差称为误差项。的差称为误差项。2022-8-8112121(,)0 ,yyyF x yymxbmxxx其中同样给定直线两端点同样给定直线两端点P1(x1,y1)和和P2(x2,y2)，可得可得直直线的方程如下：线的方程如下：xyF(x,y)0F(x,y)=0F(x,y)0F(x,y)=0F(x,y)0；直线下方的点，直线下方的点，F(x,y)0。2022-8-812 基本原理基本原理：假定假定0m1，x是最大位移方向，每次是最大位移方向，每次在在x方向上加方向上加1，y方向上加方向上加1或或0。图5-5 Brensemham算法生成直线的原理Q(,)ii

8、P x y(1,1)aiiP xy(1,)biiP xy(1,1/2)iiM xy2022-8-813由中点由中点M可得判别式可得判别式：(,)(1,0.5)0.5(1)iMMiiiidF xyF xyym xb有有：11 (0)(0)iiiiiydyydQ(,)iiP x y(1,1)aiiP xy(1,)biiP xy(1,1/2)iiM xy问题：算法结束了吗？问题：算法结束了吗？有无优化的可能？有无优化的可能？注意：计算注意：计算di 的运算量并不小的运算量并不小.2022-8-814误差项的递推误差项的递推若若di0，有有1(2,1.5)1.5(2)1.5(1)1iiiiiiiidF

9、xyym xbym xbmdmdi0(2,1.5)iiM xyQ(,)iiP x y(1,0.5)iiM xy2022-8-815误差项的递推误差项的递推若若di0，有有1(2,0.5)0.5(2)0.5(1)iiiiiiiidF xyym xbym xbmdm(2,0.5)iiM xyQ(,)iiP x y(1,0.5)iiMxy2022-8-816初始值初始值d 的计算：的计算：0000000(1,0.5)0.5(1)0.5 0.5dF xyym xbymxbmm故，关于故，关于di，有，有:0110.5;01,iiiiidmifdddmelseddmend关于关于yi+1，有，有:11

10、(0)(0)iiiiiydyyd2022-8-817 由于只关心由于只关心d 的符号的符号,故可用故可用2xd 代替代替d 来摆脱小数计来摆脱小数计算算,得到整数运算得到整数运算,于是：于是：d0=0.5-k 2xd0=x-2y d 0 时时:d=d+1-m 2x d=2x d+2x-2y；d 0 时时:d=d-m 2x d=2x d-2y。整数级整数级Bresenham算法算法2022-8-818 0m1时时Bresenham算法的步骤为算法的步骤为：1.输入直线的两端点输入直线的两端点P0(x0,y0)和和P1(x1,y1)。2.计算初始值计算初始值x,y,d=x-2y,x=x0,y=y0

11、；3.绘制点绘制点(x,y)，根据根据d的符号进行如下操作：的符号进行如下操作：若若d0，则则(x,y)更新为更新为(x+1,y+1)，d更新为更新为 d+2x-2y；否则否则 (x,y)更新为更新为(x+1,y)，d更新为更新为d-2y 。4.当直线没有画完时，转步骤当直线没有画完时，转步骤3；否则结束。；否则结束。2022-8-819void Bresenham(int xl,int yl,int xr,int yr)int x,y;/*coordinates of pixel being drawn*/int dy=yr-y1,dx=xr-x1;int ie;/*integer scal

12、ed error term*/x=xl;y=yl;/*start at left endpoint*/ie=dx-2*dy;/*initialize the error term*/while(x=xr)/*pixel-drawing loop*/PlotPixel(x,y);/*draw the pixel*/if(ie 0；而对于圆内的点，而对于圆内的点，F(x,y)0时，下一点取时，下一点取Pd(xi+1,yi-1)。M的坐标为：的坐标为：M(xi+1,yi-0.5)当当F(xM,yM)0时，取时，取Pd(xi+1,yi-1)当当F(xM,yM)=0时，约定取时，约定取Pu。构造判别式：

13、构造判别式：222)5.0()1()5.0,1(),(RyxyxFyxFdiiiiMM2022-8-828误差项的递推误差项的递推 d0：(a)d0：5)(2 )22()32()5.0()1()5.1()2()5.1,2(222222iiiiiiiiiiyxdyxRyxRyxyxFd(b)d0的情况Pxixi+2xi+1yi-1yiyi-2误差项的递推误差项的递推2022-8-830判别式的初始值判别式的初始值RRRRFd25.1 )5.0(1 )5.0,1(2202022-8-831算法步骤：算法步骤：1.输入圆的半径输入圆的半径R。2.计算初始值计算初始值d=1.25-R、x=0、y=R。

14、3.绘制点绘制点(x,y)及其在八分圆中的另外七个对称点。及其在八分圆中的另外七个对称点。4.判断判断d的符号。若的符号。若d0，则先将则先将d更新为更新为d+2x+3，再将再将(x,y)更新为更新为(x+1,y)；否则先将否则先将d更新为更新为d+2(x-y)+5，再再将将(x,y)更新为更新为(x+1,y-1)。5.当当x00；椭圆内的点椭圆内的点 F(x,y)00，取取Pd(xi+1,yi-1)p(xi,yi)pu(xi+1,yi)pd(xi+1,yi-1)M(xi+1,yi-0.5)5-17 上半部分椭圆弧的绘制原理2022-8-840误差项的递推误差项的递推 d10：(a)d0的情况

15、Pxixi+2xi+1yi-1yiyi-2误差项的递推误差项的递推 d10：判别式的初始值判别式的初始值 (弧的起点为弧的起点为(0，b)25.0()5.0()5.0,1(222222210babbababbFd椭圆弧下半部分的绘制方法类似。椭圆弧下半部分的绘制方法类似。2022-8-8435.4 多边形的扫描转换与区域填充 填充的意义：填充的意义：1.1.表示区域，表示区域，2.2.真实感显示。真实感显示。多边形的扫描转换主要是多边形的扫描转换主要是从多边形的顶点表示到点从多边形的顶点表示到点阵表示的转换阵表示的转换。区域填充是从给定的位置开始涂描直到指定的边界区域填充是从给定的位置开始涂描

16、直到指定的边界条件为止。条件为止。2022-8-8445.4.1 多边形的扫描转换 多边形的表示方法有多边形的表示方法有顶点表示顶点表示和和点阵表示点阵表示。前者用多边。前者用多边形的顶点序列来刻划多边形形的顶点序列来刻划多边形,几何意义强几何意义强,占内存少，但占内存少，但不能直接用于显示；后者用位于多边形内的象素的集合不能直接用于显示；后者用位于多边形内的象素的集合来刻划多边形来刻划多边形,方便显示方便显示,但几何意义丢失。但几何意义丢失。故需要进行多边形扫描转换故需要进行多边形扫描转换,即即:从多边形的顶点表示到从多边形的顶点表示到点阵表示的转换点阵表示的转换。1.什么是多边形的扫描转换

17、2022-8-8455.4.1 多边形的扫描转换多边形的扫描转换1.逐点判断算法逐点判断算法基本思想：基本思想：帧缓冲器中对每个象素进行扫描，确定它们是否在多边形内帧缓冲器中对每个象素进行扫描，确定它们是否在多边形内（从该象素点出发向外发射射线，若有奇数个交点，则在多（从该象素点出发向外发射射线，若有奇数个交点，则在多边形内，否则在多边形外）。边形内，否则在多边形外）。使用一个布尔量使用一个布尔量inside(P,x,y)来指示当前点是否在多边形内来指示当前点是否在多边形内的状态，从而给出多边形内的点的集合。的状态，从而给出多边形内的点的集合。然后对多边形内的点着多边形颜色，否则着背景色。然后

18、对多边形内的点着多边形颜色，否则着背景色。特点：特点：程序简单，但速度太慢。程序简单，但速度太慢。原因原因:(1)割断了各项素之间的联系；割断了各项素之间的联系；(2)孤立地考察各象素与孤立地考察各象素与多边形的内外关系，使得几乎所有象素都要判断；多边形的内外关系，使得几乎所有象素都要判断；(3)每次判每次判断需要多次求交，需要大量乘除运算，效率较低断需要多次求交，需要大量乘除运算，效率较低。2022-8-8465.4.1 多边形的扫描转换多边形的扫描转换2.扫描线算法扫描线算法特点：特点：综合利用了相邻象素之间的连贯性，避免了对象素的逐点判综合利用了相邻象素之间的连贯性，避免了对象素的逐点判

19、断和反复求交的运算，达到了减少运算次数和提高速度的目断和反复求交的运算，达到了减少运算次数和提高速度的目的。的。具体地具体地：综合利用了综合利用了（1）区域的连贯性；区域的连贯性；（2）扫描线连贯性；）扫描线连贯性；（3）边的连贯性。）边的连贯性。2022-8-847 2.1.x-扫描线算法 基本思想基本思想：按扫描线顺序计按扫描线顺序计算扫描线与多边形相交区间，算扫描线与多边形相交区间，再用指定的颜色显示这些区再用指定的颜色显示这些区间的象素。间的象素。y3的扫描线与多边形的边的扫描线与多边形的边界相交于点界相交于点(2,3)、(4,3)、(7,3)、(9,3)，定义了多边形，定义了多边形内

20、的两个区间，其中的象素内的两个区间，其中的象素应取填充色。应取填充色。图5-23 x-扫描线算法填充多边形xy213 4 5 6 7 8 91112345678910111210122022-8-848算法步骤算法步骤：(1)确定多边形所占有的最大扫描确定多边形所占有的最大扫描线数，得到多边形顶点的最线数，得到多边形顶点的最小和最大小和最大y值（值（ymin和和ymax）。）。(2)从从y=ymin到到y=ymax，每次用一每次用一条扫描线进行填充。条扫描线进行填充。(3)对一条扫描线填充的过程可分对一条扫描线填充的过程可分为四个步骤：为四个步骤：a.求交，求交，b.排序，排序，c.交点配对，

21、交点配对，d.区间填色区间填色图5-23 x-扫描线算法填充多边形xy213 4 5 6 7 8 91112345678910111210120112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)2022-8-849 存在问题存在问题：当扫描线当扫描线与多边形顶点相交与多边形顶点相交时，交点如何取舍时，交点如何取舍?xy213456789111234567891011121012图5-24 与多边形顶点相交的交点的处理 若共享顶点的两条边若共享顶点的两条边分别落在扫描线的两分别落在扫描线的两边，交点只算

22、一个；边，交点只算一个；若共享顶点的两条边若共享顶点的两条边在扫描线的同一边，在扫描线的同一边，这时交点作为零个或这时交点作为零个或两个。两个。0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)2022-8-8502.2.y连贯性算法xi,yixi+1,yi+111/k图5-26 与多边形边界相交的两条连续扫描线交点的相关性 也叫有效也叫有效(活性活性)边表算法边表算法,是是对对x-扫描线算法的改进。扫描线算法的改进。处理一条扫描线时，仅对有处理一条扫描线时，仅对有效边求交；效边求交；利用扫描线的连

23、贯性；利用扫描线的连贯性；利用多边形边的连贯性利用多边形边的连贯性 xi+1=xi+1/k。2022-8-851有效边有效边（Active Edge）：指与当前扫描线相交的指与当前扫描线相交的多边形的边，也称为活多边形的边，也称为活性边。性边。有效边表有效边表（Active Edge Table,AET）：）：把有效把有效边按与扫描线交点边按与扫描线交点x坐标坐标递增的顺序存放在一个递增的顺序存放在一个链表中，此链表称为有链表中，此链表称为有效边表。效边表。xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a)多边形P0P1P2P3P4P5P6P0p

24、2p0p62022-8-852多边形及其有效边表和边表xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a)多边形P0P1P2P3P4P5P6P0p2p0p6 边表（边表（Edge Table，ET）的构造：）的构造：1234567891011123-1/3353/485-1/2891/21 122/57 12-1795桶p3p2p3p4p5p4p5p6p2p1p0p1p0p6x|y min ymax1/k next(c)边表62022-8-853 边表边表（Edge Table）的构造的构造：(1)首先构造一个纵向链表首先构造一个纵向链表,链表的长

25、度为多边形所占有链表的长度为多边形所占有的最大扫描线数的最大扫描线数,链表的每个结点链表的每个结点(称为一个桶称为一个桶)则对则对应于多边形覆盖的每一条扫描线。应于多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小将每条边的信息链入与该边最小y坐标（坐标（ymin）相对应相对应的桶处。也就是说的桶处。也就是说,若某边的较低端点为若某边的较低端点为ymin,则该边就则该边就放在相应的扫描线桶中。放在相应的扫描线桶中。2022-8-854(3)(3)每条边的数据形成一个结点每条边的数据形成一个结点,内容包括：该扫描线与该边内容包括：该扫描线与该边的初始交点的初始交点x(即较低端点的即较低

26、端点的x值值)、1/k、该边的最大该边的最大y值值ymax。有效边表的结点存放对应边的有关信息：有效边表的结点存放对应边的有关信息：(4)同一桶中若干条边按同一桶中若干条边按x|ymin由小到大排序，若由小到大排序，若x|ymax 相等，相等，则按照则按照1/k由小到大排序。由小到大排序。x|ymin ymax 1/k NEXT2022-8-8551234567891011123-1/3353/485-1/2891/21122/5712-1795桶p3p2p3p4p5p4p5p6p2p1p0p1p0p6x|yminymax 1/k next(c)边表6多边形及其有效边表和边表xy213 4 5

27、 6 7 8 9111234567891011121012p1p3p4p5(a)多边形P0P1P2P3P4P5P6P0p2p0p62022-8-856xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a)多边形P0P1P2P3P4P5P6P0p2p0p61.4 12 0.47 12 -17 9 511.5 9 0.5 y=8 的有效边表 有效有效边表边表（Active Edge Table,AET）的构造的构造：2.5 12 0.4 7 12 -1 y=11的有效边表 2022-8-857解决顶点交点计为解决顶点交点计为1 1时的情形时的情形：图5-

28、28 将多边形的某些边缩短以分离那些应计为1个交点的顶点（a)原图（b)缩短ymax的边（c)缩短ymin的边扫描线y扫描线y+1扫描线y-12022-8-858算法步骤算法步骤：(1)(1)初始化：构造边表，初始化：构造边表，AET表置空；表置空；(2)将第一个不空的将第一个不空的ET表中的边与表中的边与AET表合并；表合并；(3)由由AET表中取出交点对进行填充。填充之后删除表中取出交点对进行填充。填充之后删除y=ymax的边；的边；(4)yi+1=yi+1,根据根据xi+1=xi+1/m计算并修改计算并修改AET表，同时合表，同时合并并ET表中表中y=yi+1桶中的边，按次序插入到桶中的

29、边，按次序插入到AET表中，表中，形成新的形成新的AET表；表；(5)AET表不为空则转表不为空则转(3)，否则结束。，否则结束。2022-8-8595.4.3 5.4.3 区域填充 区域是指已经表示成点阵形式的填充图形区域是指已经表示成点阵形式的填充图形,它是像素集合。它是像素集合。44p44(b)p的8-邻接点8 8 888p88 8(a)p的4-邻接点图5-33 邻接点的定义区域表示可用边界表示区域表示可用边界表示法和内点表示法。法和内点表示法。4-4-邻接点邻接点和8-8-邻接点，邻接点，4-4-连通区域连通区域和8-8-连通区域。连通区域。2022-8-860 边界表示法边界表示法

30、把位于给定区域边界上的象素一一列举把位于给定区域边界上的象素一一列举出来的方法，可采用边界填充算法（出来的方法，可采用边界填充算法（Boundary-fill Algorithm）填充填充。内点表示法内点表示法 枚举出给定区域内所有象素的表示方法，枚举出给定区域内所有象素的表示方法，可采用泛填充算法（可采用泛填充算法（Flood-fill Algorithm）图5-32 区域的边界表示和内点表示(a)以边界表示的4-连通区域(b)以内点表示的4-连通区域(c)以边界表示的8-连通区域(d)以内点表示的8-连通区域2022-8-8621.1.边界填充算法边界填充算法 输入种子点坐标输入种子点坐标

31、(x,y)x,y)、填充色和边界颜色。填充色和边界颜色。4-4-连通边界填充算法连通边界填充算法 用栈结构实现用栈结构实现,步骤为：步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：种子象素入栈；当栈非空时重复执行如下三步操作：(1)(1)栈顶象素出栈；栈顶象素出栈；(2)(2)将出栈象素置成填充色；将出栈象素置成填充色；(3)(3)检查出栈象素的检查出栈象素的4-4-邻接点，若其中某个象素点不邻接点，若其中某个象素点不是边界色且未置成多边形色，则把它入栈。是边界色且未置成多边形色，则把它入栈。2022-8-8638-8-连通边界填充算法连通边界填充算法 用栈结构实现，步骤为：用栈结构实现

32、，步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：种子象素入栈；当栈非空时重复执行如下三步操作：(1)(1)栈顶象素出栈；栈顶象素出栈；(2)(2)将出栈象素置成填充色；将出栈象素置成填充色；(3)(3)检查出栈象素的检查出栈象素的8-8-邻接点，若其中某个象素点不是邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。边界色且未置成多边形色，则把该象素入栈。2022-8-864 特点特点：可以用于填充带有内孔的平面区域，但把太可以用于填充带有内孔的平面区域，但把太多的象素压入堆栈多的象素压入堆栈 改进改进：通过沿扫描线填充水平象素段，来代替处理：通过沿扫描线填充水平象素段

33、，来代替处理4-4-邻接点和邻接点和8-8-邻接点。邻接点。2022-8-865沿扫描线填充象素沿扫描线填充象素段的段的4 4-连通边界填连通边界填充算法充算法:(P131 图图5-34)2022-8-8662022-8-867 种子象素入栈；当栈非空时作如下三步操作：种子象素入栈；当栈非空时作如下三步操作：(1)(1)栈顶象素出栈；栈顶象素出栈；(2)(2)填充出栈象素所在扫描行的连续象素段填充出栈象素所在扫描行的连续象素段,直到遇直到遇到边界象素为止；到边界象素为止；(3)(3)在区间中检查与当前扫描线相邻的上下两条扫描在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素线的有关象素,若

34、存在非边界、未填充的象素，则若存在非边界、未填充的象素，则把每一区间的最右象素取作种子象素入栈。把每一区间的最右象素取作种子象素入栈。2022-8-8682.2.泛填充算法 用于区域重新着色。用于区域重新着色。算法的输入包括算法的输入包括:种子点坐标种子点坐标(x,y)x,y)，填充色和填充色和内部点的颜色。内部点的颜色。算法原理：算法从指定的种子算法原理：算法从指定的种子(x,y)x,y)开始，用指开始，用指定的填充颜色赋给所有当前为给定内部颜色的定的填充颜色赋给所有当前为给定内部颜色的象素点。也分为：象素点。也分为：4 4-连通泛填充算法和连通泛填充算法和8 8-连通连通泛填充算法泛填充算

35、法2022-8-869 4-4-连通连通(8-(8-连通连通)泛填充算法步骤泛填充算法步骤如下：种子象素入栈；当栈非空时重复执行如下三步操作：种子象素入栈；当栈非空时重复执行如下三步操作：(1)(1)栈顶象素出栈；栈顶象素出栈；(2)(2)将出栈象素置成填充色；将出栈象素置成填充色；(3)(3)检查出栈象素的检查出栈象素的4-4-邻接点邻接点(8-(8-邻接点邻接点),),若其中某个若其中某个象素点不是给定内部点的颜色且未置成新的填充色，象素点不是给定内部点的颜色且未置成新的填充色，则把该象素入栈。则把该象素入栈。2022-8-8705.5 5.5 字符处理字符处理 ASCI码：码：“美国信息

36、交换用标准代码集美国信息交换用标准代码集”(American Standard Code for Information Interchange)。国标码：国标码：“中华人民共和国国家标准信息交换编码中华人民共和国国家标准信息交换编码”，简称为国标码，代号简称为国标码，代号GB231280。字库：字库中储存了每个字符的字符编码和图形信息。字库：字库中储存了每个字符的字符编码和图形信息。矢量字库矢量字库和点阵字库。点阵字库。数字、字母和汉字等符号用于图形标注。数字、字母和汉字等符号用于图形标注。5.5.1 5.5.1 点阵字符 在点阵表示中，每个字在点阵表示中，每个字符由一个点阵位图来表符由一个

37、点阵位图来表示，有示，有7 7x9x9、9x169x16等多种。等多种。显示时：形成字符的象显示时：形成字符的象素图案。素图案。图5-36 字符A的点阵表示11111111111111111111 1111111111 1 11111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000(a)字符A的点阵位图(a)字符A的象素图案 定义和显

38、示直接、简单，定义和显示直接、简单，但所占存储空间大，需但所占存储空间大，需采用压缩技术。采用压缩技术。2022-8-8725.5.2 5.5.2 矢量字符 矢量字符采用直线和曲线段来描述矢量字符采用直线和曲线段来描述字符形状字符形状,矢量字符库中记录的是笔矢量字符库中记录的是笔划信息。采用轮廓字形法来表示划信息。采用轮廓字形法来表示,如如右图所示。右图所示。显示时显示时,解释字符的每个笔划信息。解释字符的每个笔划信息。2022-8-8735.6 5.6 属性处理属性处理图素和图段的外观图素和图段的外观,由其属性来控制。使用当前属性由其属性来控制。使用当前属性值进行显示输出。值进行显示输出。5

39、.6.1 5.6.1 线型和线宽1.1.线型处理线型处理 实心段和中间空白段的长度（象素数目）可用象素模实心段和中间空白段的长度（象素数目）可用象素模板板(pixel mask)来指定。来指定。存在问题：如何保持任何方向的划线长度近似地相等存在问题：如何保持任何方向的划线长度近似地相等2022-8-874 解决办法：解决办法：可根据线的可根据线的斜率来调整实心段和中间斜率来调整实心段和中间空白段的象素数目空白段的象素数目。xy213 4 5 6 7 8 9111234567891011121012a a图5-38 相同数目象素显示的不等长划线b b2022-8-8752.2.线刷子和方刷子处理

40、线宽线刷子和方刷子处理线宽 线刷子：垂直刷子、水平刷子线刷子：垂直刷子、水平刷子图5-39 线刷子(a)(b)2022-8-876线刷子的优缺点：线刷子的优缺点：实现简单、效率高。实现简单、效率高。斜线与水平斜线与水平(或垂直或垂直)线不一样粗。线不一样粗。当线宽为偶数个象素时，线的中心将偏移半个象素。当线宽为偶数个象素时，线的中心将偏移半个象素。利用线刷子生成线的始末端总是水平或垂直的，看利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。故需起来不太自然。故需添加添加“线帽（线帽（line cap）”图5-40 线“帽子”(a)方帽(c)圆帽(b)突方帽2022-8-877图5-41

41、 线刷子产生的缺口当比较接近水平的线与比较接当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角近垂直的线汇合时，汇合处外角将有缺口。可采用将有缺口。可采用斜角连接斜角连接（miter join）、）、圆连接（圆连接（round join）、）、斜切连接（斜切连接（bevel join）。）。图5-42 线刷子产生的缺口(a)斜角连接(b)圆连接(c)斜切连接2022-8-878方刷子方刷子 方刷子绘制的线条（斜线）比用线方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些刷子所绘制的线条要粗一些 方刷子绘制的斜线与水平（或垂直方刷子绘制的斜线与水平（或垂直）线不一样粗）线不一样粗 方刷子

42、绘制的线条自然地带有一个方刷子绘制的线条自然地带有一个“方线帽方线帽”图5-43 方刷子2022-8-8794.4.曲线的线型和线宽 线型：可采用象素模板的方法。线型：可采用象素模板的方法。线宽：线宽：可采用线刷子、可采用线刷子、方刷子、方刷子、圆弧刷子和区域填充方法。圆弧刷子和区域填充方法。图5-45 利用模板110进行圆的线型处理3.3.处理线宽的其它方法 包括区域填充和改变刷子形状等。包括区域填充和改变刷子形状等。5.6.2 5.6.2 字符的属性 常用的属性有：常用的属性有：字体字体、字形字形、字号、字间距、行间距等等字号、字间距、行间距等等。一般字体确定风格一般字体确定风格,字形确定

43、字形确定外观外观,字号确定尺寸字号确定尺寸。字符的常用属性参数如图字符的常用属性参数如图5-465-46所示。所示。字符高字宽A底高基线字高顶高字符宽原点图5-46 字符的常用属性及其含义帽线2022-8-881字符串的属性字符串的属性 文本高度、文本宽度（扩展文本高度、文本宽度（扩展/压缩因子）、字符方压缩因子）、字符方向、文本路径方向、对齐方式（左对齐，中心对齐，向、文本路径方向、对齐方式（左对齐，中心对齐，或右对齐，指定起始、终止点）、文本字体、字符或右对齐，指定起始、终止点）、文本字体、字符的颜色属性等。的颜色属性等。反绘（从右到左）、倒绘（旋转反绘（从右到左）、倒绘（旋转180180

44、）、写方式）、写方式（替换或与方式）等。（替换或与方式）等。5.6.3 5.6.3 区域填充属性区域填充属性 区域填充属性选择包括区域填充属性选择包括颜色颜色、图案图案和和透明度透明度。0010 10 111(a)图案模板位图(b)用该模板进行填充图5-47 利用图案模板进行三角形的填充模板图案2022-8-8835.7 5.7 反走样反走样 用离散量表示连续量引起的失真，用离散量表示连续量引起的失真，就叫做走样就叫做走样(Liasing)。走样现象：走样现象：非水平、非垂直的直线扫描转换的非水平、非垂直的直线扫描转换的结果出现或多或少锯齿。结果出现或多或少锯齿。光栅图形产生的阶梯形。光栅图形

45、产生的阶梯形。图形中包含的微小物体在静态图形图形中包含的微小物体在静态图形中容易被丢弃或忽略中容易被丢弃或忽略,在动画序列在动画序列中时隐时现，产生闪烁。中时隐时现，产生闪烁。图5-48 绘制直线时的反走样现象2022-8-884图5-49 丢失细节(a)需显示的矩形(b)显示结果图5-50 运动图形的闪烁(a)显示(b)不显示(c)显示(d)不显示2022-8-885 反走样：反走样：用于减少或消除这种效果的技术，称为反走样用于减少或消除这种效果的技术，称为反走样（antialiasingantialiasing）。一种简单方法：一种简单方法：以较高分辨率显示对象以较高分辨率显示对象。图5-

46、51 分辨率提高一倍,阶梯状程度减小一倍过取样（过取样（supersamplingsupersampling）或后滤波或后滤波区域取样（区域取样（area samplingarea sampling）或前滤波或前滤波2022-8-8865.7.1 过取样过取样 简单过取样简单过取样 用较高分辨率进行计算，在用较高分辨率进行计算，在x和和y方向都把分方向都把分辨率提高一倍，使每个象素都对应辨率提高一倍，使每个象素都对应4个子象素。扫描转换个子象素。扫描转换得到各个子象素的颜色亮度，对得到各个子象素的颜色亮度，对4个子象素的颜色值平均，个子象素的颜色值平均，得较低分辨率下对应象素的颜色值。故得得较

47、低分辨率下对应象素的颜色值。故得5个亮度等级，个亮度等级，1、7象素亮度级为象素亮度级为1，26象素亮度级为象素亮度级为2。图5-52 简单的过取样方式12346752022-8-8875.7.2 5.7.2 简单的区域取样简单的区域取样图5-55 有宽度的直线段1 23 45 6 将每个象素亮度设置成与线条将每个象素亮度设置成与线条重叠区域面积成正比，象素重叠区域面积成正比，象素1的的亮度设置为最大亮度的亮度设置为最大亮度的40，象素象素2亮度约为亮度约为60，象素，象素3亮亮度约为度约为90。2022-8-8882022-8-889 思考题思考题 1、2、4、6、11、16、19、27 5 511.11.若采用改进的有效边表算法对图若采用改进的有效边表算法对图5 559(59(P145)P145)多边形进行转换，试写出该多边形的边表多边形进行转换，试写出该多边形的边表ETET和和y=4y=4的有的有效边表效边表AETAET。附加题：附加题：1.1.取步长为取步长为1 1，用，用BresenhamBresenham算法实现从算法实现从(0,0)(0,0)到到(8,12)(8,12)的画线，并写出每步到达点的坐标。的画线，并写出每步到达点的坐标。