第四章多边形的扫描转换和区域填充ppt课件.ppt

《第四章多边形的扫描转换和区域填充ppt课件.ppt》由会员分享，可在线阅读，更多相关《第四章多边形的扫描转换和区域填充ppt课件.ppt（105页珍藏版）》请在三一办公上搜索。

1、,第4章 多边形的扫描转换和区域填充,扫描转换和区域填充这个问题是怎样在离散的像素集上表示一个连续的二维图形。,多边形有两种重要的表示方法：顶点表示和点阵表示。,前言,前言,顶点表示用多边形的顶点序列来刻画多边形特点表示方法直观，几何意义强，占内存空间少，但没明确指明哪些像素在多边形内，不能直接用于面着色。,前言,点阵表示用位于多边形内部的像素集合来刻画多边形特点会失去很多重要的几何信息，不过它是光栅显示系统显示面着色时所需的图形表示形式。,前言,把多边形的顶点表示转换为点阵表示，这种转换称为多边形的扫描转换。即，从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓存器内的各个对应元素设

2、置相应的灰度或颜色。,多边形扫描转换主要用来填充多边形区域以及由多边形拟合的其它简单曲线区域。,取点阵表示的多边形区域的一点，并赋予指定的颜色和灰度，然后将该颜色和灰度扩展到整个区域内的过程。,多边形的扫描转换,区域填充主要用在具有复杂形状边界的多边形以及交互绘图系统中。,内容提要,多边形的扫描转换区域填充技术 直线的扫描转换反走样,4.1.1 多边形的扫描转换,多边形可以为凸多边形、凹多边形、含内环的多边形等：,（1）凸多边形,任意两顶点间的连线均在多边形内。,（2）凹多边形,任意两顶点间的连线有不在多边形内的部分。,凸多边形 凹多边形 含内环的多边形,4.1.2 逐点判断算法,基本思想：逐

3、个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。常用方法射线法,4.1.2 逐点判断算法,基本思想：由被测点向某方向作射线，计算此射线与多边形所有边的交点个数，用交点个数的奇偶性判别多边形与点的关系。判断依据：若交点个数为奇数，则被测点在多边形内部；若交点个数为偶数（包括0），则该点在多边形的外部。,射线法,A,C,B,D,a,b,d,c,4.1.2 逐点判断算法,射线f过顶点，若将交点计数为2，则F点在多边形外。 但若规定射线过顶点时，计数为1，则E在多边形内。,e,f,E,F,1,2,3,4,5,A,B,问题：当射线恰好通过多边形的顶点时，怎么判

4、断？,4.1.2 逐点判断算法,点A: 0个交点，在多边形外点B: 1个交点，在多边形内点C：3个交点，在多边形内点D: 1个交点，在多边形内点E: 2个交点，在多边形外点F: 1个交点，在多边形内（剔除重合边）,f,措施在射线左边的边与该射线相交时交点有效，应计数；而在射线右边的边与射线相交时交点无效，不计数。（左闭右开原则）,4.1.2 逐点判断算法,算法实现,void FillPolygonPbyP(Polygon *P,int polygonColor) int x,y; for(y = ymin;y = ymax;y+) for(x = xmin;x = xmax;x+)if(IsI

5、nside(P,x,y) PutPixel(x,y,polygonColor);else PutPixel(x,y,backgroundColor);/*end of FillPolygonPbyP()*/,4.1.2 逐点判断算法,算法特点,简单速度太慢由于该算法割断了各像素之间的联系，孤立地考察各像素与多边形的内外关系，使得几十万甚至几百万个像素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。,4.1.3 扫描线算法,一条扫描线上的像素存在着相关性 在多边形边处，像素性质才发生变化 将相邻像素放在一起测试，从而减少测试点的数目,区域特点,扫描线的连贯性,4.1.3

6、 扫描线算法,目标：利用相邻像素之间的连贯性，提高算法效率处理对象：非自相交多边形（自相交多边形指一个顶点 对应的边数大于2）,4.1.3 扫描线算法,基本思想,对每一条扫描线，计算扫描线与多边形边界的交点，直接连接扫描线在多边形内的每两个相邻交点，其间的所有像素就一次显示了。然后扫描线上升（下降）一个像素，重复上述工作，直至完成全部填充工作。,求出一根扫描线与多边形各边的交点： 对求得的交点进行排序： 奇偶配对求出扫描线与多边形的相交区间： 对这些相交区间填充。,I4, I3, I2, I1,I1, I2, I3, I4,(I1, I2), (I3, I4),4.1.3 扫描线算法,4.1.

7、3 扫描线算法,存在问题,当扫描线与多边形的顶点相交时，会出现异常情况。问题1：如何取舍重交点，保证交点正确配对？,4.1.3 扫描线算法-顶点交点计数,具体实现：检查重交点对应的两条边的另外两个端点的y值，按这两个y值中大于顶点y值的个数是0、1、2来决定交点是计0次、1次还是2次。,解决方法,重交点的两条边分别落在扫描线两边，取交点1次。 重交点的两条边均高于扫描线，取交点2次。 重交点的两条边均低于扫描线，取交点0次。,检查重交点的两相邻边在扫描线的哪一侧,4.1.3 扫描线算法,填充扩大化：多边形边界上像素的也被填充。问题2：避免填充扩大化？,存在问题,4.1.3 扫描线算法-填充扩大

8、化,解决方法,规定落在右/上边界的像素不予填充，而落在左/下边界的像素予以填充。具体实现：对扫描线与多边形的相交区间，取“左闭右开”，如【1，5），问题1保证了多边形的“下闭上开”,9.3.1扫描线填充算法,可以从三方面考虑加以改进以提高算法效率：,（1）在处理一条扫描线时，仅对和它相交的多边形的边（有效边）进行求交运算。,（2）需要考虑多边形的连贯性，即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似，这样在当前扫描线处理完毕之后，不必为下一条扫描线从头开始构造交点信息。,9.3.1扫描线填充算法,（3）最后考虑边的连贯性，即当某条边与当前扫描线相交时，它很可能也

9、与下一条扫描线相交。,4.1.3 扫描线算法数据结构,随着扫描线的移动，扫描线与多边形的交点和上一次交点相关：,设边的直线斜率为k，则，x=1/k,活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中。,结点内容 x： 当前扫描线与边交点的x坐标 x： 从当前扫描线到下一条扫描线间x的增量ymax： 该边所交的最高扫描线的坐标值ymax,即x=1/k为常量。则下一条扫描线与该边的交点不要重新计算，只要加一个增量x。,如何判断多边形的一条边是否与扫描线相交？,其中x为当前扫描线与边的交点，ymax是边所在的最大扫描线值，通过它可以知道何时才

10、能“抛弃”该边，x表示从当前扫描线到下一条扫描线之间的x增量即斜率的倒数。next为指向下一条边的指针,综上所述，活性边表AET的每个结点存放对应边的有关信息如下：,4.1.3 扫描线算法数据结构,注:对每条与多边形相交的扫描线都会有一个AET,一个多边形与若干扫描线,看扫描线 y = 6 的活性边表：,4.1.3 扫描线算法数据结构,4.1.3 扫描线算法数据结构,活性边表的更新,节点更新新边插入旧边删除,4.1.3 扫描线算法数据结构,为了方便活性边表的建立与更新，需构造一个新边表（NET），用来存放多边形的边的信息，分为3个步骤：,（1）首先构造一个纵向链表，链表的长度为多边形所占有的最

11、大扫描线数，链表的每个结点，称为一个桶，对应多边形覆盖的每一条扫描线。,（2）将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。也就是说，存放着该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。,4.1.3 扫描线算法数据结构,（3）每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。,4.1.3 扫描线算法数据结构,一个多边形与若干扫描线,这个结构实际上是一个指针数组，数组的每个变量是个指针，这个指针指向所有的以这个y值作为起点的边。,把多边形所有的边全部填成这样的结构，插到

12、这个指针数组里面来。,如y=1,y=5指向哪些边？,4.1.3扫描线算法步骤,1、 建立NET表；2、将扫描线纵坐标y的初值置为NET中非空元素的最小序号3、置AET为空；4、执行下列步骤直至NET和AET都为空4.1、如NET中的第y类非空，则将其中的所有边取出并插入 AET中；4.2、如果有新边插入AET，则对AET中各边排序；4.3、对AET中的边两两配对，获得有效填充区段，再填充4.4、将当前扫描线纵坐标y值递增1；4.5、将AET中满足ymaxy边删去4.6、对AET中剩下的每一条边的x递增 x，即x = x+ x,4.1.3 扫描线算法,y=2,4.1.3 扫描线算法,算法的执行过

13、程,从新边表中取出与扫描线y=1相交的初始边排序放入活性边表中，填充交点之间的区域,更新边表，删除P1P2，插入新边P6P1，填充交点之间的区域,更新边表，删除P2P3，插入新边P3P4，填充交点之间的区域,4.1.3 扫描线算法,更新边表，插入新边P5P6和P4P5，填充两对交点之间的区域,更新边表，填充两对交点之间的区域,更新边表，删除P6P1和P5P6，填充交点之间的区域,更新边表，删除P4P5和P3P4，活性边表为空，没有新边，填充算法结束,y=8,如何填充?,4舍？还是5入?,当交点的 x 坐标值是小数时需进行舍入运算。,4.1.3 扫描线算法,例：如下图所示多边形，若采用扫描线算法

14、进行填充，试写出该多边形的新边表（NET表）和当扫描线Y=3时的活性边表（AET表）。,注意：NET中，水平边不放在任何桶中，即：水平边不予处理！,4.1.3 扫描线算法,优点：充分利用了三种连贯性，算法效率比逐点填充法高很多。利用边的连贯性来加速交点的计算利用AET以排除盲目求交利用扫描线的连贯性以避免逐点判别缺点：数据结构复杂，对各种表的维护和排序开销太大，适合软件实现而不适合硬件实现。思考：如果多边形为自相交多边形，如何改进算法？,4.1.4 边界标志算法,基本思想对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的像素打上标志；设置一个布尔量inside来指示当前点的状态，若in

15、side为真，则点在多边形内，否则在多边形外，初始状态为假；填充：对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的像素；每当当前访问的像素为被打上标志的点时，就把inside取反。若访问当前像素时，对inside作必要操作之后，inside为真，则把该像素置为多边形色，否则置为背景色。,4.1.4 边界标志算法,边标志算法示意图,y=3,4.1.4 边界标志算法,void edgemark_fill(polydef, color)多边形定义 polydef； int color; 对多边形polydef 每条边进行直线扫描转换； inside = FALSE; for (每条

16、与多边形polydef相交的扫描线y ) for (扫描线上每个象素x ) if(象素x被打上边标志)/两个交点之间的区域填充 inside = ! (inside); if(inside！= FALSE) putpixel (x, y, color); else drawpixel (x, y, background); ,4.1.4 边界标志算法,用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，,由于边界标志算法不必建立、维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比扫描线算法快一至两个数量级。,4.2 区域填充技术,区域填充是指将区域内的一点(常称

17、种子点)赋予给定颜色,然后将这种颜色扩展到整个区域内的过程。,区域-指已经表示成点阵形式的填充图形，是像素的集合。,区域填充算法中，要求区域是连通的。因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它点。,4.2.1 区域的表示,区域可采用内点表示和边界表示两种表示形式。,内点表示：枚举出区域内部的所有像素，内部的所有像素着同一个颜色，边界像素着与内部像素不同的颜色。,边界表示：枚举出边界上的所有像素，边界上的所有像素着同一个颜色，内部像素着与边界像素不同的颜色。,4.2.1 区域的表示-区域的连通,区域可分为4向连通区域和8向连通区域。,四个方向运动 八个方向运动 四连通区域 八连

18、通区域,4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；,8向连通区域是从区域上任一点出发，在不越出区域的前提下，可通过八个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动组合来到达区域内任一点。,四连通区域,八连通区域,4.2.1 区域的表示-区域的连通,4.2.1 区域的表示-连通区域的区别,4连通区域也可理解成8连通区域，但是两者的边界不尽相同,4连通区域 号8连通区域 号 号,4.2.2 区域填充算法-种子填充算法,种子,边界表示的四连通区域种子填充算法内点表示的四连通区域种子填充算法边界表示的八

19、连通区域种子填充算法内点表示的八连通区域种子填充算法,由于区域可采用边界定义和内点定义两种方式，区域按连通性又可分为四连通区域和八连通区域两类，所以常用的种子填充算法有：,4.2.2 区域填充算法-种子填充算法,4.2.2 递归种子填充算法,设（x，y）为四连通区域内部的一点，old_Color为区域内部所有像素的原色。现取（x，y）为种子点，要将整个区域填充为新的颜色new_Color。,基本原理,先判别像素(x, y)的颜色，若它的值等于old_Color，则设置该象素的颜色为new_Color，并对与该象素相邻的上、下、左、右4个相邻象素作递归填充；否则不再进行处理。,void floo

20、dFill4(int x,int y,int newColor,int oldColor) if (getpixel(x,y)=oldColor) drawpixel(x,y,newColor) floodFill4(x+1,y, newColor,oldColor); floodFill4(x-1,y, newColor,oldColor); floodFill4(x,y+1, newColor,oldColor); floodFill4(x,y-1, newColor,oldColor); ,4.2.2 递归算法,4.2.3 栈结构的种子填充算法,基本原理：种子像素入栈，当栈非空时重复执行

21、如下3步操作：,（1）栈顶像素出栈；（2）将出栈像素置成要填充色；（3）按上、下、左、右顺序检查与栈像素相邻的4个像素，若其中某个像素不在边界且未置成填充色，则把该像素入栈。,4.2.3 栈结构的种子填充算法,6,7,5,4,s1,9,3,2,8,43210,0 1 2 3 4 5,例：种子象素为S1,s1,s1,7,2,4,9,4.2.3 栈结构的种子填充算法,9,9,6,7,5,4,s1,3,2,8,43210,0 1 2 3 4 5,s1,7,2,4,9,8,填充次序：s19 8 2 3 4 5 6 7,4.2.3 栈结构的种子填充算法,算法特点：（1）算法程序简单（2）需要反复递归，且

22、要求很大的存储空间以 实现栈结构（3）未考虑像素间的相关性，而是孤立地对一 个个像素进行测试,4.2.4 扫描线填充算法,在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。,4.2.4 扫描线填充算法,初始化：堆栈置空。将种子点（x，y）入栈出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的

23、左、右端点坐标为xl和xr确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最右（左）像素作为种子点压入堆栈，返回第（2）步,4.2.4 扫描线填充算法,算法执行过程,4.2.4 扫描线填充算法,其中 表示边界象素。,4.2.4 扫描线填充算法,例题: 针对下图所示的区域及给定的种子点H，说明填充的过程。,4.2.5 区域填充图案,定位公式为：valuexy=colorx%My%N,（1）定义图案（2）图案与区域的定位,绝对定位：将图案在区域所在的绘图空间坐标系中定义。,4.2.5 区域填充图案,记局部坐标系原点为:(

24、x0,y0)valuexy=color(x-x0)%M(y-y0)%N,相对定位：将图案在局部坐标系中定义。,4.2.5 区域填充图案,（3）像素着色模式透明当图案表的对应位置为1时，用前景色写像素，否则，不改变该像素的值不透明当图案表的对应位置为1时，用前景色写像素，否则，用背景色（图案背景色）写像素本质：规定前景色与背景色的组合规则，如前景色优先、背景色优先、前景色与背景色的加权组合、或各种规则的组合。,4.2.5 区域填充图案,4.2.5 区域填充图案,实例：相对定位实现区域填充图案,4.2.5 区域填充图案,（1）定义图案,int 88=0,0,0,0,0,0,0,0,0,1,1,1,

25、1,1,1,0, 0,1,1,1,1,1,1,0,0,0,0,1,1,0,0,0, 0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0, 0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,4.2.5 区域填充图案,（2）填充,for(y=101;y=170 if(amn=1) putpixel(x,y,RGB(255,0,0) else putpixel(x,y,RGB(255,255,255) ,4.2.5 区域填充图案,(d) 待填充区域的像素位图 (e) 擦除(a)中(d)区域，将像素写为背景色(f) 对待填充区域进行图案填充(g) 以透明模式把(f)绘在屏幕上

26、,例:以透明模式实现图案填充,4.2.6 多边形扫描转换与区域填充方法比较,（1）都是光栅图形面着色，用于真实感图形显示。可相互转换。（2）当用扫描转换直线段的算法将多边形的边界表示成八连通区域后，并取区域内一点作为种子点，多边形扫描转换问题就可转化为区域填充问题（3）若已知给定区域是多边形区域，并且通过一定的方法求出它的顶点坐标，则区域填充问题便可以转化为多边形扫描转换问题。,二者联系,4.2.6 多边形扫描转换与区域填充方法比较,基本思想不同多边形扫描转换是指将多边形的顶点表示转化为点阵表示，主要利用多边形各种形式的连贯性；区域填充只改变区域的填充颜色，不改变区域表示方法，填充过程中利用了

27、区域的连通性。对边界的要求不同多边形扫描转换的扫描算法只要求一条扫描线与多边形边界的交点个数为偶数，多边形的边界可以不封闭；在区域填充算法中，为了防止递归填充时跨越区域的边界，要求区域的边界是封闭,二者区别,4.2.6 多边形扫描转换与区域填充方法比较,基于的条件不同在区域填充算法中，要求给定区域内一点作为种子点，然后从这一点根据连通性将新的颜色扩散到整个区域；扫描转换多边形是从多边形的边界(顶点)信息出发，利用多种形式的连贯性进行填充的。,4.3 直线扫描转换,假设整型坐标系，直线段斜率0m1对m1，x、y互换基本原理确定最佳逼近于该直线的一组像素按扫描线顺序，对这些像素进行写操作,解决的问

28、题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。,4.3.1 DDA算法,数值微分分析（Digital Differential Analyzer，DDA）是一种增量算法。其实质是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。,已知一条直线段L（P1, P2）,其端点坐标分别为：P1 (x1, y1), P2(x2, y2)。直线段所在的直线的斜率为：,直线方程为,则,4.3.1 DDA算法,因光栅单位为1， 可以采用每次x方向增加1， y方向增加k的办法得到下一个直线点。,4.3.1 DDA算法,4.3.1 DDA算法,void Line

29、 ( /设0k1,xsxe int xs,ys;/左端点 int xe,ye; /右端点 int value) /赋给线上的像素属性值 int x; /x以步长为单位从xs增长到xe double dx =xe-xs; double dy =ye-ys; double k =dy/dx; / 直线之斜率k double y =ys; for (x=xs; x=xe; x+) WritePixel(x, Round(y), value); /像素属性值value y+=k; / y移动步长是斜率k ,4.3.1 DDA算法,例：用DDA方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。

30、,x y (yi+k) int( y+0.5)0 0 01 0.4 02 0.8 13 1.2 14 1.6 25 2.0 2,4.3.2 Bresenham算法,4.3.2 Bresenham算法,使用最广泛由误差项符号决定下一个象素取正右方像素还是右上方像素,4.3.2 Bresenham算法,基本思想x方向递增一个单位比较从理想直线到位于直线上方的像素的距离d2和相邻的位于直线下方的像素的距离d1根据距离误差项的符号确定与理想直线最近的像素,4.3.2Bresenham算法,y方向走步与否取决于d1-d2的值取决于误差e值的大小误差判断当e0.5时，最接近P2(xi+1,yi+1), y

31、方向走一步当e0.5时，最接近 P1(xi+1,yi),y方向不走步初值：e0= y/x,P,e,P1,P2,P,4.3.2 Bresenham算法,为方便与0比较，设e=e-0.5当e0时，最接近P2(xi+1,yi+1), y方向走一步当e0时，最接近P1(xi+1,yi), y 方向不走步e0= y/x-0.5,e,P1,P2,P,e,P1,P2,P,4.3.2 Bresenham算法,设e=e2x，不影响判断的准确性当e0时，最接近P2(xi+1,yi+1), y方向走一步当e0时，最接近P1(xi+1,yi), y 方向不走步e0=2y - x,4.3.2 Bresenham算法,下

32、一步误差的计算当e0时，y方向走一步 e1=2y/x 1 ei+1=ei + 2y - 2x当e0时，y方向不走步 e1=2y/x ei+1=ei + 2y,4.3.2 Bresenham算法,4.3.2 Bresenham算法,4.3.2 Bresenham算法,例：用Bresenham方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。,xye00-1031-3112-52-1,x=5， y=2，e0=-1,4.3.2 Bresenham算法,优点整数运算，速度快精度高乘2运算可用移位实现，适于硬件实现,4.3.2 Bresenham算法,例1：已知直线段起点(0, 0)，终点(8

33、,6)，利用Bresenham算法生成此直线段，写出生成过程中坐标点及误差e的变化情况,并在下面的方格中，标出直线上各点 。,4.4 反走样,走样用离散量(像素)表示连续的量(图形)而引起的失真，叫走样或混淆(aliasing)光栅图形混淆现象阶梯状边界；图形细节失真；狭小图形遗失：实时动画时隐时现，产生闪烁,4.4 反走样,（1）阶梯状的边界：在理想直线经过的每一列像素中，选择离直线最近的一个，置为直线颜色，每当前一列所选的像素不同行时，在线上就出现一个台阶。即光滑的线段变成了阶梯形状。,走样现象,4.4 反走样,（2）图形细节失真：由于光栅系统表示图形的最小单位是像素，并且当且仅当像素中心

34、被图形覆盖时，像素才被显示。,走样现象,4.2.7 反走样,（3）狭小图形遗失：由于狭小的多边形分布在两条扫描线之间，它们不覆盖任何一个像素中心，因此，没有被显示出来。,走样现象,4.2.7 反走样,（4）动态图形的闪烁,走样现象,4.4 反走样,用于减少或消除走样现象的技术称为反走样提高分辨率区域取样,4.4.1 反走样,提高分辨率,把显示器分辨率提高一倍（硬件方法）直线经过两倍的像素，锯齿数增加一倍，但同时每个阶梯的宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了一些。,4.4.1 反走样,方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量

35、则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍时间。而且它也只能减轻而不能消除锯齿问题,提高分辨率,4.4.1 反走样,高分辨率计算低分辨率显示（软件方法）,将低分辨率的像素分成多个子像素（2*2或3*3），计算出各个子像素的颜色值，然后将一个像素内的子像素的颜色取某种平均，作为该低分辨率像素的颜色。,又称超采样技术,提高分辨率,4.4.1 反走样,把每个像素分为四个子像素，扫描转换算法求得各子像素的填充值，然后对四像素的填充值简单平均，作为该像素的填充值。,算术平均,4.4.1 反走样,在确定像素的亮度等级时，既考虑子像素的多少，还应该考虑子像素的位置分布。通常会给接近于像素区域中心

36、的子像素更大的权。因为这些子像素在确定像素的整体亮度中起更重要的作用。图中示出了对33像素分割所采用的加权方案：中心子像素的加权是角子像素的4倍，是其它像素的2倍；对九个子像素的每个网格所计算出的亮度进行平均中心子像素的加权系数为1/4；顶部和底部及两侧子像素的加权系数为1/8；而角子像素的加权系数为1/16。,加权平均,4.4.2 反走样,基本思想：每个像素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与像素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该像素的亮度值。,区域采样,4.4.2 反走样,求相交区域的近似面积的离散计算方法,1、将屏幕像素分割成n个更小的子像素；2、计算中心点落在直线段内的子像素的个数，记为k，3、k/n为线段与像素相交区域面积的近似值,4.4.2 反走样,缺点像素的亮度与相交区域的面积成正比，而与相交区域落在像素内的位置无关，这仍然会导致锯齿效应。直线条上沿理想直线方向的相邻两个像素有时会有较大的灰度差。,习题,例：如下图所示多边形，若采用扫描线算法进行填充，试写出该多边形的新边表（NET表）和当扫描线Y=4时的活性边表（AET表）。,