光线追踪是像素顺序渲染，依次考虑每个像素并找到影响其颜色的对象
依次考虑每个几何图元，找到图像中被它占据的像素的过程称为光栅化（rasterization）
对象顺序渲染（object-order rendering）也可以被称为光栅化渲染（rendering by rasterization）
光栅化渲染的操作序列，被称为图形管线（graphics pipeline）
对象顺序渲染效率高，一个 pass 遍历场景中的所有几何体，明显比使用观察射线重复检索场景中指向的几何体效率高
并不是只有一种方法可以实现对象顺序渲染，基于不同的目标，有两种图形管线：
- 硬件管线：OpenGL、Direct3D 等，实时渲染
- 软件管线：用于电影制作的 RenderMan 等，高品质动画和视觉特效按比例缩放到巨大的场景中
尽管目标不同，它们有着很多的相同之处
对象顺序渲染中的任务可以分为：
- 光栅化之前的几何操作，最常见的是前两章的矩阵变换，从物体空间到屏幕空间
- 光栅化之后的像素操作，这一步由光栅器（rasterizer）完成，最常见的是隐藏面消除（hidden surface removal），将更接近相机的面放到远离相机的面的前面
在不同的阶段，也会有许多其他的操作，有时可以使用通用的程序来实现不同的渲染效果
本章中，将会将图形管线分成四个阶段：
- 几何对象（由一系列的顶点描述）从程序或文件中读入图形管线
- 顶点处理阶段（vertex-processing stage）：处理顶点，生成图元送入下一个阶段
- 光栅化阶段（rasterization stage）：光栅器（rasterizer）将图元分解成片元（fragments，一个片元对应图元覆盖的一个像素，里面存有对应的属性值）
- 片元处理阶段（fragment-processing stage）：处理片元
- 片元混合阶段（fragment-blending stage）：混合一个像素对应的多个片元（因为每个图元都会生成它自己的片元，难免会有交叉）
光栅化（Rasterization）
光栅化是对象顺序渲染的核心操作，光栅器是任何图形管线的核心
对于每个进入的图元，光栅器有两个工作：
- 枚举（enumerate）图元覆盖的像素
- 为图元覆盖的每个像素插值（interpolate）出它所对应的属性值
光栅器输出的是一组片元，每个片元代表一个特定的像素，并带有它自己的一组属性值
绘制线段
大多数图形库都包含绘制直线的命令，两个端点，绘制之间的一条线
使用直线方程（隐式方程、参数方程），本节使用隐式方程
中点算法与 Bresenham 算法画出的线相同，但在某种程度上，中点算法会更加直接一点
中点（Midpoint）算法
对于屏幕上的两个点 $(x_0,y_0)$、$(x_1,y_1)$，假设 $x_0\le x_1$，使用直线的隐式方程：
$$ f(x,y)=(y_0-y_1)x+(x_1-x_0)y+x_0y_1-x_1y_0=0 $$图像的斜率是：
$$ m=\frac{y_1-y_0}{x_1-x_0} $$$m$ 可以被分成四种情况：$m\in(-\infty,-1]$、$m\in(-1,0]$、$m\in(0,1]$、$m\in(1,+\infty)$，下面我们假设 $m\in(0,1]$，其他情况类似
对于 $m\in(0,1]$ 来说，在从左端点往右端点的移动中，平移“多于”上升（对于 $y$ 轴向下的 API 来说是下降，但在最后结果中这并不影响，两种情况通用）
中点算法的关键假设是我们尽可能画出没有“间隔（gap）”的最细的线，对角连接不认为是间隔
在线段从左端点到右端点移动时，只有两种可能性：
- 将下一个像素绘制在右方，此时新绘制的像素与当前的像素具有同样的高度
- 将下一个像素绘制在右上方（对角位置），高度会增加 $1$
按照这个方法，在 $m\in(0,1]$ 的情况下，每列中只有一个需要绘制的像素（$0$ 意味着 gap，多于一个则太粗了），每行中可能会有多个像素需要绘制
在 $m\in(0,1]$ 的情况下，中点算法首先得到左右端点像素的列号（$x$ 值），然后循环中间的每一列，得到每一列需要绘制的像素的行（$y$ 值）
伪代码的框架如下：
y = y_0
for x = x_0 to x_1 do
draw(x, y)
if (some condition) then
y = y + 1
这个算法的关键在于 if 语句的条件
一个有效的方法就是检查两个像素（右方和右上方）的中点。如果直线高于中点，那么绘制在右上方，低于中点则绘制在右方。
我们可以算出中点坐标为 $(x+1,y+0.5)$，要看直线和中点的位置关系，只需代入即可
我们把 if 语句填充好，伪代码就变成了：
y = y_0
for x = x_0 to x_1 do
draw(x, y)
if (f(x + 1, y + 0.5) < 0) then
y = y + 1
如果追求更高的效率，可以使用增量方法。
假设在中间的一步中，我们已经知道了 $f(x,y-0.5)$ 或 $f(x,y+0.5)$，那么：
$$ f(x+1,y+0.5)-f(x,y-0.5)=(y_0-y_1)+(x_1-x_0)\\ f(x+1,y+0.5)-f(x,y+0.5)=(y_0-y_1) $$这样我们就可以求得增量 $d$
伪代码如下：
y = y_0
d = f(x_0 + 1, y_0 + 0.5) // 第一次的中点位置是 (x_0 + 1, y_0 + 0.5)，计算此时的 d
for x = x_0 to x_1 do
draw(x, y)
if (d < 0) then // 如果中点在直线上方
y = y + 1
d = d + (x_1 - x_0) + (y_0 - y_1) // 计算下一次的 d
else
d = d + (y_0 - y_1) // 计算下一次的 d
这个增量版本的算法一般会更快速，但是会积累由加法带来的误差（但是线段一般不会很长，所以一般不会很严重）
可以把 $(x_1 - x_0) + (y_0 - y_1)$ 和 $(y_0 - y_1)$ 作为变量，可以更快一点（我们希望编译器帮我们做这一点，但是对于关键算法来说，要检查一下编译产物）
Bresenham 算法
和中点算法其实差不多
还是从 $m\in(0,1]$ 入手
我们知道，当 $x$ 增加 $1$ 时，$y$ 增加 $m$，我们先记为 $\delta$
我们将 $x$ 对应的真实函数值与 $y$ 之差记为 $\epsilon$
当 $\epsilon +\delta\lt0.5$ 时，在中点下方，否则在中点上方
类似于中点算法，我们每次判断完给 $\epsilon$ 加上一个 $\delta$ 就能下一次继续用了。
先算一下 $y_0$ 与它对应像素的 $y$ 值：
$$ f(x_0,y)=(y_0-y)(x_0-x_1) $$所以：
$$ y_0-y=\frac{f(x_0,y)}{x_0-x_1} $$伪代码如下：
y = y_0
epsilon = f(x_0, y_0) / (x_0 - x_1) // 上面求得
delta = (y_0 - y_1) / (x_0 - x_1) // x 增加 1 后，y 实际上增加一个斜率大小
for x = x_0 to x_1 do
draw(x, y)
epsilon = epsilon + delta // 先加上 delta
if (abs(epsilon) >= 0.5) then // 在上方，y 要加一，相应的 epsilon 要减一
epsilon = epsilon - 1.0
y = y + 1
对于其他斜率的就不搞了
三角形光栅化
我们经常想要使用二维点 $\vec {p_0}=(x_0,y_0)$、$\vec {p_1}=(x_1,y_1)$、$\vec {p_2}=(x_2,y_2)$ 来绘制二维三角形，这与线段的绘制相似，但又有一些微妙之处。
第一个微妙之处是：我们可能想要根据顶点的属性值来插值。
我们可以直接使用重心坐标系。若三个顶点的属性值为 $\vec {c_0}$、$\vec {c_1}$、$\vec {c_2}$，则在重心坐标系中的点 $(\alpha,\beta,\gamma)$ 处的值为：
$$ \vec c=\alpha\vec{c_0}+\beta\vec{c_1}+\gamma\vec{c_2} $$这种类型的颜色插值在图形中被称为 Gouraud 插值
另一个微妙之处是：通常我们栅格化的三角形有公共边和公共顶点
这意味着我们想要栅格化相邻的三角形，并且邻接的部分没有孔洞。我们可以通过中点算法来解决这个问题。先绘制轮廓，然后填充内部像素。但如果相邻的三角形有不同的属性值，那么最终公共边上的像素属性值取决于绘制顺序
避免孔洞问题和顺序问题的最常见的方法（惯例）是：仅绘制中心位置在三角形内部的像素（即 $\alpha,\beta,\gamma\in (0,1)$）。
但是这就产生了一个问题，如果中心正好在三角形的边上该怎么办。这一节后面会进行讨论。
从这几段话中，我们知道了：重心坐标允许我们决定是否绘制像素，重心坐标可以方便地进行插值。所以，我们对三角形光栅化的问题归结为有效地找到像素中心的重心坐标
暴力算法为：
for all x do
for all y do
compute (alpha, beta, gamma) for (x, y)
if (0 <= alpha, beta, gamma <= 1) do
c = alpha c_1 + beta c_2 + gamma c_3
drawpixel (x, y) with color c
在这个基础上，我们可以限制循环的 $x$ 与 $y$ 坐标的范围，使得更加高效：
x_min, x_max = floor(x_i), ceiling(x_i)
y_min, y_max = floor(y_i), ceiling(y_i)
for y = y_min to y_max do
for x = x_min to x_max do
alpha = f_12(x, y) / f_12(x_0, y_0)
beta = f_20(x, y) / f_20(x_1, y_1)
gamma = f_01(x, y) / f_01(x_2, y_2)
if (alpha, beta, gamma > 0) then
c = alpha c_1 + beta c_2 + gamma c_3
drawpixel (x, y) with color c
其中 $f_{ij}$ 计算的是到对边的高：
$$ f_{ij}(x,y)=(y_i-y_j)x+(x_j-x_i)y+x_iy_j-x_jy_i $$这里我们把 0 <= alpha, beta, gamma <= 1 替换成了 alpha, beta, gamma > 0，这是因为 $\alpha=1-\beta-\gamma$，这三个都大于 $0$ 就能保证它们都在 $(0,1)$ 之间
可以变为增量型：内层循环只有 $x$ 在变化，$\alpha$、$\beta$、$\gamma$ 三个式子中分母不变，分子是增量型的，所以它们是增量型的，所以 $\vec c$ 也是增量型的。外层也可以写成增量型
接下来考虑在边上像素绘制，我们需要定义像素属于哪一个三角形
选择任意屏幕外侧一点 $\vec p$，假设两个三角形中，公共边的对顶点分别为 $\vec {a}$、$\vec {b}$，选择与 $\vec p$ 在同一侧的对顶点对应的三角形
屏幕外的点也有可能在公共边对应的直线上，但这种情况太少了
公共点不讨论吗？对于公共点来说应该属性是相同的，公共点的属性值并不是插值得来的
$(-1, -1)$ 是一个很好的点
伪代码如下：
x_min, x_max = floor(x_i), ceiling(x_i)
y_min, y_max = floor(y_i), ceiling(y_i)
f_alpha = f_12(x_0, y_0)
f_beta = f_20(x_1, y_1)
f_gamma = f_01(x_2, y_2)
for y = y_min to y_max do
for x = x_min to x_max do
alpha = f_12(x, y) / f_alpha
beta = f_20(x, y) / f_beta
gamma = f_01(x, y) / f_gamma
if (alpha, beta, gamma >= 0) then
if (alpha > 0 or f_alpha * f_12(-1, -1) > 0) and
(beta > 0 or f_beta * f_20(-1, -1) > 0) and
(gamma > 0 or f_gamma * f_01(-1, -1) > 0) then
c = alpha c_1 + beta c_2 + gamma c_3
drawpixel (x, y) with color c
只有在两个三角形中，公共顶点使用相同的顺序（比如都是左下到右上）构造直线方程时，才能出现一个大于 $0$，一个小于 $0$ 的情况
对于一个错误的三角形，除法可能是除以零，需要正确考虑浮点错误条件或者进行判断
透视矫正插值（Perspective Correct Interpolation）
由于透视投影变换中，进行了非线性的变换，所以插值时会有一些问题
由于透视中的物体随着与摄像机的距离的增加而变小，因此在 3D 中均匀间隔的行应该在 2D 图像空间中随距离的增加而压缩。
具体地，我们先回顾一下透视投影：
$$ \mathbf P\begin{bmatrix}x\\y\\z\\1\end{bmatrix}=\begin{bmatrix}nx\\ny\\(n+f)z-fn\\z\end{bmatrix}\sim\begin{bmatrix}nx/z\\ny/z\\n+f-fn/z\\1\end{bmatrix} $$然后，再经过正交投影变换，得到透视投影矩阵：
$$ \mathbf M_{\text{per}}=\mathbf M_{\text{orth}}\mathbf P $$我们发现，经过这个变换候，每个坐标都除了一个 $z$，所以会出现离摄像机越远，越“密集”的情况
如果我们现在在相机空间中有两点 $\vec r$、$\vec R$，这两点构成的线段中一点 $\vec p=\vec r+t(\vec R-\vec r)$，那么点 $\vec p$ 的纹理坐标应该是：
$$ u_{p}=u_r+t(u_R-u_r) $$经过透视投影变换，$\vec r$、$\vec R$ 转换到规范视空间的点为 $\vec r'$、$\vec R'$，$\vec p$ 对应的点 $\vec p'=\vec r'+t'(\vec R'-\vec r')$，那么 $\vec p'$ 的纹理坐标是：
$$ u_{p'}=u_{r'}+t'(u_{R'}-u_{r'}) $$上一章我们推出过下面的关系式：
$$ t'=\frac{w_Rt}{w_r+t(w_R-w_r)} $$我们求一下反函数，可以得到：
$$ t=\frac{w_rt'}{w_R+t(w_r-w_R)} $$假如我们换成重心坐标呢？设三角形内一点 $\vec p$ 的重心坐标为 $(\alpha,\beta,\gamma)$，即：
$$ \vec p=\alpha\vec a+\beta\vec b+\gamma\vec c $$经过透视变换后：
$$ \begin{align} \vec p'&=\mathbf M_\text{per}(\alpha\vec a+\beta\vec b+\gamma\vec c)\\ &=\alpha\mathbf M_\text{per}\vec a+\beta\mathbf M_\text{per}\vec b+\gamma\mathbf M_\text{per}\vec c\\ &=\alpha\vec a'+\beta\vec b'+\gamma\vec c' \end{align} $$与上一章方法相同，同质化后变成了：
$$ \vec p'\rightarrow\frac{\alpha\vec a'+\beta\vec b'+\gamma\vec c'}{\alpha w_a+\beta w_b+\gamma w_c}\\ \vec a'\rightarrow\frac{\vec a'}{w_a}\\ \vec b'\rightarrow\frac{\vec b'}{w_b}\\ \vec c'\rightarrow\frac{\vec c'}{w_c}\\ $$然后我们看能不能找到它们之间的关系：
$$ \begin{align} \frac{\alpha\vec a'+\beta\vec b'+\gamma\vec c'}{\alpha w_a+\beta w_b+\gamma w_c} &=\frac{\alpha w_a}{\alpha w_a+\beta w_b+\gamma w_c}\frac{\vec a'}{w_a}+\cdots\\ &\equiv\alpha'\frac{\vec a'}{w_a}+\beta'\frac{\vec b'}{w_b}+\gamma'\frac{\vec c'}{w_c} \end{align} $$所以：
$$ \alpha'=\frac{\alpha w_a}{\alpha w_a+\beta w_b+\gamma w_c}\\ \beta'=\frac{\beta w_b}{\alpha w_a+\beta w_b+\gamma w_c}\\ \gamma'=\frac{\gamma w_c}{\alpha w_a+\beta w_b+\gamma w_c} $$我们令分母 $\alpha w_a+\beta w_b+\gamma w_c=S$，我们可以很容易得到：
$$ S=\frac{\alpha w_a}{\alpha'}=\frac{\beta w_b}{\beta'}=\frac{\gamma w_c}{\gamma'} $$即：
$$ \alpha':\beta':\gamma'=\alpha w_a:\beta w_b:\gamma w_c $$再整理一下：
$$ \frac{\alpha'}{w_a}:\frac{\beta'}{w_b}:\frac{\gamma'}{w_c}=\alpha:\beta:\gamma $$那么根据相加得 $1$ 的性质，我们可以得到：
$$ \alpha=\frac{\alpha'/w_a}{\alpha'/w_a+\beta'/w_b+\gamma'/w_c}\\ \beta=\frac{\beta'/w_b}{\alpha'/w_a+\beta'/w_b+\gamma'/w_c}\\ \gamma=\frac{\gamma'/w_c}{\alpha'/w_a+\beta'/w_b+\gamma'/w_c}\\ $$形式和上面的 $\alpha'$、$\beta'$、$\gamma'$ 的式子相似，只不过乘改成了除
书上的理解方式与我写的这些不同，我看不懂。
算纹理坐标的伪代码如下：
for all x_s do
for all y_s do
compute (alpha, beta, gamma) for (x_s, y_s)
if (0 <= alpha, beta, gamma <= 1) then
u_s = alpha * (u_0 / w_0) + beta * (u_1 / w_1) + gamma * (u_2 / w_2)
v_s = alpha * (v_0 / w_0) + beta * (v_1 / w_1) + gamma * (v_2 / w_2)
1_s = alpha * (1 / w_0) + beta * (1 / w_1) + gamma * (1 / w_2)
u = u_s / 1_s
v = v_s / 1_s
drawpixel (x_s, y_s) with color texture (u, v)
当然，这个伪代码中出现的许多表达式将在循环之外预先计算以加快速度
裁切（Clipping）
简单地将图元转换为屏幕空间并栅格化它们并不是很有效。这是因为视空间之外的图元——特别是眼睛后面的图元——最终被栅格化，从而导致不正确的结果。
看下面的图：
光栅化之前必须进行裁切操作，以移除可能延伸到眼睛后面的图元部分
裁切是图形学中常见的操作，当一个几何实体切除（cuts）另一个几何实体时需要进行裁切，一个重要的应用就是三角形的裁切
在准备光栅化时，需要被裁切的是在视空间外部的部分，剪切六个面是安全的，但是许多图形系统仅剪切 near plane
这一节讨论剪切的基础实现，两个最常见的方案是：
在世界坐标系中用六个包围摄像机的截面进行裁切：透视变换是由相机空间到标准视空间的变换，对八个顶点做逆透视变换，然后就能找到所有的六个面
在同质化前的齐次坐标空间进行裁切：
$$ l\le\frac{nx}{z}\le r\\ b\le\frac{ny}{z}\le t\\ f\le\frac{(n+f)z-fn}{z}\le n\\ $$这里有 $w=z$，把分子用 $x$、$y$、$z$ 代替，可以写成更一般的六个平面：
$$ \begin{align} -x+lw&=0\\ x-rw&=0\\ -y+bw&=0\\ y-tw&=0\\ -z+nw&=0\\ z-fw&=0\\ \end{align} $$这些平面相较于前一个方案更简单，所以效率会更高，但是仍然可以通过将标准视空间改成 $[0,1]^3$ 来改进效率。
不管是哪种方案，都可以写成下面的伪代码框架：
for each of six planes do
if (三角形完全在平面外部) then
break // 完全不可见
else if (三角形跨越平面) then
对三角形进行裁切
if (剩下的是四边形) then
分成两个三角形
那如何通过平面进行裁切呢？
回忆前面的章节，平面的隐式方程可以写成下面的形式：
$$ f(\vec p)=\vec n\cdot(\vec p-\vec q)=0 $$这个方程常常被写为：
$$ f(\vec p)=\vec n\cdot\vec p+D=0 $$第 12 章有叫 BSP 树的东西用来裁切（？这里应该是简化版的算法？不管了）
这很像二维空间中直线的形式，如何判断在屏幕的内侧还是外侧也和判断点在直线两端的方法差不多。
我们一般认为当 $f(\vec p)<0$ 时在面的“内侧”，否则在外侧，检查 $f (\vec a)$ 和 $f (\vec b)$ 是否有不同的符号即可
如果我们确定了线段横跨两侧，我们可以代入来求得交点，设：
$$ \vec p =\vec a+t(\vec b -\vec a) $$代入得：
$$ \vec n\cdot(\vec a+t(\vec b -\vec a))+D=0 $$解得：
$$ t=\frac{\vec n\cdot\vec a + D}{\vec n\cdot(\vec a - \vec b)} $$找到交点之后，需要根据 12 章的内容来将旧的三角形裁切，留下一个或者两个三角形
光栅化前后的操作
在图元被光栅化之前，图元的顶点必须在屏幕坐标系中被定义，并且必须知道顶点的颜色和顶点的其他需要插值的属性
准备这个数据是在顶点处理阶段完成的，在这个阶段，顶点会进行模型变换、视变换、投影变换和视图变换，映射到屏幕空间中
同时，根据需要，其他的信息（例如颜色、表面法线、纹理坐标）也会被进行相应的变换
在光栅化之后，进行进一步处理以计算每个片元的颜色和深度。这个阶段可简单（仅仅使用插值后的颜色，使用光栅器计算出来的深度）也可复杂（复杂的着色操作）
最后，片元混合阶段会重叠每个像素的图元（可能有多个）产生的片元组合起来计算最终的颜色。最常见的混合方法是选择深度最小的片元的颜色（最接近眼睛）
简单的 2D 绘制
最简单的管线在顶点或片元阶段什么都不做，在混合阶段，（按照绘制顺序）每个片元的颜色覆盖前一个片元的颜色。
应用程序直接在像素坐标中提供图元，而光栅器完成所有工作。
用于绘制用户界面、绘图和其他 2D 内容
一个小型的 3D 管线
为了在 3D 中绘制对象，对 2D 绘制流水线的唯一改变是一个变换矩阵：顶点处理阶段将输入的顶点位置乘以模型变换、视变换、投影变换和视窗变换的乘积，产生屏幕空间三角形，然后以与在 2D 中直接绘制它们相同的方式来绘制这些三角形。
最小 3D 管线的一个问题是，为了获得正确的遮挡关系，图元必须以自后而前的顺序绘制。这样的算法被称为画家算法（painter’s algorithm），类似于首先绘制绘画的背景，然后在上面绘制前景。
画家的算法是一种有效的删除隐藏表面的方法，但它有几个缺点：
- 不能处理彼此遮挡的三角形（在一个遮挡循环 occlusion cycle 中）
- 不存在从后到前的顺序（？）
- 最重要的是，按深度对图元进行排序速度很慢
使用 z-Buffer 绘制物体阻挡
在实践中，很少使用画家算法。相反，使用更加简单的算法，称为 z-buffer 算法
在每个像素上，我们记录到到目前为止绘制过的最近表面的距离，我们丢弃那些离距离更远的片元。除了红色、绿色和蓝色值之外，通过为每个像素分配一个额外的值来存储最近的距离，称为深度缓冲（depth buffer）或者 z-buffer
z-buffer 算法是在片元混合阶段实现的，通过将每个片元的深度与存储在 z-buffer 中的当前值进行比较，z-buffer 被初始化为最大值
z-buffer 算法要求每个片元携带深度。这是通过插值 $z$ 坐标得到的
z-buffer 是一种简单且实用的方法，直到现在它都是主要的方法。它比几何方法简单得多，几何法将表面切割成可以按深度排序的片段。而深度顺序只需要在像素的位置确定。它普遍支持硬件图形管道，也是软件管道最常用的方法。
精度问题：
在实践中，$z$ 值通常存储为非负整数，比真正的浮点数更好，因为快速内存很昂贵
整数的使用会造成一些精度问题，如果整数范围为 $\{0,1,\dots,B-1\}$，我们可以将 $0$ 映射到 near 平面，$B-1$ 映射到 far 平面。
我们把每个 $z$ 值放到对应的一个深度为 $\Delta z=(f-n)/B$ 的桶中（这里假设 $f$ 与 $n$ 为正数），要使得 $\Delta z$ 变小，需要让 $f-n$ 变小或者让 $B$ 变大
在创建透视图像时，必须非常小心地处理 z 缓冲区的精度。上面用到的 $\Delta z$ 是在透视投影除法之后的，即使用的是：
$$ z=n+f-\frac{fn}{z_w} $$而事实上，桶的“宽度”和 $z_w$ 有关，而不是 $z$，但是我们存储的时候使用的是 $z$，但实际上是对 $z_w$ 进行的分隔，我们可以大概估算一下实际上的 $\Delta z_w$，两边求导：
$$ \Delta z\approx\frac{fn\Delta z_w}{z_w^2} $$然后得到：
$$ \Delta z_w\approx\frac{z_w^2\Delta z}{fn} $$影响精度的是最大的“宽度”，注意到，当 $z_w$ 最大时“宽度”最大，代入 $z_w=f$ 得：
$$ \Delta z_w^\max\approx\frac{f\Delta z}{n} $$上述公式表示：如果我们希望让 $n$ 尽可能地接近 $0$（这样能在摄像机前捕获尽可能多的物体），会导致最大分箱的宽度趋向正无穷，这意味着会有大量物体无法区分它们的前后关系。
一般地，我们会希望最大分箱宽度尽可能地小，使我们能更好地区分所有物体地远近关系。因此，仔细选择 $n$ 和 $f$ 总是很重要的。
逐顶点着色（Per-vertex Shading）
现在，我们仅仅实现了设置顶点颜色，然后插值绘制出来。很多情况下，我们还需要渲染方程来对 3D 对象着色。
处理着色计算的一种方法是：在顶点处理阶段提供法向量、光源位置和颜色，对于每个顶点应用渲染方程计算颜色，然后作为顶点颜色传给光栅器，这就叫逐顶点着色，有时也被称为 Gouraud 着色
需要做出的一个决定是进行着色计算的坐标系。世界空间或相机空间都是不错的选择。要选一个正交的坐标系，因为渲染方程需要角度。相机空间更方便，因为相机在原点
逐顶点着色的缺点是它不能在着色中产生任何比图元更小的细节，因为它只对每个顶点计算一次着色，而不会计算顶点之间的着色
逐片元着色（Per-fragment Shading）
为了避免前面的伪影，我们可以在片元处理阶段，使用插值后的向量执行着色计算
在逐片段着色中，着色所需的几何信息作为属性通过光栅器传递，因此顶点阶段必须与片段阶段协调以适当地准备数据。一种方法是插值相机空间表面法线和视空间顶点位置，然后可以像在逐顶点着色中一样使用它们。
纹理映射（Texture Mapping）
纹理用来为表面的着色添加额外细节。
这个想法很简单：每次计算着色时，我们从纹理中读取着色计算中使用的值，例如漫反射颜色，而不是使用附加到正在渲染的几何体的属性。这个操作被称为纹理查找（texture lookup）：指定一个纹理坐标（texture coordinate，这是纹理域中的一个点），纹理映射系统在纹理图像中找到该点的值并返回它。纹理值随后用于着色的计算。
定义纹理坐标最常见的方法是简单地将纹理坐标作为另一个顶点属性。然后每个图元都知道自己在纹理中的位置。
着色频率（Shading Frequency）
决定在哪里进行着色计算取决于颜色变化的速度，即需要被计算的细节的尺度（scale）
大尺度的着色，例如曲面上的漫反射着色，可以不频繁地进行计算，然后进行插值
小尺度的着色，例如清晰的高光或详细的纹理，需要以高着色频率进行计算，对于需要在图像中看起来清晰的细节，着色频率至少要为每像素一个着色样本。
大尺度的着色可以安全地在顶点阶段计算，即使图元包含许多像素。需要高着色频率的效果也可以在顶点阶段计算，只要顶点在图像中足够接近。当图元大于一个像素时，它们可以考虑在片元阶段计算。
- 在电脑游戏中使用的硬件管线，通常使用覆盖几个像素的图元来确保高效率，这些硬件管线通常在逐片元着色执行大多数着色计算。
- RenderMan 系统首先将所有表面细分（subdividing）或切割（dicing）成大约像素大小的小四边形（称为微多边形 micropolygons），然后按顶点执行所有着色计算。
简单抗锯齿（Antialiasing）
如果我们对每个像素是否在图元内部做出全有或全无的判断，光栅化将产生锯齿线和三角形边缘。
事实上，简单光栅化算法生成的片元集合，有时称为标准光栅化或混叠光栅化（aliased rasterization）。它与光线跟踪器映射到三角形的像素集完全相同，光线跟踪器通过每个像素的中心发射一条光线。因此正如在光线跟踪中，解决方案是允许像素被不同的图元部分覆盖。 在实践中，这种形式的模糊有助于视觉质量，特别是在动画中。
在光栅化应用程序中有许多不同的抗锯齿方法。就像在光线跟踪器中一样，我们可以通过将每个像素值设置为以像素为中心的方形区域上颜色的平均值，来产生抗锯齿图像，称为方框过滤（box filtering）。
方框过滤抗锯齿最简单的实现方法是超采样（supersampling）：创建高分辨率图像，然后进行下采样（downsample）
锯齿的原因通常是图元的边缘而不是内部，一种广泛使用的优化方法是以高于着色的采样率来进行可见性采样。在像素中多个点上存储覆盖率和深度信息
多重采样抗锯齿（multisample antialiasing）：为每个片元存储一个颜色，加上覆盖蒙版和一组深度值
不懂
剔除（Culling）图元以提高效率
不需要对场景中的几何体全部进行遍历
识别和丢弃不可见的几何图形以节省处理它所花费的时间称为剔除（culling）。
三种常用的剔除策略（通常串联使用）是：
- 视空间剔除（view volume culling）：也被称为视锥体剔除（view frustum culling），剔除在视空间外部的几何体。要进行快速测试，而不是单独测试。在将许多三角形分组为具有相关边界体积的对象时特别有用。如果边界体积位于视图体积之外，那么构成该对象的所有三角形也是如此。这是个保守测试
- 遮蔽剔除（occlusion culling）：剔除可能在视空间内，但被更近的几何体遮挡的几何体
- 背面剔除（backface culling）：剔除背对相机的图元：当多边形模型是封闭的，即它们约束一个没有孔的封闭空间时，通常假设它们具有面向外的法向量。对于这样的模型，背向摄像机的多边形肯定会被朝向摄像机的多边形所覆盖。因此，这些多边形可以在图形管线开始之前被剔除。
问题和练习
非三角形的多边形如何光栅化？可以直接逐行扫描完成，也可以分解为三角形。
小于 $0$ 或者大于 $n+f=3$
剪切好像问题很多
略
再设置一个 $(1,1)$？
$n=4$，$f=100,000=10^5$，那么：
$$ \Delta z_w^\max\approx\frac{f\Delta z}{n}=\frac{10^5(10^5-4)/2^b}{4}\approx2.5\times10^9/2^b $$令 $\Delta z_w\le 1$，得到：
$$ b\ge\log_22.5\times 10^9\approx 32 $$所以至少需要 $32$ 位
如果 $100$ 米以内才重要，那么令 $f=100$，代入得：
$$ \Delta z_w^\max\approx\frac{f\Delta z}{n}=\frac{100(100-4)/2^b}{4}=2400/2^b $$令 $\Delta z_w\ge 1$，得到：
$$ b\ge\log_22400\approx 12 $$所以至少需要 $12$ 位