第5章基本图形生成算法(编辑修改稿)

第5章基本图形生成算法(编辑修改稿)内容摘要：

2020/10/7 华中理工大学计算机学院 陆枫 997 46 误差项的递推 d1≤0： ( a) d = 0 的情况Px iy i 2x i + 1y iy i 1x i + 2)x(bd )x(bba).(ya)(xb ba).(ya)(xb).,yF (xdiiiiiiii323250150250221222222222222212020/10/7 华中理工大学计算机学院 陆枫 997 47 d10： )22()32( )22()32()()1( )()2(),2(221222222222222221iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd( b) d 0 的情况Px i x i + 2x i + 1y i 1y iy i 2判别式的初始值 )( )(),1(222222210babbababbFd2020/10/7 华中理工大学计算机学院 陆枫 997 49 p(x i ,y i )p l (x i ,y i1 ) p r (x i+1 ,y i1 )M (x i+1 ,y )5 1 9 下半部分椭圆弧的绘制原理再来推导椭圆弧下半部分的绘制公式 原理 2020/10/7 华中理工大学计算机学院 陆枫 997 50 判别式 2222222 )1()()1,( bayaxbyxFd iiii •若 d20， 取 Pl(xi,yi1) •若 d2≤0， 取 Pr(xi+1,yi1) p(x i ,y i )p l (x i ,y i1 ) p r (x i+1 ,y i1 )M (x i+1 ,y )5 1 9 下半部分椭圆弧的绘制原理2020/10/7 华中理工大学计算机学院 陆枫 997 51 误差项的递推 d20： )y(ad )y(aba)(ya)(xb ba)(ya)(xb),yF ( xdiiiiiiii32 2222222222222222( a) d 0 的情况Px iy i 2x i + 1y iy i 1x i + 22020/10/7 华中理工大学计算机学院 陆枫 997 52 d2≤0： )32()22( )32()22()1()( )2()()2,(222222222222222222iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd( b) d = 0 的情况Px i x i + 2x i + 1y i 1y iy i 22020/10/7 华中理工大学计算机学院 陆枫 997 53 注意 ：  上半部分的终止判别  下半部分误差项的初值 算法步骤 ： a和短半轴 b。 d=b2+a2(b+)、 x=0、 y=b。 (x,y)及其在四分象限上的另外三个对称点。 2020/10/7 华中理工大学计算机学院 陆枫 997 54 d的符号。 若 d≤0， 则先将 d更新为 d+b2(2x+3)，再将 ( x,y) 更新为 ( x+1,y)； 否 则 先将 d 更 新为d+b2(2x+3)+a2(2y+2)， 再将 (x,y)更新为 (x+1,y1)。 b2(x+1)a2()时 ， 重复步骤 3和 4。 否则转到步骤 6。 (x,y)来计算下半部分中 d的初值： 222222 )1()( bayaxbd 2020/10/7 华中理工大学计算机学院 陆枫 997 55 (x,y)及其在四分象限上的另外三个对称点。 d的符号。 若 d≤0， 则先将 d更新为 b2(2xi+2)+a2(2yi+3)， 再将 (x,y)更新为 (x+1,y1)； 否则先将 d更新为 d+a2(2yi+3)， 再将 (x,y)更新为 (x,y1)。 y0时 ， 重复步骤 7和 8。 否则结束。 程序 2020/10/7 华中理工大学计算机学院 陆枫 997 56 多边形的扫描转换与区域填充 多边形的扫描转换 主要是通过确定穿越区域的扫描线的覆盖区间来填充 ， 区域填充 是从给定的位置开始涂描直到指定的边界条件为止。 2020/10/7 华中理工大学计算机学院 陆枫 997 57 多边形的扫描转换 顶点表示 用多边形的顶点序列来刻划多边形 点阵表示 是用位于多边形内的象素的集合来刻划多边形 扫描转换多边形或多边形的填充 ：从多边形顶点表示到点阵表示的转换。 1. 什么是多边形的扫描转换 2020/10/7 华中理工大学计算机学院 陆枫 997 58 2. x扫描线算法 基本思想 图5 2 3 x 扫描线算法填充多边形xy21 3 4 5 6 7 8 9 1112345678910111210 122020/10/7 华中理工大学计算机学院 陆枫 997 59 算法步骤 ： (1)确定多边形所占有的最大扫描线数 ， 得到多边形顶点的最小和最大 y值 （ ymin和 ymax）。 (2)从 y=ymin到 y=ymax， 每次用一条扫描线进行填充。 (3)对一条扫描线填充的过程可分为四个步骤： 2020/10/7 华中理工大学计算机学院 陆枫 997 60 存在问题： 当扫描线与多边形顶点相交时 ， 交点的取舍问题。 xy21 3 4 5 6 7 8 9 1112345678910111210 12图5 2 4 与多边形顶点相交的交点的处理2020/10/7 华中理工大学计算机学院 陆枫 997 61 解决 ： 当扫描线与多边形的顶点相交时 ， • 若共享顶点的两条边分别落在扫描线的两边 ， 交点只算一个； • 若共享顶点的两条边在扫描线的同一边 ， 这时交点作为零个或两个。 2020/10/7 华中理工大学计算机学院 陆枫 997 62 图5 2 5 与扫描线相交的多边形顶点的交点数0 1 1 1 1 0 2 2 2 填充过程实例 2020/10/7 华中理工大学计算机学院 陆枫 997 63 3. 改进的有效边表算法 （ Y连贯性算法 ） x i ,y ix i + 1 ,y i + 111/k图5 2 6 与多边形边界相交的两条连续扫描线交点的相关性改进原理 ： • 处理一条扫描线时 ， 仅对有效边求交 • 利用扫描线的连贯性 • 利用多边形边的连贯性 2020/10/7 华中理工大学计算机学院 陆枫 997 64 有效边 （ Active Edge） ： 指与当前扫描线相交的多边形的边 ， 也称为活性边。 有效边表 （ Active Edge Table, AET） ： 把有效边按与扫描线交点 x坐标递增的顺序存放在一个链表中 ，此链表称为有效边表。 有效边表的每个结点： x ymax 1/k next 2020/10/7 华中理工大学计算机学院 陆枫 997 65 边表 （ Edge Table） 边表的构造： (1)首先构造一个纵向链表 ， 链表的长度为多边形所占有的最大扫描线数 ， 链表的每个结点 ， 称为一个桶 ， 则对应多边形覆盖的每一条扫描线。 (2)将每条边的信息链入与该边最小 y坐标 （ ymin ） 相对应的桶处。 也就是说 ， 若某边的较低端点为 ymin， 则该边就放在相应的扫描线桶中。 2020/10/7 华中理工大学计算机学院 陆枫 997 66 (3)每条边的数据形成一个结点 ， 内容包括：该扫描线与该边的初始交点 x（ 即较低端点的 x值 ） ， 1/k，以及该边的最大 y值 ymax。 x|ymin ymax 1/k NEXT (4)同一桶中若干条边按 X|ymin由小到大排序 ， 若X|ymax 相等 ， 则按照 1/m由小到大排序。 2020/10/7 华中理工大学计算机学院 陆枫 997 67 解决顶点交点计为 1时的情形 ： 图5 2 8 将多边形的某些边缩短以分离那些应计为1 个交点的顶点（a ) 原图 （b ) 缩短y max 的边 （。