3.1 扫描转换：直线与三角形如何变成像素
3.1 扫描转换：直线与三角形如何变成像素
本节摘要：扫描转换（scan conversion）回答一个看似简单的问题：给定连续几何（端点、顶点），该点亮哪些像素？本节手推 DDA 增量算法与 Bresenham 整数算法两种经典直线画法，再用重心坐标完成三角形填充，最后直面走样并实现超采样抗锯齿。这是像素"出生"的核心时刻——第 6 章硬件光栅化器做的事，与这里手写的代码在数学上完全一致。
学习目标
阅读完本节，你应当能够：
- 写出 DDA 算法并解释"增量"省掉了什么运算
- 手推 Bresenham 的判别式，说明它为何只用整数加减
- 用重心坐标判断像素是否在三角形内，并插值顶点属性
- 实现超采样抗锯齿，算出 4 倍采样的显存与带宽代价
像素中心与覆盖判定
直线：从逐点求解到增量递推
朴素想法：直线方程 y = kx + b，每个 x 算一次 y 再四舍五入。问题是每个像素都要做一次乘法和一次加法。观察相邻像素：x 每走 1，y 恰好多走斜率 k——用上一步的结果加一个常量，就能推出下一步，乘法彻底消失。这就是 DDA（数字微分分析）：
def dda_line(p0, p1, plot): # p0, p1 为浮点坐标；plot 为画像素的回调 dx, dy = p1[0]-p0[0], p1[1]-p0[1] steps = max(abs(dx), abs(dy)) # 沿长轴步进 xinc, yinc = dx/steps, dy/steps x, y = p0 for _ in range(round(steps) + 1): plot(round(x), round(y)) x += xinc; y += yinc # 增量递推，无乘法 pixels = [] dda_line((0, 0), (5, 2), lambda x, y: pixels.append((x, y))) print(pixels) # 输出: [(0,0), (1,0), (2,1), (3,1), (4,2), (5,2)]
DDA 还有个隐藏好处：步进方向沿长轴，画出的像素链是连通的，不会有断点。但浮点增量在早期硬件上仍嫌贵，Bresenham（1965 年）更进一步，把四舍五入的判断改写成一个整数判别式，全程只用整数加减与符号判断：
def bresenham(x0, y0, x1, y1, plot): # 经典整数版，以斜率 0~1 的方向为准（其余方向对称处理） dx, dy = abs(x1-x0), abs(y1-y0) sx = 1 if x0 < x1 else -1 sy = 1 if y0 < y1 else -1 err = dx - dy # 判别式初值 while True: plot(x0, y0) if x0 == x1 and y0 == y1: break e2 = 2 * err # 翻倍避免除法 if e2 > -dy: err -= dy; x0 += sx # 偏向 x 方向一步 if e2 < dx: err += dx; y0 += sy # 需要时 y 也走一步 pixels2 = [] bresenham(0, 0, 5, 2, lambda x, y: pixels2.append((x, y))) print(pixels2 == pixels) # 输出: True，与 DDA 结果一致
判别式的直觉：err 记录理想直线与已画像素之间的"垂直欠账"，欠账累积到超过半格就还一步 y。这个算法在只支持整数运算的早期硬件上快得惊人，至今仍是嵌入式 LCD 绘图的常客。
三角形：图形学的万能图元
现代渲染里一切几何最终都拆成三角形（三点必共面、插值定义清晰、硬件专门优化）。三角形光栅化的任务：找出所有中心落在三角形内的像素，并插值出每个像素的属性（颜色、深度、纹理坐标）。
1.1 节的叉积法可以判内外，但每个像素要算三次叉积。工程上用重心坐标：三角形内任意点 P = αA + βB + γC（α+β+γ=1），(α,β,γ) 就是 P 的重心坐标，同时天然是属性插值的权重：
def barycentric(a, b, c, p): # 求 p 在三角形 abc 中的重心坐标（二维） d = (b[1]-c[1])*(a[0]-c[0]) + (c[0]-b[0])*(a[1]-c[1]) alpha = ((b[1]-c[1])*(p[0]-c[0]) + (c[0]-b[0])*(p[1]-c[1])) / d beta = ((c[1]-a[1])*(p[0]-c[0]) + (a[0]-c[0])*(p[1]-c[1])) / d return alpha, beta, 1 - alpha - beta def fill_triangle(a, b, c, color_fn, fb): # 包围盒扫描 + 重心坐标判断 xmin = max(0, int(min(a[0],b[0],c[0]))); xmax = int(max(a[0],b[0],c[0])) + 1 ymin = max(0, int(min(a[1],b[1],c[1]))); ymax = int(max(a[1],b[1],c[1])) + 1 for y in range(ymin, ymax): for x in range(xmin, xmax): w = barycentric(a, b, c, (x + 0.5, y + 0.5)) # 像素中心 if all(wi >= 0 for wi in w): fb.set_pixel(x, y, color_fn(w)) # w 即插值权重
两个必须知道的工程细节：其一，相邻三角形共享边上的像素若被两个三角形都判定为"在内"，不透明物体没问题（深度测试兜底），半透明物体就会亮一倍——GPU 用 top-left 规则统一规定共享边归哪个三角形，杜绝重复；其二，透视投影下直接用屏幕空间插值会出错，需要"透视校正插值"（除以 w 的技巧），这是第 6 章光栅化硬件的内置动作，此处埋个伏笔。
走样与超采样
用上面的算法画一条斜线，边缘立刻呈现楼梯状锯齿——1.3 节讲过，这是离散网格对连续几何的必然背叛。缓解思路一：提高采样密度。每个屏幕像素内部均匀撒 4 个采样点（2×2），各自判断在不在三角形内，颜色按覆盖率混合：
def aa_triangle(a, b, c, solid, edge, fb, x, y): # 单像素 2x2 超采样：4 个子采样点按覆盖数混合前景与边缘色 offsets = (0.25, 0.25), (0.75, 0.25), (0.25, 0.75), (0.75, 0.75) hit = 0 for ox, oy in offsets: w = barycentric(a, b, c, (x + ox, y + oy)) if all(wi >= 0 for wi in w): hit += 1 cov = hit / 4 # 覆盖率即透明度 fb.set_pixel(x, y, tuple(round(cov*s + (1-cov)*e) for s, e in zip(solid, edge))) # 覆盖 2/4 的边缘像素最终色 = 前景色与背景色各掺一半，锯齿变缓坡
代价也算笔账：4 倍采样意味着 4 倍的内外判断、4 份深度缓冲、一次解析合并，显存带宽翻倍不止。所以 GPU 的 MSAA 只对覆盖率多重采样、着色仍算一次，把省钱思路做进硬件——机制见 6.3 节。
本节要点回顾
- 增量递推消灭乘法：DDA 用加法走直线，Bresenham 进一步全整数化
- 重心坐标一举两得：既是内外判断，又是属性插值权重
- 共享边要有归属规则：top-left 规则防半透明重复叠加
- 超采样按覆盖率混合：抗锯齿的本质是承认像素有面积
- 透视校正插值：屏幕空间线性插值在透视下是错的，硬件会自动纠正
图元会画了，但屏幕外的部分画来干什么？3.2 节讲裁剪：在光栅化之前先把看不见的砍掉。