扫描线与多边形的顶点相交时.PPT

* 谢谢! IBM Confidential * * / 56 扫描线算法： 交点的取整规则 规则2： 边界上象素的取舍问题，避免填充扩大化; 解决方法： 边界象素：规定落在右上边界的象素不予填充； 具体实现时，只要对扫描线与多边形的相交区间左闭右开； 多边形的扫描转换：扫描线算法： * * / 56 扫描线算法： 交点的取整规则 规则3： 扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。 解决方法： 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 多边形的扫描转换：扫描线算法： * * / 56 计算扫描线与多边形各边的交点：最简单的方法： 将多边形的所有边放在一个表中； 缺点：效率低 改进的有效边表算法（Y连贯性算法） 改进原理： 处理一条扫描线时，仅对有效边求交； 利用扫描线的连贯性； 利用多边形边的连贯性； 多边形的扫描转换：扫描线算法： * * / 56 活性边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。 活性边表（Active Edge Table, AET）：把活性边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称活性边表。 活性边表的每个结点： x ymax 1/k next 边表（Edge Table）的构造（1/2）： (1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，对应多边形覆盖的每一条扫描线。 (2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。 多边形的扫描转换：扫描线算法： * * / 56 边表（Edge Table）的构造（2/2）： (3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。 x|ymin ymax 1/k NEXT (4)同一桶中若干条边按X|ymin由小到大排序，若X| ymin相等，则按照1/k由小到大排序。 多边形的扫描转换：扫描线算法： * * / 56 多边形的扫描转换：扫描线算法： 算法涉及的数据结构: 1）活性边：与当前扫描线相交的边。按交点x的增量顺序存放在一个链表中；该链表称作活性边表（AET); typedef struct {int ymax; float x,deltax; Edge *nextEdge; }Edge; AET的结点信息： Ymax: 所交边的最高扫描线号; X：当前扫描线与边的交点的x坐标; △X：边的斜率的倒数; Nextage: 下一条边的指针; * * / 56 2）新边表:按照边的下端点y坐标对非水平边进行分类的指针数组,下端点y坐标值等于i的边属于第i类; 作用：方便活性边表的建立与更新。 typedef struct {int ymax; float x,deltax; Edge *nextEdge; }Edge; 作用:避免盲目求交: 处理一条扫描线时，为求出它与多边形边的所有交点，必须将它与所有的边进行求交测试。实际上只有某几条边与该扫描线有交点。边的新建表正是用来排除不必要的求交测试。 多边形的扫描转换：扫描线算法： * * / 56 活性边表算法步骤 ： (1)初始化：构造边表，AET表置空； (2)将第一个不空的ET表中的边与AET表合并； (3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边； (4)yi+1=yi+1,根据xi+1=xi+1/m计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表； (5)AET表不为空则转(3)，否则结束。 多边形的扫描转换：扫描线算法： * * / 56 边填充算法： ▼求余运算：假定A为一个正整数，则M的余定义为 A – M, 记为 。计算机中取A为n位能表示的最大整数。即，A=0xFFFFFFFF ▼算法由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值的颜色。这一规律应用于多边形扫描转换，就为边填充算法。 ▼求余运算可用异或显示模式实现: ▼算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。 多边形的扫描转换：边填充算法：