1、第 3章 基本图形生成算法 3.3 区域填充 n 二维图形填充是面着色的手段，是图形到图象的重要步骤n 二维图形填充所要做的就是将图形内部所有的点 -内点 用指定的颜色表示。3.3 区域填充n 多边形的两种重要表示方法： 1、顶点表示法，即用多边形的顶点序列来表示。 2、点阵表示法，即用多边形的全体内点来表示。n 顶点表示：数学上常用的方法，精确，数据量小，又叫矢量表示n 点阵表示：工程上常用的方法，直观，数据量大，又叫栅格表示n 流行的 4D技术，大量的栅格 -矢量转换多边形的扫描转换n 多边形扫描转换是指从多边形的顶点表示到多边形的点阵表示的转换n 常用的多边形扫描转换方法有： 逐点判断方
2、法 扫描线算法 边缘填充算法逐点判断方法n 对于屏幕上的每一个像素判断是否内点n 扫描转换的实质就是找出所有的内点。n 内点的判断方法有： 射线法 累计角度法 编码方法射线法 (1)n 从一点出发的射线，若与多边形边界的交点个数为奇数，为内点；偶数，不是内点n 射线的方向不是问题，为简便，射线方向定为向右的水平线。这样只要计算射线与边界线的交点，或从待判定点出发，水平向右找边界点，直到显示器边缘射线法 (2)n 即使经过简化，计算量也非常大 要计算射线与每条边的交点 要判断交点是否在该点的右边 要判断交点是否在边的两个端点之间n 逐点法的各种方法，原理简单，但割裂了像素之间的关系，导致计算量大
3、，速度太慢。对于判断个别点是否位于多边形内部有效，用来填充多边形不合适。扫描线算法（ 1）n 扫描线算法充分利用了像素之间的各种关系，即区域的连贯性、扫描线连贯性和边的连贯性，减少了计算量，提高了速度。n 区域连贯性1 2 3 4 5两条扫描线之间的区域分割成若干个相邻区域两个相邻区域分别分属多边形内外只要确定这些区域中任何一个区域内的一个点与多边形的内外关系，就可确定所有这些区域的内外关系扫描线算法（ 2）n 扫描线的连贯性l 一条扫描线与多边形非水平边的交点数为偶数l 这些交点从左到右排序，奇数交点与其后的偶数交点之间所有的点都是多边形内点。只要两个相邻交点，就可确定一批内点。1 2 3 4扫描线算法（ 3）n 扫描线与两个非水平边的连接处的交点均为两个重合点，即理论上应有两个交点n 解决办法：非水平边上端截取一个单位n 实际上每条边不需专门处理，在算法中自动解决21 0扫描线算法（ 4）n 边的连贯性：相邻扫描线与同一条边的交点坐标在垂直方向相差 1，在水平方向相差 d,d等于边的斜率的倒数n 知道了一个交点 (xi,yi)， 就可以用加减法算出下一个交点 (xi+1,yi+1)=(xi+d,yi+1)。 边的两个端点必然属于交点。ddd
