目录
文章目录
在正式介绍多边形的扫描转换之前，先介绍点背景知识，不想看的可以直接跳过。
一、背景知识
在计算机图形学中，多边形有两种重要的表示方法。
顶点表示
- 用多边形的顶点序列来刻画多边形
- 顶点表示的特点：
表示方法直观，几何意义强，占内存空间少，但是没指明哪些像素在多边形内，不能直接用于着色
点阵表示
- 用位于多边形内部或者边界上的像素集合来刻画多边形
- 点阵表示特点：
点阵表示会失去很多重要的几何信息，但是它是光栅显示系统显示面着色时所需的图形表示形式。
二、多边形的填充方式
1.多边形扫描转换
顶点表示不能直接用于显示，必须要进行从多边形顶点表示到点阵表示的转换，这种转换就是给多边形包围的区域着色的过程。
即从多边形的给定边界出发，求出位于其内部的各个像素，并将其灰度和颜色值写入帧缓存中相应的单元，主要用来填充多边形区域以及由多边形拟合的其他简单曲线区域。
1.1 逐点判断算法
基本思想
逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。实现扫描转换多边形最简单方法就是逐点判断。
实质
进行多边形对平面上的点的包含性检查
常用方法
- 射线法
由被测点向某个方向作射线，计算此射线与多边形所有边的交点个数，用交点分布的奇偶性判别多边形与点的关系。判断依据：奇内偶外,
特殊情况遵循：左闭右开 - 弧长法（不讲）
1.2 扫描线填充算法
区域特点
- 一条扫描线上的像素存在着相关性
- 在多边形边处，像素性质才发生变化
- 将相邻像素放在一起测试，从而减少测试点的数目
基本思想
按照扫描线顺序，先计算出扫描线与多边形区域边界的交点，然后判断扫描线上的哪些部分在区域边界之内，再用要求的颜色显示边界内的像素。
实现
依次考察各条扫描线，一条扫描线从左至右与多边形的交点是成对出现的，即A,B点，C,D点之间的像素都位于多边形之内，则A、B为一个区段，C、D为一个区段。对这些区段内的像素用指定的颜色进行填充后，就完成了该扫描线的填充工作，再继续扫描下一跳扫描线。
一般多边形的填充过程，对于一条扫描线，步骤为：
存在问题
交点的个数必须是偶数才能保证填充的正确性。
1.当扫描线与多边形的顶点相交时，会出现异常情况。
这里引入一个概念-奇点
当扫描线与多边形P的交点是P的顶点时，则称该交点是奇点。
如何取舍顶点，保证交点正确配对？即如何保证交点数是偶数呢？
下面的这个具体实现讲解的非常清楚。
2.取整问题
- 扫描线与多边形边界交点坐标值不为整数
解决方法：当扫描线与多边形边界交点坐标为小数值时，如果多边形在此边界右侧，则将该小数值进1作为边界点，否则舍去小数部分并进行填充，这样可以使多边形不扩大。
3.水平边问题
扫描线与多边形的水平边相交时，交点理论上是无穷多个。
解决方法：
- 对于多边形的水平边，不计水平边与射线的交点。
4.多边形边界上像素的取舍问题？如何避免填充扩大化？
若将多边形边界看成是多边形内部，并对它们填充，则该多边形会被放大。
解决方法：
采取“左闭右开，下闭上开”的方法，即将左、下边界像素视为多边形内部，需要填充，而右上边界作为多边形外部，不予填充。
求交点的方法
求交点是通过边表和活性边表这两个数据结构来求的，具体参加下列博客。
活性边表
边表
2.区域填充
暂不研究
未完待续