第8讲边缘填充.ppt

《第8讲边缘填充.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8讲多边形的扫描转换2021/9/71信息科学与工程学院本节内容安排上节回顾5.4多边形的扫描转换小结、作业2021/9/72信息科学与工程学院上节回顾直线的扫描转换圆的扫描转换椭圆的扫描转换2021/9/73信息科学与工程学院5.4多边形的扫描转换与区域填充在光栅扫描显示器中表示一个区域，仅仅画出其边界是不够的，有时还要填上一定的灰度、色彩。多边形的扫描转换主要是通过确定穿越多边形区域的扫描线的覆盖区间来填充。/适用于多边形区域和多边形拟合的其他简单曲线区域。区域填充是从给定的位置开始涂描直到指定的边界条件为止。/适用于复杂边界的多边形以及交互式绘图系

2、统中。2021/9/74信息科学与工程学院5.4.1多边形的扫描转换多边形的两种表示方法：顶点表示：用多边形的顶点序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。点阵表示是用位于多边形内的像素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。1.什么是多边形的扫描转换P5P0P1P2P3P42021/9/75信息科学与工程学院既然大多数图形应用采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形顶点表示到点阵表示的转换，这种转换就称为扫描转换多边形或多边形的填充，扫描转换多边形或

3、多边形的填充：从多边形顶点表示到点阵表示的转换。也就是从多边形的给定边界出发，求出位于其内部的各个像素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色2021/9/76信息科学与工程学院2.x-扫描线算法基本思想:按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，完成填充工作。根据该原理，此算法可以填充凸的、凹的、带孔的多边形域。P5P0P1P2P3P42021/9/77信息科学与工程学院多边形分为凸多边形、凹多边形、含内环的多边形。①凸多边形：任意两顶点间的连线均在多边形内②凹多边形任意两顶点间的连线有不在多边内形内的部分③

4、含内环的多边形2021/9/78信息科学与工程学院x-扫描线算法原理：对于每条穿越多边形的扫描线，此算法确定扫描线与多边形相交区间的像素点位置。如：y=3算法的核心：必须按x递增顺序排列交点的x的坐标序列。2021/9/79信息科学与工程学院算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从y=ymin到y=ymax，每次用一条扫描线进行填充。对一条扫描线填充的过程可分为四个步骤：a.求交：计算扫描线与多边形各边的交点；b.排序：把所有交点按x值递增顺序排序；c.配对：第一个与第二个，第三个与第四

5、个等等；每对交点代表扫描线与多边形的一个相交区间;d.填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。2021/9/710信息科学与工程学院对下图，试想扫描转换过程？2021/9/711信息科学与工程学院存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。2021/9/712信息科学与工程学院解决：当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。具体解决方法为：检查共享顶点的两条边的另外两个端点的y值，按这两个y值中大于交点y值的个数是0

6、、1、2来决定交点数取0、1、2。2021/9/713信息科学与工程学院011110222填充过程代码2021/9/714信息科学与工程学院x-扫描线算法的缺点x-扫描线算法在处理每条扫描线时，需要与多边形的所有边求交．这样处理效率很低。这是因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。若在处理每条扫描线时，不分青红皂白地把所有边都拿来与扫描线求交，则其由绝大多数计算都是徒劳无用的。因此将x·扫描线算法加以改进，形成改进的有效边表算法，也称为y连贯性算法2021/9/715信息科学与工程学院3.改进的有效边表算法（Y连贯性算法）改进原理：

7、处理一条扫描线时，仅对有效边求交利用扫描线的连贯性利用多边形边的连贯性2021/9/716信息科学与工程学院有效边（ActiveEdge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（ActiveEdgeTable,AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点：xymax1/knextx为当前扫描线与边的交点ymax为边所在的最大扫描线值1/k为从当前扫描线到下一条扫描线间x的增量P5P0P1P2P3P42021/9/717信息科学与工程学院1.4122/5P2P1y=8712-1P0

8、P1795P0P611.591/2P5P62021/9/718信息