《32基本图形生成算法.ppt》由会员分享，可在线阅读，更多相关《32基本图形生成算法.ppt（39页珍藏版）》请在三一文库上搜索。
1、,第三章 基本图形生成算法 实区域填充算法,实区域填充算法,确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内,解决的主要问题是什么？,图案填充还有一个什么象素填什么颜色的问题 曲线围成的区域，可用多边形逼近,点在多边形内的包含性检验,检验夹角之和 射线法检验交点数,检验夹角之和,若夹角和为0，则点p在多边形外,若夹角和为360，则点p在多边形内,夹角如何计算？,大小：利用余弦定理 方向：令,当TBP斜率，为顺时针角,当T0时，AP斜率BP斜率，为逆时针角,射线法检验交点数,交点数=偶数（包括0） 点在多边形之外,交点数=奇数 点在多边形之内,左闭右开,包围盒法,凸多边形,凹多边形,逐
2、点测试效率低不实用怎么办？,实区域填充算法分类,扫描线填充算法 扫描线顺序 种子填充算法 内部一个点出发,扫描线填充算法,求交：I4, I3, I2, I1 排序：I1, I2, I3, I4 交点配对：(I1, I2), (I3, I4) 区间填色,利用图形的空间连贯性和扫描线的连贯性,填充扩大化问题,解决方法： 取中心扫描线y+0.5 检查交点右方像素的中心是否落在区间内 xlx+0.5xr,11,2019/8/29,顶点交点的计数问题,检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数,计数0次,计数1次,计数2次,有序边表算法,影响一般扫描线填充算法效率的因素？,把多边形所
3、有边放在一个表中，按顺序取出，分别计算与每条扫描线的交点？,如何提高效率？,建立每条扫描线的活性边表,何谓活性边？,求交和排序,目标是简化交点计算,有序边表算法,活性边表的建立,结点信息 x：当前扫描线与边的交点 x：从当前扫描线到下一条扫描线之间的x增量 ymax：边所交的最高扫描线号,活性边表的更新,新边插入 旧边删除,x =1/k,有序边表算法,对每条扫描线建立一个新边表,结点信息 x0：扫描线与边的初始交点 x：从当前扫描线到下一条扫描线之间的x增量 ymax：边所交的最高扫描线号,活性边表,step1：把新边表NETi中的边结点，用插入排序法 插入活性边表AET，使之按X坐标递增顺序
4、排序； step2：遍历AET表，把配对交点之间的区间(左闭右开)上的各象 素(X，Y)，用drawpixel(x,y,color)改写象素颜色值； step3：遍历AET表，把Ymax=i的结点从AET表中删除，并把 Ymaxi的结果点的X值递增X； step4：重复各扫描线,算法：(对每一条扫描线i),有序边表算法,优点： 对每个像素只访问一次 与设备无关,缺点： 数据结构复杂 只适合软件实现,边填充算法 (Edge Fill Algorithm),边填充算法 (Edge Fill Algorithm),优点： 最适合于有帧缓存的显示器 可按任意顺序处理多边形的边 仅访问与该边有交点的扫描
5、线上右方的像素，算法简单 缺点： 对复杂图形，每一像素可能被访问多次，输入/输出量大 图形输出不能与扫描同步进行，只有全部画完才能打印,栅栏填充算法 (Fence Fill Algorithm),引入栅栏的目的？,21,2019/8/29,种子填充算法,假设多边形区域内至少有一个像素已知,区域定义法： Interior-defined Boundary-defined,Flood-fill algorithm,Boundary-fill algorithm,区域连通方式： 4-connected 8-connected,区域连通方式对填充结果的影响,4连通区域边界填充算法的填充结果,8连通区域
6、边界填充算法的填充结果,简单的种子填充算法 （4连通边界）,种子像素入栈 当栈非空时，重复以下步骤： 栈顶像素出栈 将出栈象素置成填充色 按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈,填充算法演示,缺点？,4-connected boundary-fill void BoundaryFill4(int x,int y,int fill,int boundary) int current; current = getpixel(x, y); if (current != boundary) ,4-connected boundary-fill
7、 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); BoundaryFill4(x, y-1,
8、 fillColor, oldColor); ,扫描线种子填充算法,利用扫描线的连贯性 减少递归次数,扫描线种子填充算法,种子像素入栈 当栈非空时，重复以下步骤： 栈顶像素出栈 沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止 将上述区间内最左、最右像素记为xl和xr 在区间xl,xr中检查与当前扫描线相邻的上下两条扫描线是否全为边界像素、或已填充的像素，若为非边界、未填充的像素，则把每一区间的最右像素取为种子像素入栈,二维光栅图形的混淆与反混淆,混淆现象 反混淆方法,混淆(antialiasing),图形的锯齿状：图形信号连续，光栅显示系统中，离散表示。 用离散量(像素)表示连续的
9、量(图形)而引起的失真，叫混淆或叫走样(aliasing) 光栅图形混淆： 阶梯状边界； 图形细节失真； 狭小图形遗失：动画序列中时隐时现，产生闪烁。,走样现象举例,不光滑（阶梯状）的图形边界,走样现象举例,图形细节失真,走样现象举例,狭小图形的遗失与动态图形的闪烁,图形反走样技术（antialiasing）,1.从硬件角度提高分辨率 高分辨率显示器,显示器点距减少一倍 帧缓存容量增加到原来的4倍 输带宽提高4倍 扫描转换花4倍时间,代价高,图形反走样技术（antialiasing）,把显示器分辨率提高一倍 直线经过两倍的象素，锯齿也增加一倍 但同时每个阶梯的宽度也减小了一倍 所以显示出的直线
10、段看起来就平直光滑了一些,图形反走样技术（antialiasing）,方法简单，但代价非常大。显示器的水平、竖直分辨率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描换同样大小的图元却要花4倍时间。 而且它也只能减轻而不能消除锯齿问题,图形反走样技术（antialiasing）,2.从软件角度提高分辨率 高分辨率计算，低分辨率显示 像素细分技术，相当于后置滤波,只能减轻，不能消除,37,2019/8/29,图形反走样技术（antialiasing）,3.区域采样技术 改变边或直线的外观，模糊淡化阶梯 相当于图像的前置滤波,直线有宽度,38,2019/8/29,图形反走样技术（antialiasing）,0面积1/8,7/8面积1,根据相交的面积值决定像素显示的亮度级别,图形反走样技术（antialiasing）,基本思想 每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。,有宽度的线条轮廓,象素相交的五种情况及用于计算面积的量,