为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

图元属性(多边形填充)

2011-12-11 50页 ppt 2MB 34阅读

用户头像

is_867272

暂无简介

举报
图元属性(多边形填充)null 多边形的填充 多边形的填充1:多边形的扫描转换 2:多边形的区域填充 3:光栅图形的反走样算法null讨论二维区域的填充问题,即面着色的问题,也就是为指定的平面区域填上所需要的颜色。 窗口3.4.1 基本概念3.4.1 基本概念多边形:(定义)限定为有封闭折线边界且无交叉边的平面图形 多边形分类:凸多边形、凹多边形 判别凸凹多边形的方法 1、凸多边形所有向量叉积均同号。若有些叉积取正而有些为负,则是凹多边形 2、观察多边形顶点位置与每条延长线的关系,若有些顶点在某一延长线的一侧而其他一些顶...
图元属性(多边形填充)
null 多边形的填充 多边形的填充1:多边形的扫描转换 2:多边形的区域填充 3:光栅图形的反走样算法null讨论二维区域的填充问,即面着色的问题,也就是为指定的平面区域填上所需要的颜色。 窗口3.4.1 基本概念3.4.1 基本概念多边形:(定义)限定为有封闭折线边界且无交叉边的平面图形 多边形分类:凸多边形、凹多边形 判别凸凹多边形的 1、凸多边形所有向量叉积均同号。若有些叉积取正而有些为负,则是凹多边形 2、观察多边形顶点位置与每条延长线的关系,若有些顶点在某一延长线的一侧而其他一些顶点在另一侧,则是凹多边形。 分割凹多边形:向量方法、旋转方法分割凹多边形分割凹多边形xy向量方法旋转方法E1E2E3E4E5E6V2V1V3V4内-外测试内-外测试不自交的多边形、自相交的多边形 常用解决方法: 奇-偶规则、非零环绕数规则 1) 奇-偶规则(Odd-even Rule) 从任意位置p作一条射线,若与该射线相交的多边形边的数目为奇数,则p是多边形内部点,否则是外部点。 图例图例11331图例图例P’2224null2) 非零环绕数规则(Nonzero Winding Number Rule) 首先使多边形的边变为矢量。 将环绕数初始化为零。 再从任意位置p作一条射线(不经过多边形顶点)。当从p点沿射线方向移动时,对在每个方向上穿过射线的边计数,每当多边形的边从右到左穿过射线时,环绕数加1,从左到右时,环绕数减1。 处理完多边形的所有相关边之后,若环绕数为非零,则p为内部点,否则,p是外部点。 内-外测试内-外测试奇-偶规则非零环绕数规则多边形的表示方法多边形的表示方法1、表示方法:定点表示和点阵表示1)顶点表示是用多边形的顶点的序列来描述多边形,该表示几何意义强、占内存少,但它不能直观地说明哪些像素在多边形内。2)点阵表示是用位于多边形内的象素的集合来刻划多边形,该方法虽然没有多边形的几何信息,是面着色所需要的图像表示形式。 多边形填充就是把多边形的顶点表示转换为点阵表示,即从多边形的给定边界出发,求出位于其内部的各个像素,并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。实际上,也就是多边形内的区域的着色过程。3.4.2 扫描转换的常用算法3.4.2 扫描转换的常用算法逐点判断算法 扫描线算法 边缘填充算法 边界标志算法3.4.2.1 逐点判断算法3.4.2.1 逐点判断算法思想:逐个象素判别,确定它们是否在多边形内部,从而给出位于多边形内的点(象素)的集合。 难点:如何确定一个点是否在多边形内部?需要注意的问题需要注意的问题 在计算交点时,如果交点恰恰就是多边形的顶 点,必须小心处理,即要观察在此顶点相遇的两条 边,如果这两条边的其余两个顶点在新构成线段的同 一侧,应认为此线段与多边形相交二次;若多边形两 条边的其余两个顶点在新线段的异侧,则认为此线段 与多边形相交一次(奇点的处理)。算法的实现算法的实现现设P=P0P1…PnP0为一给定的多边形。Framebuffer(x,y)是与点(x,y)相对应的帧缓冲器中的元素。则逐点判断的算法可以表示成为如下的程序: for y:= screen-ymin to screen-ymax do for x:= screen-xmin to screen-xmax do if inside(p, x, y) then setpixel(framebuffer, x, y, polygon-color) else setpixel(framebuffer, x, y, back-color);null 逐点判断的算法虽然程序简单,但是不可取。原因是速度太慢,该算法割断了各个象素之间的联系,孤立的考察各个象素和多边形P的内外关系,使得几十万甚至几百万个象素都要一一判别,每次判别都要多次求交点,需要做大量的乘除运算,花费大量的时间。3.4.2.2 多边形填充的扫描线算法3.4.2.2 多边形填充的扫描线算法1、特点:充分利用了相邻象素之间的连续性,避免对象素的逐 点判断和反复求交运算,减少了计算量,提高了算法速度.基本概念: 1)扫描线的连续性:扫描线即电子枪由左向右扫过的一行,或用座标的观点来说即y=i这样的一条线 2)边的连续性 3)奇点 :扫描线与多边形P的交点是P的顶点,该交点称为 奇点。null 设多边形P的顶点, 又设 是各顶 点Pi的纵坐标yi的递减数列,当 时,屏幕上位于 和 两条扫描线之间的长方形区域被多边形P的边分割成若干梯形。1)扫描线的连续性1)扫描线的连续性设e为一整数 ≥e ≥ 。若扫描线y=e与多边形P的边Pi-1Pi相交,则记其交点的横坐标为 。令: 是该扫描线与P的边界各交点横坐标的递增序列,记为序列1。由区域的连贯性可知,此交点序列具有以下性质: (1) l是偶数。 (2) 在该扫描线上,只有区段 位于多边形P内. P内P内P内2)边的连续性2)边的连续性若d为一整数,d=e–1,且yi0≥y≥yin;设位于扫描线y=d上的交点序列为 ,记为序列2。若多边形P的边Pi-1Pi与扫描线 y=e, y=d都相交,即:则序列1和 序列2有以下关系:a:两个序列元素个数相等,即l=h b:点 和 位于多边形的同一个边上,于是有 其中mr为边Pr-1Pr的斜率 递推式1edy63y243)奇点的处理3)奇点的处理a: 多边形P的顶点可分为两类:极值点和非极值点。如果 ,称顶点Pi为极值点(P1,P2,P3,P5, P6,P8);否则称Pi为非极值点(P0,P4,P7)。若扫描线与多边形相交于多边形的顶点,则该交点(顶点)称为奇点。 b: 处理时遇到的问题 如果把每一奇点简单地计为一个交点,则交点个数可能出现奇数,如上图中的 扫描线的情况;但若将每一奇点都简单地计为两个交点,同样会导致反常的结果,如上图中 扫描线的情况。 3)奇点的处理3)奇点的处理 c: 奇点的处理 为了使交点个数保持为偶数,规定当奇点是P的极值点时,该点按两个交点计算;否则按一个交点计算。 d: 实际算法预处理: 若Pi是非极值点,则将 两边中位于扫描线y=yi上方的那条边在Pi点处截去一单位长 扫描线算法—奇点的处理扫描线算法—奇点的处理p1,p3,p4,p5属于局部极值点,要把他们两次存入交点表中。 如扫描线y=7上的交点中,有交点(2,7,13),按常规方法填充不正确,而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2,p6为非极值点,则不用如上处理。p1p2p3p4p5p6p1p2p3p4p5p62、扫描线算法的实现2、扫描线算法的实现对于每一条扫描线,多边形的填充过程可分为以下4步:1423把所有的交点按x值递增的顺序进行排列;计算扫描线与多边形各边的交点,设交点个数为n; 将排序后的第1个与第2个交点,第3个与第4个交点, ……第n-1个与第n个交点配对,每对交点就代表扫描 线与多边形的一个相交区间; 4把相交区间内的像素置成多边形的颜色,相交区间外 的像素置成背景色。扫描线算法的实现步骤扫描线算法的实现步骤对于一条扫描线填充过程可以分为四个步骤: 求交 排序 配对 填色2、扫描线算法的实现2、扫描线算法的实现3、扫描线算法的数据结构3、扫描线算法的数据结构a:数据结构 边的分类表ET和边的活化链表AEL。ET和AEL中的多边形的边由四个域组成: ymax 边的上端点的y坐标; x ET中为边的下端点的x坐标,在AEL中是边与扫描线交点的x坐标 Δx 边的斜率的倒数 next 指向下一条边的指针。告诉处理到哪条扫描线时,就 可以结束这条边了记录了初始扫描线与这条边的 初始x值记录当前扫描线与某条边的交点x值dy/dx,扫描线加1时,即y=y+1时 x=x+1/m相交的边对在哪,即要填充哪 两条边之间的区域。3、扫描线算法的数据结构AEL3、扫描线算法的数据结构AEL 边的活化链表AEL由与当前扫描线相交的所有多边形的边组成。它记录了多边形边沿扫描线的交点序列.当前扫描线与该边的交点坐标为(xi,yi),则下一条扫描线与该边的交点(xi+1,yi+1)不需要重新计算,只要加一个增量即可。 边 的 活 化 链 表2ymaxx1/mAEL中的各边按照x值 (当x的值相等时,按Δx值) 递增方向排序。3、扫描线算法的数据结构ET3、扫描线算法的数据结构ET分类表ET按边下端点的纵坐标y对边进行分类。也就是说,如果某边的较低端点为ymin,则该边就放在扫描线ymin的新边表中。同一类中,各边按x值递增的顺序排列成行。对于图3.20的多边形: [P0P1P2P3P4P5 P6]= [(2,5) (2,10) (9,6) (16,11) (16,4) (12,2) (7,2)] 多边形的边y筒注意: 其中P0和P4点是非极值点,我们在做y 边的分类之前已经做过对边e1和e4的 预处理:分别在P0和P4处截掉一个单 位以保证扫描线y=yi只与Pi-1Pi、PiPi+1 两边的一边相交,只求得一个交点。同 时由于e6是水平边,不参加分类。y12564、扫描线算法的步骤:4、扫描线算法的步骤:步骤1:(AEL初始化)将边的活化链表AEL设置为空。 步骤2:(y初始化)取扫描线纵坐标y的初始值为ET中非空元素的最小序号 步骤3:按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行下列步骤,直到边的分类表ET和边的活化链表AEL都变成空为止。5、扫描线算法的具体步骤:5、扫描线算法的具体步骤:①如边分类表ET中的第y类元素非空,则将属于该类的所有边从ET中取出并插入边的活化链表AEL中,AEL中的各边按照x值(当x的值相等时,按Δx值)递增方向排序。2从ET中选择当前扫 描线的边表,方便活 性边表的建立和更新5、扫描线算法的具体步骤:5、扫描线算法的具体步骤:②若相对于当前扫描线,边的活化链表AEL非空,则将AEL中的边两两依次配对,即第1,2边为一对,第3,4边为一对,依此类推。 每一对边与当前扫描线的交点所构成的区段位于多边形内,依次对这些区段上的点(象素)按多边形属性着色。5、扫描线算法的具体步骤:5、扫描线算法的具体步骤:③将边的活化链表AEL中满足y=ymax的边删去。 (表明一条边已经结束) ④将边的活化链表AEL剩下的每一条边的x域累加Δx,即x:=x+Δx。 (下一条扫描线与边的交点x,利用了边的连续性) ⑤将当前的扫描线的纵坐标值y累加,即y:=y+1 ( 求下一条扫描线)e0:m=-5/3,所以x变为7-5/3=5e5:m=2,所以x变为12+2=14y=y+1,即y=2+1=3null…54因为对于e5,y的 max已经到了, 故去掉e5,而 从ET表中加入e4扫描线算法描述扫描线算法描述建立ET表,置y为ET表中非空的最小y坐标值 置AEL表为空,且按照y值将ET表的边加入AEL表中 while AEL表非空并且ET表中非空 do      begin 对AEL表中的xmin值按升序排列      按照AEL表中交点前后次序,在每对奇偶交点间的x段予以填充     if 扫描线 y=ymax  then 从AEL表中删除这些边      对在AEL表中的其他边,计算与下一条扫描线的交点:x=x+1/m      计算下一条扫描线:y=y+1       按照扫描线y值把ET表中相应的边加入AEL表中 end end of algorithm扫描线算法性能分析扫描线算法性能分析 扫描线算法的数据结构和程序结构都远比逐点判断算法复杂,对各种表的维护和排序的耗费很大。但是由于它充分利用的多边形的区域、扫描线和边的三种形式的连贯性,从而避免了反复求交点的大量运算,因此速度比逐点判断法快的多。3.4.2.3 边缘填充算法3.4.2.3 边缘填充算法1、特点:采用对图像进行逐位求反的方法,免去对边排序 的工作量2、预备知识: 对颜色M作偶数次求反运算,其结果还是M,而对M作奇数次 求反运算的结果是M的反M 。在光栅图形中,如某区域已着 上值为M的某种颜色,则上述求反运算得到的结果是:对区 域作偶数次求反运算后,该区域的颜色不变;作奇数次求反 运算后,该区域的颜色则变成值为M的颜色。3、边缘填充算法的实现3、边缘填充算法的实现 实现:对多边形P的每一非水平边上的各像素做向右求反运算 即可,见下图,其中(a)为给定的多边形;(b)为对区域赋初值;(c),(d),(e)和(f)表示逐边向右求反。 3.4.2.4 边界标志算法3.4.2.4 边界标志算法1、基本原理:首先用一种特殊的颜色在帧缓冲器中将多边形 的边界(水平边的部分边界除外)勾画出来。然后再把位于多 边形内的各个像素着上所需的颜色。 2、算法具体实现步骤: 步骤1:以值为boundary-color 的特殊颜色勾画多边形P的边界。设多边形顶点为Pi= (xi, yi),0≤i≤n, xi, yi均为整数;置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必定是偶数(包括零)。 步骤2:设interior_point 是一布尔变量。对每一条扫描线从左到右进行搜索,如果当前是像素位于多边形P内,则interior_point=true,需要填上值为polygon_color的颜色;否则该像素在多边形P外,需要填上值为background_color的颜色。 3、边界标志算法实例3、边界标志算法实例标志边界并处理奇点P2(9,6)P0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1) for(i=0;i<=n;i++){ dy=p[i+1].y-p[i].y; dx=(p[i+1].x-p[i].x)/dy; if(dy>0)x=p[i].x;else x=p[i+1].x; ymax=(Math.max(p[i].y,p[i+1].y)); ymin=(Math.min(p[i].y,p[i+1].y)); for (y=ymin+1;y<=ymax ;y++ ) { x=(int)(x+dx+.5); if(pixels(x, y)==blue) pixels(x+1, y)=blue; else pixels(x, y)=blue; }} // for(i=0;i<=n;i++)确定某条边的上下端点水平边不考虑多边形的边数边界颜色-蓝色P0P1的底端点yminP0P1的上端点ymaxP1P2的底端点ymin3、边界标志算法实例3、边界标志算法实例//maxx、maxy、minx、miny是获得的多边//形最小矩形包围盒边界值 for(y1 = miny - 1 ; y1<= maxy ;y1++) { in_flag = 0; //多边形内部标志变量 for( x1 = minx - 1; x1<=maxx - 1; x1++) { l = pixels(x, y); //多边形边界颜色blue if (l == blue) { if (in_flag == 0) in_flag = 1; else in_flag = 0; } if (in_flag) pixels(x, y)=blue; //在多边形内部填充色蓝色 else pixels(x, y)=white; } } miny,minxmaxxmaxy获得当前象素 颜色以判断是否 是边界色如果是边界,且第一/三次碰到边界,就置flag为1,表明其后的象素要置成多边形的颜色如果是第二/四次遇到边界,就置flag为0,对其后的元素置背景色为白色。3、边界标志算法实例3、边界标志算法实例3.3.2.5 区域填充 一、区域的基本概念3.3.2.5 区域填充 一、区域的基本概念1、区域是指已经表示成点阵形式的像素集合。在光栅图形 中,区域可采用内点表示和边界表示两种形式进行描述。 内点表示法:把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。边界表示法:把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。null1)4连通的区域: 取区域内任意两 点,在该区域内若从其中一点出发 通过上、下、左、右四种运动可到 达另一点。2)8连通的区域: 取区域内任意两 点,若从其中任一点出发,在该 区域内通过沿水平方向、垂直方向 和对角线方向的八种运动可到达另 一点。2、区域的连通性null 3) 4连通区域也可理解成8连通区域,即4连通能达到的8连通肯定能达到,4连通只是8连通的一种特殊情况。8连通而 非4连通 的地方连通不是指边界而是边界内的区域这里是X围起来的区域·号是区域 X是边界null 但是两者的边界不尽相同。如果图中标有·号的象素组成的区域作为4连通区域,则其边界由图中的标有△号的象素组成。如果将该区域作为8连通的区域,则其边界由图中标有△号和×号的两种象素组成。 因为如果区域是8连通的,△ 边界不能将区域有效封堵,X的位置和区域又是连通的了。 图3.28四连通区域与八连通区域的不同边界二、简单的种子填充算法二、简单的种子填充算法基本思想:给定区域G一种子点(x, y),首先判断该 点是否是区域内的一点,如果是,则将该点填充为 新的颜色,然后将该点周围的四个点(四连通)或八 个点(八连通)作为新的种子点进行同样的处理,通 过这种扩散完成对整个区域的填充。算法描述如下:算法描述如下:1.将种子象素入栈; 2.当栈非空时,重复: ①栈顶象素出栈; ②若该象素未填充,则将出栈象素置成填充色 ③以该象素为中心,检查出栈象素的4-邻接点,依“左上右下”顺序将非边界象素和未填充象素压入堆栈。若其中某个象素点不是边界色且未置成填充色,则把该象素入栈 null简单的种子填充算法void flood_fill_8(int[] pixels, int x, int y, int old_color, int new_color){ if(x0&&y0) { if (pixels[y*w+x]==old_color){ pixels[y*w+x]== new_color); flood_fill_8(pixels, x,y+1,old_color,new_color); flood_fill_8(pixels, x,y-1,old_color,new_color); flood_fill_8(pixels, x-1,y,old_color,new_color); flood_fill_8(pixels, x+1,y,old_color,new_color); flood_fill_8(pixels, x+1,y+1,old_color,new_color); flood_fill_8(pixels, x+1,y-1,old_color,new_color); flood_fill_8(pixels, x-1,y+1,old_color,new_color); flood_fill_8(pixels, x-1,y-1,old_color,new_color); } } } null堆栈变化步骤 例子:null种子象素为(3,2) 填充(3,2),入栈(3,2) 出栈(3,2),填充并入栈(2,2),(3,3),(4,2),(3,1) 出栈(3,1),填充并入栈(2,1),(4,1) 出栈(4,1),出栈(2,1),出栈(4,2), 出栈(3,3),填充并入栈(2,3) 出栈(2,3),出栈(2,2),填充并入栈(1,2),出栈(1,2)递归算法的性能分析递归算法的性能分析 区域填充的递归算法程序简单,表达清楚。但由于多层递归,系统堆栈反复进出,费时费内存。三、扫描线种子填充算法三、扫描线种子填充算法1、基本思想: 从给定的种子点开始,填充当前扫描线上种子 点所在的一区段,然后确定与这一段相邻的上下两条 扫描线上位于区域内的区段(需要填充的区间),从 这些区间上各取一个种子点依次把它们存起来,作为 下次填充的种子点。反复进行这过程,直到所保存的 各区段都填充完毕。null2、算法步骤:步骤 1:(初始化)将算法设置的堆栈置为空。将给定的 种子点(x, y)压入堆栈步骤 2:(出栈)如果堆栈为空,算法结束;否则取栈顶 元素(x, y)作为种子点栈种子null步骤 3:(区段填充)从种子点(x, y)开始,沿纵坐标为y的当前扫描线向左右两个方向逐个像素用新的颜色值进行填充,直到边界为止即象素颜色等于边界色。设区间两边界的横坐标分别为xleft 和xright。步骤4:在与当前扫描线相邻的上下两条扫描线上,以区间[xleft, xright]为搜索范围,求出需要填充的各小区间,把各小区间中最右边的点并作为种子点压入堆栈,转到步骤2。 xleft xright区域填充的扫描线算法描述区域填充的扫描线算法描述将种子象素点压入堆栈 while 堆栈非空 do begin     从堆栈中弹出一个种子象素     沿着扫描线对种子象素的左右象素进行填充,直至遇到边界 象素为止     标志区间内最左和最右象素为xleft 和xright if在xleft≤x≤xright中检查与当前扫描线相邻的上下两条扫描线 全为边界象素或全为已填充过的象素 then goto 2 在xleft≤x≤xright中标记每一个既不包含边界象素又不包含已 填充过的象素的区间    将每一区间的最右象素作为种子象素压入堆栈 end end of algorithmnull3、算法的关键原则: 1)搜索原则:从前一个填充的区间(边界之间的范围xleft, xright)作为后一条扫描线种子点寻找的范围。 2)填充原则:从种子点往左,右填,填到边界12如果种子 点在这里xleftxright搜索确定种子点种子点填充null1210222233222224、实例nullStack stack=new Stack();//堆栈 pixel_stack初始化 Stack.push (point); //(x,y)是给定的种子像素 while (!stack.empty()) { p=(Point)(stack.pop());//出栈,从堆栈中取一像素作种子像素 x=p.x; y=p.y; savex=x;//保存种子点的横坐标x的值 while (dc.GetPixel(x,y)!= boundary_color) { dc.SetPixel(x,y,new_color); x++; } //从种子像素开始向右填充到边界 xright=x–1; //保存线段的右端点 x=savex–1; //设定种子点往左填充的起点x-1xr5、程序实现nullwhile (dc.GetPixel(x,y)!= boundary_color) { dc.SetPixel(x,y,new_color); x=x–1; } //从种子像素开始向左填充到边界,以上两步完成区间填充。 xleft=x+1; //保存线段的左端点,加1是因为前面 // 循环时多减一次 x=xleft; //起点是上次的左端点 y=y+1; //开始处理上一条扫描线xleftnullwhile(x<=xright) { //在上一条扫描线上检查是否需要填充 span_need_fill=false; //先设定为不需要填充 while (dc.GetPixel(x,y)==old_color&&x<=xright ) { //待填充的线段 span_need_fill=true; //发现有旧象素,需要填充 x=x+1; } //待填充的线段处理完,即遇到边界色,!=old_color跳出 if (span_need_fill) { //如果区间需要填充,则将其右端点作 为种子点压进堆栈 p=new Point(x-1,y); stack.push (p); //进栈 span_need_fill=false; } null//继续向右检查以防有遗漏 while (dc.GetPixel(x,y)!=old_color &&x<=xright ) x=x+1; } //在上一条扫描线上检查完 x=xleft; y=y–2; //形成下一条扫描线的y值 //在下一条扫描线上从左向右检查位于区间[xleft,xright]上的像素,其方法与在上一条扫描线上检查的情况完全一样。 }//出栈完如果种子 点在这里123xleftxright扫描转换和区域填充的比较扫描转换和区域填充的比较 多边形的扫描转换和区域填充是两类典型的面着色问题,在一定条件下两者可以相互转换。但二者的基本思想是不同的。 多边形的扫描转换是指将多边形的顶点表示转换成点阵表示,在扫描转换过程中利用了多边形各种形式的连贯性; 区域填充只改变区域的颜色,不改变区域的表示方法。在填充过程中应用了区域的连通性。3.4 字符的生成 3.4 字符的生成 3.4.1 点阵式字符 在点阵字符库中,每个字符由一个位图表示。该位为1表示字符的笔画经过此位,对应于此位的象素应置为字符颜色。该位为0表示字符的笔画不经过此位,对应于此位的象素应置为背景颜色。在实际应用中,有多种字体(如宋体、楷体等),每种字体又有多种大小,因此字库的存储空间是很庞大的。 null常用的点阵大小有7×9、8×8、16×16等。下图所示的是字母“P”的点阵式表示。显示点阵式字符时,只需将字库中的矩形点阵映射到帧缓冲器中的单元即可。3.4.2 轮廓式字符3.4.2 轮廓式字符轮廓式字符是将每个字符定义为一条曲线或多边形的轮廓,显示时需要进行扫描转换。如下图所示为字母“B”的轮廓表示,轮廓线构成了一个或若干个封闭的平面区域,显示时字符轮廓的内部需用扫描线填充程序来填充。 3.5 光栅图形的反走样算法3.5 光栅图形的反走样算法 a:图形的边界一般都呈阶梯形 b:图形的细节失真、狭小图形遗失 3.5.1 光栅图形的走样现象3.5.2 提高分辨率的反走样方法3.5.2 提高分辨率的反走样方法采用硬件: 采用高分辨率的光栅图形显示器,花费的代价大。 采用软件: 花费的代价小,也容易实现。高分辨率计算:将低分辨的图形显示象 素划分为许多子象素,如2×2划分, 3×3划分等,然后按通常的算法计算 出各个子象素的颜色值或灰度值。 低分辨率显示:将一象素内的各个子象 素的颜色值或灰度值的平均值作为该 象素的颜色值或灰度值。求平均值时 可取算术平均,也可取加权平均。 1、用软件提高分辨率的方法是: 高分辨率计算,低分辨率显示。 3.5.3 区域采样的反走样算法 3.5.3 区域采样的反走样算法 1、线段的反混淆算法的基本思想可归纳如下: (1)把线段看作是有宽度的狭长的矩形(因为线段是有宽度的),所以 (2)线段具有一定的面积,当线段通过某象素时,可以求出线段与像素的面积的交,然后 (3)根据每一象素与线段相交部分的面积值决定该象素的颜色值或灰度值。反走样后线段的显示3.5.3 区域采样的反走样算法 3.5.3 区域采样的反走样算法 设一条直线的斜率为m,其宽度为一个像素单位,则直线与像 素相交的情况共有5种。 在计算阴影面积时,(a)与(e)、(b)与(d)类似,(c)可用正方形的面积减去2个三角形的面积。因此只讨论(a)和(b)的情况。如下图,情况(a)的阴影面积为D2/2m;情况(b)的阴影面积为D-m/2。3.5.3 区域采样的反走样算法 3.5.3 区域采样的反走样算法 上述阴影面积是介于0~1之间的正数,用它乘以像素的最大灰度值,再取整,就可得到像素的显示灰度值。将这种区域采样的反走样算法用于直线段时,就相当于将线段上位于原相邻阶梯之间的像素置为了过渡颜色或灰度,从而使得颜色或者灰度过渡自然,变化柔和。阶梯被淡化后,线形自然就显得平直了。为了简化运算,有时候还可以采用离散的方法。即将屏幕像素均分成n个子像素,计算中心点落在直线段内的子像素的个数k,那么该像素的亮度就是最大灰度值乘以相交区域面积的近似值k/n。左图所示是n=9,k=3,近似面积为1/3的情况。 3.5.4 加权区域采样的反走样算法 3.5.4 加权区域采样的反走样算法 将像素均分成n个子像素,每个子像素的面积为1/n,计算每个子像素对原像素的贡献,并保存在一张二维的加权表中(3.5.2节的图中的(a)、(b)就是将一个像素分别均分为3×3个子像素和7×7个子像素时所对应的加权表);求出所有中心落在直线段内的子像素组成的集合,并计算这些子像素对原像素的亮度贡献之和的值,该值乘以像素的最大灰度值就得到该像素最终要显示的亮度。 null课件等相关资料下载: E-Mail:geoscience2008@126.com 密码:geoscience2008
/
本文档为【图元属性(多边形填充)】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索