9.2 剔除的判定与代价
上一节把朝向判定收敛成一个整数符号。这一节要回答两个更工程化的问题：这个判定放在管线的哪一步、它到底省下了什么。 顺带说明与站内 /graphics-gpu-driven-rendering-lod/ 的分工：那篇讲的是 GPU 驱动剔除——在 GPU 上按批次、按 LOD 分块做可见性判定，关心的是 draw call 与并行度；本卷关心的是单个三角形朝向的精确判定，以及它在 CPU 整数管线里的可测量代价。
判定放在哪一步
剔除必须在屏幕空间、光栅化循环的最前面做，理由有三条：
- 此时面积符号已经可算。 顶点已经投影到屏幕 Q6 坐标，
area是四个整数乘减，不需要任何额外状态。 - 越早跳越好。 一旦通过判定，后面就是包围盒扫描、逐像素边函数、深度比较、颜色插值——全是随面积增长的活。在门口挡掉，等于整条链都不用跑。
- 判定的成本是常数。 一次乘减加一次比较，与三角形在屏幕上多大无关。
所以正确的顺序是：先判朝向，再算包围盒。反过来（先算包围盒再判）不会错，但白算一遍包围盒。
代价拆成两笔
「省下多少」不能笼统地说，要拆成两个可测的量：
| 量 | 定义 | 量级 |
|---|---|---|
| 像素测试数 | 三角形屏幕包围盒内的像素格数 | 主项，随面积增长 |
| 覆盖像素数 | 通过深度测试、真正写入颜色缓冲的像素 | 次项，有重叠与遮挡 |
像素测试数是上界：包围盒里的每个像素格都要跑一次边函数判定，但其中只有一部分真的落在三角形内，更少的一部分能通过深度测试。所以它是「光栅化的入场费」，是剔除省下的主项。
下面这个脚本把两趟都跑一遍：一趟开剔除（只光栅化 606 个正面），一趟关剔除（把 290 个背面反绕后一并光栅化，模拟「没有剔除会怎样」），再逐三角形统计包围盒像素数。
#!/usr/bin/env python3
# file: lantern/sim/cg_raster_09_2_cull_cost.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_raster_09_2_cull_cost.py
"""9.2 剔除的判定与代价：一次整数符号比较，省下多少像素测试。
背面剔除的判定只有一个整数：屏幕空间边函数 E(A,B,C) <= 0 就跳过。
代价模型把「省下的东西」拆成两笔可测的量：
像素测试数 = 三角形屏幕包围盒的像素格数（覆盖测试的上界，主项）
覆盖像素数 = 真正通过深度测试、写入颜色缓冲的像素（次项）
对比两趟：开剔除只光栅化 606 个正面；关剔除把 290 个背面反绕后一并光栅化。
产物：out/cg_raster_09_2_cost.json、out/cg_raster_09_2_cost.csv、
out/cg_raster_09_2_cost.bin、out/cg_raster_09_2_cull_off.rgb、
out/cg_raster_09_2_cost.svg
"""
import hashlib
import json
import os
import sys
import xml.etree.ElementTree as ET
import numpy as np
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import cglib # noqa: E402
import render_raster as rr # noqa: E402
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
SVG_NS = "http://www.w3.org/2000/svg"
SUB1 = cglib.SUB1
MESH = ["terrain", "sphere0", "sphere1", "sphere2"]
def area2x(t):
return (t[6] - t[0]) * (t[13] - t[1]) - (t[7] - t[1]) * (t[12] - t[0])
def bbox_pixels(t, w, h):
"""三角形屏幕包围盒内的像素格数 —— 覆盖测试数的上界（非负，故 // 与截断一致）。"""
xs, ys = (t[0], t[6], t[12]), (t[1], t[7], t[13])
minx, maxx = max(0, min(xs) // SUB1), min(w - 1, max(xs) // SUB1)
miny, maxy = max(0, min(ys) // SUB1), min(h - 1, max(ys) // SUB1)
return 0 if minx > maxx or miny > maxy else (maxx - minx + 1) * (maxy - miny + 1)
def build_svg(path, per_mesh):
W, H, top = 520, 260, 40
svg = ET.Element("svg", {"xmlns": SVG_NS, "width": str(W), "height": str(H),
"viewBox": f"0 0 {W} {H}"})
def txt(x, y, s, size=12, fill="#222"):
ET.SubElement(svg, "text", {"x": str(x), "y": str(y), "font-size": str(size),
"fill": fill, "font-family": "monospace"}).text = s
txt(16, 22, "pixel tests per mesh (gray = cull off, green = cull on)", 12, "#666")
peak = max(v[2] for v in per_mesh) or 1
for i, (name, on, off) in enumerate(per_mesh):
y = top + i * 50
txt(16, y + 30, name, 12)
for k, (v, col) in enumerate(((off, "#888"), (on, "#3a7"))):
bw = int(300 * v / peak)
ET.SubElement(svg, "rect", {"x": "110", "y": str(y + k * 18), "width": str(bw),
"height": "15", "fill": col})
txt(116 + bw, y + k * 18 + 12, str(v), 11, col)
ET.indent(svg, space=" ")
ET.ElementTree(svg).write(path, encoding="utf-8", xml_declaration=True)
return ET.parse(path).getroot().tag.endswith("svg")
def main():
spec = cglib.load_spec()
w, h = spec["width"], spec["height"]
mvp = cglib.mat_mul(
cglib.mat_perspective(spec["camera"]["tanHalfFovYQ16"],
cglib.fdiv(cglib.f_from_int(w), cglib.f_from_int(h)),
spec["camera"]["nearQ16"], spec["camera"]["farQ16"]),
cglib.mat_look_at(tuple(spec["camera"]["eyeQ16"]), tuple(spec["camera"]["targetQ16"]),
tuple(spec["camera"]["upQ16"])))
verts, tris, vcolors = rr.build_scene(spec)
scr = []
for v in verts:
p = cglib.project(mvp, v)
scr.append(None if p is None else (*cglib.to_screen(p[0], p[1], w, h), p[2]))
rtris, mesh_of = [], []
for i, (a, b, c) in enumerate(tris):
sa, sb, sc = scr[a], scr[b], scr[c]
if sa is None or sb is None or sc is None:
continue
rtris.append((*sa, *vcolors[a], *sb, *vcolors[b], *sc, *vcolors[c]))
mesh_of.append(0 if i < 512 else 1 + (i - 512) // 128)
tests, front = [], []
for t in rtris:
front.append(area2x(t) > 0)
tests.append(bbox_pixels(t, w, h))
tests = np.array(tests, dtype=np.int32)
front = np.array(front)
# 关剔除：把背面反绕（交换第二、三顶点）使 area > 0，从而不被剔除
def rev(t):
return (t[0], t[1], t[2], t[3], t[4], t[5], t[12], t[13], t[14], t[15], t[16], t[17],
t[6], t[7], t[8], t[9], t[10], t[11])
off_tris = [t if front[i] else rev(t) for i, t in enumerate(rtris)]
on_color, on_depth, on_cov, on_cull = cglib.rasterize(rtris, w, h, spec["backgroundQ8"])
off_color, _d, off_cov, off_cull = cglib.rasterize(off_tris, w, h, spec["backgroundQ8"])
back_color, back_depth, back_cov, _bc = cglib.rasterize(
[rev(t) for i, t in enumerate(rtris) if not front[i]], w, h, spec["backgroundQ8"])
on_px = np.clip(on_color, 0, 255).astype(np.uint8)
off_px = np.clip(off_color, 0, 255).astype(np.uint8)
per_mesh = []
for m, name in enumerate(MESH):
sel = np.array([i for i in range(len(rtris)) if mesh_of[i] == m])
per_mesh.append((name, int(tests[sel][front[sel]].sum()), int(tests[sel].sum()),
int(front[sel].sum()), int((~front[sel]).sum())))
tests_on, tests_off = int(tests[front].sum()), int(tests.sum())
covered_on, covered_off = int(on_cov.sum()), int(off_cov.sum())
diff_px = int((on_px != off_px).any(axis=2).sum())
# 背面单独光栅化：它从不扩大覆盖集合（union == 正面覆盖），却在掠射处比正面更近
back_nearer = int(((back_depth < on_depth) & back_cov).sum())
out = os.path.join(ROOT, "out")
cglib.write_csv(os.path.join(out, "cg_raster_09_2_cost.csv"),
["mesh", "front", "back", "tests_cull_on", "tests_cull_off", "saved"],
[(n, f, b, ton, toff, toff - ton) for n, ton, toff, f, b in per_mesh])
with open(os.path.join(out, "cg_raster_09_2_cost.bin"), "wb") as fh:
fh.write(tests.tobytes())
with open(os.path.join(out, "cg_raster_09_2_cull_off.rgb"), "wb") as fh:
fh.write(off_px.tobytes())
svg_ok = build_svg(os.path.join(out, "cg_raster_09_2_cost.svg"),
[(n, ton, toff) for n, ton, toff, _f, _b in per_mesh])
stats = {
"canvas": [w, h], "triangles": len(rtris),
"front": int(front.sum()), "back": int((~front).sum()),
"culled_on": on_cull, "culled_off": off_cull,
"pixel_tests_cull_on": tests_on, "pixel_tests_cull_off": tests_off,
"pixel_tests_saved": tests_off - tests_on,
"saved_permille": (tests_off - tests_on) * 1000 // tests_off,
"tests_per_triangle_on": tests_on // int(front.sum()),
"tests_per_triangle_off": tests_off // len(rtris),
"covered_cull_on": covered_on, "covered_cull_off": covered_off,
"covered_delta": covered_off - covered_on,
"back_only_covered": int(back_cov.sum()),
"back_nearer_pixels": back_nearer,
"union_covered": int((on_cov | back_cov).sum()),
"image_diff_pixels": diff_px,
"sha256_off_rgb": hashlib.sha256(off_px.tobytes()).hexdigest(),
"sha256_tests_bin": hashlib.sha256(tests.tobytes()).hexdigest(),
"per_mesh": [{"mesh": n, "front": f, "back": b, "tests_on": ton, "tests_off": toff,
"saved": toff - ton} for n, ton, toff, f, b in per_mesh],
"svg_ok": svg_ok,
}
with open(os.path.join(out, "cg_raster_09_2_cost.json"), "w", encoding="utf-8") as fh:
json.dump(stats, fh, ensure_ascii=False, indent=2)
print(f"triangles : {len(rtris)} front {stats['front']} / back {stats['back']}")
print(f"culled : on={on_cull} off={off_cull}")
print(f"pixel tests : on={tests_on} off={tests_off} saved={stats['pixel_tests_saved']}"
f" ({stats['saved_permille']}‰)")
print(f"tests/triangle : on={stats['tests_per_triangle_on']} off={stats['tests_per_triangle_off']}")
print(f"covered : on={covered_on} off={covered_off} delta={stats['covered_delta']}"
f" 图像差异像素={diff_px}")
print(f"背面单独光栅化 : 覆盖={stats['back_only_covered']} 其中比正面更近={back_nearer}"
f" 并集={stats['union_covered']}")
for n, ton, toff, f, b in per_mesh:
print(f" {n:8s} front={f:3d} back={b:3d} tests on={ton:6d} off={toff:6d} saved={toff - ton:6d}")
print(f"sha256(tests) : {stats['sha256_tests_bin']}")
print(f"sha256(off.rgb): {stats['sha256_off_rgb']}")
print(f"svg : cg_raster_09_2_cost.svg (valid={svg_ok})")
return 0
if __name__ == "__main__":
sys.exit(main())
跑一次：
# snippet: 本机实跑（工作区 lantern/）
cd lantern
/opt/homebrew/bin/python3 sim/cg_raster_09_2_cull_cost.py
triangles : 896 front 606 / back 290
culled : on=290 off=0
pixel tests : on=140493 off=161448 saved=20955 (129‰)
tests/triangle : on=231 off=180
covered : on=43731 off=43731 delta=0 图像差异像素=2115
背面单独光栅化 : 覆盖=4726 其中比正面更近=2477 并集=43731
terrain front=398 back=114 tests on=131715 off=144048 saved= 12333
sphere0 front= 73 back= 55 tests on= 3216 off= 6142 saved= 2926
sphere1 front= 71 back= 57 tests on= 2404 off= 4678 saved= 2274
sphere2 front= 64 back= 64 tests on= 3158 off= 6580 saved= 3422
sha256(tests) : 5abf4407cf97b68e6af7542261e862e0ed019adab1ea6b143497baa5774e1ea2
sha256(off.rgb): f3002d3e63972b8010e26c582b942443d1a7e30d7da748373fb77cba1d13e13e
svg : cg_raster_09_2_cost.svg (valid=True)
分网格的账（out/cg_raster_09_2_cost.csv）：
mesh,front,back,tests_cull_on,tests_cull_off,saved
terrain,398,114,131715,144048,12333
sphere0,73,55,3216,6142,2926
sphere1,71,57,2404,4678,2274
sphere2,64,64,3158,6580,3422
三个值得记住的数
省下 20955 次像素测试，占 129‰。 剔除把入场费从 161448 降到 140493。这个比例（约 13%）低于「背面占三分之一」的直觉，原因是背面三角形在屏幕上普遍偏小：tests/triangle 一行显示，开剔除时平均每个被画的三角形有 231 个测试格，而全体 896 个平均只有 180 格——背面比正面小，所以剔除它们省下的比例不如数量比例那么夸张。球体上这个效应最明显：sphere2 背面 64 个、正面 64 个正好对半，但关剔除时测试数从 3158 涨到 6580，多出的 3422 几乎全在球体的侧边掠射带上。
覆盖集合分毫不变：43731 → 43731。 两趟的覆盖像素数完全相同，delta=0。这正是「封闭网格上剔除不改变图像」的量化版本——背面三角形从不扩大覆盖集合（背面单独光栅化的并集仍是 43731）。
但图像仍然差了 2115 个像素。 这是本节最反直觉的一条：覆盖集合相同，颜色却有 2115 个像素不同。原因是地形是单层开曲面：在掠射角下，相邻三角形在屏幕空间重叠，其中 2477 个像素上背面三角形比正面更近，于是关剔除时背面赢下深度测试、换掉了颜色。对封闭网格（三个球）这不会发生，对开曲面它会。所以「剔除永远不改变图像」这句话只对封闭网格成立——这条结论在第 9.3 节会以更尖锐的形式出现。
跨语言核对
P 层从同一份规格重算每个三角形的包围盒像素数，与 S 层落盘的 cost.bin（896 个小端 int32）逐字节比对；关剔除那一趟的像素缓冲也一并比对：
// snippet: core/test/cg_raster_09_2_cull_cost.test.ts（节选）
const buf = Buffer.from(tests.buffer, tests.byteOffset, tests.byteLength);
assert.equal(sha(buf), g.sha256_tests_bin); // 与 Python 侧 cost.bin 逐字节相同
const off = rtris.map((t) => signedArea2x(t.xy) > 0 ? t : {
xy: [t.xy[0], t.xy[2], t.xy[1]], // 反绕背面
d: [t.d[0], t.d[2], t.d[1]],
c: [t.c[0], t.c[2], t.c[1]],
});
assert.equal(sha(rasterize(off, spec.width, spec.height, spec.backgroundQ8).rgb),
g.sha256_off_rgb);
这里有一个容易写错的细节：反绕时必须把顶点位置、深度、颜色三样成对交换。只换位置不换深度，边函数判对的像素会读到错位的深度——这类 bug 在单色三角形上看不出来，一到顶点色渐变就露馅。
这组数字各是什么
140493 / 161448 / 20955（129‰） 是剔除的入场费账：关剔除要多跑两万个像素格，省下的比例约 13%。
231 vs 180 解释了比例为什么低于数量比例：背面普遍更小。
43731 → 43731，delta 0 说明封闭网格上剔除不改变覆盖。
2115 / 2477 是开曲面的例外：地形掠射处 2477 个像素上背面更近，其中 2115 个真的换了颜色。
两个 sha256 是跨语言的把手：cost.bin 验的是代价模型本身，off.rgb 验的是关剔除那一趟的整幅像素缓冲。
阅读导航：上一节：9.1 环绕顺序与法线朝向 · 下一节：9.3 双面材质 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。