贵州大学计算机图形学实验报告 学院：计算机科学与信息学院 专业：软件工程 班级： 姓名 学号 实验组 实验时间 指导教师 成绩 实验项目名称 实验三 多边形的扫描转换算法、区域填充算法 实验目的 通过本实验，了解并掌握在光栅显示系统中多边形的扫描转换和区域填充算法。 实验要求 1、 用光栅扫描算法画出不自交的图形： 2、 用光栅扫描算法画出自交图形： 3、 用区域填充法画出图形： 实验原理 一、光栅扫描算法： 扫描线算法是扫描转换多边形的常用算法，它充分利用了相邻像素之间的连贯性，避免了逐点判断和反复求交计算，达到了减少计算量和提高算法效率的目的。 处理对象：非自交多边形 （边与边之间除了顶点外无其它交点）。开发和利用相邻象素之间的连贯性是光栅图形学算法的重要技巧。 扫描线算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。 区域的连贯性：相邻两条扫描线构成一个水平长方形区域，并被多边形的边分割为若干梯形（一类位于多边形的内部；另一类在多边形的外部，且间隔排列）。只需知 道 该 区域内任 一梯形中一点关 于多边形的内外关 系，即 可 确 定 区域内所 有 梯形关 于多边形的内外关 系。 扫描线的连贯性：区域的连贯性在一条扫描线上 的反映 ； 边的连贯性：某 条边与当 前 扫描线相交，也 可 能 与下 一条扫描线相交。可 通过与当 前 扫描线的交点计算与下 一扫描线的交点(利用斜 率)。（区域的连贯性在相邻两扫描线上 的0 2 4 6 8 1 0 1 2 2 4 6 8 1 0 1 2 3 4 反映） 根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。 所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。 如何具体实现（如何找到入点、出点）？ 根据区域的连贯性，分为 3 个步骤： (1)求出扫描线与多边形所有边的交点； (2)把这些交点按 x 坐标值以升序排列； (3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。 步骤(3)如上图：对y＝8 的扫描线，对交点序列按 x 坐标升序排序得到的交点序列是(2,4,9,13)，然后对交点2 与4 之间、9 与13 之间的所有象素点进行填充。 求交点、排序、配对、填色 利用链表：与当前扫描线相交的边称为活性边(Active Edge)，把它们按与扫描线交点x 坐标递增的顺序存入一个链表中，称为活性边表 AEL (AE...
