当直线段与某象素有交时课件.ppt

1、1l 任何影响图元显示方法的参数一般称为属性参数。任何影响图元显示方法的参数一般称为属性参数。l 将属性选择加入图形软件包的方法：将属性选择加入图形软件包的方法：为每个输出图元功能扩充相关的参数表。为每个输出图元功能扩充相关的参数表。提供一张系统的当前属性值表。提供一张系统的当前属性值表。l 维护属性和其他参数当前值表的图形系统称为状态系统。维护属性和其他参数当前值表的图形系统称为状态系统。l 输出图元的属性和其他参数当前值表的图形系统称为状输出图元的属性和其他参数当前值表的图形系统称为状态系统。态系统。2v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v 4.3 线的属性线的

2、属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样3l 颜色是所有图元的一个基本颜色是所有图元的一个基本属性属性.用户可以选择多种颜色用户可以选择多种颜色,依赖于特定系统的能力和设计依赖于特定系统的能力和设计目标目标.颜色可用数值指定颜色可用数值指定,也可也可以从菜单或显示的标尺中选择以从菜单或显示的标尺中选择.4v

3、 4.1.1 RGB颜色分量颜色分量 在彩色光栅系统中在彩色光栅系统中,可选用的颜色数量依赖于帧缓存可选用的颜色数量依赖于帧缓存 中提供的存储容量。颜色信息有两种存储方法中提供的存储容量。颜色信息有两种存储方法:l直接存储直接存储RGB编码。编码。l存储颜色码。存储颜色码。v 4.1.2 颜色表：提供了颜色表：提供了“合理合理”数量的可同时显示的数量的可同时显示的颜色而不要求大容量的帧缓存。颜色而不要求大容量的帧缓存。670255RGB红绿兰0 x0y帧缓冲器被显示的像素67N-1M-1像素值10010001000011查找表显示器101010 010101100100100100101010

4、0101015v 4.1.3 灰度灰度l当当RGB函数中指定相同量的红色、绿色和蓝色时函数中指定相同量的红色、绿色和蓝色时,结果是某种程度的灰色。结果是某种程度的灰色。v 4.1.4 其他颜色参数其他颜色参数lCMY和和CMYK模型针对彩色打印机。模型针对彩色打印机。lHSI彩色模型更符合人描述和解释颜色的方式。彩色模型更符合人描述和解释颜色的方式。6v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v 4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描

5、线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样v 4.12 OpenGL学习学习(2)7l 颜颜 色色 用用RGB值或指向颜色表的索引值设定。值或指向颜色表的索引值设定。l 大大 小小 像素的整数倍。像素的整数倍。8v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v 4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v

6、4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样v 4.12 OpenGL学习学习(2)9l 线宽线宽 重复像素法重复像素法-优点：优点：实现简单实现简单用重复像素法绘制线段用重复像素法绘制线段 用重复像素法绘制圆弧用重复像素法绘制圆弧 10l 线宽线宽缺点：缺点：线段两端要么为水平的，要么是竖直的。线段两端要么为水平的，要么是竖直的。折线顶点处有缺口折线顶点处有缺口11图元的宽度不均匀图元的宽度不均匀产生宽度为偶数像素的图元效果不好产生宽度为偶数像素的图元效果不好(a)(a)水

7、平线段水平线段 (b)45(b)45线段线段 l 线宽线宽12l 线型线型实线长划线短划线点划线 四种常用的线型 131 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 线型可以用线型可以用0、1序列来表示，存放在数组中。序列来表示，存放在数组中。例：可以用包含例：可以用包含8个元素的整数数组来表示线型个元素的整数数组来表示线型（11111111表示实线，表示实线，11110000表示长划线，表示长划线，11001100表示短划线），此时线型以表示短划线），此时线型以8为周期重复。为周期重复。绘制绘制 if(线型线型i%8)write_pixel(x,y)；l 线型线型14

8、l 画笔和画刷画笔和画刷15用移动画笔法绘制线段用移动画笔法绘制线段 l 画笔和画刷画笔和画刷16用移动画笔法绘制圆弧用移动画笔法绘制圆弧 l 画笔和画刷画笔和画刷17(a)水平线段 (b)45线段 l 画笔和画刷画笔和画刷18l区域填充区域填充 优点优点生成的图形质量高生成的图形质量高缺点缺点 计算量大计算量大 有些图形的等距线难以获得有些图形的等距线难以获得 可以根据线条的宽度，计算出线可以根据线条的宽度，计算出线条的外轮廓，再用区域填充的方法，条的外轮廓，再用区域填充的方法，产生具有一定线宽的线条。产生具有一定线宽的线条。19l区域填充区域填充 为了改善线条端点为了改善线条端点处的形状，

9、可以在线处的形状，可以在线条端点处加上线帽条端点处加上线帽（line capline cap）。）。粗线段的连接处需粗线段的连接处需要特别考虑要特别考虑 三种常用的线帽 三种常用的粗线段的连接方式 20v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v 4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v

10、4.11 反走样反走样v 4.12 OpenGL学习学习(2)21l区域填充区域填充 对于封闭曲线来说，对于封闭曲线来说，可以先生成两条距离为线可以先生成两条距离为线宽的曲线，再填充两条曲宽的曲线，再填充两条曲线之间的区域。线之间的区域。22v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v 4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填

11、充方法v 4.10 字符属性字符属性v 4.11 反走样反走样v 4.12 OpenGL学习学习(2)23v 4.5.1 填充模式填充模式v 4.5.2 颜色调和填充区域颜色调和填充区域24l 填充方法填充方法l 基本问题基本问题25l 填充方法填充方法 均匀着色方法：将图元内部像素置成同一颜色均匀着色方法：将图元内部像素置成同一颜色位图不透明：若像素对应的位图单元为位图不透明：若像素对应的位图单元为1 1，则以，则以前景色前景色显示该像素；若为显示该像素；若为0 0，则以背景色显示该，则以背景色显示该像素；像素；位图透明：若像素对应的位图单元为位图透明：若像素对应的位图单元为1 1，则以，则

12、以前前景色景色显示该像素；显示该像素；若为若为0 0，则不做任何处理。，则不做任何处理。像素图填充：以像素对应的像素图单元的颜色像素图填充：以像素对应的像素图单元的颜色值显示该像素。值显示该像素。26l 建立区域与图像间的对应关系建立区域与图像间的对应关系2728l 以数组形式存储在处理器内存里的二维图像称为纹理。以数组形式存储在处理器内存里的二维图像称为纹理。l 此时数组元素称为纹素此时数组元素称为纹素(texel)，可以由应用程序生成，可以由应用程序生成，也可以将照片扫描输入。也可以将照片扫描输入。l 把离散数组看成一个连续的二维矩形区域纹理图案把离散数组看成一个连续的二维矩形区域纹理图案

13、T(s,t)，独立变量，独立变量s和和t是纹理坐标一般把纹理坐标缩放到是纹理坐标一般把纹理坐标缩放到0,1区间。区间。29l 把图像映射到曲面上是一个非常复杂的任务。把图像映射到曲面上是一个非常复杂的任务。30l 涉及到的坐标系涉及到的坐标系 参数坐标系可以用来建立曲线、曲面。参数坐标系可以用来建立曲线、曲面。纹理坐标系用来识别要被映射的图像上的点。纹理坐标系用来识别要被映射的图像上的点。世界坐标系从概念上说，就是映射发生的地方。世界坐标系从概念上说，就是映射发生的地方。屏幕坐标系最终图像生成的地方。屏幕坐标系最终图像生成的地方。31l 映射函数映射函数 考虑从纹理坐标到曲面上一点的映射。考虑

14、从纹理坐标到曲面上一点的映射。直观地看，需要如下函数直观地看，需要如下函数 x=x(s,t)y=y(s,t)z=z(s,t)w=w(s,t)实际采用的是间接方法。实际采用的是间接方法。32l 逆映射逆映射 给定对象上的一个点，我们想知道它对应给定对象上的一个点，我们想知道它对应于纹理中的哪个点。于纹理中的哪个点。此时需要如下形式的映射此时需要如下形式的映射s=s(x,y,z,w)t=t(x,y,z,w)这样的函数一般是很难求出来的。这样的函数一般是很难求出来的。33l 实际困难实际困难 假设要计算中心在假设要计算中心在(x(xs s,y,ys s)的一个矩形像素的颜色。的一个矩形像素的颜色。中

15、心点对应于对象上的点中心点对应于对象上的点(x,y,z(x,y,z)。如果对象是弯曲的，那么矩形像素的原像是一个曲如果对象是弯曲的，那么矩形像素的原像是一个曲边四边形。边四边形。这个曲边四边形在纹理上的原像才是对当前矩形像这个曲边四边形在纹理上的原像才是对当前矩形像素的颜色有贡献的纹理元素。素的颜色有贡献的纹理元素。34l 纹理坐标到屏幕坐标的映射纹理坐标到屏幕坐标的映射xs=xs(s,t)ys=ys(s,t)(xs,ys)表示颜色缓存中的某个位置。表示颜色缓存中的某个位置。35v 4.5.1 4.5.1 填充模式填充模式v 4.5.2 4.5.2 颜色调和填充区域颜色调和填充区域36l 线性

16、软填充算法是这类填充的一个例子，该算法在将前景线性软填充算法是这类填充的一个例子，该算法在将前景色色F与单一背景色与单一背景色B(FB)合并后绘制的区域上重新绘制。合并后绘制的区域上重新绘制。l 假如假如F和和B的值为已知，那么通过检测帧缓冲器中当前的的值为已知，那么通过检测帧缓冲器中当前的颜色内容，就可确定这些颜色原来是怎样组合的。颜色内容，就可确定这些颜色原来是怎样组合的。l 区域内将要重新填充酌每个像素的当前颜色区域内将要重新填充酌每个像素的当前颜色P，则是，则是F和和B的线性组合：的线性组合：PtF十十(1-t)B37v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v

17、4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样v 4.12 OpenGL学习学习(2)38v4.6.1 扫描线算法扫描线算法v4.6.2 有序边表算法有序边表算法39 l 边的连贯性边的连贯性：某条边与当前扫描线相交，也可能：某条边与当前扫描线相交，也可能 与下一条扫描线相交；与下一条扫描线相

18、交；l 扫描线的连贯性扫描线的连贯性：当前扫描线与各边的交点顺序：当前扫描线与各边的交点顺序 与下一条扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序 可能相同或类似；可能相同或类似；l 区间连贯性区间连贯性：同一区间上的像素取同一颜色属性：同一区间上的像素取同一颜色属性 40l 扫描线算法扫描线算法目标：利用相邻像素之间的连贯性，提高算法效率目标：利用相邻像素之间的连贯性，提高算法效率处理对象：非自交多边形处理对象：非自交多边形 （边与边之间除了顶点（边与边之间除了顶点外无其它交点）外无其它交点）41v4.6.1 扫描线算法扫描线算法v4.6.2 有序边表算法有序边表算法42l基本原理基

19、本原理 一条扫描线与多边形的边有偶数个交点一条扫描线与多边形的边有偶数个交点l步骤步骤(对于每一条扫描线对于每一条扫描线):):求交点求交点 交点排序交点排序 交点配对，填充区段交点配对，填充区段43l边的连贯性边的连贯性 第一类交点：新出现的边与扫描线的交点第一类交点：新出现的边与扫描线的交点 第二类交点：位于同一条边上的后继交点第二类交点：位于同一条边上的后继交点44l交点的取整规则交点的取整规则要求：使生成的像素全部位于多边形之内要求：使生成的像素全部位于多边形之内用于线画图元生成的四舍五入原则导致部分像素位用于线画图元生成的四舍五入原则导致部分像素位于多边形之外，从而不可用于多边形之外

20、，从而不可用假定非水平边与扫描线假定非水平边与扫描线y=ey=e相交，交点的横坐标为相交，交点的横坐标为x.x.45l 规则规则1 X为小数，即交点落于扫描线上两个相邻像素之间为小数，即交点落于扫描线上两个相邻像素之间(a)交点位于左边之上，向右取整交点位于左边之上，向右取整(b)交点位于右边之上，向左取整交点位于右边之上，向左取整46l 规则规则2 边界上象素的取舍问题，避免填充扩大化。边界上象素的取舍问题，避免填充扩大化。解决方法：解决方法：边界象素：规定落在右边界的象素不予填充。具体实现边界象素：规定落在右边界的象素不予填充。具体实现时，只要对扫描线与多边形的相交区间左闭右开。时，只要对

21、扫描线与多边形的相交区间左闭右开。47 活性边活性边：与当前扫描线相交的边。按交点：与当前扫描线相交的边。按交点x的增量顺序存的增量顺序存放在一个链表中；该链表称作放在一个链表中；该链表称作活性边表活性边表（AEL)。l 算法所涉及的数据结构：算法所涉及的数据结构：AEL 的结点信息（的结点信息（p75）：）：Ymax:所交边的最高扫描线号所交边的最高扫描线号X：当前扫描线与边的交点的：当前扫描线与边的交点的 x坐标坐标X：边的斜率的倒数：边的斜率的倒数Nextage:下一条边的指针下一条边的指针typedef struct int ymax;float x,deltax;Edge*nextE

22、dge;Edge;48 边的分类表边的分类表（ET）按照边的下端点按照边的下端点y坐标对非水平边进行分类的指针坐标对非水平边进行分类的指针数组数组,下端点下端点y坐标值等于坐标值等于i的边属于第的边属于第i类。类。typedef struct int ymax;float x,deltax;Edge*nextEdge;Edge;边的分类表的作用是避免盲目求交。边的分类表的作用是避免盲目求交。当处理一条扫描线时，为了求出它与多当处理一条扫描线时，为了求出它与多边形边的所有交点，必须将它与所有的边形边的所有交点，必须将它与所有的边进行求交测试。而实际上只有某几条边进行求交测试。而实际上只有某几条边

23、与该扫描线有交点。边的分类表正是边与该扫描线有交点。边的分类表正是用来排除不必要的求求交测试的。用来排除不必要的求求交测试的。49l 建立建立ET；l 将扫描线纵坐标将扫描线纵坐标y y的初值置为的初值置为ET中非空元素的最小序号，如在上图中，中非空元素的最小序号，如在上图中，y=1；l 置置AEL为空；为空；l 执行下列步骤直至执行下列步骤直至ET和和AEL都为空都为空 如如ET中的第中的第y类非空，则将其中的所有边取出并插入类非空，则将其中的所有边取出并插入AEL中；中；如果有新边插入如果有新边插入AEL，则对，则对AEL中各边排序；中各边排序；对对AEL中的边两两配对，（中的边两两配对，

24、（1和和2为一对，为一对，3和和4为一对，为一对，），将每），将每对边中对边中x坐标按规则取整，获得有效的填充区段，再填充坐标按规则取整，获得有效的填充区段，再填充 将当前扫描线纵坐标将当前扫描线纵坐标y值递值值递值1；将将AEL中满足中满足y=ymax边删去（边删去（！每条边被看作下闭上开的！每条边被看作下闭上开的）；）；对对AEL中剩下的每一条边的中剩下的每一条边的x递增递增deltax，即，即x=x+deltax50v4.6.1 扫描线算法扫描线算法v4.6.2 有序边表算法有序边表算法51v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v 4.3 线的属性线的属性v 4

25、.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样52v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v 4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区

26、域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样53l 扇形区域的描述扇形区域的描述:l 原理：同多边形原理：同多边形l 问题：如何确定扫描线与直线段和圆弧段的相交顺序问题：如何确定扫描线与直线段和圆弧段的相交顺序l 方法：分类方法：分类54l 假设假设 点落在第一象限点落在第一象限 ,扇形区域的图元生成扇形区域的图元生成 分分四种情况四种情况 在第一象限在第一象限 p12p55 落在第二象限，此时又分为两种情况落在第二象限，此时又分为两种情况 -当当 时时-当当 时时2pyy1221yy 56

27、落在第三象限落在第三象限 落在第四象限落在第四象限 2p2p57l 遗留问题：当遗留问题：当 落在其它区域时落在其它区域时?l 还有什么方法还有什么方法?p158v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v 4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样59l 内部定义区

28、域，是指区域内部的所有像素都具有相同的颜色内部定义区域，是指区域内部的所有像素都具有相同的颜色（old_color），），而区域边界上的像素具有不是而区域边界上的像素具有不是old_color的任的任意其它颜色。意其它颜色。l 填充内部定义区域，将该区域中的所有像素都设置为填充颜填充内部定义区域，将该区域中的所有像素都设置为填充颜色色（fill_color）的算法，称为洪水填充算法的算法，称为洪水填充算法（flood-fill algorithm）。）。l 边界定义区域，是指区域边界上的所有像素都具有相同的颜边界定义区域，是指区域边界上的所有像素都具有相同的颜色色（boundary_color

29、），），而区域内部的像素具有不是而区域内部的像素具有不是boundary_color的任意其它颜色。的任意其它颜色。l 填充边界定义区域，将该区域中的所有像素都设置为填充颜填充边界定义区域，将该区域中的所有像素都设置为填充颜色的算法，称为边界填充算法色的算法，称为边界填充算法（boundary-fill algorithm）。）。60 (a)四连通内部定义区域 (b)八连通内部定义区域内部定义区域示意图内部定义区域示意图 (a)四连通边界定义区域 (b)八连通边界定义区域边界定义区域示意图边界定义区域示意图 61v 4.9.1 简单递归简单递归v 4.9.2 扫描线算法扫描线算法62l 区域内

30、部的所有像素都具有颜色区域内部的所有像素都具有颜色old_color，从区域，从区域内部某一像素内部某一像素（x,y）开始对区域进行填充（该像素称为开始对区域进行填充（该像素称为种子点），将区域内部的所有像素都设置为填充颜色种子点），将区域内部的所有像素都设置为填充颜色fill_color。l 基本方法是：测试像素基本方法是：测试像素（x,y）是否在区域内尚未被是否在区域内尚未被填充的部分，即测试像素填充的部分，即测试像素（x,y）的颜色，若该像素的颜的颜色，若该像素的颜色等于色等于old_color且不等于且不等于fill_color，则设置该像素的，则设置该像素的颜色为颜色为fill_co

31、lor，并对与该像素相邻的像素作同样处理，并对与该像素相邻的像素作同样处理（递归调用）；否则说明该像素在区域外或已被填充过，（递归调用）；否则说明该像素在区域外或已被填充过，不再进行处理。不再进行处理。63void flood_fill_4(int x,y,old_color,fill_color)int current;current=read_pixel(x,y);if(current=old_color¤t!=fill_color)write_pixel(x,y,fill_color);flood_fill_4(x,y+1,old_color,fill_color);/*上上

32、*/flood_fill_4(x,y-1,old_color,fill_color);/*下下*/flood_fill_4(x-1,y,old_color,fill_color);/*左左*/flood_fill_4(x+1,y,old_color,fill_color);/*右右*/l 适用于四连通内部定义区域的边界填充算法为：适用于四连通内部定义区域的边界填充算法为：64l 适用于四连通边界定义区域的边界填充算法为：适用于四连通边界定义区域的边界填充算法为：void boundary_fill_4(int x,y,boundary_color,fill_color)int current;

33、current=read_pixel(x,y);if(current!=boundary_color¤t!=fill_color)write_pixel(x,y,fill_color);boundary_fill_4(x,y+1,boundary_color,fill_color);/*上上*/boundary_fill_4(x,y-1,boundary_color,fill_color);/*下下*/boundary_fill_4(x-1,y,boundary_color,fill_color);/*左左*/boundary_fill_4(x+1,y,boundary_color

34、,fill_color);/*右右*/65 boundary_color 未被填充种子点 fill_color (a)填充前 (b)填充后l 当区域内部某些像素的颜色为当区域内部某些像素的颜色为fill_color时，上述边界时，上述边界填充算法可能无法正确工作。填充算法可能无法正确工作。l 解决方法解决方法:首先建立一个与帧缓冲区对应的临时缓冲区，首先建立一个与帧缓冲区对应的临时缓冲区，帧缓冲区中颜色为帧缓冲区中颜色为boundary_color的像素在临时缓冲区的像素在临时缓冲区中用中用0来表示，颜色不为来表示，颜色不为boundary_color的像素在临时缓的像素在临时缓冲区中用冲区中

35、用1来表示，再用上述算法在临时缓冲区中用来表示，再用上述算法在临时缓冲区中用2进进行填充，最后在帧缓冲区中将对应于临时缓冲区中为行填充，最后在帧缓冲区中将对应于临时缓冲区中为2的的像素填充为像素填充为fill_color。66v 4.9.1 简单递归简单递归v 4.9.2 扫描线算法扫描线算法67l 种子点（种子点（x,y）入栈。）入栈。l 栈顶元素（栈顶元素（x,y）出栈作为种子点。）出栈作为种子点。l 从种子点（从种子点（x,y）开始沿着扫描线向左右两个方向逐个）开始沿着扫描线向左右两个方向逐个 像素进行填充，直到到达边界像素为止。像素进行填充，直到到达边界像素为止。l 将上述填充区段的左

36、右端点的横坐标分别记为将上述填充区段的左右端点的横坐标分别记为xleft和和 xright。l 在与当前扫描线相邻的上下两条扫描线的在与当前扫描线相邻的上下两条扫描线的xleft，xright范围内进行检查，看看是否全部为边界像素或已填充像素，范围内进行检查，看看是否全部为边界像素或已填充像素，若存在着非边界且未填充的像素，那么将该区段的最右端若存在着非边界且未填充的像素，那么将该区段的最右端像素作为种子点入栈。像素作为种子点入栈。681212131311444 456156(a)(b)(c)区域填充的扫描线算法的执行过程区域填充的扫描线算法的执行过程 6970v 4.1 颜色和查找表颜色和查

37、找表v 4.2 点的属性点的属性v 4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样71 l 表示字符形状的方法：表示字符形状的方法：位位 图：点阵表示图：点阵表示 轮廓线：用直线或曲线来描述字符的轮廓。轮廓线：用直线或曲线来描述字符的轮廓。需要采用扫描转换算法对轮廓线需要采用扫描转换算法对轮廓

38、线 内部进行填充。内部进行填充。如如True Type、PostScript。l 两种方法的比较两种方法的比较 位图表示位图表示:显示速度快显示速度快 占用大量的存储空间占用大量的存储空间 效果不能令人满意效果不能令人满意 轮轮 廓廓 线线:节省空间节省空间 扫描转换需要更长的处理时间扫描转换需要更长的处理时间72H f j底基帽顶字符高度字符体核73STRING底半顶基帽右中左STR顶帽半底基右左中LEFTALIGNMENTCENTERALIGNMENTRIGHTALIGNMENTALI GNMENTTOPALI GNMENTBOTTOM74v 4.1 颜色和查找表颜色和查找表v 4.2 点

39、的属性点的属性v 4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样75l 走样走样:用离散量用离散量(像素像素)表示连续的量表示连续的量(图形图形)而引起而引起 的失真，叫混淆或叫的失真，叫混淆或叫走样走样(aliasing)。l 光栅图形的走样现象光栅图形的走样现象:阶梯状边界；阶梯状边界；图

40、形细节失真；图形细节失真；狭小图形遗失：动画序列中时隐时现，产生闪烁。狭小图形遗失：动画序列中时隐时现，产生闪烁。76走样现象l 不光滑不光滑(阶梯状）的图形边界阶梯状）的图形边界77l 图形细节失真图形细节失真走样现象78l 狭小图形的遗失与狭小图形的遗失与l 动态图形的闪烁动态图形的闪烁走样现象79l 什么是什么是反走样反走样在图形显示过程中，用于减少或消除走样现象在图形显示过程中，用于减少或消除走样现象的方法。的方法。提高分辨率方法提高分辨率方法 非加权区域采样非加权区域采样 加权区域采样加权区域采样80l 提高分辨率的反走样方法提高分辨率的反走样方法 过采样过采样方法简单，但代价非常大

41、方法简单，但代价非常大!显示器的水平、竖直分辩率各提高一倍，则显示器显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的的点距减少一倍，帧缓存容量则增加到原来的4 4倍，而倍，而扫描转换同样大小的图元却要花扫描转换同样大小的图元却要花4 4倍时间。倍时间。81l 走样原因走样原因两点假设两点假设象素是数学上抽象的点，它的面积为象素是数学上抽象的点，它的面积为0，它的亮度由覆盖该点的图形的亮度所决定；它的亮度由覆盖该点的图形的亮度所决定；直线段是数学上抽象直线段，它的宽度为直线段是数学上抽象直线段，它的宽度为0。现实现实像素的面积不为像素的面积不为0；直线段的宽度

42、至少为直线段的宽度至少为1个像素；个像素；假设与现实的矛盾是导致走样出现的原因之一假设与现实的矛盾是导致走样出现的原因之一82l解决方法：改变直线段模型，由此产生解决方法：改变直线段模型，由此产生区域采样区域采样算法步算法步 骤：骤：将直线段看作具有一定宽度的狭长矩形；将直线段看作具有一定宽度的狭长矩形；当直线段与某象素有交时，求出两者相交区域的面积；当直线段与某象素有交时，求出两者相交区域的面积；根据相交区域的面积，确定该象素的亮度值根据相交区域的面积，确定该象素的亮度值 83l区域采样区域采样 直线段对一个像素亮度的贡献与两者相交区域的面积直线段对一个像素亮度的贡献与两者相交区域的面积 成

43、正比；成正比；当直线段和某个像素不相交时，它对该像素的亮度无当直线段和某个像素不相交时，它对该像素的亮度无 影响；影响；相同面积的相交区域对像素的亮度贡献相同，而与这相同面积的相交区域对像素的亮度贡献相同，而与这 个相交区域落在像素内什麽位置无关。个相交区域落在像素内什麽位置无关。l关键：如何计算这个面积？关键：如何计算这个面积？84l 计算相交区域的面积计算相交区域的面积l 加权区域采样加权区域采样l 保真多边形边界保真多边形边界85l求相交区域的近似面积求相交区域的近似面积 将屏幕象素分割成将屏幕象素分割成n个更小的子象素；个更小的子象素；计算中心点落在直线段内的子象素的个数，记为计算中心

44、点落在直线段内的子象素的个数，记为k，k/n为线段与象素相交区域面积的近似值为线段与象素相交区域面积的近似值 目的：简化计算目的：简化计算左图左图:n=16,k=3近似面积近似面积=3/1686l加权区域采样加权区域采样 改进改进非加权区域采样方法非加权区域采样方法 相交区域对象素亮度的贡献相交区域对象素亮度的贡献依赖于该区域与象素中心的距离依赖于该区域与象素中心的距离87l 反走样技术实例反走样技术实例 立方体滤波器立方体滤波器 圆锥体滤波器圆锥体滤波器 保真多边形边界保真多边形边界881.立方体滤波器892.圆锥体滤波器90 xixi-0.5xi+0.5xi+1yi-0.5yiyi+0.5

45、yi+1PLHy=k(xi-0.5)+by=k(xi+0.5)+by=k(xi+1)+b3.3.保真多边形边界保真多边形边界 -计算相交区域的面积像素实际显示的灰度值像素实际显示的灰度值 =相交面积相交面积*该像素的最大灰度值该像素的最大灰度值91v 4.1 颜色和查找表颜色和查找表v 4.2 点的属性点的属性v 4.3 线的属性线的属性v 4.4 曲线属性曲线属性v 4.5 填充区属性填充区属性v 4.6 通用扫描线填充算法通用扫描线填充算法v 4.7 凸多边形的扫描线填充凸多边形的扫描线填充v 4.8 曲线边界区域扫描线填充曲线边界区域扫描线填充v 4.9 不规则边界区域填充方法不规则边界区域填充方法v 4.10 字符属性字符属性v 4.11 反走样反走样92欢迎交流！欢迎交流！更多信息请参见更多信息请参见http:/