《第3章 基本图形生成算法2.ppt》由会员分享，可在线阅读，更多相关《第3章 基本图形生成算法2.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第3章章 基本图形生成算基本图形生成算法法2实区域填充算法 确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内解决的主要问题是什么？图案填充还有一个什么象素填什么颜色的问题曲线围成的区域，可用多边形逼近 点在多边形内的包含性检验检验夹角之和射线法检验交点数检验夹角之和若夹角和为若夹角和为0 0，则点，则点p p在多边形外在多边形外若夹角和为若夹角和为360360，则点，则点p p在多边形内在多边形内ABCDEPABCDEP夹角如何计算？大小：利用余弦定理方向：令当TBP斜率，为顺时针角当T0时，AP斜率BP斜率，为逆时针角zxABPzxBAP射线法检验交点数ABCDEPABCDEP交
2、点数=偶数（包括0）点在多边形之外交点数=奇数点在多边形之内zx左闭右开包围盒法凸多边形凸多边形凹多边形凹多边形逐点测试效率低不实用怎么办？实区域填充算法分类扫描线填充算法n n扫描线顺序扫描线顺序种子填充算法n n内部一个点出发内部一个点出发扫描线填充算法求交：I4,I3,I2,I1排序：I1,I2,I3,I4交点配对：(I1,I2),(I3,I4)区间填色利用图形的空间连贯性和扫描线的连贯性填充扩大化问题解决方法：n n取中心扫描线取中心扫描线y+0.5y+0.5n n检查交点右方像素的中心是否落在区间内检查交点右方像素的中心是否落在区间内 xlx+0.5xr顶点交点的计数问题 54321
3、0P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫描线1I5I6检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数 计数0次计数1次计数2次10/15/202210/15/20221111有序边表算法影响一般扫描线填充算法效率的因素？把多边形所有边放在一个表中，按顺序取出，把多边形所有边放在一个表中，按顺序取出，分别计算与每条扫描线的交点？分别计算与每条扫描线的交点？如何提高效率？如何提高效率？建立每条扫描线的活性边表建立每条扫描线的活性边表何谓活性边？何谓活性边？求交和排序求交和排序目标是简化交点计算目标是简化交点计算有序边表算法活性边表的建立结点信息x x
4、：当前扫描线与边的交点：当前扫描线与边的交点x x：从当前扫描线到下一条扫描线之间的：从当前扫描线到下一条扫描线之间的x x增量增量y ymaxmax：边所交的最高扫描线号：边所交的最高扫描线号活性边表的更新新边插入新边插入旧边删除旧边删除x=1/k有序边表算法对每条扫描线建立一个新边表结点信息x x0 0：扫描线与边的初始交点：扫描线与边的初始交点x x：从当前扫描线到下一条扫描线之间的：从当前扫描线到下一条扫描线之间的x x增量增量y ymaxmax：边所交的最高扫描线号：边所交的最高扫描线号边结点不必排序边结点不必排序yx0 1 2 3 4 5 6 7 8 9 101112345678P
5、6P4P2P5P2P3新边表8.57.56.55.54.53.52.51.50.5528.5-1.5 711082075-32.533P4P5P5P6P3P4P6P1P1P2P2P3活性边表活性边表5-32.533P1P2P2P3y=1.5207.833P6P1P2P3y=2.5207.1108P6P1P3P4y=3.5528.P4P51108P3P45-1.5 7P5P6207.P6P1y=5.5728.P4P51108P3P43.5-1.5 7P5P6207.P6P1y=6.5528.P4P51108P3P4y=7.5step1step1：把新边表：把新边表NETNETi i中的边结点，用
6、插入排序法中的边结点，用插入排序法 插入活性边表插入活性边表AETAET，使之按，使之按X X坐标递增顺序排序；坐标递增顺序排序；step2step2：遍历：遍历AETAET表，把配对交点之间的区间表，把配对交点之间的区间(左闭右开左闭右开)上的各象上的各象 素素(X(X，Y)Y)，用，用drawpixel(x,y,color)drawpixel(x,y,color)改写象素颜色值；改写象素颜色值；step3step3：遍历：遍历AETAET表，把表，把Y Ymaxmax=i=i的结点从的结点从AETAET表中删除，并把表中删除，并把 Ymax Ymaxi i的结果点的的结果点的X X值递增值
7、递增 X X；step4step4：重复各扫描线：重复各扫描线算法：(对每一条扫描线i)有序边表算法优点：n n对每个像素只访问一次对每个像素只访问一次n n与设备无关与设备无关缺点：n n数据结构复杂数据结构复杂n n只适合软件实现只适合软件实现边填充算法边填充算法(Edge Fill Algorithm)边填充算法边填充算法(Edge Fill Algorithm)优点：优点：n n最适合于有帧缓存的显示器最适合于有帧缓存的显示器n n可按任意顺序处理多边形的边可按任意顺序处理多边形的边n n仅访问与该边有交点的扫描线上右方的像素，仅访问与该边有交点的扫描线上右方的像素，算法简单算法简单缺
8、点：缺点：n n对复杂图形，每一像素可能被访问多次，输对复杂图形，每一像素可能被访问多次，输入入/输出量大输出量大n n图形输出不能与扫描同步进行，只有全部画图形输出不能与扫描同步进行，只有全部画完才能打印完才能打印栅栏填充算法栅栏填充算法(Fence Fill Algorithm)引入栅栏的目的？引入栅栏的目的？种子填充算法种子填充算法假设多边形区域内至少有一个像素已知假设多边形区域内至少有一个像素已知区域定义法：区域定义法：n nInterior-definedInterior-definedn nBoundary-Boundary-defineddefinedFlood-fill alg
9、orithmBoundary-fill algorithm区域连通方式：区域连通方式：n n4-connected4-connectedn n8-connected8-connected10/15/202210/15/20222121区域连通方式对填充结果的影响区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果简单的种子填充算法简单的种子填充算法（4连通边界）连通边界）种子像素入栈种子像素入栈当栈非空时，重复以下步骤：当栈非空时，重复以下步骤：n n栈顶像素出栈栈顶像素出栈栈顶像素出栈栈顶像素出栈n n将出栈象素置成填充色将出栈象素置成填充色将出栈象素
10、置成填充色将出栈象素置成填充色 n n按左、上、右、下顺序检查与出栈象素相邻的按左、上、右、下顺序检查与出栈象素相邻的按左、上、右、下顺序检查与出栈象素相邻的按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成四象素，若其中某象素不在边界上且未被置成四象素，若其中某象素不在边界上且未被置成四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈填充色，则将其入栈填充色，则将其入栈填充色，则将其入栈 填充算法演示填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799缺点？4-con
11、nected boundary-fill4-connected boundary-fill void BoundaryFill4(int x,int y,int fill,int void BoundaryFill4(int x,int y,int fill,int boundary)boundary)int current;int current;current=getpixel(x,y);current=getpixel(x,y);if(current!=boundary)&(current!=fill)if(current!=boundary)&(current!=fill)putpix
12、el(x,y,fill);putpixel(x,y,fill);BoundaryFill4(x+1,y,fill,boundary);BoundaryFill4(x+1,y,fill,boundary);BoundaryFill4(x-1,y,fill,boundary);BoundaryFill4(x-1,y,fill,boundary);BoundaryFill4(x,y+1,fill,boundary);BoundaryFill4(x,y+1,fill,boundary);BoundaryFill4(x,y-1,fill,boundary);BoundaryFill4(x,y-1,fil
13、l,boundary);4-connected boundary-fill4-connected boundary-fill void FloodFill4(int x,int y,int fillColor,int void FloodFill4(int x,int y,int fillColor,int oldColor)oldColor)int current;int current;current=getpixel(x,y);current=getpixel(x,y);if(current=oldColor)if(current=oldColor)putpixel(x,y,fillCo
14、lor);putpixel(x,y,fillColor);BoundaryFill4(x+1,y,fillColor,oldColor);BoundaryFill4(x+1,y,fillColor,oldColor);BoundaryFill4(x-1,y,fillColor,oldColor);BoundaryFill4(x-1,y,fillColor,oldColor);BoundaryFill4(x,y+1,fillColor,oldColor);BoundaryFill4(x,y+1,fillColor,oldColor);BoundaryFill4(x,y-1,fillColor,o
15、ldColor);BoundaryFill4(x,y-1,fillColor,oldColor);扫描线种子填充算法利用扫描线的连贯性减少递归次数扫描线种子填充算法种子像素入栈种子像素入栈当栈非空时，重复以下步骤：当栈非空时，重复以下步骤：n n栈顶像素出栈栈顶像素出栈栈顶像素出栈栈顶像素出栈n n沿扫描线对出栈像素的左右像素进行填充，沿扫描线对出栈像素的左右像素进行填充，沿扫描线对出栈像素的左右像素进行填充，沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止直到遇到边界像素为止直到遇到边界像素为止直到遇到边界像素为止n n将上述区间内最左、最右像素记为将上述区间内最左、最右像素记为将
16、上述区间内最左、最右像素记为将上述区间内最左、最右像素记为x xl l和和和和x xr r n n在区间在区间在区间在区间 x xl l,x xr r 中中中中检查与当前扫描线相邻的上检查与当前扫描线相邻的上检查与当前扫描线相邻的上检查与当前扫描线相邻的上下两条扫描线下两条扫描线下两条扫描线下两条扫描线是否全为边界像素、或已填充是否全为边界像素、或已填充是否全为边界像素、或已填充是否全为边界像素、或已填充的像素，若为非边界、未填充的像素，则的像素，若为非边界、未填充的像素，则的像素，若为非边界、未填充的像素，则的像素，若为非边界、未填充的像素，则把把把把每一区间的最右像素取为种子像素入栈每一区
17、间的最右像素取为种子像素入栈每一区间的最右像素取为种子像素入栈每一区间的最右像素取为种子像素入栈 二维光栅图形的混淆与反混淆二维光栅图形的混淆与反混淆混淆现象混淆现象反混淆方法反混淆方法混淆(antialiasing)图形的锯齿状：图形信号连续，光栅显示系统中，离散图形的锯齿状：图形信号连续，光栅显示系统中，离散表示。表示。用离散量用离散量(像素像素)表示连续的量表示连续的量(图形图形)而引起的失真，叫而引起的失真，叫混淆或叫混淆或叫走样走样(aliasing)(aliasing)光栅图形混淆：光栅图形混淆：阶梯状边界；阶梯状边界；图形细节失真；图形细节失真；狭小图形遗失：动画序列中时隐时现，
18、产生闪烁。狭小图形遗失：动画序列中时隐时现，产生闪烁。图形反走样技术（antialiasing）l1.1.从硬件角度提高分辨率从硬件角度提高分辨率n n高分辨率显示器高分辨率显示器l显示器点距减少一倍显示器点距减少一倍l帧缓存容量增加到原来的帧缓存容量增加到原来的4 4倍倍l输带宽提高输带宽提高4 4倍倍l扫描转换花扫描转换花4 4倍时间倍时间l代价高代价高图形反走样技术（antialiasing）l2.2.从软件角度替高分辨率从软件角度替高分辨率n n高分辨率计算，低分辨率显示高分辨率计算，低分辨率显示n n像素细分技术，相当于后置滤波像素细分技术，相当于后置滤波1111算术平均1 22142121加权平均l只能减轻，不能消除只能减轻，不能消除图形反走样技术（antialiasing）3.区域采样技术n n改变边或直线的外观，模糊淡化阶梯改变边或直线的外观，模糊淡化阶梯n n相当于图像的前置滤波相当于图像的前置滤波点有限区域直线有宽度10/15/202210/15/20223232图形反走样技术（antialiasing）8级灰度0面积1/87/8面积1根据相交的面积值决定像素显示的亮度级别10/15/202210/15/20223333