8.3 体素的引擎接入
体素 → 网格的算法本身——贪心合并的正确性、网格着色器、GPU 驱动的剔除——归 渲染原理专题 与 网格着色器与次世代管线 讲，本节不重推。本节只算美术侧的账：体素模型转成网格之后，三角数、顶点数、材质槽数各是多少，与预算差多远。
引擎的渲染管线只认三角网格，不认体素格子。所以体素风格的最后一步，是把 8.1 那笔「体素账」翻译成「网格账」。这里有两级简化：第一级是内表面剔除（8.1 已算，716 个面不用画），第二级是贪心合并（greedy meshing）——把同一朝向、同一颜色、共面的相邻面并成更大的矩形。
两级简化：剔除与合并
| 阶段 | 四边形数 | 三角数 | 顶点数 | 说明 |
|---|---|---|---|---|
| 朴素（每暴露面 1 四边形） | 238 | 476 | 952 | 暴露面 × (2 三角 / 4 顶点) |
| 贪心合并后 | 30 | 60 | 120 | 同朝向同色共面矩形合并 |
合并率 (238 − 30) × 1000 ÷ 238 = 873 千分比——同一份体素模型，朴素路线要 476 个三角，合并后只要 60 个。合并是按「轴 × 朝向 × 平面」分组做的：先按面法线方向切成若干平面，每个平面是一张「面内坐标 → 颜色」的掩码，再在掩码上贪心合并同色矩形。
S 层：体素 → 网格的转换账
下面这段是 S 层脚本，读同一份配置，算朴素与贪心合并后的四边形、三角、顶点、合并率、材质槽，与预算对账，并用纯 xml.etree 生成对比条形图 SVG。全整数地板除。
#!/usr/bin/env python3
# file: sim/st08_mesh_account.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/st08_mesh_account.py
"""卷三 8.3 体素的引擎接入（S 层）：体素 → 网格的转换账。
引擎不直接吃体素，要吃三角网格。两种路线：① 朴素路线——每个暴露面出 1 个四边形
（2 三角 / 4 顶点）；② 贪心合并（greedy meshing）——把同一朝向、同一颜色、共面的相邻
面并成更大的矩形。脚本读 config/st08_voxel.json，算暴露面数、朴素与贪心合并后的
四边形/三角/顶点数、合并率千分比、材质槽数，并与预算对账。全整数地板除。
纯 xml.etree 生成 SVG。落 out/st08_mesh_account.json 供 P 层对照。"""
import hashlib
import json
import os
import sys
import xml.etree.ElementTree as ET
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
NBR = [("+x", (1, 0, 0), 0), ("-x", (-1, 0, 0), 0), ("+y", (0, 1, 0), 1),
("-y", (0, -1, 0), 1), ("+z", (0, 0, 1), 2), ("-z", (0, 0, -1), 2)]
PLANE = {0: (0, 1, 2), 1: (1, 0, 2), 2: (2, 0, 1)} # 轴 -> (面朝向轴, 面内 u 轴, 面内 v 轴)
def rasterize(cfg):
grid = {}
for b in cfg["boxes"]:
for x in range(b["min"][0], b["max"][0] + 1):
for y in range(b["min"][1], b["max"][1] + 1):
for z in range(b["min"][2], b["max"][2] + 1):
grid[(x, y, z)] = b["color"]
return grid
def planes_of(grid):
"""把暴露面按 (轴, 朝向, 平面索引) 分组，每组是一张 {面内坐标: 颜色} 掩码。"""
planes = {}
for pos, color in grid.items():
for sign, d, axis in NBR:
if (pos[0] + d[0], pos[1] + d[1], pos[2] + d[2]) in grid:
continue
sa, ua, va = PLANE[axis]
planes.setdefault((axis, sign, pos[sa]), {})[(pos[ua], pos[va])] = color
return planes
def greedy(mask):
"""贪心矩形合并：返回 (矩形数, {颜色: 矩形数})。整数、确定性、无随机。"""
cells, seen, quads, per = set(mask), set(), 0, {}
for (u, v) in sorted(cells):
if (u, v) in seen:
continue
col = mask[(u, v)]
w = 1
while (u + w, v) in cells and (u + w, v) not in seen and mask[(u + w, v)] == col:
w += 1
h = 1
while all((u + i, v + h) in cells and (u + i, v + h) not in seen and mask[(u + i, v + h)] == col
for i in range(w)):
h += 1
seen.update((u + i, v + j) for i in range(w) for j in range(h))
quads += 1
per[col] = per.get(col, 0) + 1
return quads, per
def analyze(cfg):
grid = rasterize(cfg)
planes = planes_of(grid)
naive = sum(len(m) for m in planes.values())
gq, per = 0, {}
for m in planes.values():
q, pm = greedy(m)
gq += q
for k, n in pm.items():
per[k] = per.get(k, 0) + n
per = {k: per[k] for k in sorted(per)}
slots = len(set(grid.values()))
bud = cfg["budget"]
rep = {"project": cfg["project"], "theme": cfg["theme"], "naiveQuads": naive, "greedyQuads": gq,
"naiveTriangles": naive * 2, "greedyTriangles": gq * 2, "naiveVertices": naive * 4,
"greedyVertices": gq * 4, "mergedPermille": (naive - gq) * 1000 // naive,
"greedyQuadsPerMaterial": per, "materialSlots": slots, "trisLow": bud["trisLow"],
"materialSlotsLow": bud["materialSlotsLow"], "trisWithinBudget": gq * 2 <= bud["trisLow"],
"slotsWithinBudget": slots <= bud["materialSlotsLow"]}
rep["canonical"] = json.dumps({"naiveQuads": naive, "greedyQuads": gq, "greedyTriangles": gq * 2,
"mergedPermille": rep["mergedPermille"], "greedyQuadsPerMaterial": per},
separators=(",", ":"), ensure_ascii=False)
rep["digest"] = hashlib.sha256(rep["canonical"].encode()).hexdigest()[:16]
return rep
def write_svg(rep, path):
"""朴素 vs 贪心合并的三角数条形图：条长 = 三角数 × 180 / naiveTriangles，整数。"""
n = rep["naiveTriangles"]
bars = [("naive", n, "#c084fc"), ("greedy", rep["greedyTriangles"], "#5ac8b4")]
root = ET.Element("svg", {"xmlns": "http://www.w3.org/2000/svg", "width": "360", "height": "120"})
for i, (name, val, color) in enumerate(bars):
y = 20 + i * 46
t = ET.SubElement(root, "text", {"x": "14", "y": str(y + 18), "fill": "#94a3b8",
"font-family": "monospace", "font-size": "12"})
t.text = f"{name} {val} tris"
ET.SubElement(root, "rect", {"x": "140", "y": str(y), "width": str(val * 180 // n),
"height": "26", "rx": "4", "fill": color})
t = ET.SubElement(root, "text", {"x": "14", "y": "114", "fill": "#94a3b8",
"font-family": "monospace", "font-size": "10"})
t.text = f"budget={rep['trisLow']} slots={rep['materialSlots']} merged={rep['mergedPermille']}permille"
ET.ElementTree(root).write(path, encoding="utf-8", xml_declaration=True)
def main():
cfg = json.load(open(os.path.join(ROOT, "config/st08_voxel.json"), encoding="utf-8"))
rep = analyze(cfg)
json.dump(rep, open(os.path.join(ROOT, "out/st08_mesh_account.json"), "w", encoding="utf-8"),
ensure_ascii=False, indent=2, sort_keys=True)
write_svg(rep, os.path.join(ROOT, "out/st08_mesh_account.svg"))
print(f"naiveQuads={rep['naiveQuads']} greedyQuads={rep['greedyQuads']} "
f"mergedPermille={rep['mergedPermille']}")
print(f"naiveTriangles={rep['naiveTriangles']} greedyTriangles={rep['greedyTriangles']} "
f"budget={rep['trisLow']} withinBudget={rep['trisWithinBudget']}")
print(f"vertices naive={rep['naiveVertices']} greedy={rep['greedyVertices']} "
f"materialSlots={rep['materialSlots']} slotsLow={rep['materialSlotsLow']} "
f"slotsWithinBudget={rep['slotsWithinBudget']}")
print(f"greedyQuadsPerMaterial={rep['greedyQuadsPerMaterial']}")
print(f"digest={rep['digest']}")
print("wrote out/st08_mesh_account.json + out/st08_mesh_account.svg")
return 0
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/st08_mesh_account.py（同机相对量级）：
naiveQuads=238 greedyQuads=30 mergedPermille=873
naiveTriangles=476 greedyTriangles=60 budget=1500 withinBudget=True
vertices naive=952 greedy=120 materialSlots=3 slotsLow=2 slotsWithinBudget=False
greedyQuadsPerMaterial={'A': 4, 'B': 14, 'M': 12}
digest=81024b922adddb95
wrote out/st08_mesh_account.json + out/st08_mesh_account.svg
三角账很清楚：476 → 60，withinBudget=True（60 ≤ 1500）。但材质槽踩线了：模型用了 3 种材料（B / M / A），而低档预算 materialSlotsLow=2，slotsWithinBudget=False。这是一条真实的规格违例——greedyQuadsPerMaterial 里 A=4 只有 4 个矩形，却要多开一个材质槽。两种收法：把 A（灯芯）的强调色并进 M 用顶点色表达，或者承认这件资产要按中档（材质槽预算更宽）计。
P 层：同一笔账的跨语言对照
下面这段是 P 层 TypeScript 内核 core/src/st08/mesh.ts。collectFaces 按同一套分组切平面，greedyMerge 用同一套「先横向、再纵向」的贪心顺序，保证与 Python 侧合并出同一个矩形数。
// file: core/src/st08/mesh.ts
// tier: P
// verify: node --test 'core/test/st08_*.test.ts'
// 体素 → 网格的转换账内核：暴露面 → 朴素四边形；贪心合并同朝向同色共面矩形 → 合并四边形。
// 与 sim/st08_mesh_account.py 同口径：全整数，逐位一致。只允许可擦除 TS 语法。
import type { Vec3 } from "./voxel.ts";
import { rasterize, NEIGHBORS, vkey, type VoxelModel } from "./voxel.ts";
// 轴 -> (面朝向轴, 面内 u 轴, 面内 v 轴)
const PLANE: Record<number, number[]> = { 0: [0, 1, 2], 1: [1, 0, 2], 2: [2, 0, 1] };
export type FacePlane = { axis: number; sign: string; plane: number; mask: Map<string, string> };
/** 把暴露面按 (轴, 朝向, 平面索引) 分组，每组是一张 {面内坐标: 颜色} 掩码。 */
export function collectFaces(grid: Map<string, string>): FacePlane[] {
const groups = new Map<string, FacePlane>();
for (const [k, color] of grid) {
const [x, y, z] = k.split(",").map(Number);
for (const [sign, d] of NEIGHBORS) {
if (grid.has(vkey(x + d[0], y + d[1], z + d[2]))) continue;
const axis = d[0] !== 0 ? 0 : d[1] !== 0 ? 1 : 2;
const [sa, ua, va] = PLANE[axis];
const pos = [x, y, z];
const gk = `${axis}:${sign}:${pos[sa]}`;
if (!groups.has(gk)) groups.set(gk, { axis, sign, plane: pos[sa], mask: new Map() });
groups.get(gk)!.mask.set(`${pos[ua]},${pos[va]}`, color);
}
}
return [...groups.values()];
}
export type MergeResult = { quads: number; perMat: Record<string, number> };
/** 贪心矩形合并：整数、确定性、无随机。 */
export function greedyMerge(mask: Map<string, string>): MergeResult {
const cells = new Set(mask.keys());
const visited = new Set<string>();
const perMat: Record<string, number> = {};
let quads = 0;
const sorted = [...cells].sort((a, b) => {
const [au, av] = a.split(",").map(Number);
const [bu, bv] = b.split(",").map(Number);
return au - bu || av - bv;
});
for (const ck of sorted) {
if (visited.has(ck)) continue;
const [u, v] = ck.split(",").map(Number);
const color = mask.get(ck)!;
let w = 1;
while (mask.get(`${u + w},${v}`) === color && !visited.has(`${u + w},${v}`)) w++;
let h = 1;
for (;;) {
let ok = true;
for (let i = 0; i < w; i++) {
const p = `${u + i},${v + h}`;
if (mask.get(p) !== color || visited.has(p)) { ok = false; break; }
}
if (!ok) break;
h++;
}
for (let i = 0; i < w; i++) for (let j = 0; j < h; j++) visited.add(`${u + i},${v + j}`);
quads++;
perMat[color] = (perMat[color] || 0) + 1;
}
const sorted2: Record<string, number> = {};
for (const k of Object.keys(perMat).sort()) sorted2[k] = perMat[k];
return { quads, perMat: sorted2 };
}
export type MeshAccount = {
naiveQuads: number; greedyQuads: number; naiveTriangles: number; greedyTriangles: number;
naiveVertices: number; greedyVertices: number; mergedPermille: number;
greedyQuadsPerMaterial: Record<string, number>; materialSlots: number;
trisWithinBudget: boolean; slotsWithinBudget: boolean;
};
export function meshAccount(model: VoxelModel, budget: { trisLow: number; materialSlotsLow: number }): MeshAccount {
const grid = rasterize(model);
const planes = collectFaces(grid);
const naive = planes.reduce((s, p) => s + p.mask.size, 0);
const perMat: Record<string, number> = {};
let greedy = 0;
for (const p of planes) {
const r = greedyMerge(p.mask);
greedy += r.quads;
for (const [k, n] of Object.entries(r.perMat)) perMat[k] = (perMat[k] || 0) + n;
}
const sorted: Record<string, number> = {};
for (const k of Object.keys(perMat).sort()) sorted[k] = perMat[k];
const slots = new Set(grid.values()).size;
return {
naiveQuads: naive, greedyQuads: greedy, naiveTriangles: naive * 2, greedyTriangles: greedy * 2,
naiveVertices: naive * 4, greedyVertices: greedy * 4,
mergedPermille: Math.floor(((naive - greedy) * 1000) / naive),
greedyQuadsPerMaterial: sorted, materialSlots: slots,
trisWithinBudget: greedy * 2 <= budget.trisLow, slotsWithinBudget: slots <= budget.materialSlotsLow,
};
}
测试 core/test/st08_mesh.test.ts 读 out/st08_mesh_account.json 逐位比对。本机实跑 node --test 'core/test/st08_*.test.ts'（本节 5 条，三节合计 16 条）：
✔ 跨语言：朴素 / 合并四边形、三角、顶点、合并率逐位一致（整数类） (2.14325ms)
✔ 跨语言：canonical 摘要与 digest 完全一致 (1.355375ms)
✔ 负例：孤立单体 6 个面彼此不共面，贪心合并一个都合不掉 (0.108334ms)
✔ 负例：同一平面内两个同色相邻面必须并成一个矩形 (0.136084ms)
✔ 负例：材质槽超低档预算必须判越界 (0.723459ms)
ℹ tests 5
ℹ pass 5
ℹ fail 0
两条负例把合并的两个极端钉死：孤立单体的 6 个面彼此不共面，合并数必须等于朴素数（mergedPermille=0）；同一平面内两个同色相邻面必须并成一个矩形，合并数必须小于朴素数。跨语言 digest 81024b922adddb95 与 Python 侧逐位相同。
边界与取舍
- 真实渲染下的体素观感——贪心合并后的网格在真实渲染器里长什么样、合并边界会不会露出接缝——需要真实渲染器与引擎，命令行不可复现，标 X；本节只对面数、三角数、顶点数、材质槽做整数账，不产生真实画面。
- 合并率 873‰、三角 476→60、材质槽 3 都是本机相对量级，换一个体素模型必须重跑，绝对数值不可移植。
- 材质槽 3 > 低档预算 2 是真实违例，不是 bug：它说明「面数达标 ≠ 资产达标」，两笔账要分开对。
| 检查项 | 合格标准 |
|---|---|
| 三角可复算 | 合并四边形 × 2 = 三角数，顶点 = 四边形 × 4 |
| 合并正确 | 孤立面合不掉、共面同色面必须合得掉 |
| 预算分开对 | 三角预算与材质槽预算各自判，互不掩盖 |
| 真渲染标 X | 不把「网格正确」写成「画面正确」 |
体素这一章到此收口：网格、调色板、引擎接入三笔账都落在整数上。下一章换一个几何基座——等距投影，同样用整数算术把 tile 与屏幕坐标对上。
阅读导航：上一节：8.2 体素调色板与光照简化 · 下一节：9.1 等距投影的整数变换 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。