图形管线中的光栅化
Rasterization, Bresenham's line algorithm, Barycentric coordinates
目录
光栅化位于渲染管线的 Primitive Assembly 之后，Fragment Shader 之前。而对于 D3D、OpenGL 这类有 Tessellation 和 Geometry Shader 的 API，光栅化则位于 Geometry Shader 之后。本文讨论的是 OpenGL ES 2.0，没有 Tessellation 和 Geometry Shader，所以光栅化位于 Primitive Assembly 之后。
Primitive 裁剪
光栅化的输入是 Primitive Assembly 的输出。在 Primitive Assembly 的最后阶段，会对 Primitive 进行裁剪。对于点 Primitive，如果该点位于裁剪体（Clipping Volume） 在裁剪空间中，裁剪体的定义是 $$ -w_c \leq x_c \leq w_c \\ -w_c \leq y_c \leq w_c \\ -w_c \leq z_c \leq w_c $$ 的远近裁剪平面之外，则该点会被裁剪掉；对于线段 Primitive，如果该线段和远近裁剪平面相交，则该线段会被裁剪，然后生成一个或两个新的顶点，对于每个被裁剪的顶点，会生成一个新的值，$0 \leq t \leq 1$，而与被裁剪顶点的varying变量也会被裁剪，使用线性插值得到 因为这个线性插值是在裁剪空间上完成的，还没有除以 $w_c$，所以裁剪的varying值是透视正确的。 ；对于三角形 Primitive，如果每一条边都位于裁剪体内，则不会进行裁剪，否则就会被裁剪或被 discarded，因为三角形被裁剪会引入新的顶点，所以会变成多边形（Polygon）。以上这个裁剪过程详细内容可参考OpenGL ES 2.0 规范的 2.13 节 Primitive Clipping。
Primitive 裁剪完之后，会对裁剪空间的顶点做透视除法，得到 NDC，然后对 NDC 做 viewport 变换，得到顶点的窗口坐标，然后将顶点的窗口坐标发送到光栅化器，完成顶点的光栅化。
下面介绍OpenGL ES 2.0 规范中第三章光栅化的做法。
光栅化
光栅化是将一个 Primitive 转换为二维图像的过程，包含两个过程，
- 首先是确定窗口坐标中的哪些网格方块是被该 Primitive 占据的，
- 然后是对每个被占据的网格方块赋予一个颜色（实际上是在 fragment shader 中进行着色的）和深度值。
光栅化完之后会得到很多 fragments，它们会被传到 fragment shader 中进行执行，得到每个 fragment 的颜色值，而深度值由光栅化的过程决定（也有扩展可以使得在 fragment shader 中修改深度值）。最后，得到颜色值和深度值（还有可选的 stencil 值）的 fragments 会传到 per-fragment operations 阶段，包括 scissor test、stencil test、depth test、blending 和 dithering。
一个网格方块和它的参数被称为一个 fragment，这些参数包括带符号的 $z$ 值和 varying 数据，这些参数统称为该 fragment 的 associated data。一个 fragment 位于它的左下角，一个整数网格坐标。光栅化也指向一个 fragment 的 center，它从该 fragment 左下角偏移了 $(\frac{1}{2}, \frac{1}{2})$。
点的光栅化
对于 point 类型的 primitive，光栅化输出的是正方形的 fragments，正方形的中心点位于 $(x_w, y_w)$，而该正方形边长由 vertex shader 的输出gl_PointSize控制，该值不能无限大，有一个范围，由具体的实现自己定义。除了gl_PointCoord 之外，生成的所有 fragments 的varying数据都是一样的，内置变量gl_PointCoord定义了每个 fragment 位于该矩形内的坐标空间$(s, t)$，分别从左往右地 0 到 1 和从上往下地从 0 到 1。下面的公式可以用来计算 $(s, t)$ 的值：
$$ s = \frac{1}{2} + \frac{x_f + \frac{1}{2} - x_w}{\text{size}} \\ t = \frac{1}{2} - \frac{y_f + \frac{1}{2} - y_w}{\text{size}} $$
公式中的 size 即该点的大小gl_PointSize，$(x_f, y_f)$ 是该 fragment 的窗口坐标，$(x_w, y_w)$ 是顶点的窗口坐标，顶点的窗口坐标对于所有的 fragments 都一样。例如 $(x_w, y_w) = (200, 100), \text{size} = 50$ 时，$x_f$ 和 $y_f$ 的范围分别是 $[175, 225]$ 和 $[75, 125]$。下面是 WebGL 中光栅化点 Primitive 的结果：
这个$(s,t)$值和可以控制点大小的特性使得用点 Primitive 实现带纹理的正方形变成可能，例如像素大小不变（或可变）的 Billboard 和粒子系统。
线段的光栅化
线段由一个 line strip、一个 line loop 或一系列单独的 lines 产生。
如果线段和裁剪体相交，则线段会被裁剪到裁剪体的边界，对应的顶点属性和varying数据也会用线性插值重新生成，然后再进行光栅化。
被光栅化的线段宽度可以用LineWidth来控制，线宽具有一定的范围，但通常只能是 1。
光栅化线段首先需要确定该线段是 x-major 的还是 y-major 的，斜率位于 $[-1,1]$ 之间的线段是 x-major 的，否则就是 y-major 的。
GL 使用 "diamond-exit" 规则来确定光栅化线段会产生哪些 fragments。对于 center 位于窗口坐标 $(x_f,y_f)$ 的 fragment，定义一个菱形区域，它是四个半平面的交集：
$$ R_f = \{(x, y) \Big| | x-x_f | + |y-y_f| < 1/2 \} $$
起点和终点分别是 $\mathbf{p}_a$ 和 $\mathbf{p}_b$ 的线段会产生哪些与 $R_f$ 相交的 fragments，但是，如果 $\mathbf{p}_b$ 位于 $R_f$ 内，则不会产生 $\mathbf{p}_b$ 对应的 fragment。
当 $\mathbf{p}_a$ 和 $\mathbf{p}_b$ 位于 fragment center 时，这些 fragments 的生成方式就会简化成做了一点修改的 Bresenham 算法：在这种描述下生成的线是“半开的”，即最后的 fragment 不会被绘制。这意味着当光栅化一系列相连的线段时，线段之间的公共端点只会被生成一次，而不是两次（如果使用的是 Bresenham 算法就会生成两次）。
下面是使用 Bresenham 算法 模拟光栅化线段的结果：
然后是计算每个被光栅化的 fragments 的 associated data。假设生成的 fragment 的 center 是 $\mathbf{p}_r = (x_d, y_d)$，而两个端点是 $\mathbf{p}_a = (x_a, y_a)$ 和 $\mathbf{p}_b = (x_b, y_b)$。则设
$$ t = \frac{(\mathbf{p}_r - \mathbf{p}_a) \cdot (\mathbf{p}_b - \mathbf{p}_a)}{||\mathbf{p}_b - \mathbf{p}_a||^2} $$
那么该 fragment 的 associate data $f$ 是
$$ f = \frac{(1-t) f_a / w_a + t f_b / w_b}{(1-t) / w_a + t / w_b} $$
其中的 $f_a$ 和 $f_b$ 分别是该线段端点的 associated data，$w_a$ 和 $w_b$ 分别是该线段端点的 clip $w$ coordinates。但是，深度值（window $z$）必须使用线性插值：
$$ f = (1-t) f_a + t f_b $$
多边形的光栅化
多边形由 triangle strip、triangle fan 或一系列单独的 triangles 生成。像点和线段一样，多边形的光栅化也由一些变量控制。
第一部是先确定该多边形是正面的还是背面的，这由该多边形在窗口坐标下的面积的符号决定：
$$ a = \frac{1}{2} \sum_{i=0}^{N-1} x^i_w y^{i \oplus 1}_w - x^{i \oplus 1}_w y^i_w $$
其中的 $x_w^i$ 和 $y_w^i$ 是 $n$ 顶点多边形的第 $i$ 个顶点的窗口坐标，而 $i \oplus 1$ 对 $(i+1)$ 取模。如果顶点顺序是逆时针的，则面积的符号的正，如果是顺时针的，则符号是负的。而如果FrontFace设为CCW，则可以直接使用该符号，如果是CW，则表示该面积的符号应该先取反，然后再使用 OpenGL ES 2.0 规范的 3.5.1 小节对这里是否取反的描述刚好反了，ES 3.0 规范的 3.6.1 小节改回来了。 。完成可能的取反之后，如果符号是正的，则表示该多边形是正面的，否则表示是背面的。例如如果顶点顺序是逆时针，则计算的符号是正的，然后FrontFace设为CCW，则不用取反，直接使用，如果是CW，则要取反，逆时针的符号变成负的，表示逆时针顺序对应的是背面。
可以使用CullFace决定是否对正面或背面进行光栅化。
用于光栅化多边形生成 fragments 的规则被称为 point sampling。
生成一个 triangle 内的 fragments 之后，这些 fragments 的 associated data 由 triangle 的重心坐标（barycentric coordinates）得到。重心坐标是三个数字 $a, b, c$ 的集合，它们的范围都是 $[0, 1]$，且 $a+b+c=1$。得到重心坐标后，就可以计算该三角形内或边界上的任意点的坐标：
$$ p = a p_a + b p_b + c p_c $$
其中 $p_a$、$p_b$ 和 $p_c$ 是该三角形的顶点，而 $a, b, c$ 是：
$$ a = \frac{A(p p_b p_c)}{A(p_a p_b p_c)}, b = \frac{A(b p_a p_c)}{A(p_a p_b p_c)}, c = \frac{A(p p_a p_b)}{A(p_a p_b p_c)} $$
其中的 $A(lmn)$ 表示的是顶点为 $l, m, n$ 的三角形在窗口坐标下的面积。
将位于 $p_a, p_b, p_c$ 的一个 datum（即顶点属性，例如顶点坐标，顶点纹理坐标，顶点法线）分别记为 $f_a, f_b, f_c$，则位于一个 fragment 的 datum 值 $f$ 为：
$$ f = \frac{a f_a / w_a + b f_b / w_b + c f_c / w_c}{a / w_a + b / w_b + c / w_c} $$
其中的 $w_a, w_b, w_c$ 分别是 $p_a, p_b, p_c$ 的裁剪坐标的 $w$ 分量。$a, b, c$ 必须对应该 fragment center 的精确坐标。
就像线段的光栅化那样，深度值（window $z$）必须使用线性插值得到：
$$ f = a f_a + b f_b + c f_c $$
下面是使用重心坐标模拟光栅化三角形的结果：
拖动三角形的顶点，当三角形变得很细时，你会发现光栅化的 fragment 会变得“断断续续”的，这种锯齿被称为 sub-pixel aliasing。可以通过增加光栅化时的采样数来解决，例如 SSAA 或 MSAA。Diving into Anti-Aliasing 是一篇不错的文章，其介绍了锯齿的类型以及对应的抗锯齿办法。
深度值偏移
光栅化多边形时，还可以通过设置额外的状态，计算一个值，对所有 fragments 的深度值进行一定的偏移。调用PolygonOffset(float factor, float units)可以设置这些状态。要使用这个深度值偏移的功能还需要调用Enable来开启POLYGON_OFFSET_FILL。
这个功能可以用在渲染两个叠加的面时，对另一个面的深度值进行一定的偏移，避免它们之间的 z-fighting，还可以用在 Shadow Map 中，作为深度值的 bias。
还需要注意的是，即使对深度值做了偏移，但 fragments 的深度值总是被限制在 $[0, 1]$ 之间。
无论是点、线段或多边形，光栅化时只对 fragment 的 center 采样了一次，所以都会产生锯齿！有些图形 API 允许在光栅化阶段进行多次采样，以减少锯齿的产生，即 MSAA。