多边形的转换与区域填充ppt课件.ppt

《多边形的转换与区域填充ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021年8月4日计算机图形学13.4多边形的扫描转换与区域填充多边形扫描转换与区域填充可以统称区域填充，就是如何用颜色或图案来填充一个二维区域。填充主要做两件工作：一是确定需要填充的范围，二是确定填充的内容。一般区域填充指的是已知区域内一个种子，然后由种子向周围蔓延填充规定区域。方法：扫描线法：x-扫描线法-〉有序边表法，边填充算法种子填充算法（区域填充）2021年8月4日计算机图形学23.4.1扫描转换（扫描线）法多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设

2、置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。三种方法：扫描线算法边填充算法边界标志法2021年8月4日计算机图形学3多边形分类多边形分为凸多边形、凹多边形、含内环的多边形。2021年8月4日计算机图形学4多边形表示多边形的表示方法顶点表示点阵表示顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。2021年8月4日计算机图形学53.4.1.1扫描线算法-x扫描线法扫描线算法目标：利用相邻像素

3、之间的连贯性，提高算法效率处理对象：非自交多边形（边与边之间除了顶点外无其它交点）2021年8月4日计算机图形学6步骤(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤：①计算扫描线与多边形各边的交点。②对求得的交点进行排序。③奇偶配对求出扫描线与多边形的相交区间。④对这些相交区间填充色。2021年8月4日计算机图形学7需要解决的几个问题扫描线与多边形顶点相交时交点的取舍问题多边形边界上像素点的取舍问题水平边的

4、处理减少求交运算问题2021年8月4日计算机图形学8需要解决的几个问题（一）一、当扫描线与多边形顶点相交时，交点的取舍问题。解决：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。2021年8月4日计算机图形学9具体实现时只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。2021年8月4日计算机图形学10xy213456789111234567891011121012与多边形顶点相交的交点的处理2021

5、年8月4日计算机图形学11011110222与扫描线相交的多边形顶点的交点数2021年8月4日计算机图形学12需要解决的几个问题（二）二、边界上象素的取舍问题，避免填充扩大化。解决方法：边界象素：规定落在右上边界的象素不予填充。具体实现时，只要对扫描线与多边形的相交区间实行：左闭右开（左边界像素填充，右边界像素不填充）下闭上开（下边界像素填充，上边界像素不填充）属于谁？2021年8月4日计算机图形学13需要解决的几个问题（三）三、水平边的处理（与扫描线重合）将水平边画出后删去，不参加求交，即求交后的操作（但是在计算交点个数时算作一个点）。2021年8月4

6、日计算机图形学14需要解决的几个问题（四）减少求交算法：x-扫描线法在处理每条扫描线时需要与多边形的所有边求交，而实际上一条扫描线往往只与少数几条边相交，因此降低了效率，于是提出了改进算法—有序边表法，也称y连贯性算法。2021年8月4日计算机图形学153.4.1.2扫描转换法-有序边表法该法与x-扫描线法基本过程一样，只是在处理求交计算时作了改进。2021年8月4日计算机图形学16改进思路可以从以下方面考虑：1在处理一条扫描线时，仅对与它相交的边（有效边）进行求交运算，于是可以构造活性边表。2考虑扫描描线的连贯性，即当前扫描线与各边的交点顺序与下一条扫

7、描线与各边的交点顺序很可能相同或者相似。3多边形边的连贯性，即当一条边与当前扫描线相交时，它可能也与下一条扫描线相交。2021年8月4日计算机图形学17所有的边和扫描线求交，效率很低。因为一条扫描线往往只和少数几条边相交。如何判断多边形的一条边与扫描线是否相交？有效边（ActiveEdge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（ActiveEdgeTable,AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效（活性）边表。2021年8月4日计算机图形学18数据结构与实现步骤只需对当前扫描线的活动边表作更新

8、，即可得到下一条扫描线的活动边表。2021年8月4日计算机图形学19如何计算下一