6.1 边函数与覆盖判定
上一章把世界坐标一路压到了屏幕上的整数像素坐标，但「一个像素该不该被三角形涂上颜色」这个问题还没回答。本章回答它——而且是用纯整数回答。站内的 /graphics-anti-aliasing-methods/
讲的是 MSAA / TAA 在图形 API 里怎么配、怎么取样本；本节和它分工明确：那篇关心「一个像素采几个样本」，本节关心一个样本落没落在三角形里，以及这个判定如何用整数做到跨语言逐位可复现。
覆盖判定是整条渲染管线里最容易被「想当然」的一步。很多人写 for x, y in bbox: if inside(x, y)，inside 里塞一堆浮点叉积。本节要把它拆成三件事：边函数的几何含义、屏幕坐标系下的环绕符号、以及子像素精度带来的边界效应。拆完你会发现，一个三角形光栅化的全部信息，就是三个整数。
边函数就是有向面积的 2 倍
给定三角形顶点 $A$、$B$ 与任意点 $P$，定义边函数
$$E(A,B,P) = (B_x-A_x)(P_y-A_y) - (B_y-A_y)(P_x-A_x)$$
这就是向量 $B-A$ 与 $P-A$ 的二维叉积。它等于三角形 $A,B,P$ 的有向面积的 2 倍：把 $P$ 换成 $A$ 或 $B$，两个向量共线，叉积为 0；把 $P$ 换成 $C$，得到的就是三角形 $A,B,C$ 的有向面积的 2 倍。这正是本节脚本里第一组断言：
E(A,B,C) : 696320 = 2 x 有向面积 348160.0；E(A,B,A)=0、E(A,B,B)=0
对三角形的三条边各取一次边函数（E(A,B,P)、E(B,C,P)、E(C,A,P)），如果三个值同号，$P$ 就在三条边的同一侧，也就是在三角形内部。这就是「三个边函数同号即点在三角形内」的全部含义——没有三角函数，没有开方，只有整数乘减。
屏幕空间 y 向下：area > 0 是哪一种环绕
屏幕坐标系里 $y$ 轴是向下的（像素 $(0,0)$ 在左上角）。这和数学课本里 $y$ 向上的直觉正好相反，于是「逆时针」这个词在屏幕空间里会骗人。判据很简单：把三角形自己代进边函数，
$$\text{area} = E(A,B,C) = (B_x-A_x)(C_y-A_y) - (B_y-A_y)(C_x-A_x)$$
在屏幕空间 $y$ 向下的坐标系里，area > 0 对应顶点按「左上 → 右上 → 下」的绕行顺序（若把它画在纸上、纸的 $y$ 轴朝下看，是逆时针）。本卷统一约定：area > 0 为正面，area <= 0 直接背面剔除。
这个符号不是学术洁癖，是实打实踩过的坑。程序化地形生成时，如果三角形索引写成 (a, c, b) 而不是 (a, b, c)，整个地形的 area 全部变号，几百个三角形会在剔除阶段被一次性扔掉——屏幕上只剩背景色，而代码本身没有任何报错。所以本卷所有网格生成器都带一行注释标明环绕约定，脚本里也专门留了一个断言把这条钉死：
翻转环绕 area : -696320 covered=0 culled=1
交换两个顶点，area 从 696320 变成 -696320，覆盖数从 86 掉到 0，剔除计数变成 1。符号就是可见性。
子像素精度与像素中心
屏幕坐标是 Q6 定点：1 个像素 = 64 个单位，整数。像素 $(px, py)$ 的中心取在
$$X = px \cdot 64 + 32, \qquad Y = py \cdot 64 + 32$$
为什么是 $+32$ 而不是 $+0$？因为像素不是一个点，而是一个 $1\times1$ 的方块；把判定点取在方块中心，等价于「这个像素的代表点是否落在三角形里」。取左上角会让整幅图像系统性偏移半个像素，取任意其他位置则会让边缘像素的归属随机抖动。
子像素精度到底有没有用？本节的扰动实验直接回答：把同一个三角形整体平移若干 Q6 单位，再看覆盖像素数的变化。
扰动实验（覆盖像素 / 相对 base 的变化）:
base dx= 0 dy= 0 covered= 86 delta=+0
sub +1x dx= 1 dy= 0 covered= 85 delta=-1
sub +1y dx= 0 dy= 1 covered= 86 delta=+0
sub +8x dx= 8 dy= 0 covered= 85 delta=-1
sub -3x+5y dx= -3 dy= 5 covered= 84 delta=-2
sub +31x dx= 31 dy= 0 covered= 85 delta=-1
pixel +1x dx= 64 dy= 0 covered= 86 delta=+0
pixel +1y dx= 0 dy= 64 covered= 86 delta=+0
pixel +2x+3y dx= 128 dy= 192 covered= 86 delta=+0
pixel -1x-1y dx= -64 dy= -64 covered= 86 delta=+0
两种平移的行为截然不同：
- 子像素平移（$1$、$8$、$31$ 单位，即 $1/64$ 到半个像素）会改变覆盖数：$+1$ 单位少 1 个像素，$-3x+5y$ 少 2 个。这说明边函数真的在逐单位地追踪边缘穿过了哪些像素中心。
- 整像素平移（$64$ 的整数倍）覆盖数严格不变，恒为 86。因为平移整数像素是「像素中心集合」上的一个双射，覆盖像素整体搬家、数量不变。
这两条合起来构成一个可证伪的检验：任何把屏幕坐标量化到整像素的「非恒等实现」（比如先在整数像素上算叉积、再补一个中心偏移），在子像素扰动下会给出 delta 恒为 0 的结果，与上表第二行矛盾。子像素精度不是装饰，是能被扰动实验抓出来的。
共享边：>= 0 的代价
覆盖判据的最后一步是符号比较。用 >= 0 还是 > 0？本卷用 >= 0，因为它让「三个边函数都非负」成为一个干净的布尔条件。代价是：落在共享边上的像素会被相邻的两个三角形同时认领。
把正方形沿对角线 $y=x$ 切成两个三角形，各自单独光栅化后取覆盖掩码的交集：
三角形单独覆盖 : lo=28 hi=28（差 7 个重复像素）
共享对角线像素 : 7（被两个三角形同时认领，edge == 0）
四边形覆盖 : 49 像素（culled=0）；png 150 bytes
两个三角形各自覆盖 28 个像素，并集只有 49 个——$28 + 28 - 49 = 7$ 个像素被重复认领，正好是对角线上 edge == 0 的那 7 个。如果改用 > 0，这 7 个像素会一个都不画，四边形中间出现一条裂缝。所以 >= 0 和 > 0 各有各的病：前者重复、后者漏画。工业界的解法是 top-left rule——对每个三角形，规定「只认领上边和左边的边缘像素」，让共享边像素唯一归属于某一个三角形。这条规则如何整数化，留到第 13 章细讲；本节先把它的问题定义清楚。
可运行产物：一个三角形，一张扰动表
下面这个脚本把上面所有断言变成可复现的数字。它只做一件事：拿一个三角形，量它的覆盖数，然后平移、翻转、切分，观察覆盖数怎么变。所有量级都远小于 $2^{53}$，故逐像素层用 numpy int64 即可，无需 BigInt。
#!/usr/bin/env python3
# file: lantern/sim/cg_raster_06_1_edge.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_raster_06_1_edge.py
"""6.1 边函数与覆盖判定：几何意义、环绕符号、子像素精度、共享边归属。
只用一个三角形：E(A,B,P) 是三角形 A、B、P 有向面积的 2 倍；三个边函数同号即在内部；
屏幕空间 y 向下时 area > 0 为正面；平移 1 个子像素单位会改变覆盖数（证明子像素不是恒等），
平移整数像素不会；`>= 0` 让共享边像素被两个三角形同时认领。
产物：out/cg_raster_06_1_edge.png、out/cg_raster_06_1_quad.png、out/cg_raster_06_1_edge.json。
"""
import json
import os
import sys
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import cglib # noqa: E402
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
W, H, BG, COL = 24, 20, (0, 0, 0), (200, 120, 60)
SUB1, HALF = cglib.SUB1, cglib.SUB1 // 2 # 64 / 32
def edge(ax, ay, bx, by, px, py):
"""E(A,B,P) = (B-A) x (P-A)，等于三角形 A、B、P 有向面积的 2 倍。"""
return (bx - ax) * (py - ay) - (by - ay) * (px - ax)
def mk_tri(A, B, C, col=COL):
return (A[0], A[1], 0, col[0], col[1], col[2],
B[0], B[1], 0, col[0], col[1], col[2],
C[0], C[1], 0, col[0], col[1], col[2])
def cover(tris):
color, _depth, covered, culled = cglib.rasterize(tris, W, H, BG)
return int(covered.sum()), culled, color, covered
def shift(tri, dx, dy):
o = list(tri)
for k in (0, 6, 12):
o[k] += dx
o[k + 1] += dy
return tuple(o)
A, B, C = (5 * SUB1, 3 * SUB1), (19 * SUB1, 7 * SUB1), (8 * SUB1, 16 * SUB1)
tri = mk_tri(A, B, C)
area = edge(A[0], A[1], B[0], B[1], C[0], C[1])
base, _, base_color, _ = cover([tri])
flip_area = edge(A[0], A[1], C[0], C[1], B[0], B[1])
flip_cnt, flip_cull, _, _ = cover([mk_tri(A, C, B)])
probes = [("base", 0, 0), ("sub +1x", 1, 0), ("sub +1y", 0, 1), ("sub +8x", 8, 0),
("sub -3x+5y", -3, 5), ("sub +31x", 31, 0), ("pixel +1x", SUB1, 0),
("pixel +1y", 0, SUB1), ("pixel +2x+3y", 2 * SUB1, 3 * SUB1),
("pixel -1x-1y", -SUB1, -SUB1)]
rows = []
for n, dx, dy in probes:
cnt, _, _, _ = cover([shift(tri, dx, dy)])
rows.append((n, dx, dy, cnt, cnt - base))
# 正方形沿对角线 y = x 切成两个三角形：落在对角线上的像素被两者同时认领
Q, R = (HALF, HALF), (HALF + 6 * SUB1, HALF)
S, T = (HALF + 6 * SUB1, HALF + 6 * SUB1), (HALF, HALF + 6 * SUB1)
lo, _, _, cov_lo = cover([mk_tri(Q, R, S, (220, 60, 60))])
hi, _, _, cov_hi = cover([mk_tri(Q, S, T, (60, 140, 220))])
both_claim = int((cov_lo & cov_hi).sum())
quad, quad_cull, quad_color, _ = cover([mk_tri(Q, R, S, (220, 60, 60)),
mk_tri(Q, S, T, (60, 140, 220))])
out = os.path.join(ROOT, "out")
png = cglib.save_png(os.path.join(out, "cg_raster_06_1_edge.png"), base_color)
cglib.save_png(os.path.join(out, "cg_raster_06_1_quad.png"), quad_color)
with open(os.path.join(out, "cg_raster_06_1_edge.json"), "w", encoding="utf-8") as fh:
json.dump({"canvas": [W, H], "triangle": [list(A), list(B), list(C)], "area2x": area,
"base_covered": base, "flipped_area2x": flip_area, "flipped_covered": flip_cnt,
"flipped_culled": flip_cull, "tri_lo_covered": lo, "tri_hi_covered": hi,
"shared_edge_pixels": both_claim, "quad_covered": quad, "quad_culled": quad_cull,
"perturb": [{"name": n, "dx": dx, "dy": dy, "covered": c, "delta": d}
for n, dx, dy, c, d in rows]}, fh, ensure_ascii=False, indent=2)
print(f"canvas : {W}x{H}（1 像素 = {SUB1} 单位，像素中心 = px*{SUB1} + {HALF}）")
print(f"triangle : A={A} B={B} C={C}")
print(f"E(A,B,C) : {area} = 2 x 有向面积 {area / 2:.1f}；E(A,B,A)=0、E(A,B,B)=0")
print(f"base covered : {base} 像素")
print(f"翻转环绕 area : {flip_area} covered={flip_cnt} culled={flip_cull}")
print("扰动实验（覆盖像素 / 相对 base 的变化）:")
for n, dx, dy, c, d in rows:
print(f" {n:14s} dx={dx:5d} dy={dy:5d} covered={c:4d} delta={d:+d}")
print(f"三角形单独覆盖 : lo={lo} hi={hi}（差 {lo + hi - quad} 个重复像素）")
print(f"共享对角线像素 : {both_claim}（被两个三角形同时认领，edge == 0）")
print(f"四边形覆盖 : {quad} 像素（culled={quad_cull}）；png {png} bytes")
cglib.rasterize 是 S 层的共享底座，它内部的覆盖判据就是本节推的那三个边函数与 >= 0。脚本不重写它，只调用它并读回 covered 掩码——lo & hi 两个掩码的按位与，就是「被两个三角形同时认领」的像素。
跨语言断言：同一个边函数，两种语言
S 层的数字要能当基准，前提是它在另一种语言里能逐像素复现。下面这个 TypeScript 内核用 Number 重写边函数与覆盖掩码（量级 $\le 2^{22}$，远在浮点整数区内），再用 node --test 把 S 层写出的 JSON 逐条对上。
// file: lantern/core/src/lantern/cg_raster_06_edge.ts
// tier: P
// verify: node --test 'core/test/cg_raster_06_*.test.ts'
// 6.1 的最小边函数内核：与 Python 侧 sim/cg_raster_06_1_edge.py 的 edge() 逐字对齐。
//
// 逐像素层用 Number 而不是 BigInt：屏幕 Q6 坐标 <= 24*64 = 2^10.6，
// 边函数 <= 2 * 2^21.2 = 2^22.2 < 2^53，浮点整数区精确（BRIEF §3.2）。
// 像素中心取 px*64 + 32；覆盖判据用 `>= 0`，故共享边像素会被相邻三角形重复认领。
export const SUB1 = 64; // 1 像素 = 64 个 Q6 单位
export const HALF = SUB1 >> 1; // 32：像素中心相对像素左上角的偏移
export type XY = [number, number];
/** 边函数 E(A,B,P) = (B-A) x (P-A)，等于三角形 A、B、P 有向面积的 2 倍。 */
export function edge(ax: number, ay: number, bx: number, by: number, px: number, py: number): number {
return (bx - ax) * (py - ay) - (by - ay) * (px - ax);
}
/** 两个 Q6 屏幕坐标的有向面积（= E(A,B,C)），> 0 表示屏幕空间逆时针正面。 */
export function signedArea2x(xy: XY[]): number {
return edge(xy[0][0], xy[0][1], xy[1][0], xy[1][1], xy[2][0], xy[2][1]);
}
/** 逐像素覆盖掩码：像素中心落在三条边的同侧（均 >= 0）即为覆盖。 */
export function coverMask(xy: XY[], w: number, h: number): Uint8Array {
const mask = new Uint8Array(w * h);
const area = signedArea2x(xy);
if (area <= 0) return mask; // 背面剔除：area <= 0 的三角形整块丢弃
const xs = [xy[0][0], xy[1][0], xy[2][0]];
const ys = [xy[0][1], xy[1][1], xy[2][1]];
const minx = Math.max(0, Math.floor(Math.min(xs[0], xs[1], xs[2]) / SUB1));
const maxx = Math.min(w - 1, Math.floor(Math.max(xs[0], xs[1], xs[2]) / SUB1));
const miny = Math.max(0, Math.floor(Math.min(ys[0], ys[1], ys[2]) / SUB1));
const maxy = Math.min(h - 1, Math.floor(Math.max(ys[0], ys[1], ys[2]) / SUB1));
for (let py = miny; py <= maxy; py += 1) {
const Y = py * SUB1 + HALF;
for (let px = minx; px <= maxx; px += 1) {
const X = px * SUB1 + HALF;
const w0 = edge(xs[1], ys[1], xs[2], ys[2], X, Y);
const w1 = edge(xs[2], ys[2], xs[0], ys[0], X, Y);
const w2 = edge(xs[0], ys[0], xs[1], ys[1], X, Y);
if (w0 >= 0 && w1 >= 0 && w2 >= 0) mask[py * w + px] = 1;
}
}
return mask;
}
/** 覆盖像素数。 */
export function coverCount(xy: XY[], w: number, h: number): number {
let n = 0;
const mask = coverMask(xy, w, h);
for (let i = 0; i < mask.length; i += 1) n += mask[i];
return n;
}
node --test 'core/test/cg_raster_06_1_edge.test.ts' 的实测输出：
✔ 边函数：E(A,B,C) 等于有向面积的 2 倍，顶点在边上恒为 0
✔ 覆盖数：与 Python 侧逐像素一致
✔ 环绕符号：交换两个顶点使 area 变号，三角形被背面剔除
✔ 子像素扰动：平移 1 个 Q6 单位改变覆盖数，平移整数像素不改变
✔ 共享边：`>= 0` 让对角线上的像素被两个三角形同时认领
ℹ tests 5 ℹ pass 5 ℹ fail 0
5 条断言全绿：TypeScript 复现了 Python 的覆盖数、环绕符号、扰动表与共享边像素数。这就是「一份规格、两种语言、同一个整数结果」的最小样本——下一节把边函数归一化成重心坐标，用它插值颜色与深度。
阅读导航：上一节：5.3 视锥与近远平面 · 下一节：6.2 重心坐标与插值 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。