计算机图形学05:二维图形算法-光栅化
引言：从几何到像素
让我们回顾一下渲染的核心任务：将我们用几何图元（点、线、多边形）建立的虚拟世界，最终呈现为屏幕上的图像。这个过程可以分解为两大步骤：
几何处理阶段： 对几何体进行变换、投影等操作，确定它们在屏幕空间中的位置和形状。
光栅化阶段： 确定这个经过变换的几何体覆盖了屏幕网格中的哪些像素。
着色阶段： 为这些被覆盖的像素计算出最终的颜色。
今天，我们的焦点就是第二步：光栅化，也称为扫描转换 (Scan Conversion)。
可以想象，GPU每秒需要处理数以亿计的三角形。因此，光栅化算法的效率直接决定了图形系统的性能。现代GPU已经将这些算法固化到了硬件中，但理解其原理，对于我们深入学习图形学，以及进行性能优化都至关重要。这些算法本身，也是算法设计思想的绝佳体现——它们通过巧妙的增量计算和整数运算，将复杂的几何问题转化为了高效的硬件操作。
1. 核心问题：点亮哪些像素？
光栅化算法需要满足一系列苛刻的要求，才能产生高质量的图像：
准确性： 选择的像素应尽可能贴近理想的几何线条。
连续性： 线条应该是连续的，不能有中断的空洞。
亮度均匀： 线条的视觉亮度不应因其斜率不同而发生明显变化。
效率： 算法必须极快，因为这是渲染管线中最频繁执行的操作之一。
可扩展性： 算法应能支持不同的线宽和线型（如虚线、点线）。
我们将从最简单的图元——直线段开始，探讨如何完美地实现它的光栅化。
2. 直线的光栅化
我们的任务是：给定直线的两个端点 $P_1(x_1, y_1)$ 和 $P_2(x_2, y_2)$，找出一条最佳的像素路径来近似这条直线。
2.1 最朴素的算法：DDA (Digital Differential Analyzer)
这是最直观的想法。我们知道直线的斜截式方程是 $y = mx + c$，其中斜率 $m = \frac{\Delta y}{\Delta x} = \frac{y_2 - y_1}{x_2 - x_1}$。
DDA算法的思路是：
沿着变化更快的坐标轴（主轴）以单位步长前进。
根据斜率计算另一个坐标轴的增量。
将计算出的浮点坐标四舍五入，得到最终的像素整数坐标。
以斜率 $|m| \le 1$ 的情况为例（X轴是主轴）：
// 伪代码
float m = (y2 - y1) / (x2 - x1);
float y = y1;
for (int x = x1; x <= x2; x++) {
drawPixel(x, round(y));
y = y + m; // y递增一个斜率
}
优点：
思路简单，易于理解。
缺点：
浮点数运算： 算法中涉及浮点数加法和round函数，这在早期硬件中是非常昂贵的。
累积误差： 浮点数加法会不断累积误差，可能导致绘制的直线偏离理想位置。
DDA是一个增量式算法，即每一步的计算都基于上一步的结果。这个思想非常重要，接下来的Bresenham算法将其发挥到了极致。
2.2 整数的胜利：Bresenham直线算法
1965年，IBM的Jack Bresenham发明了一种完全使用整数运算来绘制直线的算法，成为了图形学历史上的一个里程碑。其核心思想被后来的中点画线法所借鉴和发展，我们以中点法来讲解这个思路。
核心思想：
假设我们已经画好了像素 $P(x_p, y_p)$，下一步我们只能在两个候选像素中选择一个：东向 (E) 的 $(x_p+1, y_p)$ 或东北向 (NE) 的 $(x_p+1, y_p+1)$。我们该如何做出选择？
决策依据： 检查两个候选像素的中点 $M(x_p+1, y_p+0.5)$ 位于理想直线的上方还是下方。
如果中点在理想直线上方，说明直线更靠近E点，我们选择E。
如果中点在理想直线下方，说明直线更靠近NE点，我们选择NE。
如何用整数运算实现？
我们将直线的隐式方程改写为 $F(x, y) = ax + by + c = 0$，其中 $a = y_2 - y_1 = \Delta y$, $b = -(x_2 - x_1) = -\Delta x$。
$F(x, y) > 0$ 表示点在直线上方。
$F(x, y) < 0$ 表示点在直线下方。
我们定义一个决策变量 $d = F(M) = F(x_p+1, y_p+0.5)$。
我们发现，每一步的决策变量都可以通过上一步的决策变量和一个整数增量计算出来！
如果上一步选择了E，则下一个中点相对于上一个中点只在x方向移动了1，新的决策变量 $d_{new} = d_{old} + \Delta y$。
如果上一步选择了NE，则下一个中点在x和y方向都移动了1，新的决策变量 $d_{new} = d_{old} + \Delta y - \Delta x$。
通过将所有计算乘以2，我们可以完全消除初始决策变量中的0.5，从而实现纯整数运算。
Bresenham/中点算法的优势：
高效： 只包含整数加法、减法和位移运算，极其适合硬件实现。
精确： 没有浮点数带来的累积误差。
通用： 可以轻松扩展到处理所有八个象限的直线，以及圆和椭圆的绘制。
3. 多边形的填充 (Polygon Filling)
绘制完轮廓线后，我们常常需要填充多边形的内部区域。
3.1 核心问题：点在多边形内还是外？ (Point Classification)
这是一个基础的几何问题。我们有两种经典的方法：
奇偶规则 (Even-Odd Rule / Odd-Parity Rule):
从待测点P向任意方向画一条射线。
计算射线与多边形边的交点个数。
如果交点个数为奇数，则点P在多边形内部。
如果交点个数为偶数，则点P在多边形外部。
非零环绕数规则 (Non-Zero Winding Number Rule):
想象一条从点P出发，末端拴在多边形边上的橡皮筋。
让橡皮筋的末端沿多边形的边完整地绕行一圈。
计算橡皮筋绕点P的总圈数（逆时针为+1，顺时针为-1），这个数就是环绕数。
如果环绕数不为零，则点P在内部。
如果环绕数为零，则点P在外部。
对于简单的凸多边形，两种规则结果相同。但对于自相交的复杂多边形，它们会产生不同的结果。
3.2 扫描线填充算法 (Scan-Line Filling)
逐个像素地进行内外判断效率太低。扫描线算法利用了图形的相干性 (Coherence)，即相邻像素、相邻扫描线的属性很可能是相似的。
算法流程：
从下到上，逐条扫描线（即y值固定的像素行）进行处理。
对于当前扫描线，计算它与多边形所有边的交点。
将所有交点按x坐标从小到大排序。
将交点两两配对，填充每对交点之间的像素区间。
优化与特殊情况处理：
效率提升： 使用活性边表 (Active Edge Table, AET)，只保留与当前扫描线相交的边，并利用边的斜率倒数，以增量方式高效地更新下一条扫描线的交点x坐标。
特殊情况： 需要妥善处理水平边和交点恰好是多边形顶点的情况，以保证奇偶规则的正确性。
3.3 种子填充算法 (Seed Fill Algorithms)
这是另一类填充算法，常见于绘图软件中的“油漆桶”工具。
核心思想： 从多边形内部的一个已知像素点（种子）开始，向四周递归地扩散，直到遇到边界。
连通性：
4-连通： 每次只扩散到当前像素的上下左右四个邻居。
8-连通： 扩散到上下左右以及对角线的八个邻居。
实现： 通常使用栈或队列的非递归方式实现，以避免深度递归导致的栈溢出。
4. 走样与反走样 (Aliasing and Anti-aliasing)
我们所有的光栅化算法，都是在一个离散的像素网格上对一个连续的几何信号进行采样。根据采样定理，如果采样率不足，就会产生走样 (Aliasing)。
在图形学中，走样最直观的表现就是：
锯齿 (Jaggies): 直线和曲线的边缘呈现阶梯状。
细节丢失： 过于微小的物体可能在采样时被完全漏掉。
摩尔纹： 当精细的重复图案与像素网格相互作用时产生的干扰图案。
反走样 (Anti-aliasing) 就是用于减轻或消除走样现象的技术。
核心思想： 不再将一个像素视为一个点，而是视为一个有面积的方块。像素的最终颜色，应该由该像素区域内被几何图形覆盖的面积比例来决定。
区域采样 (Area Sampling):
超采样 (Supersampling, SSAA): 以高于屏幕分辨率的倍数进行渲染（例如4x SSAA就是以4倍分辨率渲染），然后将多个子像素的颜色平均，得到最终一个像素的颜色。效果最好，但计算开销巨大。
多重采样 (Multisampling, MSAA): 一种优化的超采样。只对几何体边缘的像素进行多次采样，内部像素只采样一次。这是现代游戏中应用最广泛的反走样技术。
5. 裁剪 (Clipping)
我们的虚拟世界可能是无限大的，但我们的视口（屏幕或窗口）是有限的。裁剪就是丢弃完全在视口之外的图元，并精确计算与视口边界相交的图元的新顶点，只保留视口内部的部分。
裁剪通常在光栅化之前进行，因为这样可以避免对那些最终看不见的图元进行昂贵的光栅化计算。
Cohen-Sutherland 直线裁剪算法:
将屏幕空间划分为9个区域，每个区域分配一个4位的“外码”。
通过对线段两个端点的外码进行位运算，可以快速地进行“平凡接受”（完全在内部）和“平凡拒绝”（完全在外部）。
对于相交情况，则计算交点，用交点替换掉在外部的端点，然后重复此过程。
Sutherland-Hodgeman 多边形裁剪算法:
一个非常优雅的算法。它将复杂的多边形裁剪问题，分解为对四条边界（上、下、左、右）的依次裁剪。
每次用一条边界（一条无限长的直线）去裁剪一个输入的多边形，生成一个新的多边形，作为下一次裁剪的输入。
这个过程非常适合流水线处理，易于硬件实现。