第3章基本图形生成算法2.ppt

《第3章基本图形生成算法2.ppt》由会员分享，可在线阅读，更多相关《第3章基本图形生成算法2.ppt（33页珍藏版）》请在优知文库上搜索。

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

2、奇数点在多边形之内zx左闭右开包围盒法凸多边形凹多边形逐点测试效率低不实用怎么办？实区域填充算法分类扫描线填充算法扫描线填充算法01 2 3 4 5 6 71234567yx88 9 10扫描线5P4P1P2P3P5扫描线2I1I2I3I4求交：I4,I3,I2,I1排序：I1,I2,I3,I4交点配对：(I1,I2),(I3,I4)区间填色利用图形的空间连贯性和扫描线的连贯性填充扩大化问题解决方法：012345671234567yx012345671234567yxP1P2P3P4012345671234567yx012345671234567yxP1P2P3P4顶点交点的计数问题 5432

3、10P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫描线1I5I6检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数 计数0次计数1次计数2次有序边表算法影响一般扫描线填充算法效率的因素？把多边形所有边放在一个表中，按顺序取出，分别计算与每条扫描线的交点？如何提高效率？建立每条扫描线的活性边表何谓活性边？求交和排序目标是简化交点计算有序边表算法活性边表的建立结点信息活性边表的更新x=1/k有序边表算法对每条扫描线建立一个新边表结点信息yx0 1 2 3 4 5 6 7 8 9 101112345678P6P4P2P5P2P3新边表8.57.56.55.54.5

4、3.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.5step1：把新边表NETi中的边结点，用插入排序法 插入活性边表AET，使之按X坐标递增顺序排序；step2：遍历AET表，把配

5、对交点之间的区间(左闭右开)上的各象 素(X，Y)，用drawpixel(x,y,color)改写象素颜色值；step3：遍历AET表，把Ymax=i的结点从AET表中删除，并把 Ymaxi的结果点的X值递增X；step4：重复各扫描线算法：(对每一条扫描线i)有序边表算法优点：缺点：P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4(a)(b)(c)(d)(e)P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4P5P1P2P3P4(a)(b)(c)(d)(e)P4栅栏线Flood-fill algorithmBo

6、undary-fill algorithm4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果（6754S9328S247938479484795684796847978479847994794796754S9328S799缺点？4-connected boundary-fillvoid BoundaryFill4(int x,int y,int fill,int boundary)int current;current=getpixel(x,y);if(current!=boundary)&(current!=fill)putpixel(x,y,fill);BoundaryFil

7、l4(x+1,y,fill,boundary);BoundaryFill4(x-1,y,fill,boundary);BoundaryFill4(x,y+1,fill,boundary);BoundaryFill4(x,y-1,fill,boundary);4-connected boundary-fillvoid FloodFill4(int x,int y,int fillColor,int oldColor)int current;current=getpixel(x,y);if(current=oldColor)putpixel(x,y,fillColor);BoundaryFill4

8、(x+1,y,fillColor,oldColor);BoundaryFill4(x-1,y,fillColor,oldColor);BoundaryFill4(x,y+1,fillColor,oldColor);BoundaryFill4(x,y-1,fillColor,oldColor);扫描线种子填充算法利用扫描线的连贯性减少递归次数扫描线种子填充算法混淆(antialiasing)图形的锯齿状：图形信号连续，光栅显示系统中，离散表示。用离散量(像素)表示连续的量(图形)而引起的失真，叫混淆或叫(aliasing)光栅图形混淆：阶梯状边界；图形细节失真；狭小图形遗失：动画序列中时隐时现，产生闪烁。图形反走样技术（antialiasing）1.从硬件角度提高分辨率显示器点距减少一倍帧缓存容量增加到原来的4倍输带宽提高4倍扫描转换花4倍时间代价高图形反走样技术（antialiasing）2.从软件角度替高分辨率1111算术平均1 22142121加权平均只能减轻，不能消除图形反走样技术（antialiasing）3.区域采样技术点有限区域直线有宽度图形反走样技术（antialiasing）8级灰度0面积1/87/8面积1根据相交的面积值决定像素显示的亮度级别