Class5_多边形的扫描转换和区域填充.pptxVIP

信息科学与工程学院 牛冬梅 12J904 ise_niudm@第三章 基本图形生成算法 -多边形的扫描转换和区域填充 在光栅扫描显示器中表示一个区域，仅仅画出其边界是不够的，有时还要填上一定的灰度、色彩。多边形的扫描转换主要是通过确定穿越多边形区域的扫描线的覆盖区间来填充。适用于多边形区域和多边形拟合的其他简单曲线区域。区域填充是从给定的位置开始涂描直到指定的边界条件为止。适用于复杂边界的多边形以及交互式绘图系统中。3.4 多边形的扫描转换和区域填充 3.4.1 多边形的扫描转换3.4.2 区域填充3.4.3 反走样3.4 多边形的扫描转换和区域填充 3.4.1 多边形的扫描转换3.4.2 区域填充3.4.3 反走样3.4 多边形的扫描转换和区域填充 多边形的两种表示方法：顶点表示：用多边形的顶点序列来刻划多边形。直观、几何意义强、占内存少，易于进行几何变换；但由于它没有明确指出哪些像素在多边形内，故不能直接用于面着色。点阵表示: 是用位于多边形内的像素的集合来刻划多边形。便于运用帧缓冲存储器表示图形，易于面着色；但是失去了许多重要的几何信息（比如边界、顶点）。3.4.1 多边形的扫描转换P1P2P3P4P5顶点表示P6 点阵表示P1 P2 P3 P4 P5 P6 多边形的分类 可分为：凸多边形、凹多边形、含内环的多边形凸多边形：任意两顶点间的连线均在多边形内凹多边形：存在两顶点间的连线有不在多边形内的部分含内环的多边形3.4.1 多边形的扫描转换 既然大多数图形应用采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形顶点表示到点阵表示的转换，这种转换就称为扫描转换多边形或多边形的填充。定义：多边形的扫描转换／多边形的填充：从多边形顶点表示到点阵表示的转换。也就是从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色。3.4.1 多边形的扫描转换 x-扫描线算法 改进的有效边表算法（也叫：y连贯性算法）3.4.1 多边形的扫描转换 基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。根据该原理，此算法可以填充凸的、凹的、含内环的多边形域。 x-扫描线算法xy213456789111234567891011121012 对于每条穿越多边形的扫描线，x-扫描线算法确定扫描线与多边形边相交区间的像素点位置。 x-扫描线算法xy213456789111234567891011121012(3,1)(6,5)(8,1)(1,7)(3,12)(7,8)(12,9)如扫描线y=3与多边形的边界相交于4点,因而对(2,3),(4,3), (7,3),(9,3)对应的像素点进行着色。算法的核心是需按x递增顺序排列交点的x坐标序列。 ? x-扫描线算法算法步骤 对下图，试想扫描转换的过程？ x-扫描线算法xy213456789111234567891011121012(3,1)(6,5)(8,1)(1,7)(3,12)(7,8)(12,9) 存在问题 当扫描线与多边形顶点相交时，会出现异常情况。 x-扫描线算法xy213456789111234567891011121012在填充过程，当扫描线与多边形顶点相交时，交点的取舍问题??（交点的个数应保证为偶数个）。 解决方案 当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。 x-扫描线算法xy213456789111234567891011121012具体解决方法为：检查共享顶点的两条边的另外两个端点的y值，按这两个y值中大于交点y值的个数是0、1、2来决定交点数取0、1、2。2201 x-扫描线算法01111022220 x-扫描线算法的缺点 效率低。x-扫描线算法在处理每条扫描线时，需要与多边形的所有边求交，这样处理效率很低。这是因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。若在处理每条扫描线时，不分青红皂白地把所有边都拿来与扫描线求交，则其由绝大多数计算都是徒劳无用的。 x-扫描线算法最理想的算法是不求交（排序、配对、填色总是要的）！如果不求交，那会极大提高算法的效率。若有1024条扫描线，绘制一个100多边形，需要求多少次交？ xi,yixi+1,yi+1? 改进的有效边表算法（y连贯性算法）11/k 改进原理在处理一条扫描线时，仅对与它相交的多边形的边（有效边）进行求交运算。需要考虑扫描线的连贯性，即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似，这样在