计算机图形学 第4章 二维实面积图形的生成ppt课件.ppt

《计算机图形学 第4章 二维实面积图形的生成ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章二维实面积图形的生成矩形填充1区域填充2图案填充3注意：当两个矩形共享一条边时，存在该边属于谁的问题。对于任一个矩形，处理它的四个边的原则是左闭右开，下闭上开。按照这个原则，上图中的共享边应属于右边的矩形。4.1矩形填充多边形的表示方法顶点表示法：用多边形的顶点序列来刻画多边形;点阵表示法：用位于多边形内的像素的集合来刻画多边形。4.2区域填充多边形的扫描转换：找到多边形内部的像素，并设置相应的颜色，实质是对多边形包围的区域着色的过程。实现：1）逐点判断法算法简单，但速度太慢、效率很低；2）扫描线算法；3）边填充算法；4）

2、种子填充算法。研究对象：非自交多边形思想：将扫描转换多边形的问题分解到每条扫描线上，即按照扫描线的顺序，计算绘图窗口内每条扫描线与多边形的相交区间，再用指定的颜色来填充这段区间，就完成整个多边形的扫描转换工作。4.2.1多边形的扫描转换算法扫描线的连贯性：将交点按横坐标递增的顺序排序，第1个交点和第2个交点之间，第3个交点和第4个交点之间……其内像素位于多边形内部。一条扫描线上的填充步骤：(1)求交：计算扫描线与多边形各边的交点。(2)排序：将所有交点按横坐标从小到大的顺序排序。(3)交点配对：将交点按顺序两两配对，每对交点构成

3、扫描线与多边形的一个相交区间。(4)区间填充：将相交区间内的像素置为多边形颜色，其他区间内的像素置为背景颜色。边的连贯性:(1)扫描线yi与边相交，线yi+1在端点P1、P2间，则线yi+1也可与该边相交；(2)交点：Xi+1=Xi+1/kYi+1=Yi+1交点取整问题交点的横坐标有可能是小数，在交点两两配对确定填充区间前，要对交点的横坐标取整。交点取舍问题（1）扫描线与多边形相交于多边形的顶点时，交点的取舍问题；（2）交点落在某一像素点上时，交点的取舍问题。前者保证交点正确配对，后者避免填充区域扩大化。进行多边形填充时，要考虑

4、交点落在像素上的情况。解决：左闭右开，下闭上开原则扫描线算法的数据结构活性边表(ActiveEdgeList，AEL)；边的分类表(EdgeList，ET)；表中的每个结点都是边结构，边结构包含边的以下四个信息：(1)边的上端点的Y坐标；(2)在AEL中为当前扫描线与边的交点的X坐标，在ET中为边的下端点的X坐标；(3)边的斜率的倒数；(4)next：指向下一条边的指针。活性边:与当前扫描线相交的多边形的边。活性边表：将活性边按与扫描线交点x坐标递增的顺序存放的链表。边的分类表ET：按边的下端点的Y坐标对非水平边进行分类的指针数

5、组，其包含的元素的个数为多边形的所有顶点的Y坐标的最大值加1。扫描转换多边形的扫描线算法1.建立ET。2.将扫描线纵坐标的初始值取为ET中非空元素的最小序号。3.将AEL设置为空。4.执行下列步骤直至ET和AEL均为空。(1)如果ET中的第y类非空，则将其中的所有边取出并插入到AEL中；(2)如果有新的边插入AEL，则对AEL中各边进行排序；(3)对AEL中的边两两配对(1和2为一对，3和4为一对，……)，并将每对边中的x按规则取整，获得有效的填充区间，再填充；(4)将当前扫描线纵坐标y值递增1，即y=y+1；(5)将AEL中满

6、足ymax=y的边删去(因为每条边被看作是下闭上开的)；(6)对AEL中剩下的每条边的x递增m，即x=x+m。思想：利用求余(差)运算代替交点排序、配对构造的填充空间。原理：在光栅图形中，像素点颜色值M经偶数次求余运算后，该像素颜色值不变；而做奇数次求余运算后，该像素为值为余数的颜色。算法：（1）以扫描线为中心的边填充算法；（2）以边为中心的边填充算法。4.2.2边填充算法以扫描线为中心的边填充算法思想：将每条扫描线和多边形的交点（x,y）右方的所有像素取余，多边形的每条边作此处理，多边形的顺序随意。以边为中心的边填充算法对多边

7、形逐边进行求余运算，即对多边形的每一非水平边上的像素向右求余。步骤如下：1.将绘图窗口内的每个像素的颜色值置为(如图为白色)。2.逐边求余。对多边形的每一条非水平边上所有像素向右求余。以边为中心的边填充算法也被称为边缘填充算法。此算法之所以被称为边缘填充算法，是因为它一边画多边形的边界，一边向右求余，当多边形的所有边界画完后，多边形的扫描转换也随之完成。特点：算法简单，易于实现；每个像素被访问多次，输入输出量比较大。改进：栅栏填充法栅栏：经过多边形顶点且与扫描线垂直的直线，将多边形分成两半。添加栅栏，让扫描线与多边形交点和栅栏间

8、的像素取余。P57图3.3思想：先将区域内的一像素(称为种子点)赋予指定的颜色，然后将该像素的颜色值扩展到整个区域内其他的像素。要求：填充区域是连通的，分为四连通区域和八连通区域。4.2.3种子填充算法四连通区域：任取区域内两个像素，若在该区域内，通过上、下、左