15.2 网格的表示与加载

#!/usr/bin/env python3
# file: lantern/sim/cg_raster_15_2_mesh_representation.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/cg_raster_15_2_mesh_representation.py
"""15.2 网格的表示与加载：索引顶点缓冲 vs 独立三角形，以及整数去重与回读。

一个球（subdiv=2）有两种存法：索引表示存 66 个顶点 + 128 个索引三元组；独立三角形表示把
每个角点摊开成 384 个顶点槽、不要索引，两者的字节差是一笔整数账。去重是反向操作：按
(x,y,z) 定点三元组做字典去重，顶点数下降而三角形集合不变。「加载」指把本脚本写出的小端
int32 缓冲回读成顶点表与索引表，断言逐项相同、再序列化逐字节相同。
产物：out/cg_raster_15_2_dedup.json、out/cg_raster_15_2_nonindexed.bin、out/cg_raster_15_2_dedup.bin。
"""

import hashlib
import json
import os
import struct
import sys

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 expand(verts, tris):
    """索引表示 -> 独立三角形表示：每个角点复制一份顶点，索引退化为 0,1,2,3,..."""
    out_v, out_t = [], []
    for a, b, c in tris:
        n = len(out_v)
        out_v.extend((verts[a], verts[b], verts[c]))
        out_t.append((n, n + 1, n + 2))
    return out_v, out_t


def dedup(verts, tris):
    """按 (x,y,z) 定点三元组字典去重；返回 (新顶点表, 重映射索引, 合并数)。"""
    table, remap, new_v = {}, [], []
    for v in verts:
        idx = table.get(v)
        if idx is None:
            idx = len(new_v)
            new_v.append(v)
            table[v] = idx
        remap.append(idx)
    return new_v, [(remap[a], remap[b], remap[c]) for a, b, c in tris], len(verts) - len(new_v)


def tri_coord_set(verts, tris):
    """三角形集合：每个三角形的三个顶点坐标（排序后）组成的可比较键。"""
    return {tuple(sorted((verts[a], verts[b], verts[c]))) for a, b, c in tris}


def pack(verts, tris):
    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 unpack(blob, nv, nt):
    """把索引缓冲回读成顶点表与索引表（「加载」）。"""
    vals = struct.unpack("<%di" % (nv * 3 + nt * 3), blob)
    verts = [(vals[i], vals[i + 1], vals[i + 2]) for i in range(0, nv * 3, 3)]
    tris = [tuple(vals[nv * 3 + i:nv * 3 + i + 3]) for i in range(0, nt * 3, 3)]
    return verts, tris


def main():
    spec = cglib.load_spec()
    out = os.path.join(ROOT, "out")
    os.makedirs(out, exist_ok=True)
    sp = spec["spheres"][0]
    sv, st = cglib.build_sphere(sp["centerQ16"], sp["radiusQ16"], sp["subdiv"])

    idx_bytes = len(sv) * 12 + len(st) * 12          # 66 顶点 + 128 索引三元组
    flat_v, flat_t = expand(sv, st)
    flat_bytes = len(flat_v) * 12                    # 384 个顶点槽
    assert len(flat_v) == 3 * len(st), "独立三角形顶点槽数应为 3*F"

    dd_v, dd_t, merged = dedup(flat_v, flat_t)
    assert len(dd_t) == len(st), "去重后三角形数必须不变"
    assert len(dd_v) < len(flat_v), "去重后顶点数必须下降"
    assert tri_coord_set(flat_v, flat_t) == tri_coord_set(dd_v, dd_t), "三角形集合必须完全相同"
    assert len(dd_v) == len(sv), "去重后顶点数应回到索引表示的顶点数"

    dd_blob = pack(dd_v, dd_t)
    back_v, back_t = unpack(dd_blob, len(dd_v), len(dd_t))
    assert back_v == list(dd_v) and back_t == list(dd_t), "回读的几何必须与写出的逐项相同"
    assert pack(back_v, back_t) == dd_blob, "回读再序列化必须逐字节相同"

    flat_blob = pack(flat_v, flat_t)
    for name, blob in (("nonindexed", flat_blob), ("dedup", dd_blob)):
        with open(os.path.join(out, f"cg_raster_15_2_{name}.bin"), "wb") as fh:
            fh.write(blob)

    t = spec["terrain"]
    tv, tt = cglib.build_terrain(t["gridN"], t["extentQ16"], t["heightScaleQ16"], t["noiseSeed"])
    sc_v, sc_t = list(tv), list(tt)
    for s in spec["spheres"]:
        a, b = cglib.build_sphere(s["centerQ16"], s["radiusQ16"], s["subdiv"])
        base = len(sc_v)
        sc_v.extend(a)
        sc_t.extend((x + base, y + base, z + base) for x, y, z in b)

    digest = hashlib.sha256(flat_blob).hexdigest()
    stats = {"sphere": {"verts": len(sv), "tris": len(st)},
             "indexed_bytes": idx_bytes, "nonindexed_bytes": flat_bytes,
             "nonindexed_slots": len(flat_v), "saved_bytes": flat_bytes - idx_bytes,
             "ratio_permille": flat_bytes * 1000 // idx_bytes,
             "dedup_verts": len(dd_v), "dedup_tris": len(dd_t), "merged": merged,
             "dedup_bytes": len(dd_blob),
             "scene_verts": len(sc_v), "scene_tris": len(sc_t),
             "scene_indexed_bytes": len(sc_v) * 12 + len(sc_t) * 12,
             "scene_nonindexed_bytes": len(sc_t) * 3 * 12,
             "sha256_nonindexed": digest}
    with open(os.path.join(out, "cg_raster_15_2_dedup.json"), "w", encoding="utf-8") as fh:
        json.dump(stats, fh, ensure_ascii=False, indent=2)

    print(f"球 subdiv={sp['subdiv']}      : {len(sv)} 顶点 / {len(st)} 三角形")
    print(f"索引表示           : {len(sv)}*12 + {len(st)}*12 = {idx_bytes} bytes")
    print(f"独立三角形表示     : {len(flat_v)}*12 = {flat_bytes} bytes（{len(flat_v)} 个顶点槽）")
    print(f"字节差             : {flat_bytes - idx_bytes} bytes（独立三角形是索引的 "
          f"{flat_bytes / idx_bytes:.3f} 倍）")
    print(f"去重（字典按 x,y,z）: {len(flat_v)} -> {len(dd_v)} 顶点（合并 {merged} 个），"
          f"三角形 {len(flat_t)} -> {len(dd_t)}")
    print(f"去重后索引缓冲     : {len(dd_blob)} bytes")
    print("回读 round-trip    : verts/tris 逐项相同，再序列化逐字节相同")
    print(f"整场景             : {len(sc_v)} 顶点 / {len(sc_t)} 三角形；"
          f"索引 {stats['scene_indexed_bytes']} bytes vs 独立 {stats['scene_nonindexed_bytes']} bytes")
    print(f"sha256(nonindexed) : {digest}")
    return 0


if __name__ == "__main__":
    sys.exit(main())

球 subdiv=2      : 66 顶点 / 128 三角形
索引表示           : 66*12 + 128*12 = 2328 bytes
独立三角形表示     : 384*12 = 4608 bytes（384 个顶点槽）
字节差             : 2280 bytes（独立三角形是索引的 1.979 倍）
去重（字典按 x,y,z）: 384 -> 66 顶点（合并 318 个），三角形 128 -> 128
去重后索引缓冲     : 2328 bytes
回读 round-trip    : verts/tris 逐项相同，再序列化逐字节相同
整场景             : 487 顶点 / 896 三角形；索引 16596 bytes vs 独立 32256 bytes
sha256(nonindexed) : de15129291f22609f9696b9968e158755d0a93e6d454a2a98e314d3d1abc3530

// file: lantern/core/test/cg_raster_15_2_mesh_representation.test.ts
// tier: P
// verify: node --test 'core/test/cg_raster_15_2_mesh_representation.test.ts'
// 15.2 的跨语言断言：展开、去重、字节账必须与 Python 侧
// sim/cg_raster_15_2_mesh_representation.py 完全一致，独立三角形缓冲逐字节相同。

import assert from "node:assert/strict";
import { createHash } from "node:crypto";
import { readFileSync } from "node:fs";
import { dirname, join } from "node:path";
import { test } from "node:test";
import { fileURLToPath } from "node:url";

import {
  dedupMesh,
  expandToNonIndexed,
  packGeometry,
  triangleCoordSet,
} from "../src/lantern/cg_raster_15_mesh.ts";
import { buildSphere } from "../src/lantern/mesh.ts";
import type { SceneSpec } from "../src/lantern/pipeline.ts";
import type { Vec3 } from "../src/lantern/vec.ts";

const root = join(dirname(fileURLToPath(import.meta.url)), "..", "..");
const spec = JSON.parse(readFileSync(join(root, "config", "scene_spec.json"), "utf8")) as SceneSpec;
const g = JSON.parse(readFileSync(join(root, "out", "cg_raster_15_2_dedup.json"), "utf8")) as {
  sphere: { verts: number; tris: number };
  indexed_bytes: number;
  nonindexed_bytes: number;
  nonindexed_slots: number;
  saved_bytes: number;
  ratio_permille: number;
  dedup_verts: number;
  dedup_tris: number;
  merged: number;
  dedup_bytes: number;
  scene_indexed_bytes: number;
  scene_nonindexed_bytes: number;
  sha256_nonindexed: string;
};
const goldenFlat = readFileSync(join(root, "out", "cg_raster_15_2_nonindexed.bin"));
const goldenDedup = readFileSync(join(root, "out", "cg_raster_15_2_dedup.bin"));
const sha = (b: Uint8Array | Buffer): string => createHash("sha256").update(b).digest("hex");

const sp = spec.spheres[0];
const sphere = buildSphere(
  sp.centerQ16.map((n) => BigInt(n)) as Vec3,
  BigInt(sp.radiusQ16),
  sp.subdiv,
);

test("字节账：索引表示 66*12+128*12，独立三角形 384*12", () => {
  const flat = expandToNonIndexed(sphere);
  assert.equal(sphere.verts.length, g.sphere.verts);
  assert.equal(sphere.tris.length, g.sphere.tris);
  assert.equal(flat.verts.length, g.nonindexed_slots);
  assert.equal(sphere.verts.length * 12 + sphere.tris.length * 12, g.indexed_bytes);
  assert.equal(flat.verts.length * 12, g.nonindexed_bytes);
  assert.equal(g.nonindexed_bytes - g.indexed_bytes, g.saved_bytes);
  assert.equal(g.nonindexed_bytes * 1000 / g.indexed_bytes | 0, g.ratio_permille);
});

test("去重：384 -> 66 顶点，三角形数不变，三角形集合完全相同", () => {
  const flat = expandToNonIndexed(sphere);
  const { mesh: dd, merged } = dedupMesh(flat);
  assert.equal(dd.verts.length, g.dedup_verts);
  assert.equal(dd.tris.length, g.dedup_tris);
  assert.equal(merged, g.merged);
  assert.equal(dd.tris.length, sphere.tris.length);
  assert.ok(dd.verts.length < flat.verts.length, "去重后顶点数必须下降");
  assert.deepEqual([...triangleCoordSet(dd)].sort(), [...triangleCoordSet(flat)].sort());
});

test("【核心】独立三角形缓冲与 Python 侧逐字节相同（sha256）", () => {
  const blob = packGeometry(expandToNonIndexed(sphere));
  assert.equal(sha(blob), g.sha256_nonindexed);
  assert.ok(Buffer.from(blob).equals(goldenFlat));
});

test("去重后的索引缓冲与 Python 侧逐字节相同", () => {
  const { mesh: dd } = dedupMesh(expandToNonIndexed(sphere));
  const blob = packGeometry(dd);
  assert.equal(blob.length, g.dedup_bytes);
  assert.ok(Buffer.from(blob).equals(goldenDedup));
});

test("负例：过度去重（坐标右移 16 位当键）会并掉不同顶点，必须被三角形集合拒绝", () => {
  const flat = expandToNonIndexed(sphere);
  const seen = new Map<string, number>();
  const verts: Vec3[] = [];
  const remap: number[] = [];
  for (const v of flat.verts) {
    const key = `${v[0] >> 16n},${v[1] >> 16n},${v[2] >> 16n}`;
    let idx = seen.get(key);
    if (idx === undefined) {
      idx = verts.length;
      verts.push(v);
      seen.set(key, idx);
    }
    remap.push(idx);
  }
  const bad = { verts, tris: flat.tris.map(([a, b, c]) => [remap[a], remap[b], remap[c]] as [number, number, number]) };
  assert.ok(bad.verts.length < g.dedup_verts, "过度去重应把顶点数压得更低");
  assert.notDeepEqual([...triangleCoordSet(bad)].sort(), [...triangleCoordSet(flat)].sort());
});

ℹ tests 5  ℹ pass 5  ℹ fail 0