【学习课件】第3章基本图形生成算法

1、实区域填充算法哈尔滨工业大学计算机学院苏小红第三章 基本图形生成算法精选课件实区域填充算法 确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内解决的主要问题是什么？图案填充还有一个什么象素填什么颜色的问题曲线围成的区域，可用多边形逼近 精选课件点在多边形内的包含性检验检验夹角之和射线法检验交点数精选课件检验夹角之和若夹角和为0，则点p在多边形外若夹角和为360，则点p在多边形内ABCDEPABCDEP精选课件夹角如何计算？大小：利用余弦定理方向：令当TBP斜率，为顺时针角当T0时，AP斜率BP斜率，为逆时针角zxABPzxBAP精选课件射线法检验交点数ABCDEPABCDEP交点数=偶

2、数（包括0）点在多边形之外交点数=奇数点在多边形之内zx左闭右开精选课件包围盒法凸多边形凹多边形逐点测试效率低不实用怎么办？精选课件实区域填充算法分类扫描线填充算法扫描线顺序种子填充算法内部一个点出发精选课件扫描线填充算法求交：I4, I3, I2, I1排序：I1, I2, I3, I4交点配对：(I1, I2), (I3, I4)区间填色利用图形的空间连贯性和扫描线的连贯性精选课件填充扩大化问题解决方法：取中心扫描线y+0.5检查交点右方像素的中心是否落在区间内 xlx+0.5xr精选课件顶点交点的计数问题 543210P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫

3、描线1I5I6检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数 计数0次计数1次计数2次7/28/202211精选课件有序边表算法影响一般扫描线填充算法效率的因素？把多边形所有边放在一个表中，按顺序取出，分别计算与每条扫描线的交点？如何提高效率？建立每条扫描线的活性边表何谓活性边？求交和排序目标是简化交点计算精选课件有序边表算法活性边表的建立结点信息x：当前扫描线与边的交点x：从当前扫描线到下一条扫描线之间的x增量ymax：边所交的最高扫描线号活性边表的更新新边插入旧边删除x =1/k精选课件有序边表算法对每条扫描线建立一个新边表结点信息x0：扫描线与边的初始交点x：从当前扫描线

4、到下一条扫描线之间的x增量ymax：边所交的最高扫描线号边结点不必排序精选课件yx0123456789101112345678P6P4P2P5P2P3新边表8.57.56.55.54.53.52.51.50.5528.5-1.5711082075-32.533P4P5P5P6P3P4P6P1P1P2P2P3活性边表5-32.533P1P2P2P3y=1.5207.833P6P1P2P3y=2.5207.1108P6P1P3P4y=3.5528.P4P51108P3P45-1.57P5P6207.P6P1y=5.5728.P4P51108P3P43.5-1.57P5P6207.P6P1y=6.5

5、528.P4P51108P3P4y=7.5精选课件step1：把新边表NETi中的边结点，用插入排序法 插入活性边表AET，使之按X坐标递增顺序排序；step2：遍历AET表，把配对交点之间的区间(左闭右开)上的各象 素(X，Y)，用drawpixel(x,y,color)改写象素颜色值；step3：遍历AET表，把Ymax=i的结点从AET表中删除，并把 Ymaxi的结果点的X值递增X；step4：重复各扫描线算法：(对每一条扫描线i)精选课件有序边表算法优点：对每个像素只访问一次与设备无关缺点：数据结构复杂只适合软件实现精选课件边填充算法(Edge Fill Algorithm) 精选课件

6、边填充算法(Edge Fill Algorithm) 优点：最适合于有帧缓存的显示器可按任意顺序处理多边形的边仅访问与该边有交点的扫描线上右方的像素，算法简单缺点：对复杂图形，每一像素可能被访问多次，输入/输出量大图形输出不能与扫描同步进行，只有全部画完才能打印精选课件栅栏填充算法(Fence Fill Algorithm) 引入栅栏的目的？精选课件种子填充算法假设多边形区域内至少有一个像素已知区域定义法：Interior-definedBoundary-definedFlood-fill algorithmBoundary-fill algorithm区域连通方式：4-connected8-

7、connected7/28/202221精选课件区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果精选课件简单的种子填充算法（4连通边界）种子像素入栈当栈非空时，重复以下步骤：栈顶像素出栈将出栈象素置成填充色 按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈 精选课件填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799缺点？精选课件4-connected boundary-fill void BoundaryFill

8、4(int x,int y,int fill,int boundary) int current; current = getpixel(x, y); if (current != boundary) & (current != fill) putpixel(x, y, fill); BoundaryFill4(x+1, y, fill, boundary); BoundaryFill4(x-1, y, fill, boundary); BoundaryFill4(x, y+1, fill, boundary); BoundaryFill4(x, y-1, fill, boundary); 4

9、-connected boundary-fill void FloodFill4(int x,int y,int fillColor,int oldColor) int current; current = getpixel(x, y); if (current = oldColor) putpixel(x, y, fillColor); BoundaryFill4(x+1, y, fillColor, oldColor); BoundaryFill4(x-1, y, fillColor, oldColor); BoundaryFill4(x, y+1, fillColor, oldColor

10、); BoundaryFill4(x, y-1, fillColor, oldColor); 精选课件扫描线种子填充算法利用扫描线的连贯性减少递归次数精选课件扫描线种子填充算法种子像素入栈当栈非空时，重复以下步骤：栈顶像素出栈沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止将上述区间内最左、最右像素记为xl和xr 在区间xl,xr中检查与当前扫描线相邻的上下两条扫描线是否全为边界像素、或已填充的像素，若为非边界、未填充的像素，则把每一区间的最右像素取为种子像素入栈 精选课件二维光栅图形的混淆与反混淆混淆现象反混淆方法精选课件混淆(antialiasing)图形的锯齿状：图形信号连续，光栅显示系统中，离散表示。用离散量(像素)表示连续的量(图形)而引起的失真，叫混淆或叫走样(aliasing)光栅图形混淆：阶梯状边界；图形细节失真；狭小图形遗失：动画序列中时隐时现，产生闪烁。精选课件图形反走样技术（antialiasing）1.从硬件角度提高分辨率高分辨率显示器显示器点距减少一倍帧缓存容量增加到原来的4倍输带宽提高4倍扫描转换花4倍时间代价高精选课件图形反走样技术（antialiasing）2.从软件角度替高分辨率高分辨率计算，低分辨率显示像素细分技术，相当于后置滤波1111算术平均122142