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

第3章 二维实面积图形的生成 3.1 矩 形 填 充 设矩形的两对角顶点的坐标分别为(xmin，ymin)，(xmax，ymax)(如图3.1所示)，为了将它用指定的颜色均匀填充，只要将矩形内的每个点按指定颜色填充即可， 3.1 矩 形 填 充 注意：当两个矩形共享一条边时(如图3.2所示) ，一般采用一个折中的处理方法：对于任一个矩形，处理它的四个边的原则是左闭右开，下闭上开。 3.2 区 域 填 充 3.2.1 多边形的扫描转换算法 1. 多边形的扫描转换 在计算机图形学中，多边形有两种重要的表示方法：顶点表示法和点阵表示法。 3.2.1 多边形的扫描转换算法 由于多边形的顶点表示既直观，又有很强的几何意义，所以大多数图形系统都采用顶点序列来表示多边形。实现多边形扫描转换的最简单方法是逐点判断法，即逐个判断绘图窗口内的像素，确定它是否位于多边形区域内部，从而求出在多边形区域内部的像素的集合。 3.2.1 多边形的扫描转换算法 2. 扫描线的连贯性与边的连贯性 扫描线算法是扫描转换多边形的常用算法。多边形的扫描线算法就是将扫描转换多边形的问题分解到一条条扫描线上，也就是按照扫描线的顺序，计算绘图窗口内每一条扫描线与多边形的相交区间，再用指定的颜色来填充这段区间，就完成了整个多边形的扫描转换工作。 3.2.1 多边形的扫描转换算法 一条扫描线上的填充过程可以分为以下四个步骤。 (1) 求交：计算扫描线与多边形各边的交点。 (2) 排序：将所有交点按横坐标从小到大的顺序排序。 (3) 交点配对：将交点按顺序两两配对，每对交点构成扫描线与多边形的一个相交区间。 (4) 区间填充：将相交区间内的像素置为多边形颜色，其他区间内的像素置为背景颜色。 为了减少求交点的计算量，可以利用边的连贯性。 3.2.1 多边形的扫描转换算法 3. 交点取整和取舍问题 当交点位于多边的左边界上(如图3.7(a)所示)，则取其右端的像素(int(x)+1,d)；当交点位于多边的右边界上(如图3.7(b)所示) ，则取其左端的像素(int(x),d)。 3.2.1 多边形的扫描转换算法 当扫描线与多边形相交于多边形的顶点时，交点的取舍问题 。如图3.8所示 3.2.1 多边形的扫描转换算法 具体的处理方法是：检查与扫描线相交的两条边的另外两个端点的值，两个值中大于交点值的个数是0，1，2，来决定取0，1，2个交点。 例如，在图3.8(a)和3.8(b)中，扫描线与多边形相交于顶点，而共享该顶点的两条边的另外两个顶点的值中，只有一个顶点的值大于交点值，所以(x,d)算作一个交点。 3.2.1 多边形的扫描转换算法 在进行多边形的填充时，还要考虑当交点落在像素上的情况。我们采取“左闭右开”的原则。在具体实现时，对落在多边形左边界上的像素进行填充，如图3.10(a)所示，而对落在多边形右边界上的像素不填充，如图3.10(b)所示。 3.2.1 多边形的扫描转换算法 4. 扫描线算法 为了实现扫描线算法，引进了两个灵活的数据结构，它们是活性边表 (Active Edge List，AEL)和边的分类表 (Edge List，ET)，这两个表中的每个结点都是边结构。 通过活性边表，可以充分利用边的连贯性和扫描线的连贯性，减少求交计算量和提高排序效率。 3.2.1 多边形的扫描转换算法 例如 3.2.1 多边形的扫描转换算法 该多边形的分类边表如下图所示 3.2.1 多边形的扫描转换算法 【算法3.1】 扫描转换多边形的扫描线算法。 步骤1 建立ET； 步骤2 将扫描线纵坐标的初始值取为ET中非空元 素的最小序号； 步骤3 将AEL设置为空； 步骤4 执行下列步骤直至ET和AEL均为空。 3.2.2 边填充算法 假设A是一个给定的正整数，M为任一正整数，则M的余定义为A-M，记为 。在光栅图形中，如某区域已着上值为M的某种颜色，则该上述求余运算的性质反映出来的现象是：对该区域的颜色值做偶数次求余运算后，该区域的颜色值不变；而做奇数次求余运算后，该区域的颜色则变为值为的颜色。这一现象可用于多边形的扫描转换中，就称为边填充算法。 3.2.2 边填充算法 【算法3.2】 以扫描线为中心的边填充算法。 设 是当前扫描线与多边形边的交点的x坐标的数列(没有排序) ，填充该扫描线上位于多边形内的区间由下面的步骤完成。 步骤1 将当前扫描线上的所有像素着上值为的颜色； 步骤2 求余。 3.2.2 边填充算法 完成上面两个步骤后，扫描线上位于多边形内部的像素被奇数次求余，故被着上值为M的颜色；位于多边形外部的像素被偶数次求余，故被着上值为