Rasterization — triangles to fragments & the z-buffer光栅化——三角形到片元与深度缓冲

Lesson 01 sketched the rasterization loop and lesson 02 delivered triangles into screen space. Now we actually turn a screen-space triangle into covered pixels — and resolve which surface wins when triangles overlap. Everything here rests on one tiny signed quantity, the edge function, computed three times per pixel: it decides coverage, hands us interpolation weights for free, breaks ties on shared edges, and even tells us which way a triangle faces. Then a single per-pixel number, depth, replaces a whole family of broken sorting schemes. 第 01 课勾勒了光栅化循环，第 02 课把三角形送进了屏幕空间。现在我们真正把一个屏幕空间三角形变成被覆盖的像素——并在三角形重叠时决出哪个表面胜出。这里的一切都立在一个小小的有符号量上，即边函数，每个像素算三次：它判定覆盖、免费送上插值权重、在共享边上打破平局，甚至还告诉我们三角形朝向哪边。随后，单个逐像素的数——深度——取代了一整族有缺陷的排序方案。

1 · The core question: which pixels does a triangle cover?核心问题：三角形覆盖哪些像素？

Lesson 02 left us with a triangle whose three vertices are already in screen space — plain 2D pixel coordinates, the perspective divide behind us. The rasterizer's job now is a coverage query: for each candidate pixel, is its center inside the triangle? Everything downstream (shading, texturing, depth) only happens at pixels the triangle actually covers, so this test runs an enormous number of times and must be cheap.

第 02 课给我们留下了一个三角形，它的三个顶点已在屏幕空间——就是普通的二维像素坐标，透视除法已在身后。光栅化器现在的活儿是一次覆盖查询：对每个候选像素，它的中心是否在三角形内？下游的一切（着色、纹理、深度）只在三角形真正覆盖的像素上发生，所以这个测试要跑极多次，必须便宜。

Here is the one primitive that does it. Given a directed edge from A to B and a query point P, the edge function is

下面就是完成它的那一个基本运算。给定一条从 A 指向 B 的有向边，以及查询点 P，边函数为

Read it two ways. Algebraically it is the 2D cross product of (B − A) with (P − A), so its sign says which side of the infinite line AB the point lies on — the half-plane test. Geometrically its magnitude is twice the signed area of triangle ABP. One expression answers both "which side?" and "how much area?", and we will use both facts.

用两种方式来读它。代数上，它是 (B − A) 与 (P − A) 的二维叉积，因此它的符号说明该点落在无限直线 AB 的哪一侧——即半平面测试。几何上，它的大小是三角形 ABP 的有符号面积的两倍。一个表达式同时回答“哪一侧？”与“多少面积？”，这两个事实我们都会用到。

A triangle is the intersection of three half-planes, one per edge. Walk its three vertices in a consistent order (say counter-clockwise) and evaluate the edge function for each directed edge against P. If the three results all share the same sign, P is on the interior side of every edge, so it is inside; if any sign disagrees, P is outside. That is the entire inside test — three multiply-adds and a sign check:

一个三角形是三个半平面的交集，每条边一个。以一致的顺序（比如逆时针）走过它的三个顶点，对每条有向边就 P 求边函数。如果三个结果同号，则 P 在每条边的内侧，故在内部；只要有一个符号不一致，P 就在外部。这就是整个内部测试——三次乘加加一次符号检查：

One more thing keeps this from being wasteful. We do not test every pixel on screen against every triangle — that would be pixels × triangles, the very cost lesson 01 warned about. Instead we compute the triangle's bounding box: x from min to max of the three vertices, likewise y, clamped to the framebuffer. We scan only that rectangle. A triangle covering 40 pixels inside a 60-pixel box costs 60 coverage tests, not the whole screen — the widget below counts exactly these two numbers.

还有一件事让它不至于浪费。我们不会拿屏幕上每个像素去测试每个三角形——那会是像素 × 三角形，正是第 01 课警告过的开销。取而代之，我们计算三角形的包围盒：x 取三顶点的 min 到 max，y 同理，并裁到帧缓冲范围内。我们只扫描那个矩形。一个在 60 像素盒子里覆盖 40 像素的三角形，花费 60 次覆盖测试，而非整屏——下面的控件正是数这两个数。

2 · Barycentric coordinates fall out for free重心坐标免费掉出来

We paid for three edge functions to decide coverage. Here is the bonus: those same three numbers, normalized, are the point's barycentric coordinates — the weights that write P as a blend of the three vertices. Recall each edge function is twice a signed area. The edge E(B,C,P) is twice the area of the sub-triangle PBC — the one opposite vertex A. Divide the three sub-areas by the whole triangle's area and you get three weights that sum to one:

我们为判定覆盖付了三个边函数的账。这里是赠品：这同样的三个数，归一化之后，就是该点的重心坐标——把 P 写成三个顶点的混合的那组权重。回忆每个边函数是有符号面积的两倍。边 E(B,C,P) 是子三角形 PBC 面积的两倍——就是对着顶点 A 的那个。把三个子面积各除以整个三角形的面积，就得到三个求和为一的权重：

Read the two facts together. The sign test of section 1 is exactly the statement "all three barycentrics are non-negative" — coverage and interpolation are the same computation seen from two angles. And once P is covered, any per-vertex quantity — a color, a texture coordinate, a normal, a depth — is reconstructed at P by the same weights: v_P = α v_A + β v_B + γ v_C. A vertex with weight 1 and the others 0 reproduces that vertex; the centroid has all three equal to 1/3. This is the interpolation machinery lesson 05 needs — and lesson 05 will show it must be applied to 1/w, not screen values, to stay perspective-correct. For now: coverage buys us the weights, for free, at every covered pixel.

把这两个事实合起来读。第 1 节的符号测试恰恰就是“三个重心坐标都非负”这句话——覆盖与插值是同一计算的两个视角。而一旦 P 被覆盖，任何逐顶点的量——颜色、纹理坐标、法线、深度——都可用同一组权重在 P 处重建：v_P = α v_A + β v_B + γ v_C。某顶点权重为 1、其余为 0 就复现该顶点；重心处三者都等于 1/3。这正是第 05 课需要的插值机制——而第 05 课会说明它必须作用在 1/w 上、而非屏幕值上，才能保持透视校正。眼下只需记住：覆盖在每个被覆盖像素处免费买来了这组权重。

3 · The top-left rule — one edge, one owner左上规则——一条边，一个归属

Real meshes are watertight: adjacent triangles share edges exactly. That creates a boundary problem the inside test alone gets wrong. Consider a pixel center that lands precisely on the shared edge between two triangles. With the plain ≥ 0 test, both triangles report it inside — because the shared edge has edge-function value exactly 0 for each. The consequences are visible bugs:

真实网格是密封的：相邻三角形恰好共享边。这带来一个仅靠内部测试会出错的边界问题。考虑一个像素中心恰好落在两个三角形之间的共享边上。用朴素的 ≥ 0 测试，两个三角形都报告它在内——因为那条共享边对各自而言边函数值恰为 0。后果是可见的 bug：

• Double-shading: the pixel is drawn by both triangles. With opaque triangles you waste work; with transparency (blending) the shared seam is drawn twice and shows up as a brighter or darker line.重复着色：该像素被两个三角形都画了。对不透明三角形是浪费工作量；对带透明度（混合）的三角形，共享缝被画了两次，表现为一条更亮或更暗的线。
• Gaps: if instead you flip to a strict > 0 test to avoid the double, pixels exactly on the edge are now claimed by neither triangle, and cracks of background color appear along seams.裂缝：如果你反过来改用严格的 > 0 测试来避免重复，那么恰好在边上的像素现在两个三角形都不认领，缝隙处便出现背景色的裂纹。

The top-left rule (also called a fill rule) is a deterministic tie-break that gives every shared edge to exactly one of the two triangles. The convention: a pixel exactly on an edge is considered inside only if that edge is a top edge (horizontal, with the triangle below it) or a left edge (going downward, with the triangle to its right). For a covered-boundary case we accept the edge function when it is strictly positive, or zero on a top/left edge; we reject zero on any other edge. Because two triangles sharing an edge traverse it in opposite directions, exactly one of them sees it as top/left — so the pixel is claimed once. No gaps, no doubles, and — critically — the decision depends only on the edge's geometry, not on draw order, so the result is deterministic and consistent everywhere the edge appears.

左上规则（也称填充规则）是一个确定性的平局判定，把每条共享边恰好判给两个三角形中的一个。约定是：恰好落在边上的像素被视为在内，仅当该边是上边（水平、三角形在其下方）或左边（向下走、三角形在其右侧）。对覆盖到边界的情形，当边函数严格为正、或在上/左边上为零时我们接受它；在任何其他边上为零则拒绝。因为共享一条边的两个三角形沿相反方向遍历它，其中恰有一个把它看作上/左边——于是该像素被认领一次。没有裂缝、没有重复，而且——关键在于——该判定只依赖边的几何，不依赖绘制顺序，所以结果是确定的，且在这条边出现的每一处都一致。

4 · Visibility with a depth buffer用深度缓冲解决可见性

Coverage tells us which pixels a triangle touches; it does not tell us which triangle the eye actually sees when several cover the same pixel. That is the visibility question from lesson 01, and rasterization needs an answer that fits its triangle-by-triangle loop.

覆盖告诉我们一个三角形碰到哪些像素；它没告诉我们当多个三角形覆盖同一像素时，眼睛实际看到的是哪一个。这就是第 01 课的可见性问题，而光栅化需要一个契合其“逐三角形”循环的答案。

The tempting classical answer is the painter's algorithm: sort all triangles back-to-front and draw them in that order, so nearer triangles paint over farther ones — like a painter laying down background before foreground. It is simple and it fails, for reasons that are structural, not fixable by a better sort:

诱人的经典答案是画家算法：把所有三角形按从远到近排序、再依序绘制，于是近的三角形盖在远的之上——就像画家先铺背景再画前景。它简单，却会失败，原因是结构性的，靠更好的排序补不了：

• Cyclic overlaps. Three long triangles can each partly occlude the next in a loop (A over B over C over A). No single back-to-front ordering exists — the "correct order" is a cycle, so any linear sort is wrong somewhere.循环遮挡。三个长三角形可以首尾相接地各遮住下一个（A 盖 B、B 盖 C、C 盖 A）。不存在单一的从远到近排序——“正确顺序”是个环，所以任何线性排序都会在某处出错。
• Interpenetration. Two triangles that pass through each other have no consistent front/back — near one edge A is in front, near another B is. Order is per-pixel, not per-triangle, so no triangle-level sort can be right.相互穿插。两个彼此穿过的三角形没有一致的前后——在一条边附近 A 在前，在另一条边附近 B 在前。顺序是逐像素的，而非逐三角形，所以任何三角形级的排序都不可能正确。
• Cost. Sorting is O(T log T) every frame and needs all triangles in hand at once, which fights the streaming, one-triangle-at-a-time pipeline the GPU wants.开销。排序每帧是 O(T log T)，且要求一次性握有全部三角形，这与 GPU 想要的、逐三角形流式的流水线相冲突。

The fix is to make visibility a per-pixel, order-independent decision — the z-buffer (depth buffer). Allocate, alongside the color framebuffer, a second buffer holding one depth per pixel, all initialized to +∞ (the far plane). When a triangle covers a pixel, interpolate its depth there (barycentrically, from section 2) and compare against the stored depth. Keep the fragment — write its color and its depth — iff the new depth is smaller (nearer). Otherwise discard it. That is the whole algorithm:

解决办法是把可见性变成一个逐像素、与顺序无关的决定——即 z-buffer（深度缓冲）。在颜色帧缓冲之外，再分配一个每像素存一个深度的缓冲，全部初始化为 +∞（远平面）。当一个三角形覆盖某像素时，在该处插值它的深度（用第 2 节的重心坐标），并与已存深度比较。当且仅当新深度更小（更近）时保留该片元——写入它的颜色和深度；否则丢弃它。这就是全部算法：

for each triangle T:                       // any order — order does not matter
  for each pixel P in T's bounding box:
    if covered(T, P):                      // three edge functions share sign
      z = interpolate_depth(T, P)          // barycentric α,β,γ
      if z < zbuf[P]:                      // nearer than what's already there?
        color[P] = shade(T, P)             // keep this fragment
        zbuf[P]  = z

Read why it beats the painter. The comparison is O(1) per fragment and depends only on the pixel's own stored depth, so triangles may arrive in any order and the final image is identical — cyclic overlaps and interpenetration resolve automatically because the contest is settled independently at each pixel, exactly where order truly is per-pixel. The cost is memory (a full-resolution depth buffer) and bandwidth (a read-compare-maybe-write per fragment), both of which GPUs are built to absorb. The widget below runs precisely this loop and, when you disable the depth test, shows the "last-drawn wins" bug the z-buffer cures.

读懂它为何胜过画家算法。比较对每个片元是 O(1)，且只依赖该像素自己存的深度，所以三角形可以按任意顺序到来而最终图像相同——循环遮挡与相互穿插会自动解决，因为这场竞争在每个像素处被独立裁定，恰好就在“顺序真正是逐像素”的地方。代价是内存（一个全分辨率深度缓冲）与带宽（每片元一次“读—比较—或许写”），二者 GPU 生来就能吸收。下面的控件正是跑这个循环，而当你关掉深度测试时，会显示 z-buffer 所治愈的“后画者胜”的 bug。

One catch remains, and it is the source of a classic artifact. The depth we store is screen-space z after the perspective divide, and that value is nonlinear in true camera distance: dividing by w ≈ Z packs most of the [0,1] depth range into the region right in front of the camera. So depth precision is lavish near the camera and starved far away. When two surfaces are nearly coplanar in the distance, their quantized depths can collide and the winner flickers pixel-to-pixel as the camera moves — z-fighting.

还剩一个陷阱，也是一个经典瑕疵的根源。我们存的深度是透视除法之后的屏幕空间 z，而这个值对真实相机距离是非线性的：除以 w ≈ Z 把 [0,1] 深度范围的大部分挤到了相机正前方那一片。于是深度精度在近处极其充裕、在远处却匮乏。当远处两个表面近乎共面时，它们量化后的深度会撞车，随着相机移动，胜者在像素间闪烁——即 z-fighting。

// Edge function: signed area / half-plane test (lesson 01, made real here).
function edge(ax,ay,bx,by,px,py){ return (px-ax)*(by-ay) - (py-ay)*(bx-ax); }

// Scan ONLY the bounding box, not the whole grid.
var minx = Math.floor(Math.min(Ax,Bx,Cx)), maxx = Math.ceil(Math.max(Ax,Bx,Cx));
var miny = Math.floor(Math.min(Ay,By,Cy)), maxy = Math.ceil(Math.max(Ay,By,Cy));
for (var y=miny; y<maxy; y++) for (var x=minx; x<maxx; x++){
  tests++;
  var px=x+0.5, py=y+0.5;                 // pixel CENTER
  var w0=edge(Bx,By,Cx,Cy,px,py), w1=edge(Cx,Cy,Ax,Ay,px,py), w2=edge(Ax,Ay,Bx,By,px,py);
  var inside = (w0>=0&&w1>=0&&w2>=0)||(w0<=0&&w1<=0&&w2<=0);
  if (!inside) continue;
  // z-buffer: keep the nearer surface, order-independent. Depth test OFF ⇒ last drawn wins.
  if (!depthTest || zA < zbuf[y*GW+x]) { color[y*GW+x] = colA; zbuf[y*GW+x] = zA; }
}

5 · Culling & clipping — skip work before it starts剔除与裁剪——在开工前就跳过

Two guards run before the coverage loop, each removing triangles that would otherwise waste it — and each reuses machinery we already have.

两道防线跑在覆盖循环之前，各自剔除本会白费循环的三角形——而且各自复用了我们已有的机制。

Back-face culling. A closed opaque object shows you only its front-facing triangles; the ones on the far side point away and are always hidden by the near side. We can detect them for free from the sign we already computed. In screen space, a triangle whose vertices we authored counter-clockwise has a positive total edge-function sum (twice its area); if that sum comes out negative, the triangle has been flipped by projection — it is facing away — and we discard it before scanning a single pixel. This is one comparison that can cull roughly half of a mesh's triangles. (The winding convention is a choice; you set which sign means "front" once, consistently.)

背面剔除。一个封闭不透明物体只让你看到它朝前的三角形；背面的那些朝向别处，总被近侧挡住。我们能从已经算好的符号里免费探出它们。在屏幕空间，我们按逆时针编写顶点的三角形有正的边函数总和（其面积的两倍）；如果这个和算出来是负的，说明该三角形被投影翻了面——它朝向别处——于是在扫描任何一个像素之前就丢弃它。这是一次比较，能剔掉一个网格大约一半的三角形。（环绕约定是个选择；你一次性、一致地设定哪个符号代表“正面”即可。）

Near-plane clipping. Here is a subtler hazard tied straight to lesson 02's transform chain. The perspective divide is a division by w, and w is (essentially) the camera-space depth. A vertex behind or exactly on the camera plane has w ≤ 0. Divide by that and you get a division by zero or, worse, a sign flip that folds geometry from behind the eye into the visible image as a garbage triangle. So we must clip against the near plane in clip space, before the divide — cut each triangle along w = (a small positive) ε, producing one or two new triangles that lie entirely in front of the camera, and only then divide. This is exactly why lesson 02 insisted clip space exist as a distinct stage: it is the last place the divide is still safe to defer.

近平面裁剪。这里有个更隐蔽、直接系于第 02 课变换链的隐患。透视除法是除以 w，而 w（本质上）就是相机空间深度。位于相机平面之后或恰好之上的顶点有 w ≤ 0。除以它，你会得到除以零，或者更糟——一次符号翻转，把眼睛背后的几何折叠成一个垃圾三角形塞进可见图像。所以我们必须在裁剪空间、除法之前，对近平面做裁剪——沿 w =（一个小正数）ε 切开每个三角形，产出一或两个完全落在相机前方的新三角形，然后才做除法。这正是第 02 课坚持让裁剪空间作为独立阶段存在的原因：那是最后一处仍能安全推迟除法的地方。

The other four frustum planes (left, right, top, bottom) could also be clipped this way, but doing so for every triangle is wasteful when most are already on-screen. GPUs instead use a guard band: they clip only against the near plane (correctness — the divide demands it) and a region generously larger than the screen, then simply let the rasterizer's bounding-box clamp discard the off-screen pixels of anything within the guard band. Full clipping is reserved for triangles that also cross the guard band. Correctness where it is mandatory, cheap scissoring everywhere else.

其余四个视锥平面（左、右、上、下）也可以这样裁剪，但当大多数三角形本就在屏内时，对每个都这么做很浪费。GPU 转而使用护栏带（guard band）：只对近平面（正确性——除法要求如此）以及一个比屏幕慷慨得多的区域做裁剪，然后干脆让光栅化器的包围盒裁剪去丢弃护栏带内之物的屏外像素。完整裁剪只留给同时越过护栏带的三角形。在必须之处保证正确，在其余处用廉价的裁切。

Where this points next接下来指向何处

We can now take a screen-space triangle and turn it into a set of covered pixels — fragments — each carrying interpolated barycentric weights and a depth that a z-buffer uses to keep the nearest surface, with the top-left rule sealing the seams and culling/clipping trimming the input. But a fragment so far is just a covered location with a flat color. Its real job is to sample surface detail: a color from a texture image, a normal from a normal map, a coordinate that varies smoothly across the triangle. Lesson 05 picks up the interpolation thread exactly where section 2 dropped it — and reveals the catch it flagged: interpolating screen-space values linearly is wrong under perspective, so we must interpolate attribute/w and 1/w and divide, giving perspective-correct interpolation and texture mapping.

现在我们能把一个屏幕空间三角形变成一组被覆盖的像素——片元——每个都带着插值好的重心权重和一个深度，z-buffer 用它保留最近的表面，左上规则封住接缝，剔除/裁剪修剪输入。但迄今为止一个片元只是一个带纯色的被覆盖位置。它真正的活儿是采样表面细节：从纹理图像取一个颜色、从法线贴图取一个法线、一个在三角形上平滑变化的坐标。第 05 课正好从第 2 节松手之处接起插值这条线——并揭示它标记过的那个陷阱：在透视下对屏幕空间值做线性插值是错的，所以我们必须插值 属性/w 与 1/w 再相除，得到透视校正插值与纹理映射。

Interview prompts面试题

• Given a triangle's three vertices and a pixel center, how do you test if the pixel is inside, and why is the bounding box involved? (§1 — evaluate the three edge functions E(A,B,P); inside iff they share sign; scan only the triangle's bounding box to avoid pixels × triangles cost.) 给定三角形的三个顶点和一个像素中心，你如何测试该像素是否在内，为什么要牵涉包围盒？(§1 — 求三个边函数 E(A,B,P)；同号即在内；只扫描三角形的包围盒，以避免像素 × 三角形的开销。)
• What are barycentric coordinates, and how do they relate to the edge functions you already computed for coverage? (§2 — normalized edge functions = sub-triangle-area weights α,β,γ ≥ 0, Σ=1; the inside test is exactly "all three non-negative," and they interpolate any per-vertex attribute.) 什么是重心坐标，它们与你为覆盖已经算出的边函数有何关系？(§2 — 归一化的边函数 = 子三角形面积权重 α,β,γ ≥ 0, Σ=1；内部测试恰是“三者皆非负”，它们能插值任何逐顶点属性。)
• Why does the top-left (fill) rule exist, and what breaks without it? (§3 — pixels exactly on a shared edge are claimed by both triangles (double-shade) or neither (gaps); the rule is a deterministic, order-independent tie-break giving each shared edge one owner.) 左上（填充）规则为何存在，没有它会坏掉什么？(§3 — 恰在共享边上的像素被两个三角形都认领（重复着色）或都不认领（裂缝）；该规则是一个确定、与顺序无关的平局判定，给每条共享边一个归属。)
• Contrast the painter's algorithm with the z-buffer. Give two cases the painter's algorithm cannot handle. (§4 — painter sorts triangles back-to-front, O(T log T) and fails on cyclic overlaps and interpenetration (order is per-pixel); the z-buffer keeps the nearer fragment per pixel, O(1) and order-independent.) 对比画家算法与 z-buffer。举出两个画家算法无法处理的情形。(§4 — 画家算法把三角形从远到近排序，O(T log T)，在循环遮挡与相互穿插上失败（顺序是逐像素的）；z-buffer 每像素保留更近的片元，O(1) 且与顺序无关。)
• What causes z-fighting, and how do you fix it? (§4 — screen-space z is nonlinear after the divide (precision crowded near the camera), so distant near-coplanar surfaces collide in depth and flicker; fix with tighter near/far, reversed-z, or a depth bias.) 是什么导致 z-fighting，你如何修它？(§4 — 屏幕空间 z 在除法后是非线性的（精度在相机近处拥挤），故远处近乎共面的表面在深度上撞车而闪烁；用更紧的 near/far、reversed-z 或深度偏置来修。)
• How does back-face culling work, and why must near-plane clipping happen before the perspective divide? (§5 — the sign of the triangle's total edge-function (winding) flips when it faces away, so cull on that sign; a vertex with w ≤ 0 is behind the eye, and dividing by it is undefined / sign-flips geometry, so clip against near in clip space first.) 背面剔除如何工作，为什么近平面裁剪必须发生在透视除法之前？(§5 — 三角形边函数总和的符号（环绕）在其朝外时翻转，故按该符号剔除；w ≤ 0 的顶点在眼睛之后，除以它无定义 / 会翻转几何符号，所以先在裁剪空间对近平面裁剪。)