第三章 二维实面积图形的生成 计算机图形技术 知识PPT.pptx

;;;; 2. 扫描线的连贯性与边的连贯性 扫描线算法是扫描转换多边形的常用算法，它充分利用了像素之间的连贯性，避免了对像素的逐点判断，减少了计算量，提高了速度。 这里所讨论的多边形是非自交多边形(边与边之间除了顶点外无其他交点) ，这种非自交多边形可以是凸的、凹的，还可以是带孔的。对于自交多边形的扫描转换，只需对本小节的算法稍加修改即可。 多边形的扫描线算法就是将扫描转换多边形的问题分解到一条条扫描线上，也就是按照扫描线的顺序，计算绘图窗口内每一条扫描线与多边形的相交区间，再用指定的颜色来填充这段区间，就完成了整个多边形的扫描转换工作。 ;; 4. 扫描线算法 为了实现多边形的扫描转换，可根据边的连贯性和扫描线的连贯性，按从下到上的顺序求得各条扫描线与多边形的交点序列，并将这些交点两两配对，确定填充区间并填充。此算法就是对多边形扫描转换的扫描线算法。 ; 通过活性边表，可以充分利用边的连贯性和扫描线的连贯性，减少求交计算量和提高排序效率。为了方便活性边表的建立和更新，需要建立边的分类表ET。ET是按边的下端点的 坐标对非水平边进行分类的指针数组，其包含的元素的个数为多边形的所有顶点的 坐标的最大值加1。如下图示; 引进了活性边表AEL和分类边表ET后，扫描转换多边形的扫描线算法可以描述如下： 1.建立ET。 2 .将扫描线纵坐标 的初始值取为ET中非空元素的最小序号。 3 .将AEL设置为空。 4 .执行下列步骤直至ET和AEL均为空。 (1) 如果ET中的第 类非空，则将其中的所有边取出并插入到AEL中； (2) 如果有新的边插入AEL，则对AEL中各边进行排序； (3) 对AEL中的边两两配对(1和2为一对，3和4为一对，……)，并将每 对边中的 按规则取整，获得有效的填充区间，再填充； (4) 将当前扫描线纵坐标 值递增1，即 ； (5) 将AEL中满足 的边删去(因为每条边被看作是下闭上开的) ； (6) 对AEL中剩下的每条边的 递增 ，即 。 ;; 以边为中心的边填充算法就是对多边形逐边进行求余运算，即对多边形的每一非水平边上的像素向右求余。以边为中心的边填充算法???叙述如下： 1.将绘图窗口内的每个像素的颜色值置为 (如图3.16中置为白色) 。 2.逐边求余。对多边形的每一条非水平边上所有像素向右求余。 以边为中心的边填充算法的执行过程如下图所示。 ; 种子填充算法先将区域内的一像素(称为种子点)赋予指定的颜色，然后将该像素的颜色值扩展到整个区域内其他的像素。; 八连通区域 任取区域内两个像素，若在该区域内，通过水平、垂直、四个对角线八个方向的运动(如图(a)所示)，这两个像素可以相互到达，则称该区域为八连通的。图(b)所示的区域为内点表示的八连通区域，图(c)所示的区域为边界表示的八连通区域。 ;1. 递归填充算法 ;1 .初始化。将算法设置的堆栈置空，种子点 压入堆栈。 2 .出栈。若堆栈为空，则算法结束；否则取栈顶元素 ，并以 的值为当前扫描线号。 3 .填充并确定种子点所在的区段。从种子点 出发，沿着当前扫描线向左、右两个方向逐个像素进行填色，其值置为newcolor，直到到达边界。以xleft和xright分别表示填充的区段两端点的横坐标。 4 .确定新的种子点。分别在与当前扫描线上相邻的上、下两条扫描线上确定位于区间[xleft，xright]内的给定区域内的区段；如果这些区段内不存在非边界且未被填充的像素，则转到步骤2，否则取区段内的最右像素作为种子点压入堆栈，再转到步骤2继续执行。 ;;;2. 位图图案填充 ;