二维图形生成原理.ppt

* 见附页 * * * * * * * * 图形生成原理Principles of Picture Generation （ 1 ）凸多边形---指任意两顶点间的连线均在多边形内 （ 2 ）凹多边形---指任意两顶点间的连线有不在多边形内的部分 （ 3 ）含内环的多边形---多边形内再套有多边形，多边形内的多边形也叫内环，内环之间不能相交。 多边形的类形 计算机中多边形的表示方法 顶点表示: 用多边形的顶点序列来表示多边形 点阵表示: 用位于多边形内的象素的集合来表示多边形 多边形的扫描转换 把多边形从顶点表示转换到点阵表示。 多边形的扫描转换方法 扫描线算法； 边缘填充法； 栅栏填充法； 边界标志法。 基本思想 按扫描顺序，计算每条扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。 区间的端点可以通过计算扫描线与多边形边界线的交点获得。 *算法的核心：须按x递增顺序 排列交点的x坐标序列 扫描转换-扫描线算法 (1)确定多边形所占有的最大扫描线数：得到多边形顶点的最小和最大y值（ymin和ymax）。 (2)从y=ymin到y=ymax，每次用一条扫描线进行填充。 (3)对一条扫描线填充的过程可分为四个步骤： a.求交 b.排序 c.交点配对 d.区间填色 扫描线算法-算法步骤： 存在问题*：当扫描线与多边形顶点相交时，交点的取舍问题。 扫描线算法 解决： 当扫描线与多边形的顶点相交时， 若共享顶点的两条边分别落在扫描线的两边，交点只算一个； 若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。 具体实现方式： 检查共享顶点的两条边的另外两个端点的y值，按这两个y值中大于交点y值的个数是几来决定交点数取0，1，2。 扫描线算法 0 1 1 1 1 0 2 2 2 扫描线算法 0 解决顶点交点计为1时的情形*： 改进的有效（活性）边表算法 改进： 处理一条扫描线时，仅对有效边求交 利用多边形边的连贯性*，如图：若y=yi,x=xi,则当 y=yi+1=yi+1,xi+1=xi+1/k 有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。 有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。 有效边表的每个结点： x ymax 1/k next 边所在的最大扫描线值 改进的有效（活性）边表算法-数据结构 边表*（Edge Table） 边表的构造： (1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖每一条扫描线。 (2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。 改进的有效（活性）边表算法-数据结构 (3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。 x|ymin ymax 1/k NEXT (4)同一桶中若干条边按X|ymin由小到大排序，若X|ymin 相等，则按照1/k由小到大排序。 改进的有效（活性）边表算法-数据结构 解决顶点交点计为1时的情形*： 算法步骤： (1)初始化：构造边表，AET表置空； (2)将第一个不空的ET表中的边与AET表合并； (3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边； (4)yi+1=yi+1,根据xi+1=xi+1/k计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表； (5)AET表不为空则转(3)，否则结束。 * * * * * 见附页 * * * * * * * *