多边形扫描转换算法、区域填充算法.doc

贵州大学计算机图形学实验报告 学院：计算机科学与信息学院 专业：软件工程 班级： 姓名 学号 实验组 实验时间 指导教师 成绩 实验项目名称 实验三 多边形的扫描转换算法、区域填充算法 实验目的 通过本实验，了解并掌握在光栅显示系统中多边形的扫描转换和区域填充算法。 实验要求 用光栅扫描算法画出不自交的图形： 用光栅扫描算法画出自交图形： 用区域填充法画出图形： 实验原理 光栅扫描算法： 扫描线算法是扫描转换多边形的常用算法，它充分利用了相邻像素之间的连贯性，避免了逐点判断和反复求交计算，达到了减少计算量和提高算法效率的目的。 处理对象：非自交多边形 （边与边之间除了顶点外无其它交点）。开发和利用相邻象素之间的连贯性是光栅图形学算法的重要技巧。 扫描线算法综合利用了区域的连贯性、扫描线的连贯性和边的连贯性等三种形式的连贯性。 区域的连贯性：相邻两条扫描线构成一个水平长方形区域，并被多边形的边分割为若干梯形（一类位于多边形的内部；另一类在多边形的外部，且间隔排列）。只需知道该区域内任一梯形中一点关于多边形的内外关系，即可确定区域内所有梯形关于多边形的内外关系。 扫描线的连贯性：区域的连贯性在一条扫描线上的反映； 边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交。可通过与当前扫描线的交点计算与下一扫描线的交点(利用斜率)。（区域的连贯性在相邻两扫描线上的反映） 根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。 所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。 如何具体实现（如何找到入点、出点）？ 根据区域的连贯性，分为3个步骤： (1)求出扫描线与多边形所有边的交点； (2)把这些交点按x坐标值以升序排列； (3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。 步骤(3)如上图：对y＝8的扫描线，对交点序列按x坐标升序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。 求交点、排序、配对、填色 利用链表：与当前扫描线相交的边称为活性边(Active Edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活性边表AEL (AEL， Active Edge List)。它记录了多边形边沿扫描线的交点序列。 AEL中每个对象需要存放的信息： ymax：边所交的最高扫描线； x：当前扫描线与边的交点； Δx：从当前扫描线到下一条扫描线之间的x增量 next：指向下一对象的指针。 伪码： 建立ET，置y为ET中非空桶的最小序号； 置AEL表为空，且把y桶中ET表的边加入AEL表中； while AEL表中非空 do?????begin 对AEL表中的x、 Δx按升序排列； ???? 按照AEL表中交点前后次序，在每对奇偶交点间的x段予 以填充； ? 计算下一条扫描线：y=y+1； if 扫描线 y=ymax??then 从AEL表中删除这些边； ???? 对在AEL表中的其他边，计算与下一条扫描线的交点： x=x +Δx ?????按照扫描线y值把ET表中相应桶中的边加入AEL表中；end end of algorithm 区域填充算法： 区域可采用两种表示形式: 内点表示 枚举区域内部的所有像素； 内部的所有像素着同一个颜色； 边界像素着不同的颜色。 边界表示： 枚举出边界上所有的像素； 边界上的所有像素着同一颜色； 内部像素着不同的颜色。 区域填充 先将区域内的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。 简单种子算法 扫描线种子算法 要求区域是“连通”的。 测试对象为象素段 ,对区域内的每一象素段,只保留其最右边(或左边)的象素作为种子象素. 区域填充(扫描线算法)： –目标：减少递归层次 –适用于内点表示的4连通区域 基本过程： 当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 算法步骤： 1、填充并确定种子区段； 2、初始化：将种子区段压入堆栈； 3、出栈：如果堆栈为空，则算法结束；否则取栈顶元素y,xLeft,xRight），以纵坐标为y的扫描线为当前扫描线，[xLeft, xRight]为有哪些信誉好的足球投注网站区间； 4、填充并确定新的区段 。 实验环境 Win7系统，eclipse，jdk 实验步骤 根据上面算法的原理，在实验环境中进行算法的实现； 实验内容 扫描线算法核心代码： private void ScanLine(Graphics2D g2) {