计算机图形学 CG043填充ppt课件.ppt

《计算机图形学 CG043填充ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基本图形的扫描算法4.3区域填充多边形有两种重要的表示方法：顶点表示和点阵表示把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。4.3区域填充在这一节中将讨论图形系统中新的图元——多边形研究有关多边形的概念以及如何表示多边形学习逐点判断算法、扫描线算法、边填充算法，种子填充算法等多边形填充的方法，及区域填充图案算法。1.多边形所谓多边形就是用一系列首尾相连的线段构成的图形，这些组成多边形边界的线段称为多边形的边，多边形的边的端点称为多边形的顶点，一般来说一个多边形应是封闭的。多边形又可以分成两大类：凸多边形和凹多边形。所谓凸多边形是指这样一类多边形：如果在多边

2、形内任选两个点，将这两个点用线段连接后，此线段上所有的点都在多边形内，这就是凸多边形。而凹多边形就是非凸多边形。凸凹多边形2.点是否在多边形内部的检验为了对多边形内部的象素点赋值，首先要解决如何判断一个点是否在多边形内部。判断的方法是，先在多边形外部找一个点，然后用线段连接此点和有疑问的点，计算出此线段与多边形边界相交的次数，如果交点的数目为奇数，则疑问点在多边形内部；如果为偶数，此点在多边形外部。图示P’2324图示11332问题在计算交点时，如果交点恰恰就是多边形的顶点，必须小心处理。此时要观察在此顶点相遇的两条边,如果这两条边的其余二个顶点在新构成线段的:同一侧，应认为此线段与多边

3、形相交二次；异侧，则认为此线段与多边形相交一次。解决P’23242解决1133213.连贯性原理1）边的连贯性当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交。2）扫描线的连贯性当前线与各边的交点顺序与下一条扫描线与各边的交点很可能相同或非常类似。3）区间的连贯性Yk+1yk4.填充算法1）扫描线算法充分利用了扫描线连贯性原理，避免了针对于象素点的逐点判别，有效地选择象素点来进行多边形的填充。4.填充算法----扫描线算法扫描线算法的基本思想：对给定的多边形，用一组水平(垂直)的扫描线进行扫描，对每一条扫描线均可求出与多边形边的交点；这些交点将扫描线分割成落在多边形内部和落在

4、多边形外部的线段，二者相间排列；将落在多边形内部的扫描线段上的所有象素点赋以给定的色彩值。可见，算法中不需要检验每一个象素点，而只考虑与多边形边相交的交点分割后的扫描线段。多边形与若干扫描线A03421123456781011x5678y9P3(11,3)P4(11,8)P2(5,1)P1(2,2)P5(5,5)P6(2,7)BCDGFE返回算法求解对于一条扫描线的处理，可以分为四个步骤：（1）求交点：首先求出扫描线与多边形各边的交点（2）交点排序：将这些交点按X坐标递增顺序排序（3）交点匹配：即从左到右确定落在多边形内部的那些线段；（4）区间填充：填充落在多边形内部的线段。两个特殊问题：

5、一是当扫描线与多边形顶点相交时，交点的取舍问题；二是多边形边界上像素的取舍问题。问题一的解决扫描线交于一个顶点，而共享顶点的二条边分别落在扫描线的两边。这时交点只算一个；当共享交点的二条边在扫描线的同一边，这时交点作为0个或者2个(取决于该点是多边形的局部最高点还是局部的最低点)。具体实现时，只需检查顶点两条边的另外两个端点的y值。按这两个y值中大于顶/交点y值的个数是0、1或2来决定是取零个、一个、还是二个。问题二的解决规定落在右/上边界的像素不予以填充，而落在左/下边界的像素予以填充。问题一的解决用于保证的交点正确配对，而问题二的解决用于避免填充扩大化。y321x412340算法求解P

6、1P2P3P4P5P6求扫描线与多边形边交点的方法最简单的方法是将多边形的所有边放在一个表中，在处理每条扫描线时，从表中顺序取出所有的边，分别求这些边与扫描线的交点。这样做的结果将做一些无益的求交点动作，因为扫描线并不一定与多边形的边相交，扫描线只与部分甚至较少的边相交，因此在进行扫描线与多边形边求交点时，应只求那些与扫描线相交的边的交点。活性边表（AEL--ActiveEdgeList）把与当前扫描线相交的边称活化边并把它们按与扫描线交点X坐标递增的顺序存放在一个链表中，称此链表为活性边表。活性边表每个节点存放对应边的有关信息。活性边表（AEL--ActiveEdgeList）根据边和扫

7、描线的连贯性更新AEL：假定当前扫描线与多边形某一条边的交点的X坐标为x，则下一条扫描线与该边的交点只要加一个增量△x。设该边的直线方程为：ax+by+c=0，当前若y＝yi，x=xi；则当y=yi+1时，xi+1=xi-b/a=xi+Δx(其中Δx=-b/a为常数)活性边表（AEL--ActiveEdgeList）使用增量法计算时，我们需要知道一条边何时不再与下一条扫描线相交，以便及时把它从活性边表中删除出去：边的最大