想象你拿到一幅十字绣图纸：图纸上是一朵线条流畅的玫瑰，但你没法用笔描线，只能对照图纸，在网格布上一格一格绣出彩色的 x。绣完退后三步看——玫瑰出现了；凑近一看，全是方方正正的小格子。电脑屏幕就是同一回事：所谓“几何图形”只是数学世界里的完美线条，而屏幕是一张由像素组成的网格布。把完美线条翻译成“该点亮哪些格子”的过程，就是光栅化（Rasterization）。这篇文章要讲透光栅化里最经典的两件事：Bresenham 画线——决定一条斜线该点亮哪些像素格；扫描线填充——决定一个多边形内部该点亮哪些像素格。它们一个负责“绣线”，一个负责“填面”，合起来就是渲染管线最底层的针法。搞懂它们，你就拿到了理解 GPU 渲染的入场券。

岗位关联

光栅化是渲染管线的中枢环节：理解扫描线与 Bresenham 的整数智慧，等于拿到读懂 GPU 渲染、引擎优化与图形调试的底层钥匙，是图形学与可视化方向从业者的必修课。

目录
  1. 可视化演示
  2. 一、光栅化概念：从图纸到网格布
  3. 二、Bresenham 画线：绣针的每一步抉择
  4. 三、扫描线填充：一行一行绣出色块
  5. 四、多边形边界：凹凸图形都认得
  6. 五、反走样技术：别让楼梯变成锯齿
  7. 六、性能优化策略：绣娘的省线之道
  8. 七、GPU 管线应用：十字绣工厂流水线
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

动态演示光栅化算法详解的核心机制，通过架构/数据/状态/性能四种模式展示关键概念与交互流程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

光栅化算法详解：画线算法 画线算法的基本概念与问题定义 DDA（数字微分分析器）算法 核心机制可视化 光栅化算法详解整体架构与关键组件

一、光栅化概念：从图纸到网格布

拿一幅十字绣图纸来说：图纸上的玫瑰轮廓是一条光滑的曲线，但你永远无法在网格布上绣出真正的弧线——针脚只能落在横竖交错的格点上。屏幕和网格布一模一样：几何图形是数学世界里的“光滑图纸”，而屏幕是物理世界里的“网格布”，由一个个像素组成。光栅化（Rasterization）就是那个拿着图纸对号入座、决定每个格子要不要下针的绣娘。

在渲染管线里，光栅化夹在两个环节中间：前面是顶点处理，负责把三维模型的顶点变换、投影到二维屏幕；后面是片元着色，负责给已经确定的像素算颜色。光栅化就像车间里的“制版工”：拿到一条边、一个三角形的几何描述，吐出“这张网格布上哪些格属于它”的清单。

判断的默认标准叫中心点采样：取每个像素格正中心的点 (i+0.5, j+0.5)，用数学方法判断它是否落在图形内部。落在内部就点亮这个像素，落在外面就跳过。这个“点亮或跳过”的二值决策，是所有光栅化算法的共同起点——Bresenham 画线、扫描线填充、GPU 三角形遍历，都是围绕“怎么快速判断”做文章。

所以光栅化的本质，是把你脑子里的“完美图纸”翻译成网格布上的“一针一线”。后文要讲的两种经典算法，正是绣娘手里的两件工具：一件绣线（Bresenham），一件填面（扫描线）。

pixel(i,j)={1,(i+0.5, j+0.5)∈S0,其他\text{pixel}(i, j) =\begin{cases}1, & (i + 0.5,\ j + 0.5) \in S \\0, & \text{其他}\end{cases}
每个像素格取中心点作为采样位置，中心落在图形 S 内则点亮，否则不点亮——这是所有光栅化算法的起点。
  1. 像素中心第 i 列第 j 行的格子，其正中心坐标是 (i+0.5, j+0.5)，屏幕网格由此离散化。
    (i+0.5, j+0.5)(i + 0.5,\ j + 0.5)
  2. 归属判断判断这个中心点是否属于几何图形 S，S 是三角形或多边形的数学定义。
    (i+0.5, j+0.5)∈S(i + 0.5,\ j + 0.5) \in S
  3. 二值点亮属于则像素值为 1（点亮），不属于则为 0（不点亮），得到最终像素结果。
    pixel(i,j)∈{0,1}\text{pixel}(i, j) \in \{0, 1\}

二、Bresenham 画线：绣针的每一步抉择

绣一条从布面左下角到右上角的斜线时，绣娘每次只能横向往右挪一格，同时面临一个抉择：这一针是留在原行，还是斜上一格到下一行？肉眼当然能看出大概，但要绣得贴近图纸上那条理想斜线，每次抉择都要有依据。Bresenham 算法的全部智慧，就是把“这针该不该往上走”变成一次极其廉价的判断。

数学上，起点终点之间有一条理想直线 y = mx + b。光栅化要做的，是找出离这条理想线最近的像素格序列。如果每次 x 加 1，那么 y 要么不变、要么加 1，问题被压缩成二选一。关键是我们不希望每步都算浮点乘法，所以 Bresenham 定义了一个整数决策参数 p，用它的符号代表“理想线此刻更靠近上面那格还是下面那格”。

算法先求出 Δx = x1 − x0 和 Δy = y1 − y0，然后从 p0 = 2Δy − Δx 出发，每前进一格按规则更新 p。乘 2 是为了把小数误差变成整数，这样整个过程只需要整数加法和一次比较，最适合硬件流水线。

就像绣娘心里记住“偏差偏上还是偏下”的账，每走一格只需要翻一页账本，花一次加法——Bresenham 把一条斜线绣得又直又省力。

p0=2Δy−Δxp_0 = 2\Delta y - \Delta x
pi+1={pi+2Δy,pi<0pi+2(Δy−Δx),pi≥0p_{i+1} =\begin{cases}p_i + 2\Delta y, & p_i < 0 \\p_i + 2(\Delta y - \Delta x), & p_i \geq 0\end{cases}
决策参数 p 是“当前像素到理想直线误差”的两倍整数版本：p<0 时直线更贴近当前行，p≥0 时应当上移一行。
  1. 求差分Δx 与 Δy 是起点到终点的横纵增量，前提是斜率在 0 到 1 之间。
    Δx=x1−x0,Δy=y1−y0\Delta x = x_1 - x_0,\quad \Delta y = y_1 - y_0
  2. 初始参数p0 由差分组合而来，乘 2 是为了把小数误差变成整数运算。
    p0=2Δy−Δxp_0 = 2\Delta y - \Delta x
  3. 低位决策p_i < 0 表示理想线更靠近下方格子，y 不变，只补一点误差。
    pi+1=pi+2Δyp_{i+1} = p_i + 2\Delta y
  4. 高位决策p_i ≥ 0 表示理想线更靠近上方格子，y 加 1，同时修正误差。
    pi+1=pi+2(Δy−Δx),yi+1=yi+1p_{i+1} = p_i + 2(\Delta y - \Delta x),\quad y_{i+1} = y_i + 1

三、扫描线填充：一行一行绣出色块

画线是一条针脚，填充一面色块就是另一种活法。绣一面蓝色小旗子时，绣娘不会从中心胡乱下针，而是从最上面一行开始，找到旗子在这一行的左边界，一针针绣到右边界，然后换下一行。这个“逐行扫过、见入口进、见出口出”的绣法，就是扫描线填充的直觉。

对多边形做扫描线填充时，我们让扫描线 y 从多边形的最低行走到最高行。每一行，先求这条扫描线与多边形所有边的交点，得到一串 x 坐标；然后按 x 从小到大排序，两两配对成 （入口，出口），把这两个 x 之间的整列像素全部点亮。为什么要排序配对？因为这条规则让凹多边形也天然正确——射线穿过多边形，总是“进一次、出一次”，交点永远成对。

逐边重新求交点有点浪费，于是有了活性边表（Active Edge Table，AET）。每条边只记录 y_min、y_max、当前交点 x 和斜率倒数 1/m；每一行只更新“活跃中”的边，对 x 做一次加法得到新交点。这个增量技巧把每行的求交工作量从“扫描全部边”降为“只扫活跃边”。

扫描线填充就像是绣娘的“逐行攻略”：先把一行里入口出口都标好，再一鼓作气绣完这一行。理解了它，便理解了填充类光栅化的核心骨架。

xi+1=xi+1m,m=ΔyΔxx_{i+1} = x_i + \frac{1}{m},\qquad m = \frac{\Delta y}{\Delta x}
扫描线每下降一行，边与扫描线交点的 x 值用斜率倒数做一次加法增量，避免每行重新解方程。
  1. 斜率定义边的斜率 m 是纵向增量与横向增量之比。
    m=ΔyΔxm = \frac{\Delta y}{\Delta x}
  2. 反向增量y 每增加 1，交点 x 对应移动的量是 1/m。
    1m=ΔxΔy\frac{1}{m} = \frac{\Delta x}{\Delta y}
  3. 递推求交从边的一个端点出发，逐行累加得到该行交点横坐标。
    xi+1=xi+ΔxΔyx_{i+1} = x_i + \frac{\Delta x}{\Delta y}
  4. 取整落格交点 x 是浮点数，取整后作为该行填充区间的左右边界。
    xstart=⌈xleft⌉,xend=⌊xright⌋x_{\text{start}} = \lceil x_{\text{left}} \rceil,\quad x_{\text{end}} = \lfloor x_{\text{right}} \rfloor

四、多边形边界：凹凸图形都认得

十字绣图纸上偶尔会遇到别扭的边界：一个凹进去的五角星，某一行会被切成好几段；顶点恰好压在线格上时，数边界很容易数重。这些边界上的“暗坑”，正是扫描线填充最容易出错的地方。

多边形在计算机里通常用一组按顺序排列的顶点表示，相邻顶点构成一条边。填充时逐条边和扫描线求交。当扫描线恰好穿过一个顶点——比如三角形的顶角——这条线同时碰到两条边的端点，如果两条边都计交点，就会多出一个交点，配对就乱了。

标准解法是给顶点定一个“归属规则”：每条边只对 y_min 端点那一侧负责，换算到代码里就是约定 y_min ≤ y < y_max 才计交点。这样水平边不参与求交，顶点也只被一条边计数，凹凸多边形都能正确填充。若要判断一个任意点是否在多边形内部，还可以用环绕数规则：从该点向右发一条射线，数它与边界的穿越次数，奇数次为内部。

边界规则就像绣花的“下针规范”：针脚压线时只算一次，凹进凸出都按同一套口诀处理。把边界数清楚了，再复杂的形状也能绣得明明白白。

xint=xi+yP−yiyi+1−yi⋅(xi+1−xi)x_{\text{int}} = x_i + \frac{y_P - y_i}{y_{i+1} - y_i} \cdot (x_{i+1} - x_i)
N=∑i=0n−1{1,(yi>yP)⊕(yi+1>yP) 且 xP<xint0,其他N = \sum_{i=0}^{n-1}\begin{cases}1, & (y_i > y_P) \oplus (y_{i+1} > y_P) \text{ 且 } x_P < x_{\text{int}} \\0, & \text{其他}\end{cases}
环绕数统计从点 P 向右的射线穿过多边形边界的次数，穿越次数为奇数则点在内部。
  1. 插值交点射线 y = y_P 与边所在直线的交点横坐标，用两端点线性插值求出。
    xint=xi+yP−yiyi+1−yi(xi+1−xi)x_{\text{int}} = x_i + \frac{y_P - y_i}{y_{i+1} - y_i}(x_{i+1} - x_i)
  2. 穿越判断异或运算检查边的两个端点是否分居 y_P 两侧，只有穿越的边才可能计数。
    (yi>yP)⊕(yi+1>yP)(y_i > y_P) \oplus (y_{i+1} > y_P)
  3. 右向计数交点必须位于点 P 的右侧（x_P < x_int），保证射线方向一致。
    xP<xintx_P < x_{\text{int}}
  4. 奇偶结论N 为奇数则点 P 在多边形内部，偶数则在外部。
    P∈内部  ⟺  N mod 2=1P \in \text{内部} \iff N \bmod 2 = 1

五、反走样技术：别让楼梯变成锯齿

你凑近看十字绣的斜线，会发现它是一串歪歪扭扭的台阶；退远看才觉得光滑。屏幕像素更大、格子更粗时，这些台阶就成了刺眼的“锯齿”。锯齿的学名叫走样（Aliasing），本质是采样点数不够，物理世界的细节在离散网格上“打滑”了。

光栅化默认的中心点采样是“要么黑要么白”的倔脾气：像素中心在图形内就全亮，在外就全黑。一条斜线斜斜切过像素格时，有些格子的中心恰好擦过边界，于是边缘像素被整格点亮或整格放弃，锯齿就产生了。反走样（Anti-aliasing）的思路是：别这么绝情，按“图形覆盖了这个像素多大面积”来决定这个像素该显示成什么颜色。

最直接的做法是超采样（SSAA）：把每个像素再细分成 2×2 或 4×4 个子格子，分别采样，统计有多少子格落在图形内，得到覆盖率。然后按覆盖率把前景线和背景色混合：覆盖率 1 全画线色，覆盖率 0 全画背景，覆盖率 0.5 就画中间色。现代 GPU 更常用多重采样（MSAA），只在边缘像素做超采样，成本更低。

反走样就像是给锯齿台阶抹了一层过渡的水泥，让粗暴的黑白二分变成平滑的灰度过渡。边缘不再生硬，视觉上那条线便重新“光滑”起来。

coverage=AcoveredApixel\text{coverage} = \frac{A_{\text{covered}}}{A_{\text{pixel}}}
Cout=coverage×Cline+(1−coverage)×CbgC_{\text{out}} = \text{coverage} \times C_{\text{line}} + (1 - \text{coverage}) \times C_{\text{bg}}
覆盖率 = 图形覆盖像素面积 ÷ 像素总面积；边缘像素按覆盖率把前景线色和背景色加权混合，产生平滑过渡。
  1. 覆盖面积A_covered 是图形在像素格内占的面积，A_pixel 是格子总面积，前者不超过后者。
    Acovered≤ApixelA_{\text{covered}} \leq A_{\text{pixel}}
  2. 覆盖率比值在 0 到 1 之间，1 表示全被图形覆盖，0 表示完全露出。
    coverage=AcoveredApixel\text{coverage} = \frac{A_{\text{covered}}}{A_{\text{pixel}}}
  3. 前景加权线色以覆盖率为权重参与最终颜色的混合。
    coverage×Cline\text{coverage} \times C_{\text{line}}
  4. 背景补全剩余比例 (1 − coverage) 分给背景色，最终颜色落在两者之间。
    (1−coverage)×Cbg(1 - \text{coverage}) \times C_{\text{bg}}

六、性能优化策略：绣娘的省线之道

老练的绣娘从不每绣一针就重新掏图纸量距离，而是记住“下一针大概偏差多少”，每针只做一次微调。光栅化的性能密码正是这个道理：把可以重复利用的中间结果喂给下一步，把最贵的运算换成最便宜的。

增量计算是第一条主线。Bresenham 每画一个像素只需一次整数加法和一次比较；扫描线填充用活性边表避免逐行重算交点。相比之下，朴素做法每画一个点都算一次 y = mx + b，成本是浮点乘法加加法，还要面对舍入误差。别小看这一加一乘之差，画一条几百万像素的线，差距是数百倍的浮点开销。

局部性和并行是第二三条主线。扫描线从上到下逐行处理，访问的像素地址基本连续，正好命中 CPU/GPU 的高速缓存；而不同行、不同三角形互相独立，可以切给成百上千个计算单元并行光栅化。现代 GPU 的固定功能光栅化单元，本质上就是把“判断像素归属”这一步做成每秒执行几十亿次的专用流水线。

增量化、局部化、并行化——这三板斧让光栅化从“能用”变成“快到看不见”。绣娘手快是因为心里有账，GPU 快是因为把账本分给了几万只手同时翻。

pi+1=pi+c(1 次整数加法)p_{i+1} = p_i + c \quad (\text{1 次整数加法})
yi=m⋅xi+b(1 次浮点乘法 + 1 次浮点加法)y_i = m \cdot x_i + b \quad (\text{1 次浮点乘法 + 1 次浮点加法})
Bresenham 把“每像素”的成本压到一次整数加法，而朴素直线求值需要浮点乘加——差距在数百万像素级别被放大。
  1. 增量步进决策参数只叠加常数 c，c 由 p 的符号决定，无需乘除法。
    c∈{2Δy, 2(Δy−Δx)}c \in \{2\Delta y,\ 2(\Delta y - \Delta x)\}
  2. 朴素求值直接代入直线方程 y = mx + b，每次浮点乘法加加法。
    yi=m⋅xi+by_i = m \cdot x_i + b
  3. 精度差异整数运算零舍入误差，浮点运算有累计误差。
    误差整数=0,误差浮点≠0\text{误差}_{\text{整数}} = 0,\quad \text{误差}_{\text{浮点}} \neq 0
  4. 并行放大各行独立，GPU 把每像素成本除以核心数，吞吐量再提升上百倍。
    吞吐量≈像素数Ncore×1每像素成本\text{吞吐量} \approx \frac{\text{像素数}}{N_{\text{core}}} \times \frac{1}{\text{每像素成本}}

七、GPU 管线应用：十字绣工厂流水线

现代 GPU 是一座巨大的十字绣工厂。几何车间先把图样（顶点）变换、裁剪好，光栅化车间把每条线、每个三角形翻译成“该下针的格子清单”，着色车间再给每一格调配颜色，最后由包装车间（帧缓冲）把成品摆上货架（屏幕）。

在渲染管线里，顶点处理之后、片元着色之前就是光栅化阶段。它负责两件事：一是三角形设置——根据三个顶点计算边函数系数；二是三角形遍历——对覆盖区域内的每个像素中心，用边函数判断是否落在三角形内，从而生成一个“片元”。片元不是最终像素，它只是带着坐标、深度、覆盖率等信息的候选像素，还要经历深度测试和颜色混合才能写入屏幕。

GPU 用得最多的归属判断工具是边函数（Edge Function）。对三角形的每条边，定义一个带符号的线性表达式，把像素中心坐标代进去，符号为正表示在边的某一侧。三个符号同侧，则像素在三角形内。边函数是线性的，可以在像素间做增量步进，因此非常适合硬件流水线并行计算。

从十字绣工厂的视角看，光栅化是那条把几何变像素的传送带。理解了它，你就看懂了 GPU 每帧数千万三角形背后最朴素的那一针一线。

Eab(x,y)=(xb−xa)(y−ya)−(yb−ya)(x−xa)E_{ab}(x, y) = (x_b - x_a)(y - y_a) - (y_b - y_a)(x - x_a)
边函数是点 P 相对有向边 ab 的带符号面积；对三角形三条边的符号都为正（或都为负），则点 P 在三角形内部。
  1. 有向边边 ab 的方向向量由两端点坐标差给出。
    (xb−xa, yb−ya)(x_b - x_a,\ y_b - y_a)
  2. 符号面积点 P 与起点 a 的连线向量和边向量做叉积，结果是带符号面积。
    Eab(x,y)=(xb−xa)(y−ya)−(yb−ya)(x−xa)E_{ab}(x, y) = (x_b - x_a)(y - y_a) - (y_b - y_a)(x - x_a)
  3. 同侧判定三角形三条边 E_ab、E_bc、E_ca 对 P 同号，则 P 在三边的同一侧，即内部。
    sgn(Eab)=sgn(Ebc)=sgn(Eca)\text{sgn}(E_{ab}) = \text{sgn}(E_{bc}) = \text{sgn}(E_{ca})
  4. 增量步进E 是 x、y 的线性函数，GPU 沿扫描线逐像素累加更新，无需每次重算乘法。
    E(x+1,y)=E(x,y)+(ya−yb)E(x + 1, y) = E(x, y) + (y_a - y_b)

AI 应用场景

场景一：渲染引擎中的三角形批量光栅化

阶段：渲染管线的光栅化阶段（图形基础设施层）。

解决的问题：三维重建、神经辐射场（NeRF）等 AI 模型输出的几何信息，最终要变成屏幕上可看的画面。传统 CPU 逐像素填充太慢，AI 应用的实时可视化需要 GPU 每秒光栅化数百万个三角形，把每个三角形快速转成片元。

具体案例：训练好的 NeRF 重建出三角网格，游戏引擎把它导入场景后，GPU 光栅化单元用边函数逐三角形判断像素归属，产出片元交给着色器，实现实时漫游预览。

场景二：矢量地图与 2D 图形库的平滑绘制

阶段：前端可视化数据呈现（图形输出）。

解决的问题：地图数据是矢量线段和多边形（道路、行政区边界），直接按坐标连线会出锯齿。扫描线填充负责区域着色，Bresenham 类笔画负责线段栅格化，反走样负责边缘软化，三者结合让城市道路和边界在任意缩放级别都平滑清晰。

具体案例：高德/Google 地图做矢量瓦片渲染时，把道路折线转换成像素笔画，用覆盖率混合软化边缘；缩放级别变化时重新光栅化，保证路线标注不闪烁、不锯齿。

场景三：自动驾驶仿真数据合成

阶段：训练数据生成（合成数据管线）。

解决的问题：真实驾驶图像标注贵、覆盖全场景难。仿真平台用渲染引擎合成带标注的街景图像——虚拟车道线、路牌、车辆边界框都先经光栅化变成像素，再反推生成 2D/3D 标签。

具体案例：自动驾驶仿真器每帧调用 GPU 光栅化渲染 RGB 图和深度图，同时把语义标签按同一光栅化路径生成，保证“图”和“标注”严格对齐，供感知模型预训练。

Python 演示

python73 行
"""光栅化算法演示: Bresenham 画线 + 扫描线填充多边形""" import math  def bresenham_line(x0, y0, x1, y1):    """Bresenham 整数画线算法, 返回所有像素点列表"""    points = []    dx = abs(x1 - x0)    dy = abs(y1 - y0)    sx = 1 if x0 < x1 else -1    sy = 1 if y0 < y1 else -1    err = dx - dy    x, y = x0, y0    while True:        points.append((x, y))        if x == x1 and y == y1:            break        e2 = 2 * err        if e2 > -dy:            err -= dy            x += sx        if e2 < dx:            err += dx            y += sy    return points  def scanline_fill(vertices, rows=20, cols=20):    """扫描线填充: 逐行求交点, 奇偶配对填充内部像素"""    pixels = []    edges = []    n = len(vertices)    for i in range(n):        x1, y1 = vertices[i]        x2, y2 = vertices[(i + 1) % n]        if y1 == y2:            continue        if y1 > y2:            x1, y1, x2, y2 = x2, y2, x1, y1        edges.append((y1, y2, x1, x2))    for y in range(rows):        xs = []        for y_min, y_max, x1, x2 in edges:            if y_min <= y < y_max:                t = (y - y_min) / (y_max - y_min)                xs.append(x1 + t * (x2 - x1))        xs.sort()        for i in range(0, len(xs) - 1, 2):            x_start = int(math.ceil(xs[i]))            x_end = int(math.floor(xs[i + 1]))            for x in range(x_start, x_end + 1):                pixels.append((x, y))    return pixels  def render(points, rows=20, cols=20):    """把像素点列表渲染成字符画"""    grid = [['.'] * cols for _ in range(rows)]    for x, y in points:        if 0 <= x < cols and 0 <= y < rows:            grid[y][x] = '#'    for row in grid:        print(''.join(row))  if __name__ == '__main__':    print('Bresenham 画线: (1,1) -> (18,8)')    render(bresenham_line(1, 1, 18, 8))    print()    print('扫描线填充三角形: (3,3) (16,6) (8,17)')    triangle = [(3, 3), (16, 6), (8, 17)]    render(scanline_fill(triangle))
目的：用 Python 手写实现 Bresenham 画线和扫描线填充，在字符画网格上直观看到“矢量图形变像素”的过程。
  1. err = dx - dy初始化误差项，这是 Bresenham 的“心里账本”，记录理想线偏离当前格的距离。
  2. e2 = 2 * err误差翻倍后用一次判断同时决定 x 和 y 两个方向，避免浮点运算。
  3. if e2 > -dy:` 与 `if e2 < dx:按误差符号决定横纵方向是否各走一格，等价于决策参数 p 的符号判断。
  4. if y1 == y2: continue水平边不参与扫描线求交，它是边界处理的第一步。
  5. if y_min <= y < y_max:只统计下端点，保证顶点只被一条边计数，避免配对错乱。
  6. t = (y - y_min) / (y_max - y_min)线性插值求出该行交点的横坐标，正是 x_i + 1/m 的展开形式。
  7. xs.sort()交点按 x 排序，奇偶配对的前提。
  8. for i in range(0, len(xs) - 1, 2):每两个交点配成一队 （入口，出口），填充中间所有像素。

常见误区

误区我一直觉得锯齿是像素太大造成的，只要用 4K 显示器，像素小到看不见，边缘自然就光滑了，反走样技术是不是就多余了？

正解分辨率提高只是把台阶变小变密，只要每个像素还做“全亮或不亮”的二值决策，楼梯照样存在。锯齿的根源是离散采样：图形是连续的，采样点是有限的，采样不够密就会丢失细节。反走样通过覆盖率混合颜色，从原理上软化边缘，和分辨率是互补关系——4K 下依然需要反走样。

为何常见：像素密度大到人眼分辨不出单个像素时，锯齿视觉上被掩盖了，让人误以为问题消失了。

误区扫描线填充要按扫描线把多边形切成一块块，凹多边形一行会被切出好几段，这算法肯定处理不了凹的，只能用凸的。

正解恰恰相反，奇偶规则天然支持凹多边形。做法是把该行所有边交点按 x 排序，然后两两配对成 （入口，出口） 区间填充。凹多边形只是多出几对交点、多出几个区间，规则完全不变。真正要小心的是顶点重合计数和水平边。

为何常见：教材示例多用凸多边形画图，容易让人误以为算法前提是凸。

误区Bresenham 的推导假设斜率在 0 到 1 之间，那竖线、斜率非常大的线它是不是根本画不了？

正解通过八分对称，把 x/y 互换、坐标取反，任意方向的线段都可以映射到第一卦限处理。实际实现中，可以同时维护 x 和 y 两个方向的误差（如 e2 同时判断两个方向），横竖斜通吃的代码并不复杂。

为何常见：只看教材对 0<m<1 的推导步骤，没注意算法后段关于对称性的说明。

误区现在 GPU 都是强大的浮点计算单元，Bresenham 用整数躲浮点，纯粹是几十年前硬件弱的历史遗留，实战没用了。

正解整数运算意味着零除法、零舍入误差、稳定可预测的时序，在 FPGA 光栅化器、嵌入式显示、低功耗芯片中依然是标准。更重要的是，Bresenham 的“增量误差”思想被现代三角形遍历的边函数步进继承，只是换了个对象。

为何常见：只接触桌面 GPU 的浮点生态，没见过硬件实现和功耗敏感场景。

误区光栅化嘛，就是把图形的颜色填到一个个像素格子里，跟油漆桶工具差不多，扫描线填充就是涂色的过程。

正解光栅化只回答“哪些像素属于这个图形”，它产出的是片元——携带坐标、深度、覆盖率属性的候选像素，并不负责最终颜色。真正决定颜色的是后面的片元着色器；扫描线“填充”指的是生成像素集合，颜色涂抹是着色阶段的事。把两者分开，才能正确理解渲染管线。

为何常见：“填充”这个词容易让人联想到填充颜色，概念混淆是图形学新手常见问题。

面试题

Q1. 关于 Bresenham 画线算法的决策参数 p，下列哪些说法正确？

多选题 · mid

  • A.p 的符号决定 y 是否加一← 正确答案
  • B.p 的更新只用整数加减← 正确答案
  • C.p 为负时 y 坐标不变← 正确答案
  • D.p 的初始值与斜率无关

答案：ABC。p 是 Bresenham 的“心里账本”，符号决定 y 是否上移，更新只做整数加减。p0 = 2Δy − Δx 显然依赖斜率（Δy/Δx），所以 D 错。

Q2. 光栅化阶段输入和输出分别是什么？

单选题 · easy

  • A.输入图元输出像素点← 正确答案
  • B.输入像素输出图元
  • C.输入贴图输出坐标
  • D.输入顶点输出光源

答案：A。光栅化把矢量图元（直线、三角形）翻译成像素/片元。就像十字绣把图纸上的玫瑰变成网格布上的格子，方向是从图元到像素，B/C/D 方向或对象都错了。

Q3. 扫描线填充中奇偶规则的作用是？

单选题 · easy

  • A.判断内部并配对填充← 正确答案
  • B.计算直线的斜率
  • C.提高像素的刷新率
  • D.给顶点重新排序

答案：A。奇偶规则把交点排序后两两配对为 （入口，出口），确定哪些区间属于多边形内部。它和斜率、刷新率、顶点排序无关。

Q4. Bresenham 算法初始决策参数 p0 的公式是？

单选题 · easy

  • A.p0 等于两倍的 dy 减 dx← 正确答案
  • B.p0 等于 dy 加两倍的 dx
  • C.p0 等于 dx 减两倍的 dy
  • D.p0 等于 dy 减去 dx 的差

答案：A。p0 = 2Δy − Δx，乘 2 是为了把误差小数整数化。其余三个公式都会让初始误差符号失去意义。

Q5. 扫描线填充时，活性边表通常要记录哪些信息？

单选题 · mid

  • A.交点 x 和斜率倒数← 正确答案
  • B.边的颜色和透明度
  • C.顶点的法线向量
  • D.光线的入射角度

答案：A。活性边表记录当前交点 x 和 1/m，用于每行做一次加法递推求交。颜色、法线、光照是着色阶段的事。

Q6. 多边形顶点恰好落在扫描线上时，正确做法是？

单选题 · mid

  • A.只让下端点计一次交点← 正确答案
  • B.顶点处两条边都计数
  • C.直接忽略这条扫描线
  • D.把顶点平移到下一行

答案：A。约定 y_min ≤ y < y_max 只对下端点计交点，避免顶点被两条边重复计数。两条边都计会多出交点、破坏配对，忽略整行会漏填，平移顶点会变形。

Q7. 反走样技术解决的核心问题是什么？

单选题 · mid

  • A.斜线边缘出现锯齿← 正确答案
  • B.多边形内部颜色不均
  • C.纹理加载速度过慢
  • D.模型顶点数量太多

答案：A。锯齿（走样）是离散采样带来的台阶状边缘。反走样用覆盖率混合颜色软化它，与内部填色、纹理速度、顶点数无关。

Q8. 与朴素 y=mx+b 求点相比，Bresenham 最大的优势是？

单选题 · hard

  • A.全程整数加减比较运算← 正确答案
  • B.可以画出任意旋转角度
  • C.不需要知道起点终点
  • D.自动处理颜色渐变效果

答案：A。Bresenham 每画一个像素只需一次整数加法和一次比较，没有乘除和浮点舍入。任意方向靠八分对称实现，起点终点是算法必要输入，颜色渐变根本不是它的职责。

Q9. 关于扫描线增量求交，以下说法正确的有？

多选题 · mid

  • A.用斜率倒数做行间递推← 正确答案
  • B.每行都要重新遍历全部边求交
  • C.活性边表只更新活跃边← 正确答案
  • D.水平边不参与求交计算← 正确答案

答案：ACD。增量法用 1/m 做加法递推，活性边表只更新经过当前行的边，水平边被跳过。B 是朴素做法，正是活性边表要优化的对象。

Q10. 关于现代 GPU 光栅化三角形，正确的描述是哪些？

多选题 · extreme

  • A.用边函数判断像素归属← 正确答案
  • B.光栅化在着色之前执行← 正确答案
  • C.片元带坐标深度属性← 正确答案
  • D.光栅化直接决定颜色

答案：ABC。GPU 用边函数的符号判断像素是否在三角形内（A 对）；管线顺序是光栅化在前、片元着色在后（B 对）；片元携带坐标、深度、覆盖率等候选属性（C 对）。决定颜色的是着色器，不是光栅化（D 错）。