5、二维图形填充li.ppt

第5讲 二维图形填充 二维图形填充是面着色的手段，是图形到图象的重要步骤 二维图形填充所要做的就是将图形内部所有的点----内点用指定的颜色表示。 多边形的两种重要表示方法：1、顶点表示法，即用多边形的顶点序列来表示。2、点阵表示法，即用多边形的全体内点来表示。 顶点表示：数学上常用的方法，精确，数据量小，又叫矢量表示 点阵表示：工程上常用的方法，直观，数据量大，又叫栅格表示 流行的4D技术，大量的栅格--矢量转换 多边形的扫描转换 多边形扫描转换是指从多边形的顶点表示到多边形的点阵表示的转换 常用的多边形扫描转换方法有： 逐点判断方法 扫描线算法 边界标志算法 种子填充算法 逐点判断方法 对于屏幕上的每一个像素判断是否内点 内点：多边形内部的点。 扫描转换的实质就是找出所有的内点。 内点的判断方法有： 射线法 累计角度法 编码方法 射线法(1) 从一点出发的射线，若与多边形边界的交点个数为奇数，为内点；偶数，不是内点 射线的方向不是问题，为简便，射线方向定为向右的水平线。这样只要计算射线与非水平线的交点 射线法(2) 即使经过简化，计算量也非常大 要计算射线与每条边的交点 要判断交点是否在该点的右边 要判断交点是否在边的两个端点之间 逐点法的各种方法，原理简单，但割裂了像素之间的关系，导致计算量大，速度太慢。对于判断个别点是否位于多边形内部有效，用来填充多边形不合适。 扫描线算法（1） 扫描线算法充分利用了像素之间的各种关系，即区域的连贯性、扫描线连贯性和边的连贯性，减少了计算量，提高了速度。 区域连贯性 扫描线算法（2） 扫描线的连贯性 一条扫描线与多边形非水平边的交点数为偶数 这些交点从左到右排序，奇数交点与其后的偶数交点之间所有的点都是多边形内点。只要两个相邻交点，就可确定一批内点。 扫描线算法（3） 扫描线与两个非水平边的连接处的交点均为两个重合点，即理论上应有两个交点 解决办法：非水平边上端截取一个单位 实际上每条边不需专门处理，在算法中自动解决 扫描线算法（4） 边的连贯性：相邻扫描线与同一条边的交点坐标在垂直方向相差1，在水平方向相差d,d等于边的斜率的倒数 知道了一个交点(xi,yi)，就可以用加减法算出下一个交点(xi+1,yi+1)=(xi+d,yi+1)。边的两个端点必然属于交点。 扫描线算法（5） 扫描线算法充分利用三个连贯性，通过对有关数据的组织，以很小的计算量，实现对多边形的扫描转换。 扫描线算法对每条非水平边按如下结构组织： ymax:边的上端点的y坐标 x:边的下端点的x坐标 dx:边的斜率的倒数 next:指向下一条边的指针 扫描线算法（6） 建立边表（ET），按下列要求将多边形的每条非水平边的边结构放入ET表： ET表是按边下端点的y坐标对非水平边进行分类的指针数组 下端点的y坐标为i的边归入第i类 有多少条扫描线，就设多少类边 同一类中，各边按x值递增的顺序排列成行 x值相等时就按dx值递增的顺序排列 扫描线算法（7） 例题：建立右图ET表 解：1号边是水平边，去掉 0号边： 2号边： 3号边： 4号边： 5号边： 6号边： 扫描线算法（8） 组织ET表： 扫描线算法（9） 活化边链表AEL:与扫描线相交的边结构组成。 边结构组成情况随扫描线位置的变化而不断变化。 边结构中的x值随扫描线递增不断变化。 扫描线算法（10） 扫描线算法描述如下： 1.建立ET表 2.将扫描线纵坐标y的初值置为ET表非空元素的最小序号 3.置AEL为空 4.执行下列步骤，直到ET、AEL都为空： 如果ET中的第y类非空，将其中所有的边取出并插入AEL 扫描线算法描述如下： 如果有新的插入AEL,则对AEL各边排序 对AEL中的边两两配对，每对边中的x取整，获得有效填充区段，并填充 将当前扫描线纵坐标y值递增1 将AEL中满足y=ymax的边删除 对AEL中剩下的边的x字段作x=x+dx操作 练习一 练习二 p56 边界标志算法(1) 边界标志算法(2) 边界标志算法(3) 边界标志算法(4) 种子填充算法 面着色的另一类算法是种子填充算法，与扫描转换的区别在于：要求区域有一个连通的边界，需要一颗种子点。 适合于已经画出大量边界线的场合 适合于人机交互操作方式，或者事先保留了种子点 最常用的是递归和扫描线种子填充算法 递归填充算法(1)  递归种子填充算法（2） 递归种子填充算法（3） 扫描线种子填充算法（1） 具体算法：教材p64 堆栈的概念：堆栈是计算机领域常用的概念，是一个存储区，后进先出，先进后出 扫描线种子填充算法（2） 扫描线种子填充过程说明 * * 1 2 3 4 5 两条扫描线之间的区域分割成若干个相邻区域 两个相邻区域分别分属