第章多边形填充.ppt

苏大计算机科学与技术学院 第三章 二维图形生成技术 扫描转换矩形（1/2） 方法： 扫描转换矩形（2/2） 问题： 矩形是简单的多边形，那么为什么要单独处理矩形？ 比一般多边形可简化计算。 应用非常多，如窗口系统。 共享边界如何处理？ 原则：左闭右开，下闭上开 扫描转换多边形 多边形的表示方法 顶点表示 点阵表示 顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。 点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。 扫描转换多边形 多边形的种类 凸多边形：指任意两顶点间的连线均在多边形内 凹多边形：指任意两顶点间的连线有不在多边形内的部分 含内环的多边形：指多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相交 扫描转换多边形 多边形的扫描转换 把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。 扫描转换多边形 逐点判断法 扫描线算法 边缘填充算法 逐点判断法 逐个判断象素并确定它们是否在多边形之内的点的集合 如何判断点在多边形的内外关系？ 射线法 累计角度法 编码法 优缺点 优点：逐点判断法程序简单 缺点：速度太慢，效率低。 逐点判断法算法 射线法 步骤： 从待判别点v发出射线 求交点个数k k的奇偶性决定了点与多边形的内外关系，交点个数为奇数，则该点位于多边形的内部；否则该点位于多边形之外。 奇异情况处理 奇异情况出现在射线恰好经过多边形的顶点的时候。 解决方法：左闭右开或者下闭上开 累计角度法 步骤 从v点向多边形P顶点发出射线，形成有向角 计算有向角的和，得出结论 预处理 离散计算方法：编码方法 编码方法（累计角度方法的离散方法） Step: 1 预处理，测试点在边上否？ 2 V为中点作局部坐标系,对象限按逆时针（或顺时针）编码； 3 顶点编码Ipi， 4 边编码PiPi+1: △PiPi+1=Ipi+1-Ipi 5 计算∑△PiPi+1 （其中△PnPn+1 = △PnP0)： 若 ∑ 为0, V在P外；若 ∑ 为+/-4，V 在P内； 扫描线算法 目标： 利用相邻像素之间的连贯性，提高算法效率 处理对象： 非自交多边形 （边与边之间除了顶点外无其它交点） 扫描线算法 基本思想： 用水平扫描线从上到下扫描由点线段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，完成转换工作。 对于一条扫描线填充过程可以分为四个步骤： 求交 排序 配对 填色 扫描线算法 要求：一条扫描线与多边形的边 有偶数个交点 交点的取整规则 要求：使生成的像素全部位于多边形之内 用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用 假定非水平边与扫描线y=e相交，交点的横坐标为x，规则如下 交点的取整规则 规则1： X为小数，即交点落于扫描线上两个相邻像素之间 解决方法： (a)交点位于左边之上，向右取整 (b)交点位于右边之上，向左取整 交点的取整规则 规则2： 边界上象素的取舍问题，避免填充扩大化。 解决方法： 边界象素：规定落在右、上边界的象素不予填充。 具体实现，对扫描线与多边形的相交区间左闭右开 交点的取整规则 规则3： 扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。 解决方法： 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 交点取舍例子 扫描线与多边形相交的边分别位于扫描线的两侧，则计一个交点，如点P5，P6。 扫描线与多边形相交的边分别位于扫描线同侧，且 yiyi-1，yiyi+1，则计2个交点(填色)，如P2。若 yiyi-1，yiyi+1，则计0个交点(不填色)，如P1。 扫描线与多边形边界重合 (当要区分边界和边界内区域时需特殊处理)，则计1个交点。　 扫描线算法 几个概念 边的连贯性： 某条边与当前扫描线相交，也可能与下一条扫描线相交； 扫描线的连贯性： 当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序可能相同或类似； 区间连贯性： 同一区间上的像素取同一颜色属性 区域的连贯性 1）梯形的两底边分