计算机图形学的课件(精品·公开课件).ppt

第四章 多边形填充 4.1　实面积图形的概念 4.2 有效边表填充算法 4.3 边缘填充算法 4.5 本章小结 4.6 习题 4.1　实面积图形的概念 实面积图形既能描述物体的几何轮廓，又能表现物体的表面色彩，与人们观察物体表面的习惯相一致，同时，实面积图形也是描述三维物体、绘制三维真实感图形的基础。 4.1.1 多边形的表示 4.2 有效边表填充算法 4.2.1 填充原理 4.2.2 边界像素的处理原则 4.2.3 有效边和有效边表 4.2.4 边表 4.2.1 填充原理 4.2.2 边界像素的处理原则 4.2.3 有效边和有效边表形 4.2.4 边表 4.3 边缘填充算法 4.3.1 填充原理 4.3.2 填充过程 4.3.1 填充原理 4.3.2 填充过程 4.4 区域填充算法 填充原理 四邻接点和八邻接点 四连通域和八连通域 四邻接点和八邻接点填充算法 填充原理 条件： 1.点阵表示的区域 2.区域内部或边界具有同一种颜色，且边界色与内部色不同 3.有一个种子点 做法： 从种子点出发向周围扩展 四邻接点和八邻接点 四连通域和八连通域 4.5 本章小结 * * 在计算机图形学中，多边形有两种示方法：顶点表示法和点阵表示法。 图 4-3 多边形的顶点表示法 P0 P1 P2 P3 P4 P5 图 4-4 多边形的点阵表示法 ⑴顶点表示法 多边形的顶点表示法是用多边形的顶点序列来描述。特点是直观、占内存少，易于进行几何变换，但由于没有 明确指出哪些像素在多边形内，所以不能直接进行填充，需要对多边形进行扫描转换，顶点表示法如图4-3所示。 ⑵点阵表示法 多边形的点阵表示法是用多边形覆盖的像素点集来描述。 特点是便于直接确定实面积图形覆盖的像素点，是多边形填充所需要的表示形式，但是缺少了多边形顶点的几何信息，如图4-4所示。 ⑶多边形的扫描转换 将多边形的描述从顶点表示法变换到点阵表示法的过程，称为多边形的扫描转换。即从多边形的顶点信息出发，求出多边形内部的各个像素点信息。 多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间内的所有像素，即完成填充工作。有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。 图 4-5 用一条扫描线填充多边形 P0 P1 P2 P3 P4 P5 P6 在图4-5中，多边形覆盖了12条扫描线。扫描线y＝3与多边形有4个交点（2.3，3），(4.5，3），（7，3）和（9，3）。对交点进行圆整处理后的结果为（2，3），(5，3），（7，3）和（9，3）。按x值递增的顺序对交点进行排序、配对后的填充区间为（2，5）和（7，9），共有7个像素点需要填充为指定颜色。 在实际填充过程中，需要考虑到边界像素影响问题：图4-6中正方形P0P2P4P6被等分为四个小正方形。假定小正方形P0P1P8P7被填充为绿色，P1P2P3P8被填充为橙色，P8P3P4P5被填充为绿色，P7P8P5P6被填充为橙色。四个小正方形的公共边为：P1P8、P8P5、P7P8和P8P3。考虑到公共边P1P8既是正方形P0P1P8P7的右边界，又是正方形P1P2P3P8的左边界；考虑到P7P8既是是正方形P0P1P8P7的上边界，又是正方形P7P8P5P6的下边界，那么P1P8和P7P8应该填充为哪一个小正方形的颜色？同理，P8P5 和P8P3应该填充为哪一个小正方形的颜色？ 图 4-6 边界像素的问题 P0 P1 P2 P3 P4 P5 P6 P7 图 4-7 边界像素的处理 P8 P0 P1 P2 P3 P4 P5 P6 P7 P8 在实际填充过程中，也需要考虑到像素面积大小的影响问题：对左下角为（1，1），右上角为（3，3）的正方形进行填充时，若边界上的所有像素全部填充，就得到图4-8所示的结果。所填像素覆盖的面积为3×3个单位，而正方形的面积实际只有2×2个单位。 图 4-8 面积3×3 图 4-9 面积2×2 为了保解决这些问题，在多边形填充过程中，常采用“下闭上开”和“左闭右开”的原则对边界像素进行处理。图4-6的处理结果如图4-7所示，每个小正方形的右边界像素和上边界像素都没有填充。图4-8的处理结果如图4-9所示，上面一行像素和右面一列像素没有填充。 按照此原则对图4-5中的一些特殊点进行处理： 1.P2点的处理原则