15.1 程序化网格生成
前十四章一直在「已经有一批三角形」这个前提下工作。本章把三角形造出来，而且不读任何外部文件。站内的 glTF 资产管线
讲的是资产导入工程——文件格式怎么解析、网格怎么压缩、导入器怎么设计；本卷讲的是程序化几何的整数生成：几何完全由 config/scene_spec.json 的字段与整数噪声派生，一个字节的外部模型文件都不读。一个读文件，一个算文件，分工清楚。程序化几何对本书这套「逐字节可复现」的方法论特别友好：外部模型的顶点坐标是别人算的浮点数，你没法断言它；程序化几何的每个坐标都是自己用整数推出来的，可以写解析公式、可以跨语言对照。所以《烛影山谷》的整场景——起伏地形加三个材质球——没有一件外部素材。
两种几何，同一个约束
场景规格里只有两类几何来源：
terrain：一张gridN × gridN的规则高度场，高度由整数噪声函数给出；spheres[]：若干球，每个由八面体细分生成，细分次数由subdiv字段给出。
两者的共同约束是全整数：不许出现浮点常量、不许出现 sin / cos、不许调用 random。这不是洁癖——本套的核心主张是「同一份规格在 Python 与 TypeScript 下产出逐字节相同的缓冲」，而浮点三角函数在两种语言里的实现细节（libm 版本、-ffast-math、求值顺序）没有任何跨语言保证。整数没有这个问题：加减乘、算术右移、显式向零截断的定点除法，都是精确定义的。
八面体细分球：顶点数的解析式
球面本身是超越曲面，任何多边形化都是逼近。常见的做法是经纬球：按纬度切圈、按经度分段，坐标用 $\sin$/$\cos$ 算。本书不这么做，原因就是上一段——三角函数表一旦有偏差，顶点会飞出画面，而且没法跨语言复现。改用八面体细分：
- 取正八面体的 6 个顶点 $(\pm 1, 0, 0)$、$(0, \pm 1, 0)$、$(0, 0, \pm 1)$，归一化到单位球面；
- 把 8 个三角形面各切一刀：每条边的中点归一化回球面，一个三角形变成 4 个；
- 重复第 2 步
subdiv次； - 最后乘半径、加球心。
全流程只有整数加法、算术右移（>> 1 取中点）与定点归一化（v_norm，内部用 fsqrt 与 fdiv），没有一次三角函数。
顶点数有闭式解。设第 $d$ 步后有 $V_d$ 个顶点、$F_d$ 个面。初始 $V_0 = 6$、$F_0 = 8$。细分时每条边中点成为新顶点，而三角网格的边数 $E_d = 3F_d/2$，所以
$$V_{d+1} = V_d + E_d = V_d + \tfrac{3}{2} F_d = V_d + 12 \cdot 4^d, \qquad F_{d+1} = 4 F_d = 8 \cdot 4^{d+1}$$
对 $V$ 求和解这个一阶递推：
$$V_d = 6 + 12\sum_{k=0}^{d-1} 4^k = 6 + 12\cdot\frac{4^d - 1}{3} = 4^{d+1} + 2$$
面数更直接：$F_d = 8 \cdot 4^d$。脚本把这两条公式对 subdiv = 0..3 逐个断言，实测全部吻合：subdiv = 0, 1, 2, 3 依次给出 6/8、18/32、66/128、258/512（顶点/三角形），与公式逐个对上。
注意 subdiv = 2 时是 66 顶点 / 128 三角形，而不是「8 的某个幂」：相邻三角形共享边中点，正是这个共享让 $V$ 只按 $4^d$ 增长而不是 $4^{d+1}$。下一节讨论表示法时，它就是索引缓冲省下的字节。
地形：整数噪声 + 双线性 + smoothstep
地形是一张规则格点的高度场。terrain.gridN = 16 表示 16 × 16 个格子，也就是 17 × 17 = 289 个格点。这里要小心一个容易写错的计数：顶点数是 (gridN+1)^2 而不是 gridN^2——$N$ 个格子需要 $N+1$ 个格线交点。三角形数则是每个格子两个：$2N^2 = 512$。
高度来自一个确定性整数哈希噪声 _hash_noise(ix, iz, seed)：把格点整数坐标与种子做三次乘加异或、右移混合、取模 $2^{16}$，得到 $[0, 65536)$ 的 Q16.16 值。它没有任何浮点、没有 random——同一份 (ix, iz, seed) 必然给出同一个数。
格点之间的插值用双线性 + smoothstep：
$$n = a + \mathrm{ss}(t_z),(b - a),\quad a = n_{00} + \mathrm{ss}(t_x)(n_{10} - n_{00}),\quad b = n_{01} + \mathrm{ss}(t_x)(n_{11} - n_{01})$$
其中 $\mathrm{ss}(t) = 3t^2 - 2t^3$，分数部分 $t_x, t_z$ 由世界坐标对格点间距取余得到。为什么不用线性插值？线性插值在格线上导数不连续，地形会出现明显的「折纸」棱线；smoothstep 在 $t=0$ 与 $t=1$ 处导数为零，格子之间的过渡是光滑的。全部是整数乘加与 >> 16，没有任何 pow。
噪声格点间距取 4.0 世界单位（Q16.16 里就是 1 << 18），这个常数决定起伏尺度：太小则地形像砂纸，太大则整个场景只有一两个坡。实测高度落在 $[8856, 188874]$（Q16.16），即 0.135 到 2.882 个世界单位。
地形没有法线（卷一第 1 章的最小模型里，地形法线简化为竖直向上），起伏靠顶点色显现：低处用 albedoQ8 = [72, 82, 66]（深色），高处用 albedoHighQ8 = [158, 152, 132]（浅色），中间按高度归一化后的 $t$ 线性插值，即 t = min(ONE, max(0, (y << 16) // hs)) 后对三个通道各取 lo[i] + (((hi[i] - lo[i]) * t) >> 16)。实测最低处顶点色为 (75, 85, 68)、最高处为 (154, 149, 129)（低/高参考色分别是 [72, 82, 66] 与 [158, 152, 132]）。
这里 y << 16 之后再整除 hs：因为 $y \ge 0$ 且 $hs > 0$，分子非负，所以 // 与向零截断一致，两种语言可复现（BRIEF §3.3）。最低点颜色 (75, 85, 68) 比 albedoQ8 亮一点，因为最低顶点并不在 $t = 0$ 处——噪声哈希最小值不是 0，说明插值真的在按高度取值。
可运行产物
下面这个脚本把上面所有断言变成可复现的数字：对 subdiv = 0..3 验证顶点数公式，装配整场景并断言对上基线 487 顶点 / 896 三角形，把几何序列化成小端 int32 缓冲取 sha256，最后采样 128 × 128 个点画出地形俯视图。
#!/usr/bin/env python3
# file: lantern/sim/cg_raster_15_1_procedural_mesh.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_raster_15_1_procedural_mesh.py
"""15.1 程序化网格生成：八面体细分球 + 整数噪声地形，全整数、无三角函数、无随机数。
几何全部由 config/scene_spec.json 的字段派生，不读任何外部模型文件；顶点数与三角形数
的解析公式被钉成断言，整场景几何序列化成小端 int32 缓冲并取 sha256 供 TypeScript 复现。
产物：out/cg_raster_15_1_mesh.bin、out/cg_raster_15_1_mesh.json、out/cg_raster_15_1_terrain.png。
"""
import hashlib
import json
import os
import struct
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__)))
def sphere_formula(d):
"""V = 4^(d+1) + 2，F = 8*4^d：每步 V_{d+1} = V_d + 12*4^d（第 d 步边数 = 3F_d/2）。"""
return 4 ** (d + 1) + 2, 8 * (4 ** d)
def terrain_albedo(y, lo, hi, hs):
"""顶点色按高度在 albedoQ8（低处）与 albedoHighQ8（高处）间整数插值。"""
t = (y << 16) // hs if hs else 0
t = min(cglib.ONE, max(0, t))
return tuple(lo[i] + (((hi[i] - lo[i]) * t) >> 16) for i in range(3))
def pack(verts, tris):
"""顶点（x,y,z Q16.16）与索引（a,b,c）打包成小端 int32 缓冲。"""
buf = bytearray()
for v in verts:
buf += struct.pack("<iii", v[0], v[1], v[2])
for a, b, c in tris:
buf += struct.pack("<iii", a, b, c)
return bytes(buf)
def main():
spec = cglib.load_spec()
out = os.path.join(ROOT, "out")
os.makedirs(out, exist_ok=True)
rows = []
for d in range(4):
sv, st = cglib.build_sphere((0, 0, 0), cglib.ONE, d)
ev, ef = sphere_formula(d)
assert (len(sv), len(st)) == (ev, ef), f"subdiv={d} 实测与公式不符"
rows.append((d, len(sv), len(st), ev, ef))
terr = spec["terrain"]
n = terr["gridN"]
tv, tt = cglib.build_terrain(n, terr["extentQ16"], terr["heightScaleQ16"], terr["noiseSeed"])
assert len(tv) == (n + 1) ** 2, "地形顶点数应为 (gridN+1)^2"
assert len(tt) == 2 * n ** 2, "地形三角形数应为 2*gridN^2"
verts, tris = list(tv), list(tt)
alb = [terrain_albedo(y, terr["albedoQ8"], terr["albedoHighQ8"], terr["heightScaleQ16"])
for _, y, _ in tv]
for sp in spec["spheres"]:
sv, st = cglib.build_sphere(sp["centerQ16"], sp["radiusQ16"], sp["subdiv"])
b = len(verts)
verts.extend(sv)
tris.extend((a + b, c + b, e + b) for a, c, e in st)
assert (len(verts), len(tris)) == (487, 896), "场景装配必须对上卷一基线"
blob = pack(verts, tris)
digest = hashlib.sha256(blob).hexdigest()
with open(os.path.join(out, "cg_raster_15_1_mesh.bin"), "wb") as fh:
fh.write(blob)
m, ext = 128, terr["extentQ16"]
img = np.array([[cglib.terrain_height(-ext + (2 * ext * i) // (m - 1),
-ext + (2 * ext * j) // (m - 1),
terr["noiseSeed"], terr["heightScaleQ16"])
for i in range(m)] for j in range(m)], dtype=np.int64)
png = cglib.save_gray_png(os.path.join(out, "cg_raster_15_1_terrain.png"), img)
ymin, ymax = min(v[1] for v in tv), max(v[1] for v in tv)
ilo = min(range(len(tv)), key=lambda k: tv[k][1])
ihi = max(range(len(tv)), key=lambda k: tv[k][1])
stats = {"gridN": n, "terrain_verts": len(tv), "terrain_tris": len(tt),
"sphere_formula": [{"subdiv": d, "verts": v, "tris": f,
"verts_formula": ev, "tris_formula": ef} for d, v, f, ev, ef in rows],
"scene_verts": len(verts), "scene_tris": len(tris),
"height_min": ymin, "height_max": ymax,
"albedo_lo": list(alb[ilo]), "albedo_hi": list(alb[ihi]),
"bytes": len(blob), "sha256": digest}
with open(os.path.join(out, "cg_raster_15_1_mesh.json"), "w", encoding="utf-8") as fh:
json.dump(stats, fh, ensure_ascii=False, indent=2)
print("八面体细分球（实测 vs 公式 4^(d+1)+2 / 8*4^d）:")
for d, v, f, ev, ef in rows:
print(f" subdiv={d} verts={v:4d}(={ev:4d}) tris={f:4d}(={ef:4d})")
print(f"地形 gridN={n} : 格点 {n + 1}x{n + 1} -> verts={len(tv)}"
f"（格子数 gridN^2={n ** 2}）；tris={len(tt)}=2*gridN^2")
print(f"地形高度范围 : y in [{ymin}, {ymax}] Q16.16"
f"（{ymin / 65536:.3f} .. {ymax / 65536:.3f} 世界单位）")
print(f"顶点色插值样例 : 最低处 albedo={alb[ilo]} -> 最高处 albedo={alb[ihi]}"
f"（区间 {terr['albedoQ8']} .. {terr['albedoHighQ8']}）")
print(f"场景装配 : verts={len(verts)} tris={len(tris)}"
f"（= 地形 {len(tv)}/{len(tt)} + 3 球 x {rows[2][1]}/{rows[2][2]}）")
print(f"几何缓冲 : {len(blob)} bytes（顶点 487*12 + 索引 896*3*4）")
print(f"sha256(geometry) : {digest}")
print(f"terrain png : {png} bytes")
return 0
if __name__ == "__main__":
sys.exit(main())
实测输出如下（脚本开头的顶点数公式对账 5 行已在上文给出，这里从地形那行接续）：
地形 gridN=16 : 格点 17x17 -> verts=289（格子数 gridN^2=256）；tris=512=2*gridN^2
地形高度范围 : y in [8856, 188874] Q16.16（0.135 .. 2.882 世界单位）
顶点色插值样例 : 最低处 albedo=(75, 85, 68) -> 最高处 albedo=(154, 149, 129)（区间 [72, 82, 66] .. [158, 152, 132]）
场景装配 : verts=487 tris=896（= 地形 289/512 + 3 球 x 66/128）
几何缓冲 : 16596 bytes（顶点 487*12 + 索引 896*3*4）
sha256(geometry) : f633176ae1b459a4b6428e8ac0f27b91eb1bdd11fd027f4d0d9a94e975f49cf8
terrain png : 7503 bytes
487 = 289 + 3 × 66，896 = 512 + 3 × 128——整场景的顶点与三角形正好对上前几章的基线统计。16596 字节 = 487 × 12（顶点 3 个 int32） + 896 × 12（三个索引各一个 int32）。
跨语言断言：同一份几何，两种语言
几何要能当基准，前提是它在另一种语言里能逐字节复现。下面的 TypeScript 模块用 BigInt 重写同一套生成与序列化：buildSphere / buildTerrain 逐字对齐 Python 侧，packGeometry 按小端 int32 打包。测试用 node --test 读 S 侧写出的 out/cg_raster_15_1_mesh.bin，逐字节比对并核对 sha256。
// file: lantern/core/src/lantern/cg_raster_15_mesh.ts
// tier: P
// verify: node --test 'core/test/cg_raster_15_*.test.ts'
// 15.1 / 15.2 共用的几何工具：解析公式、场景装配、几何序列化、展开与去重。
// 与 Python 侧 sim/cg_raster_15_1_procedural_mesh.py 与 cg_raster_15_2_mesh_representation.py 对齐。
// 顶点层是 BigInt（Q16.16 矩阵链会超 2^53），序列化时再降到 int32 小端。
import { type Mesh, buildSphere, buildTerrain } from "./mesh.ts";
import type { SceneSpec } from "./pipeline.ts";
import type { Vec3 } from "./vec.ts";
/** 八面体细分球的解析顶点/面数：V = 4^(d+1) + 2，F = 8 * 4^d。 */
export function sphereFormula(subdiv: number): { verts: number; tris: number } {
return { verts: 4 ** (subdiv + 1) + 2, tris: 8 * 4 ** subdiv };
}
/** 顶点色按高度在 albedoQ8（低处）与 albedoHighQ8（高处）间整数插值。 */
export function terrainAlbedo(
y: bigint,
lo: readonly number[],
hi: readonly number[],
heightScale: bigint,
): [number, number, number] {
let t = heightScale === 0n ? 0n : (y << 16n) / heightScale;
if (t > 65536n) t = 65536n;
if (t < 0n) t = 0n;
return [0, 1, 2].map(
(i) => lo[i] + Number(((BigInt(hi[i] - lo[i]) * t) >> 16n)),
) as [number, number, number];
}
/** 场景几何（地形 + 若干球）：顶点/索引顺序与 Python 侧 build_scene 逐字一致。 */
export function buildSceneGeometry(spec: SceneSpec): Mesh {
const t = spec.terrain;
const tv = buildTerrain(t.gridN, BigInt(t.extentQ16), BigInt(t.heightScaleQ16), BigInt(t.noiseSeed));
const verts: Vec3[] = tv.verts.slice();
const tris: [number, number, number][] = tv.tris.slice();
for (const sp of spec.spheres) {
const mesh = buildSphere(sp.centerQ16.map((n) => BigInt(n)) as Vec3, BigInt(sp.radiusQ16), sp.subdiv);
const base = verts.length;
verts.push(...mesh.verts);
for (const [a, b, c] of mesh.tris) tris.push([a + base, b + base, c + base]);
}
return { verts, tris };
}
/** 顶点（x,y,z Q16.16）与三角形索引（a,b,c）打包成小端 int32 缓冲。 */
export function packGeometry(mesh: Mesh): Uint8Array {
const buf = new Uint8Array(mesh.verts.length * 12 + mesh.tris.length * 12);
const dv = new DataView(buf.buffer);
let o = 0;
for (const v of mesh.verts) {
dv.setInt32(o, Number(v[0]), true);
dv.setInt32(o + 4, Number(v[1]), true);
dv.setInt32(o + 8, Number(v[2]), true);
o += 12;
}
for (const t of mesh.tris) {
dv.setInt32(o, t[0], true);
dv.setInt32(o + 4, t[1], true);
dv.setInt32(o + 8, t[2], true);
o += 12;
}
return buf;
}
/** 索引表示 -> 独立三角形表示：每个角点复制一份顶点，索引退化为 0,1,2,3,4,5,...。 */
export function expandToNonIndexed(mesh: Mesh): Mesh {
const verts: Vec3[] = [];
const tris: [number, number, number][] = [];
for (const [a, b, c] of mesh.tris) {
const n = verts.length;
verts.push(mesh.verts[a], mesh.verts[b], mesh.verts[c]);
tris.push([n, n + 1, n + 2]);
}
return { verts, tris };
}
/** 按 (x,y,z) 定点三元组去重：返回新顶点表与重映射后的索引（三角形顺序不变）。 */
export function dedupMesh(mesh: Mesh): { mesh: Mesh; merged: number } {
const verts: Vec3[] = [];
const seen = new Map<string, number>();
const remap: number[] = [];
for (const v of mesh.verts) {
const key = `${v[0]},${v[1]},${v[2]}`;
let idx = seen.get(key);
if (idx === undefined) {
idx = verts.length;
verts.push(v);
seen.set(key, idx);
}
remap.push(idx);
}
const tris = mesh.tris.map(([a, b, c]) => [remap[a], remap[b], remap[c]] as [number, number, number]);
return { mesh: { verts, tris }, merged: mesh.verts.length - verts.length };
}
/** 三角形集合（顶点坐标三元组，按坐标排序）——去重前后必须完全相同。 */
export function triangleCoordSet(mesh: Mesh): Set<string> {
const out = new Set<string>();
for (const [a, b, c] of mesh.tris) {
out.add([mesh.verts[a], mesh.verts[b], mesh.verts[c]]
.map((v) => `${v[0]},${v[1]},${v[2]}`).sort().join("|"));
}
return out;
}
node --test 'core/test/cg_raster_15_1_procedural_mesh.test.ts' 实测 7 条断言全绿：
ℹ tests 7 ℹ pass 7 ℹ fail 0
其中「【核心】几何缓冲与 Python 侧逐字节相同」既比 sha256 也比 .bin 原始字节；两个负例把「细分次数改一级」与「三角形环绕反转」分别喂进去，digest 都必须分叉——判据不拒绝错误实现，PASS 就不可信。
与基线对账
本章的几何生成必须能解释前几章的基线统计 487 顶点 / 896 三角形，实测正好吻合，没有差额。需要说明一处口径：任务描述里的「地形顶点数 = gridN^2」指的是格子数（16 × 16 = 256 个格子），顶点数则是格点数 (gridN+1)^2 = 289——$N$ 个格子需要 $N+1$ 个格线交点。若误把顶点数写成 256，整场景会变成 454 顶点，与基线对不上。这个 off-by-one 在网格生成里很常见，所以脚本把它写成断言。
下一节换一个视角：同样的几何，用索引缓冲存和用独立三角形存，字节账差多少；以及怎么用整数去重把独立三角形表示压回索引表示。
阅读导航：上一节：14.3 中间缓冲的可视化 · 下一节：15.2 网格的表示与加载 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。