第三章 二维实面积图形的生成.ppt

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

1、第3章二维实面积图形的生成矩形填充1区域填充2图案填充3本章知识结构图3.1矩形填充矩形是多边形的一个特例‚可以用多边形的扫描转换算法来进行填充‚但多边形的扫描转换算法针对的是一般多边形，其中用到比较复杂的算法和数据结构，所以用它来填充简单的矩形时效率很低。而矩形在各种图形应用(特别是在窗口系统)中用得较多，所以一般来说，图形软件包都将它单独作为一类图元来处理，利用矩形的简单性来提高绘图效率。注意：当两个矩形共享一条边时，存在该边属于谁的问题。对于任一个矩形，处理它的四个边的原则是左闭右开，下闭上开。按照这个原则，上图中的共享边应属于右边的矩形。3.2.1

2、多边形的扫描转换算法在计算机图形学中，多边形有两种重要的表示方法：顶点表示法和点阵表示法。顶点表示法就是用多边形的顶点序列来刻画多边形;点阵表示是用位于多边形内的像素的集合来刻画多边形。两种表示法如下图示由于多边形的顶点表示既直观，又有很强的几何意义，所以大多数图形系统都采用顶点序列来表示多边形。多边形的扫描转换过程实质上就是对多边形包围的区域着色的过程，因此是一种面着色方法。实现多边形扫描转换的最简单方法是逐点判断法，即逐个判断绘图窗口内的像素，确定它是否位于多边形区域内部，从而求出在多边形区域内部的像素的集合。3.2区域填充2.扫描线的连贯性与边的连贯

3、性扫描线算法是扫描转换多边形的常用算法，它充分利用了像素之间的连贯性，避免了对像素的逐点判断，减少了计算量，提高了速度。这里所讨论的多边形是非自交多边形(边与边之间除了顶点外无其他交点)，这种非自交多边形可以是凸的、凹的，还可以是带孔的。对于自交多边形的扫描转换，只需对本小节的算法稍加修改即可。多边形的扫描线算法就是将扫描转换多边形的问题分解到一条条扫描线上，也就是按照扫描线的顺序，计算绘图窗口内每一条扫描线与多边形的相交区间，再用指定的颜色来填充这段区间，就完成了整个多边形的扫描转换工作。如上所示，每条扫描线与多边形的边有偶数个交点，若将这些交点按横坐标

4、递增的顺序排序，第1个交点和第2个交点之间，第3个交点和第4个交点之间……其内像素位于多边形内部，这种性质被称为扫描线的连贯性。当用指定的多边形颜色填充了这些区间后，该扫描线上的填充工作就完成了。因此一条扫描线上的填充过程可以分为以下四个步骤。(1)求交：计算扫描线与多边形各边的交点。(2)排序：将所有交点按横坐标从小到大的顺序排序。(3)交点配对：将交点按顺序两两配对，每对交点构成扫描线与多边形的一个相交区间。(4)区间填充：将相交区间内的像素置为多边形颜色，其他区间内的像素置为背景颜色。扫描转换多边形的关键是计算扫描线与多边形各边的交点。当多边形具有很

5、多的边数时，这种求交点的计算量是很大的。为了减少求交点的计算量，可以利用边的连贯性。3.交点取整和取舍问题先讨论交点的取整问题。从上面的讨论可以看出，利用边的连贯性，不需要求扫描线与多边形所有边的交点，避免了盲目求交，减少了计算量，解决了求交点的问题。但由于得到的交点的横坐标有可能是小数，而显示器是整数坐标系，所以在交点两两配对确定填充区间之前，需要对交点的横坐标取整。在交点取整时可能出现各种情况。交点的取舍问题包括两个方面：一是当扫描线与多边形相交于多边形的顶点时，交点的取舍问题；二是当交点落在某一像素点上时，交点的取舍问题。前者保证交点正确配对，后者避

6、免填充区域扩大化。在进行多边形的填充时，还要考虑当交点落在像素上的情况。如果将落在像素上的所有交点都进行填充，就会造成填充扩大化。4.扫描线算法为了实现多边形的扫描转换，可根据边的连贯性和扫描线的连贯性，按从下到上的顺序求得各条扫描线与多边形的交点序列，并将这些交点两两配对，确定填充区间并填充。此算法就是对多边形扫描转换的扫描线算法。为了实现扫描线算法，引进了两个灵活的数据结构，它们是活性边表(ActiveEdgeList，AEL)和边的分类表(EdgeList，ET)，这两个表中的每个结点都是边结构。边结构包含边的以下四个信息。(1)边的上端点的坐标；(

7、2)：在AEL中为当前扫描线与边的交点的坐标，在ET中为边的下端点的坐标；(3)：边的斜率的倒数；(4)next：指向下一条边的指针。与当前扫描线相交的边被称为活性边，并将这些活性边按与扫描线相交的交点坐标递增的顺序存放在一个链表中，此链表被称为活性边表。通过活性边表，可以充分利用边的连贯性和扫描线的连贯性，减少求交计算量和提高排序效率。为了方便活性边表的建立和更新，需要建立边的分类表ET。ET是按边的下端点的坐标对非水平边进行分类的指针数组，其包含的元素的个数为多边形的所有顶点的坐标的最大值加1。如下图示活性边表AEL是为了减少求交计算量和提高排序效率。

8、而引进分类边表是为了避免盲目求交。当处理某一条扫描线时，为了求得它