本文为记录专业课计算机图形学的部分笔记，参考教材为Angel的第八版交互式计算机图形学——基于WebGL 2.0的自顶向下方法。
1、本节我们考虑光栅化（Rasterization），这也称为扫描转换，是确定哪些像素在由顶点表示的图元内部的过程（生成片元，片元有位置值（像素位置）和由顶点属性值插值得到的颜色、纹理坐标等其他属性），最终像素的颜色由颜色、纹理和其他顶点属性确定。以下是我们默认的前提：
①颜色buffer是一个n x m像素阵列，(0,0)对应于左下角。
②像素可由图形系统内部函数赋颜色值：write_pixel(int ix, int iy, int value)。
③颜色buffer是离散的，只讨论位于整数ix和iy位置上的像素。
④如果片元位置为(63.4 , 157.9)，取(63 ,158) 或(63.5, 157.5)，取决于像素中心位于整数值还是半整数值。
2、为了解决直线扫描转换平凡算法的“乘法”，考虑Digital Differential Analyzer，即数值微分法。DDA过去是一个机器设备，用于求解微分方程的数值解。
但是，DDA画出的是对于每个x最接近的整数y，这对于斜率大的直线有问题。这是一种取样问题，X方向的微小变化会引起Y方向的巨大变化，采样不稳定。解决方法是利用对称性，只对0 ≤|m| ≤1的直线应用上述算法。对于|m|>1的直线，交换x与y的角色。即对于每个y，找出最接近的整数x。
3、DDA算法中每一步还是需要一次浮点取整/加法，因此我们考虑Bresenham算法，这个算法可以不出现任何浮点运算，是硬件和软件光栅化器的标准算法。我们仍然只考虑0 ≤m ≤1的情形，其它情形利用对称性处理，假设像素中心在半整数，如果从一个已被确定激活的像素出发，那么下
一像素的可能位置只会有两种可能：
(a-b)的几何意义，原始决策变量解决了取整问题，但是有浮点乘法/除法运算，如何避免？引入新决策变量，整数计算形式 d = Δx ( a - b ), 避免浮点运算。这里，d为整数，当d > 0采用下像素；d < 0 采用上像素。但是仍然有整数乘法? 下一步，用整数增量加法方法：
考虑Bresenham算法中决策变量d的初值，在x=x1处，给定整点，为起始点，第一个点，直接绘制。
4、Bresenham算法增量形式算法的优点：对每个x值，只需要进行整数加法以及整数减法的符号判断；可以在图形芯片上用单个指令实现（如SIMD单指令多数据流）。两个例子（前者为a-b形式，后者为b-a形式）：
5、补充介绍直线扫描转换的吴方法/二步法：
决策变量 = 交点减中点。
6、早期的光栅系统可以显示被填充（转换）的多边形，但无法实时给多边形内部每个点着以不同颜色（只能单色显示）。对于直线的光栅化算法，占统治地位的是Bresenham算法，那么多边形呢？多边形的填充算法多种多样，具体选择与系统的实现框架有关，可以分为二大类：①将多边形几何形状转换为像素区域；②已经是某种颜色像素区域填充为另外一种颜色，都是像素区域。
7、我们先来考虑如何区分多边形的内部与外部？对于凸多边形，显然这很容易；但对于非简单多边形，就非常困难，可以：
①采用奇偶检测（Odd even test）/相交测试（Crossing test），统计与边界的交点数：
这里的补充详见第27讲。
②使用Winding number环绕次数方法：
注：在射线法实现中，通常是从点向右发出一条射线，当向上的边穿过射线记为+1，向下的边穿过射线记为-1。在五角星中，最外层区域并没有被边界包围、环绕数为0；五个角（三角形区域）边界绕了它们一圈、环绕数为1；中心（五边形区域）边界实际上绕了它两圈，环绕数为2。
8、OpenGL只保证正确填充凸多边形，实际应用时，由用户保证这条约定被遵守，或者用其它软件把给定多边形剖分为凸多边形（一般结果就是三角形的集合）。好的剖分算法应当不生成过长或过细的三角形，例如 Delaunay三角剖分（三角形的外接圆不包含面内的其他任何点），GLU具有实现这种剖分的功能。不同定义，不同的结果：
9、接下来我们考虑填充与分类（Fill and Sort）。
在帧缓冲区中的填充：一般在流水线尾部进行填充，而且只接受凸多边形，非凸多边形需要已被剖分。此外，顶点处的亮度（颜色）已被计算出来（Gouraud明暗处理算法）。与z缓冲区算法结合在一起（跟踪扫描线，插值亮度；增量方法工作量不大）。主要方法：满水填充法、扫描线填充方法、奇偶填充测试等。
10、我们先考虑漫水填充法（Flood Fill）。如果已经对多边形的边进行了扫描转换（光栅化）处理（多边形边界已经用像素表示了），需要得到边的前景色表示，即需要对对多边形内部像素进行颜色点亮处理。也就是把多边形的边扫描转化为边/内部填充颜色（黑），如果已知多边形区域和位于内部的一个种子点（白，未填充），那么可以递归填充：
```
flood_fill(int x, int y) { //从内部点开始
if(read_pixel(x,y)= = WHITE) { //查找未填充的像素
write_pixel(x,y,BLACK); //用前景色填充该像素
flood_fill(x-1, y); //本例，在四联通区域递归调用
flood_fill(x+1, y); // 也有八联通区域递归调用
flood_fill(x, y+1);
flood_fill(x, y-1);
} }
```
11、递归填充算法（一种基于底层数据结构的实现，这里是栈）的思路：
种子像素入栈stack，当栈非空时，执行如下三步操作（补充完整的漫水填充法算法）
（1）栈顶像素出栈；
（2）将出栈像素置成多边形色/前景色 ；
（3）按某个固定次序（例如上、下、左、右），检查与出栈像素相邻的四个象素
另：若其中某个像素不在边界上并且未置成多边形色，则把该像素入栈。
注意到有重复入栈现象（比如一个栈有两个4）。
12、对Singularities奇异点处理：（详见第27讲）
13、接下来我们考虑扫描线填充算法（Scan Line Fill）。该算法通过维持一个特别的数据结构（结构中保存扫描线与多边形的交点），然后按扫描线进行排序，逐扫描线跨距/区间（span）进行填充。
扫描线算法可描述如下（详见第28讲）
① 建立ET（预处理好的边表）；
② 将扫描线纵坐标y的初值置为ET中非空元素的最小序号，AET为空；
③ 执行下列步骤直至ET和AET都为空：
（a）把ET中与当前扫描线相交的边拷贝到与AET，同时保存AET中按x值实现的排序序列；
（b）对于扫描线y，在一对交点之间填充所需要的像素值；
（c）从AET中删去y＞ymax的项；
（d）对于仍留在AET中的每一项，用 x+dx 代替 x；
（e）检查并保证AET中各项按x值的排序；
（f）使y增1，成为下一条扫描线的坐标。
14、线段和多边形边线光栅化结果呈锯齿状的现象，这称为走样（Aliasing）。走样源于把连续表示的理想对象（无限分辨率）转换为离散表示的采样近似逼近对象（有限分辨率）。具体而言，走样误差是由帧缓冲区的3个问题所引起：
①大小为n * m的帧缓冲区，像素个数固定不变。多条不同的连续线段可能被相同的像素图案来近似表示 ，混淆在一起。
②像素位置固定于均匀分布栅格上，也就是不能把像素放于任意位置。
③像素的大小和形状固定，而多边形边缘形状变化
15、理想的线段应当是一个像素宽，但不能直接绘制，必须离散化成方形像素序列。如果对于每个x选择最佳的y（或者反过来）会导致走样的光栅化直线。注意，数学/几何上的最优不一定是视觉上的最优！
而对多边形，走样问题可能非常严重：
