32基本图形生成算法.ppt

第三章 基本图形生成算法实区域填充算法 实区域填充算法 确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内 点在多边形内的包含性检验 检验夹角之和 射线法检验交点数 检验夹角之和 若夹角和为0，则点p在多边形外 夹角如何计算？ 大小：利用余弦定理 方向：令 射线法检验交点数 逐点测试效率低不实用怎么办？ 包围盒法 实区域填充算法分类 扫描线填充算法 扫描线顺序 种子填充算法 内部一个点出发 扫描线填充算法 填充扩大化问题 顶点交点的计数问题 有序边表算法 影响一般扫描线填充算法效率的因素？ 有序边表算法 活性边表的建立 有序边表算法 对每条扫描线建立一个新边表 step1：把新边表NET［i］中的边结点，用插入排序法 插入活性边表AET，使之按X坐标递增顺序排序； step2：遍历AET表，把配对交点之间的区间(左闭右开)上的各象 素(X，Y)，用drawpixel(x,y,color)改写象素颜色值； step3：遍历AET表，把Ymax=i的结点从AET表中删除，并把 Ymax＞i的结果点的X值递增△X； step4：重复各扫描线 有序边表算法 优点： 对每个像素只访问一次 与设备无关 边填充算法(Edge Fill Algorithm) 边填充算法(Edge Fill Algorithm) 优点： 最适合于有帧缓存的显示器 可按任意顺序处理多边形的边 仅访问与该边有交点的扫描线上右方的像素，算法简单 缺点： 对复杂图形，每一像素可能被访问多次，输入/输出量大 图形输出不能与扫描同步进行，只有全部画完才能打印 栅栏填充算法(Fence Fill Algorithm) 引入栅栏的目的？ 种子填充算法 假设多边形区域内至少有一个像素已知 区域连通方式对填充结果的影响 简单的种子填充算法（4连通边界） 种子像素入栈 当栈非空时，重复以下步骤： 栈顶像素出栈 将出栈象素置成填充色 按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈 填充算法演示 4-connected boundary-fill void BoundaryFill4(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); } } 扫描线种子填充算法 利用扫描线的连贯性 减少递归次数 扫描线种子填充算法 种子像素入栈 当栈非空时，重复以下步骤： 栈顶像素出栈 沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止 将上述区间内最左、最右像素记为xl和xr 在区间[xl,xr]中检查与当前扫描线相邻的上下两条扫描线是否全为边界像素、或已填充的像素，若为非边界、未填充的像素，则把每一区间的最右像素取为种子像素入栈 二维光栅图形的混淆与反混淆 混淆现象 反混淆方法 混淆(antialiasing) 图形的锯齿状：图形信号连续，光栅显示系统中，离散表示。 用离散量(像素)表示连续的量(图形)而引起的失真，叫混淆或叫走样(aliasing) 光栅图形混淆： 阶梯状边界； 图形细节失真； 狭小图形遗失：动画序列中时隐时现，产生闪烁。 走样现象举例 不光滑（阶梯状）的图形边界 走样现象举例 图形细节失真 走样现象举例 狭小图形的遗失与动态图形的闪烁 图形反走样技术（antialiasing） 1.从硬件角度提高分辨率 高分辨率显示器 图形反走样技术（antialiasing） 把显示器分辨率提高一倍 直线经过两倍的象素，锯齿也增加一倍 但同时每个阶梯的宽度也减小了一倍 所以显示出的直线段看起来就平直光滑了一些 图形反走样技术（antialiasing） 方法简单，但代价非常大。显示器的水平、竖直分辨率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描换同样大小的图元却要花4倍时间。 而且它也只能减轻而不能消除锯齿问题 图形反走样技术