13.2 边函数规则的整数化
6.1 留下了一个悬而未决的问题：覆盖判据用 >= 0 会让共享边像素被相邻两个三角形同时认领，用 > 0 又会一个都不画。工业界的答案叫 top-left rule。站内的 《渲染引擎》
从引擎架构的角度讲 RHI 抽象与 frame graph；本节和它分工不同：那套书关心「渲染器怎么组织」，本节关心一条归属规则怎么用整数写出来、又怎么用可证伪的断言验证它不重不漏。
规则本身一句话：每个三角形只认领「上边」和「左边」的边界像素。这样共享边像素唯一归属于一侧，既不重复也不留缝。难点在于——「上边」「左边」这两个几何直觉，必须翻译成一组只看整数坐标差的布尔条件，才能在 Python 与 TypeScript 下逐字节一致。
共享边归谁：>= 0 的两种病
先把问题定义清楚。覆盖判据对三条边各算一次边函数 $E(A,B,P)$，三条都非负即在三角形内。当 $P$ 恰好落在边上时 $E = 0$，>= 0 放行、> 0 拒绝。把正方形沿主对角线切成两个三角形，对角线就是一条共享边：
- 用
>= 0：对角线上的像素同时满足两个三角形的「三条边非负」，被认领两次——先画的被后画的覆盖，多做一遍无用功，透明度混合时还会出错。 - 用
> 0：对角线上的像素两边都不满足，谁都不画——四边形中间裂开一条缝。
两种病都是共享边造成的。解法不是换个符号，而是给「$E = 0$」的像素补一条方向归属规则。
top-left rule 的整数判据
屏幕空间 $y$ 向下。对一条有向边 $A \to B$，规定它拥有自己的边界样本，当且仅当：
$$\big(B_y - A_y < 0\big) \quad \text{或} \quad \big(B_y - A_y = 0 ;\wedge; B_x - A_x > 0\big)$$
第一项说「这条边朝上走」（$y$ 减小）——它就是三角形的左边；第二项说「这条边水平向右走」——它是顶边。两条合起来，正好是「上边与左边」。其余方向（向下走的右边、水平向左走的底边）不拥有边界样本。
于是覆盖判据变成：三条边函数都 $> 0$，或者 $= 0$ 且该边被拥有。对 $E = 0$ 的像素，只有拥有它的那条边放行；共享边上两个三角形方向相反，恰好只有一个拥有它——归属唯一。判据里没有除法、没有开方、没有浮点，只有整数比较。
把变量隔离出来：顶点落在像素角上
要验证这条规则，得先把无关变量排除掉。如果用例的外边界恰好穿过像素中心，那外边界本身也会触发归属判定，结果里就混进了「外边界漏没漏」的噪声，看不出共享边的效果。
做法是让正方形的顶点落在像素角上（坐标为 64 的整数倍）。这样外边界位于像素之间的缝隙上，不经过任何像素中心；唯一「中心恰好落在边上」的就是那条共享对角线。变量被隔离成单独一条边，测出来的差异只能归因于它。
网格上的强断言：不重不漏
取 4×4 像素的正方形沿主对角线切分，再拼成 3×3 网格（每格两个三角形，共 18 个）。逐个像素累加「被多少个三角形认领」，得到一张认领计数图。
用例 1 正方形 4x4 像素（顶点在像素角上，沿主对角线切分）:
20 认领合计 并集 16 重复 4 最大认领 2
16 认领合计 并集 16 重复 0 最大认领 1
用例 2 3x3 网格（18 三角形）:
naive 认领合计 180 并集 144 重复 36 最大认领 2
topleft 认领合计 144 并集 144 重复 0 最大认领 1
共享边像素 36 其中 top-left 下认领 != 1 的：0（不漏）
top-left 无任何重复认领 : True
这是一条可证伪的强断言。topleft 行的三个数必须同时成立：认领合计 = 并集（没有像素被认领超过一次）、重复 = 0、最大认领 = 1。只要共享边上有任意一个像素被两个三角形同时认领，认领合计就会大于并集；只要有任意一个像素两边都不认领，并集就会比 naive 少——两个方向都被堵死。实测 144 = 144、重复 0、最大认领 1，gaps = 0：36 个共享边像素在 top-left 下恰好各被认领一次。
而 naive 行给出重复 36、最大认领 2——正好是 3×3 网格里 36 个共享边像素。判据既接受了正确实现，又拒绝了 naive 实现，这才叫可信。
整场景：真实重叠 vs 共享边
把规则放到 896 个三角形的整场景上，数字会变得没那么干净。
用例 3 整场景（896 三角形，含球体与地形真实重叠）:
naive 认领合计 47673 并集 43731 重复 3942 最大认领 4
topleft 认领合计 47672 并集 43731 重复 3941 最大认领 4
naive 重复 3942 个像素，但 top-left 只消掉了其中 1 个（47673 → 47672）。为什么？因为整场景里的重复绝大多数不是共享边，而是真实几何重叠：球体插进地形、两个三角形在屏幕上真的叠在一起，最大认领到了 4。这些重叠是合法的——它们该由深度测试（Z-buffer）决定谁在前，而不是由覆盖规则消掉。top-left 只负责消掉共享边那 1 个像素，并且不改变覆盖并集（43731 → 43731）。
这条区分很重要：覆盖归属（谁画这个像素）和深度裁决（谁赢这个像素）是两件事。共享边归属错会导致重复着色，几何重叠则交给深度缓冲。混为一谈，就会误以为「重复像素多 = 有 bug」。
S 层内核：边归属的整数实现
下面的内核把上面所有量变成可复现的数字。owned 是那条整数判据，cover_mask 用 w == 0 && !owned 把不该认领的边界样本剔掉。
#!/usr/bin/env python3
# file: lantern/sim/cg_raster_13_rulelib.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_raster_13_2_edge_rule.py
"""13.2 的整数 top-left rule 内核：边函数、边归属、覆盖掩码、认领计数。
约定：屏幕空间 y 向下，area > 0 为正面，E(A,B,P) >= 0 表示 P 在边 A→B 内侧。
有向边 A→B 拥有其边界样本 iff (B.y-A.y) < 0（左边）或 (B.y-A.y)==0 且 (B.x-A.x)>0（顶边）。
像素中心 X = px*64 + 32、Y = py*64 + 32。逐像素层用 numpy int64，量级 <= 2^31.2。
"""
import numpy as np
SUB1 = 64
HALF = SUB1 // 2
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 owned(ax, ay, bx, by):
"""有向边 A→B 是否拥有其边界样本（top-left rule）。"""
dy = by - ay
if dy < 0:
return True
return dy == 0 and bx - ax > 0
def cover_mask(xy, width, height, rule):
"""覆盖掩码。rule='naive' 用 `>= 0`；rule='topleft' 用 top-left rule。"""
mask = np.zeros((height, width), dtype=bool)
xs = [xy[0][0], xy[1][0], xy[2][0]]
ys = [xy[0][1], xy[1][1], xy[2][1]]
area = edge(xs[0], ys[0], xs[1], ys[1], xs[2], ys[2])
if area <= 0:
return mask
minx = max(0, min(xs) // SUB1)
maxx = min(width - 1, max(xs) // SUB1)
miny = max(0, min(ys) // SUB1)
maxy = min(height - 1, max(ys) // SUB1)
if minx > maxx or miny > maxy:
return mask
px = np.arange(minx, maxx + 1, dtype=np.int64) * SUB1 + HALF
py = np.arange(miny, maxy + 1, dtype=np.int64) * SUB1 + HALF
PX, PY = np.meshgrid(px, py)
# 边 0 = P1→P2，边 1 = P2→P0，边 2 = P0→P1（与 cglib.rasterize 的 w0/w1/w2 同序）
w0 = (xs[2] - xs[1]) * (PY - ys[1]) - (ys[2] - ys[1]) * (PX - xs[1])
w1 = (xs[0] - xs[2]) * (PY - ys[2]) - (ys[0] - ys[2]) * (PX - xs[2])
w2 = (xs[1] - xs[0]) * (PY - ys[0]) - (ys[1] - ys[0]) * (PX - xs[0])
inside = (w0 >= 0) & (w1 >= 0) & (w2 >= 0)
if rule == "topleft":
if not owned(xs[1], ys[1], xs[2], ys[2]):
inside &= w0 != 0
if not owned(xs[2], ys[2], xs[0], ys[0]):
inside &= w1 != 0
if not owned(xs[0], ys[0], xs[1], ys[1]):
inside &= w2 != 0
mask[miny : maxy + 1, minx : maxx + 1] = inside
return mask
def claims(tris_xy, width, height, rule):
"""逐三角形累加认领计数。"""
count = np.zeros((height, width), dtype=np.int32)
for xy in tris_xy:
count += cover_mask(xy, width, height, rule).astype(np.int32)
return count
def summarize(count):
union = count > 0
return {"sum_claims": int(count.sum()), "union": int(union.sum()),
"duplicated": int(count.sum()) - int(union.sum()),
"max_claim": int(count.max()), "pixels_over1": int((count >= 2).sum())}
def split_square(x0, y0, side):
"""顶点落在像素角上的正方形，沿主对角线切成两个三角形。"""
p0, p1 = (x0, y0), (x0 + side, y0)
p2, p3 = (x0 + side, y0 + side), (x0, y0 + side)
return [[p0, p1, p2], [p0, p2, p3]]
驱动脚本 sim/cg_raster_13_2_edge_rule.py 调用这个内核跑三个用例，落盘 out/cg_raster_13_2_quad.png、out/cg_raster_13_2_rule.svg 与 out/cg_raster_13_2_edge_rule.json。逐像素层用 numpy int64，边函数量级 $\le 2^{31.2}$，远在精确整数区。
跨语言断言：同一个归属规则，两种语言
S 层的计数要当基准，前提是 TypeScript 侧能逐字节复现。下面的内核用 Number 重写 owned 与 cover_mask（逐像素层量级 $\le 2^{29.6} < 2^{53}$，浮点整数区精确），再用 node --test 把 S 层 JSON 逐条对上。
// file: lantern/core/src/lantern/cg_raster_13_edge_rule.ts
// tier: P
// verify: node --test 'core/test/cg_raster_13_2_edge_rule.test.ts'
// 13.2 的整数 top-left rule 内核：与 Python 侧 sim/cg_raster_13_2_edge_rule.py
// 的 owned / cover_mask 逐字对齐。
//
// 约定：屏幕空间 y 向下，area > 0 为正面，边函数 E(A,B,P) >= 0 表示 P 在边 A→B 内侧。
// 有向边 A→B 拥有其边界样本 iff (B.y-A.y) < 0（左边）或 (B.y-A.y)==0 且 (B.x-A.x)>0（顶边）。
// 逐像素层用 Number：屏幕 Q6 坐标 <= 320*64 = 2^14.3，边函数 <= 2^29.6，浮点整数区精确。
export const SUB1 = 64; // 1 像素 = 64 个 Q6 单位
export const HALF = SUB1 >> 1; // 32：像素中心相对像素左上角的偏移
export type XY = [number, number];
export type Rule = "naive" | "topleft";
/** 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);
}
/** 有向边 A→B 是否拥有其边界样本（top-left rule）。 */
export function owned(ax: number, ay: number, bx: number, by: number): boolean {
const dy = by - ay;
if (dy < 0) return true;
return dy === 0 && bx - ax > 0;
}
/** 覆盖掩码。rule='naive' 用 `>= 0`；rule='topleft' 用 top-left rule。 */
export function coverMask(xy: XY[], w: number, h: number, rule: Rule): Uint8Array {
const mask = new Uint8Array(w * h);
const xs = [xy[0][0], xy[1][0], xy[2][0]];
const ys = [xy[0][1], xy[1][1], xy[2][1]];
const area = edge(xs[0], ys[0], xs[1], ys[1], xs[2], ys[2]);
if (area <= 0) return mask;
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));
const o0 = owned(xs[1], ys[1], xs[2], ys[2]);
const o1 = owned(xs[2], ys[2], xs[0], ys[0]);
const o2 = owned(xs[0], ys[0], xs[1], ys[1]);
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) continue;
if (rule === "topleft") {
if (w0 === 0 && !o0) continue;
if (w1 === 0 && !o1) continue;
if (w2 === 0 && !o2) continue;
}
mask[py * w + px] = 1;
}
}
return mask;
}
/** 逐三角形累加认领计数。 */
export function claims(tris: XY[][], w: number, h: number, rule: Rule): Int32Array {
const count = new Int32Array(w * h);
for (const t of tris) {
const m = coverMask(t, w, h, rule);
for (let i = 0; i < count.length; i += 1) count[i] += m[i];
}
return count;
}
export type Summary = {
sum_claims: number;
union: number;
duplicated: number;
max_claim: number;
pixels_over1: number;
};
export function summarize(count: Int32Array): Summary {
let sum = 0;
let union = 0;
let max = 0;
let over1 = 0;
for (let i = 0; i < count.length; i += 1) {
sum += count[i];
if (count[i] > 0) union += 1;
if (count[i] > max) max = count[i];
if (count[i] >= 2) over1 += 1;
}
return { sum_claims: sum, union, duplicated: sum - union, max_claim: max, pixels_over1: over1 };
}
/** 顶点落在像素角上的正方形，沿主对角线切成两个三角形。 */
export function splitSquare(x0: number, y0: number, side: number): XY[][] {
const p0: XY = [x0, y0];
const p1: XY = [x0 + side, y0];
const p2: XY = [x0 + side, y0 + side];
const p3: XY = [x0, y0 + side];
return [[p0, p1, p2], [p0, p2, p3]];
}
node --test 'core/test/cg_raster_13_2_edge_rule.test.ts' 的实测输出：
✔ top-left rule：方向判据与边归属
✔ 正方形：naive 对角线重复 4 像素，top-left 恰好各 1 次
✔ 3x3 网格：共享边像素恰好被一个三角形认领（不重不漏）
✔ 整场景：真实重叠使 naive 重复远大于共享边重复
✔ 负例：naive `>= 0` 规则在网格上必须重复认领（判据不被负例拒绝则不可信）
ℹ tests 5 ℹ pass 5 ℹ fail 0
5 条全绿：TypeScript 复现了 Python 的方向判据、正方形与网格计数、整场景数字，还带一条负例——断言 naive >= 0 必然重复认领。判据既接受 top-left、又拒绝 naive，才值得信。下一节把这条规则连同整条定点管线一起推到跨语言比对：同一份规格在 Python 与 TypeScript 下给出同一个 sha256。
阅读导航：上一节：13.1 定点与浮点的分歧 · 下一节：13.3 跨语言逐位一致的验证 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。