输出图元.PPT

假定：当扫描线与多边形的顶点相交时，交点只算一个 解决方法：　 问题二：当扫描线与多边形顶点相交时，交点算几个？ 扫描线y=2: 2，8，2 求交 －＞ [2，2)，8 排序 －＞ 2，2，8 交点配对 扫描线y=7: 11，9，2 －＞ [2，9)，11 －＞ 2，9 ，11 2，8 －＞ [2，8) －＞ 2，8 　共享顶点的两条边分别落在扫描线的两侧，扫描线与顶点的交点只算1个； ╳ 　共享顶点的两条边在扫描线的同侧，扫描线与顶点的交点算为0个或2个： 　　　　顶点是多边形的局部最高点，交点数算0个 　 顶点是多边形的局部最低点，交点数算2个 　　1. 求交： 　　扫描线填充算法的四个步骤： 　　3. 交点配对： 　　2. 排序： 　　4. 区间填色： 图3-18 与多边形相交的两条相邻扫描线 扫描线 与AB的交点： 扫描线 与AB的交点： 　　1. 求交： 　　扫描线填充算法的四个步骤： 　　3. 交点配对： 　　2. 排序： 　　4. 区间填色： 　 　　 每个结点包含相交边的如下信息：　 扫描线y=4的活性边表： 活性边表：把与扫描线　相交的边信息按交点x坐标递增的顺序保存在一个链表中，此链表称为扫描线　的活性边表(活化边表)。 　 　　　：边的最大y值 　　　：扫描线　与边的交点x坐标 　　　：边斜率的倒数 箭头　：指向下一个结点的指针　 扫描线y=5的活性边表： 扫描线y=6的活性边表： 扫描线 的活性边表： 扫描线 的活性边表： 活性边表的构建原则： 1.修改原则：相邻扫描线 　、　 和多边形的相交边很可能相同。当扫描线 处理完后，不必为扫描线 从新构建活性边表，只需在扫描线 活性边表的基础上进行修改即可。 扫描线y=6的活性边表： 扫描线y=7的活性边表： 2.删除原则:与扫描线 相交的边，若其　　　 　，则该边与下一条扫描线　 不再相交，要从扫描线 的活性边表中删除。 3. 新增原则:如果扫描线 有新交上的边，则在构建扫描线 的活性边表时，需将新交上的边插入到 活性边表的适当位置，保持有序性。 新边表 图3-20 各扫描线新边表 　　　：边的最大y值 　　　：该扫描线与边的初始交点x坐标 　　　：边斜率的倒数 新边表：把与扫描线　交的新边信息按交点x坐标递增的顺序保存在一个链表中，此链表称为扫描线　的新边表。若某边的最低位置为　，则该边就放在扫描线　的新边表中。 　扫描线新边表 扫描线活性边表 图3-21 新边表到活性边表 新边表 活性边表的三个构造原则 修改原则 删除原则 新增原则 3．4．2 种子填充算法 　　种子填充算法的基本思想:如在区域内部有一象素已知，由此出发找到区域内的所有象素。 四向算法 八向算法 　 种子填充算法适用于用边界定义的区域，该算法也可称为边界填充算法。 种子填充算法 图3-22 　　可以使用栈结构实现四向算法，步骤如下： 　　种子象素入栈，当栈非空时重复执行如下三步操作： 　　1. 栈顶象素出栈； 　　2. 将出栈象素置成填充色； 　　3. 按右、上、左、下逆时针顺序检查与出栈象素相邻的四个象素，若　　　 其中某个象素不在边界且未置成填充色，则把该象素入栈。 图3－23 椎栈动态示意图 　　考虑更有效的方法，步骤如下： 图3－24　填充象素区间及椎栈示意图 　　种子象素入栈，当栈非空时重复执行如下三步操作： 　　1. 栈顶象素出栈； 2. 将出栈象素所在水平扫描线的连续象素段置成填充色，直至遇到边　　　 界象素为止； 　 3. 按下、上顺序检查当前扫描线相邻两条扫描线的有关象素是否为边　　　 界象素或已填充象素，若存在非边界、未填充的象素，则把每一区间的最左象素入栈。　　 线段明显落在裁剪窗口外(丢弃该线段)； 图3－26 线段与裁剪窗口 用计算机显示图形时，必须确定图形中哪些部分落在指定区域内，哪些部分落在指定区域外，这个处理过程称为裁剪。指定区域称为裁剪窗口，一般把裁剪窗口定义为矩形。 对于点（x,y)的裁剪，只要判别四个不等式： 图3－25 　　 线段完全落在裁剪窗口内(显示该线段)； 线段与裁剪窗口的位置关系： 　 不能明确判定线段与裁剪窗口的位置关系(必须通过交点计算，得到线段在裁剪窗口内的部分并显示)。 3.5 线段的裁剪 窗口 **1* 图3－27 区域编码 3．5．1 Cohen-Sutherland线段裁剪算法 采用编码方法，每个区都用一个四位二进制区域码表示该区与裁剪窗口的位置关系：