10.3 画家算法与深度排序
前两节都在围绕深度缓冲做文章：10.1 算它的精度，10.2 治它的冲突。这一节退回到一个更早的思路——干脆不要深度缓冲。画家算法的做法和油画一样：把要画的东西按前后排好序，从最远的开始往近处一层层盖，后画的自然盖住先画的。它和纹理层叠的取舍有点像，如果你关心纹理侧的顺序问题，可以看 纹理与显存 那篇——那篇讲的是纹理显存管理；本卷讲的是深度缓冲的定点精度与分布。
画家算法省掉了逐像素比较，代价是：它只能按整个三角形排序，无法在三角形内部判断局部前后。本节要用两个场景把这个代价量化——一个场景里画家与 z-buffer 逐字节相同，另一个场景里它们必然分歧，并说清分歧出在哪里。
画家算法：不做逐像素测试
画家算法的规则一句话：按每个三角形的质心深度从远到近排序，依次光栅化，后画的覆盖先画的。质心深度取三个顶点深度的整数平均。
它和 z-buffer 的根本区别在于「粒度」：z-buffer 在每个像素上比较深度，画家算法在每个三角形上比较一次。粒度粗，就必然有它判不准的情形——当两个三角形在空间里真的交叉、或在屏幕上互相穿插时，「谁整体在前」这个问题没有统一答案，质心排序只能给出一个全局折中。
怎么用共享光栅化器实现画家算法
本卷不想为画家算法再写一个光栅化器。观察到一个事实：共享库 cglib.rasterize 逐像素插值出的深度，在三角形内部是常数当且仅当三个顶点深度相等——因为重心权重满足 $w_0 + w_1 + w_2 = \text{area}$，常数深度插出来仍是那个常数。
于是可以玩一个转换：把第 $k$ 个要画的三角形的三个顶点深度都设成 $-k$。这样它的插值深度恒为 $-k$，而 rasterize 的深度测试是「越小越近」，$-k$ 随绘制次序单调下降——后画的（更负）自然覆盖先画的。画家语义被完整地翻译成了一次普通的 z-buffer 调用，一行覆盖/插值逻辑都不用改。
两个场景：可分离与相交
用两个场景检验它：
- 场景 A（可分离）：两块平行墙，一块在 $z = -1$（前）、一块在 $z = -2$（后），投影后前墙完整盖住后墙，两面互不穿插。这种场景里「整块前后」是明确的，画家算法和 z-buffer 应该给出逐字节相同的结果。
- 场景 B（相交）：一块水平条（$y = -0.3$，$z$ 从 $-1$ 到 $-2.5$）与一块斜条在空间里真的交叉。交叉处「谁在前」逐像素不同，质心排序只能二选一，必然在交叉带判错——两法允许不同，且差异可数。
实测：0 与 63
场景 A（两面平行墙，可分离）: 4 三角形，绘制顺序（远->近）= [49539, 49539, 33026, 33026]
画家 vs z-buffer 不同像素 : 0 <- 可分离场景应逐字节相同
画家结果 sha256 : fcdef1b7ffafd0372830020fd88a6768ca953a293161ef98e5b0e6893c7bb816
场景 B（水平条 x 竖直条，相交）: 4 三角形，覆盖 920 像素
画家 vs z-buffer 不同像素 : 63 <- 质心排序在交叉处判错局部前后
差异占比 : 68‰
读法：
- 场景 A 差异 0 像素。两块平行墙质心深度分别是 $33026$（前墙）和 $49539$（后墙），排序后从远到近画（$49539$ 先、$33026$ 后），结果与逐像素 z-buffer 逐字节相同。这不是巧合，是「整块前后明确」这一前提的直接后果——当场景可分离时，三角形级排序与像素级测试给出同一答案。
sha256是场景 A 结果的字节指纹，供 P 层复算。 - 场景 B 差异 63 像素，占覆盖的 68‰。水平条与斜条在屏幕上重叠 $920$ 个像素，其中 $63$ 个落在交叉带：那里斜条时前时后，质心排序的单一选择必然有错。差异是允许的——画家算法在这类场景下本就不保证正确。这也正是当年 z-buffer 取代画家算法的原因：像素级粒度换来了对穿插场景的正确性。
可运行产物
下面的脚本渲染两个场景，分别跑画家算法与 z-buffer，统计差异像素，并把场景 A 的三角形清单落盘供 P 层重放。它复用共享库 cglib.rasterize。
#!/usr/bin/env python3
# file: lantern/sim/cg_raster_10_3_painter.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_raster_10_3_painter.py
"""10.3 画家算法与深度排序：按质心深度排序逐三角形绘制，与 z-buffer 逐像素对照。
画家算法不做逐像素深度测试，只按三角形质心深度从远到近画，后画的盖住先画的。
本脚本用共享库 cglib.rasterize 实现它：把第 k 个要画的三角形的三个顶点深度都设成
`-k`，则插值深度恒为 `-k`（因 w0+w1+w2 == area），`<` 测试让后画的（更负）覆盖先画的
——这就是画家语义，且不重写任何覆盖/插值逻辑。
两个场景：
A 可分离（两面平行墙，投影后一块在前一块在后，互不穿插）——画家与 z-buffer 应逐字节相同。
B 相交（一块水平条与一块竖直条在空间里真的交叉）——质心排序会判错局部前后，两法不同。
产物：out/cg_raster_10_3_painter_a.rgb（场景 A 的画家结果，供 P 层 sha256 比对）、
out/cg_raster_10_3_painter.json、out/cg_raster_10_3_{a,b}_painter.png、_zbuf.png。
"""
import hashlib
import json
import os
import sys
import numpy as np
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__)))
ONE = cglib.ONE
W, H = 64, 48
BG = (12, 14, 20)
def make_mvp(tan_half, aspect, near, far):
view0 = cglib.mat_look_at((0, 0, 0), (0, 0, -ONE), (0, ONE, 0))
return cglib.mat_mul(cglib.mat_perspective(tan_half, aspect, near, far), view0)
def quad_tris(mvp, corners, color):
"""四个 Q16 世界角点 -> 两个屏幕空间三角形（屏幕 Q6 + Q16 深度 + 颜色）。"""
scr = []
for c in corners:
r = cglib.project(mvp, c)
if r is None:
return None
sx, sy = cglib.to_screen(r[0], r[1], W, H)
scr.append((sx, sy, r[2]))
tris = []
for a, b, c in ((0, 1, 2), (0, 2, 3)):
area = (scr[b][0] - scr[a][0]) * (scr[c][1] - scr[a][1]) - (scr[b][1] - scr[a][1]) * (scr[c][0] - scr[a][0])
if area <= 0: # 屏幕空间逆时针为正面
b, c = c, b
tris.append(tuple(v for p in (scr[a], scr[b], scr[c]) for v in (p[0], p[1], p[2], *color)))
return tris
def centroid_depth(t):
"""三角形质心深度（Q16）：三个顶点深度的整数平均。"""
return (t[2] + t[8] + t[14]) // 3
def painter(tris, W, H, bg):
"""按质心深度从远到近画：第 k 个画的三角形深度设为 -k（后画者胜）。"""
order = sorted(range(len(tris)), key=lambda i: -centroid_depth(tris[i]))
ptris = []
for rank, i in enumerate(order):
t = tris[i]
ptris.append((t[0], t[1], -rank, t[3], t[4], t[5],
t[6], t[7], -rank, t[9], t[10], t[11],
t[12], t[13], -rank, t[15], t[16], t[17]))
color, _depth, covered, culled = cglib.rasterize(ptris, W, H, bg)
return color, covered, culled, [int(centroid_depth(tris[i])) for i in order]
def zbuffer(tris, W, H, bg):
color, depth, covered, culled = cglib.rasterize(tris, W, H, bg)
return color, depth, covered, culled
def main():
spec = cglib.load_spec()
cam = spec["camera"]
aspect = cglib.fdiv(cglib.f_from_int(W), cglib.f_from_int(H))
mvp = make_mvp(cam["tanHalfFovYQ16"], aspect, cam["nearQ16"], cam["farQ16"])
def q(v):
return round(v * ONE)
# 场景 A：两块平行墙（z=-1 前 / z=-2 后），投影后一块完整盖住另一块
red, blue = (220, 90, 70), (90, 180, 220)
wall_f = [(-q(0.8), -q(0.6), -q(1.0)), (q(0.8), -q(0.6), -q(1.0)),
(q(0.8), q(0.6), -q(1.0)), (-q(0.8), q(0.6), -q(1.0))]
wall_b = [(-q(1.6), -q(1.2), -q(2.0)), (q(1.6), -q(1.2), -q(2.0)),
(q(1.6), q(1.2), -q(2.0)), (-q(1.6), q(1.2), -q(2.0))]
tris_a = quad_tris(mvp, wall_b, blue) + quad_tris(mvp, wall_f, red) # 反序输入也无妨，画家会重排
pa, pca, _pculla, order_a = painter(tris_a, W, H, BG)
za, _zda, _zca, _zculla = zbuffer(tris_a, W, H, BG)
diff_a = int(np.any(pa != za, axis=2).sum())
# 场景 B：一块水平条（y=-0.3，z 从 -1 到 -2.5）与一块斜条在空间里真交叉
green, yellow = (90, 200, 120), (230, 200, 80)
strip_h = [(-q(0.7), -q(0.3), -q(1.0)), (q(0.7), -q(0.3), -q(1.0)),
(q(0.7), -q(0.3), -q(2.5)), (-q(0.7), -q(0.3), -q(2.5))]
strip_s = [(-q(0.5), -q(0.8), -q(1.2)), (q(0.5), -q(0.8), -q(1.2)),
(q(0.5), q(0.4), -q(2.2)), (-q(0.5), q(0.4), -q(2.2))]
tris_b = quad_tris(mvp, strip_h, green) + quad_tris(mvp, strip_s, yellow)
pb, pcb, _pcullb, _order_b = painter(tris_b, W, H, BG)
zb, _zdb, _zcb, _zcullb = zbuffer(tris_b, W, H, BG)
diff_b = int(np.any(pb != zb, axis=2).sum())
cover_b = int((pcb | _zcb).sum())
out = os.path.join(ROOT, "out")
rgb_a = np.clip(pa, 0, 255).astype(np.uint8).tobytes()
with open(os.path.join(out, "cg_raster_10_3_painter_a.rgb"), "wb") as fh:
fh.write(rgb_a)
sha_a = hashlib.sha256(rgb_a).hexdigest()
cglib.save_png(os.path.join(out, "cg_raster_10_3_a_painter.png"), pa)
cglib.save_png(os.path.join(out, "cg_raster_10_3_a_zbuf.png"), za)
cglib.save_png(os.path.join(out, "cg_raster_10_3_b_painter.png"), pb)
cglib.save_png(os.path.join(out, "cg_raster_10_3_b_zbuf.png"), zb)
# 场景 A 的三角形清单（供 P 层重放）
scene_a = [{"xy": [[t[0], t[1]], [t[6], t[7]], [t[12], t[13]]],
"d": [t[2], t[8], t[14]], "c": [list(t[3:6]), list(t[9:12]), list(t[15:18])]}
for t in tris_a]
with open(os.path.join(out, "cg_raster_10_3_painter.json"), "w", encoding="utf-8") as fh:
json.dump({
"canvas": [W, H], "backgroundQ8": list(BG),
"scene_a": {"triangles": scene_a, "painter_sha256": sha_a,
"painter_vs_zbuf_diff": diff_a, "draw_order": order_a},
"scene_b": {"triangles": len(tris_b), "painter_vs_zbuf_diff": diff_b, "covered": cover_b},
}, fh, ensure_ascii=False, indent=2)
print(f"场景 A（两面平行墙，可分离）: {len(tris_a)} 三角形，绘制顺序（远->近）= {order_a}")
print(f" 画家 vs z-buffer 不同像素 : {diff_a} <- 可分离场景应逐字节相同")
print(f" 画家结果 sha256 : {sha_a}")
print(f"场景 B（水平条 x 竖直条，相交）: {len(tris_b)} 三角形，覆盖 {cover_b} 像素")
print(f" 画家 vs z-buffer 不同像素 : {diff_b} <- 质心排序在交叉处判错局部前后")
print(f" 差异占比 : {diff_b * 1000 // max(1, cover_b)}‰")
return 0
if __name__ == "__main__":
sys.exit(main())
实测输出：
场景 A（两面平行墙，可分离）: 4 三角形，绘制顺序（远->近）= [49539, 49539, 33026, 33026]
画家 vs z-buffer 不同像素 : 0 <- 可分离场景应逐字节相同
画家结果 sha256 : fcdef1b7ffafd0372830020fd88a6768ca953a293161ef98e5b0e6893c7bb816
场景 B（水平条 x 竖直条，相交）: 4 三角形，覆盖 920 像素
画家 vs z-buffer 不同像素 : 63 <- 质心排序在交叉处判错局部前后
差异占比 : 68‰
P 层：重放场景 A 并做逐字节比对
TypeScript 侧把画家逻辑重写进 core/src/lantern/cg_raster_10_painter.ts（centroidDepth / painterOrder / painterRasterize，同样用「深度 = 绘制序号的相反数」这一转换）。测试 core/test/cg_raster_10_3_painter.test.ts 读入 S 层落盘的场景 A 三角形清单，重放画家算法，做 sha256 逐字节比对——Python 与 TypeScript 两份实现逐字节相同，结果哈希 $fcdef1b7\dots$。
测试覆盖三个正例与一个负例：
- 绘制顺序与 Python 侧一致（按质心深度降序，$[49539, 49539, 33026, 33026]$）。
- 画家结果与 Python 侧逐字节相同（
sha256相等）。 - 场景 A 里画家与 z-buffer 差异为 $0$，与金标准一致。
- 负例：把排序方向写反（近到远）必须给出不同结果。断言反序结果与正序不同、且哈希不等于金标准——证明「排序方向」是判据的实质。
场景 B 的差异数（$63$）只由 S 层统计并落盘，P 层断言其大于 $0$：相交场景下质心排序必然判错局部前后，两法不同是预期的，不是 bug。本节 5 条测试全部通过。
下一节进入第 11 章：从「画什么、盖什么」转向「采样」——一个像素到底采了多少信息，以及为什么会出现走样。
阅读导航：上一节：10.2 深度冲突与逆转 z · 下一节：11.1 采样定理与走样 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。