图形学CG第4讲扫描转换.ppt

* * 边的活化链表(AEL): 由与当前扫描线相交的所有多边形的边组成,它记录了多边形的边沿扫描线的交点序列,并根据递推公式不断地刷新交点序列. * * 算法步骤如下: (1)初始化：构造边表，AET表置空； (2)将第一个不空的ET表中的边与AET表合并； (3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边； (4)yi+1=yi+1,根据xi+1=xi+1/m计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表； (5)AET表不为空则转(3)，否则结束。 * * 扫描线算法的优点： 这是一种非常有效的算法，它使所显示的每—个象素只访问一次，输入、输出的要求可降为最少。由于该算法与输入、输出的细节无关，因而它也与设备无关。 扫描线算法的主要缺点： 对各种表的维持和排序的开销太大，适合软件实现而不适合硬件实现。 7.2 区域填充 填充条件： 已经表示成点阵形式的填充图形，它是象素的集合。 定义： 指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。 算法要求： 区域是连通的。一个封闭区域确定以后,填充要解决的问题是如何确定填充的象素以及如何高效地填充。 * * 1. 区域的表示 区域表示方法：内点表示和边界表示。 内点表示:枚举出区域内部的所有象素，内部的所有象素着同一个颜色，边界象素着与内部象素不同的颜色。 边界表示:枚举出边界上所有的象素，边界上的所有象素着同一颜色，内部象素着与边界象素不同的颜色。 * * 区域:是指已经表示成点阵形式的填充图形，它是像素集合.。 区域的连通方式:4-邻接点和8-邻接点 * * (b)p的8-邻接点 4 4 p 4 4 8 8 8 8 8 p 8 8 8 (a)p的4-邻接点 图4-13 邻接点的定义 * * 图3.3.2 区域的边界表示和内点表示 (a)以边界表示的4-连通区域 (b)以内点表示的4-连通区域 (c)以边界表示的8-连通区域 (d)以内点表示的8-连通区域 2.递归算法 在要填充的区域内取一点(X，Y),将该点的当前颜色记为oldcolor,用要填充的颜色newcolor去取代(内点表示). 递归函数如下： procedure flood-fill(X,Y,oldcolor,newcolor:integer); begin if getpixel(framebuffer,x,y)=oldcolor then begin setpixel(framebuffer,x,y,newcolor); flood-fill(X,Y+1,oldcolor,newcolor); flood-fill(X,Y-1,oldcolor,newcolor); flood-fill(X-1,Y,oldcolor,newcolor); flood-fill(X+1,Y,oldcolor,newcolor); end end * * 3.栈结构算法 递归算法的缺点:递归算法的原理和程序都很简单，但由于多次递归，费时费内存，计算机的效率将非常低。 栈结构算法: 算法的输入：种子点坐标(x,y)，填充色和边界颜色。 栈结构实现4-连通边界填充算法的算法步骤为： * * * * 算法原理： 种子像素入栈；当栈非空时重复执行如下三步操作： （1） 找顶像素出栈； （2） 将出栈像素置成填充色； （3） 按某一个顺序如左、上、右、下检查与出栈像素相邻的四个像素，若其中某个像素还是区域中原有颜色，或不为边界，则把该像素入栈。 * * ? ? 1 ? ? ? ? ? ? ? ? ? ? ? 3 3 4 5 6 ? ? ? ? ? ? 2 9 9 9 9 9 9 8 ? ? ? ? 4 4 4 4 4 4 4 4 4 ? ? ? 6 6 6 6 6 6 6 6 6 6 ? s 8 1 8 8 8 8 8 8 8 8 8 s 2 1 3 4 5 6 9 8 4 6 8 优点:可以用于填充带有内孔的平面区域。 缺点:把太多的象素压入堆栈 改进 通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。 * * 3 扫描线算法 4-连通边界填充算法步骤： 种子象素入栈；当栈非空时作如下三步操作： 1 栈顶像素出栈； 2 沿扫描线对出栈像素的左右像素进行填充，直至