第 4 讲：裁剪、光栅化与反走样

几何对象是连续的，屏幕却只有离散像素。光栅化要做的就是把“这条线、这个三角形覆盖了哪些位置”变成有限个片元。

1. 为什么先裁剪

视口外的几何即使最后看不见，也会浪费光栅化和着色开销。一个有向直线或平面把空间分成两个半空间；凸裁剪区域可看成若干半空间的交。若点 $\mathbf p$ 对所有边界函数都满足约定符号，它就在区域内。

Cohen–Sutherland 线段裁剪

矩形外部被分成九个区域，每个端点用四位区域码表示上、下、左、右关系。

• 两端区域码都为零：整段接受。
• 两端区域码按位与非零：两端位于同一外侧半空间，整段拒绝。
• 其他情况：选一个外部端点，与对应边界求交，替换端点后继续。

它把大部分明显情况变成几次位运算，只有跨边界线段才真正算交点。

Sutherland–Hodgman 多边形裁剪

依次拿多边形对裁剪窗口的每条边处理。扫描相邻顶点 $S\to P$ 时只有四种情况：

$S$	$P$	输出
内	内	$P$
内	外	交点
外	内	交点、$P$
外	外	无

一条边裁完的输出多边形，再作为下一条边的输入。该算法天然适合凸裁剪窗口。

2. 直线怎样落到像素格

最直接的增量算法让 $x$ 每次加 $1$，按斜率更新 $y$，再选最近像素。若每一步都做浮点乘法和四舍五入，代价不小。

Bresenham 把“下一个选东边像素还是东北像素”改写成对隐式直线函数

$$f(x,y)=Ax+By+C$$

在两个候选像素中点的符号判断。由于每次只移动一格，判别量可用整数加减递推。标准推导通常先处理 $0\le m\le1$，其他八分象限通过交换坐标和改变步进方向统一。

3. 三角形为什么是基本图元

三点一定共面，三角形总是凸的，也容易插值。给逆时针三角形 $A,B,C$，定义边函数

$$E_{AB}(P) =(B_x-A_x)(P_y-A_y) -(B_y-A_y)(P_x-A_x).$$

若三个边函数都非负，像素中心 $P$ 就在三角形内部或边上。实际实现还要约定共享边由哪一个三角形拥有，例如 top-left rule，避免相邻三角形之间出现裂缝或重复覆盖。

蛮力扫描整张屏幕很浪费。先求三角形轴对齐包围盒，只在盒内测试；边函数又是线性的，横向或纵向移动一个像素时可增量更新。更大的三角形还可用分块或层次测试快速跳过整片全外区域。

4. 光栅化本质是采样

把三角形看成一个二维指示函数：内部为 $1$、外部为 $0$。每个像素只取中心一点，就是对这个连续函数做点采样。高频边界超过采样率后，会出现：

• 斜边的阶梯状锯齿。
• 细密纹理的摩尔纹。
• 运动中看似反转的车轮。

这些不是三个无关故障，而是同一个 aliasing 问题：不同的连续信号在低采样率下产生了同样或错误的离散结果。

5. 反走样为什么要“先平均”

理想像素值不是中心点颜色，而是像素面积内信号的平均：

$$I_{pixel} =\frac{1}{A} \int_{\text{pixel}}I(x,y)\,dx\,dy.$$

精确积分通常太贵，于是用多个子像素样本近似：

1. 每像素取 $N\times N$ 个样本。
2. 分别判断覆盖并着色。
3. 把样本平均成最终像素。

这就是 supersampling。它在采样前近似做低通滤波，代价则大约随样本数增长。多重采样可复用部分着色结果，专门改善几何边缘。

反走样不能凭空恢复已经丢掉的信息。若纹理在一个像素里重复很多次，即使几何边缘多采样也不够，还需要 Mipmap 或各向异性过滤等预滤波技术。