5.1 装箱算法与装箱率
卷一 10.2 图集打包与装箱率
从美术规范的角度回答了「图集该不该做、做多大、装得有多满」，那里用的是均匀格 + 货架装箱，复现了共享真源基线 slots=256 placed=37 permille=144。本节换到管线工程的角度，讲同一道整数装箱题里被规范侧略过的那一半：算法本身——为什么必须是确定性的、shelf 与 skyline 差在哪、以及「同一批输入产出同一张布局」这件事怎么被机器验证。纹理显存与压缩格式的原理归 graphics-texture-memory
，本节不重推。
先立一条不变量：装箱率是整数千分比 placedArea*1000 // atlasArea，装箱算法必须确定性。 前者保证跨语言对得上账，后者保证「重跑一次图集」不会悄悄换掉半张图的 UV。
5.1.1 确定性是装箱的隐藏契约
一个装箱器看起来只需要「装进去」这一个正确性条件，其实还有第二个：同样的输入必须给出同样的输出。理由很工程化——图集重打包是流水线里的常规动作（新增一个图标、改一次 gutter、升一档尺寸都会触发），而每一块矩形的位置都会被烘进 sprite 的 UV。只要装箱器有任何非确定性来源（哈希表遍历顺序、随机初始点、浮点比较），重打包后 UV 就会漂移，而漂移会顺着引用链一路传到材质与屏幕（这正是 5.3 图集变更的传播与回归 要处理的事）。
本节的确定性靠三件事保证：排序锁死（高度降序 → 宽度降序 → id 升序，第三键是固定 tie-break）、全整数（不出现浮点比较）、零随机（不调用任何随机源）。可验证性则靠一个布局摘要：把每块写成 id@x,y、按 id 排序、拼起来取 sha256 前 16 位。两张布局的摘要相同，就说明每一块都在同一个位置。
5.1.2 配置：31 个混合尺寸矩形
输入是《星屑旅店》的 31 个矩形，尺寸从 32 到 512 不等（图标 32/64、头像与家具 128、条幅 256×128、主视觉 512×256），完整条目见 config/ta05_atlas.json。三个图集档位 [512, 1024, 2048]，块间留白 gutter=2。选择混合尺寸而非均匀格，是为了让 shelf 与 skyline 的差异真的显出来——均匀格下两种算法退化成同一个结果。
5.1.3 S 层：shelf 与 skyline 两种确定性装箱
下面这段是 S 层脚本，读共享真源与本节配置，先复现基线，再把 31 个矩形分别用 shelf（货架：一行放满就换行）与 skyline（天际线：在分段轮廓上找「最低 y、其次最左 x」的落点）装进三档图集，逐档输出 placed/overflow/装箱率/布局摘要：
#!/usr/bin/env python3
# file: sim/ta05_pack.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/ta05_pack.py
"""图集装箱算法与装箱率（S 层，卷二 5.1）。shelf（货架）与 skyline（天际线，BL）两种确定性
装箱共用同一排序（高度降序 → 宽度降序 → id 升序）；装箱率 = placedArea*1000 // (W*H)，全整数；
布局摘要 digest 锁死「同一批输入 → 同一张布局」。先复现共享真源基线（slots=256 placed=37
permille=144），再对 config/ta05_atlas.json 的 31 个矩形跑 512/1024/2048。落盘 out/ta05_pack.json。"""
import hashlib
import json
import os
import sys
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
SPEC = os.path.join(ROOT, "config/visual_spec.json")
CFG = os.path.join(ROOT, "config/ta05_atlas.json")
OUT = os.path.join(ROOT, "out")
def atlas_slots(w: int, h: int, cell: int) -> int:
"""与 consume.py / spec.ts 同源：整数地板除。"""
return (w // cell) * (h // cell)
def shelf_uniform(cell: int, count: int, w: int, h: int):
"""与 consume.py / spec.ts 同源：均匀格货架装箱。"""
placed = min(count, (w // cell) * (h // cell))
return placed, placed * cell * cell
def _order(items):
"""确定性排序：高度降序 → 宽度降序 → id 升序（固定 tie-break，禁随机）。"""
return sorted(items, key=lambda it: (-it["h"], -it["w"], it["id"]))
def shelf_pack(items, W: int, H: int, gutter: int):
"""货架装箱。返回 (placed, overflow_ids, shelves, placed_area)。"""
x = y = shelf_h = shelves = 0
placed, overflow = [], []
for it in _order(items):
fw, fh = it["w"] + gutter, it["h"] + gutter
if fw > W or fh > H:
overflow.append(it["id"])
continue
if x > 0 and x + fw > W:
y += shelf_h
x = shelf_h = 0
if y + fh > H:
overflow.append(it["id"])
continue
if x == 0:
shelves += 1
placed.append({"id": it["id"], "x": x, "y": y, "w": it["w"], "h": it["h"]})
x += fw
shelf_h = max(shelf_h, fh)
area = sum(p["w"] * p["h"] for p in placed)
return placed, sorted(overflow), shelves, area
def _skyline_find(nodes, w: int, h: int, H: int):
"""分段天际线 (x, width, top_y) 上找「最低 y，其次最左 x」的落点。"""
best, n = None, len(nodes)
for i in range(n):
y, left, j, ok = nodes[i][2], w, i, True
while left > 0:
if j >= n:
ok = False
break
y = max(y, nodes[j][2])
if y + h > H:
ok = False
break
left -= nodes[j][1]
j += 1
if not ok:
continue
x = nodes[i][0]
if best is None or y < best[1] or (y == best[1] and x < best[0]):
best = (x, y)
return best
def _skyline_add(nodes, x: int, top: int, w: int):
"""把 [x, x+w] 段抬到 top，裁剪重叠段 + 相邻同高合并，保持覆盖 [0,W]。"""
x2, out = x + w, []
for nx, nw, ny in nodes:
nx2 = nx + nw
if nx2 <= x or nx >= x2:
out.append([nx, nw, ny])
continue
if nx < x:
out.append([nx, x - nx, ny])
if nx2 > x2:
out.append([x2, nx2 - x2, ny])
out.append([x, w, top])
out.sort(key=lambda t: t[0])
merged = []
for nx, nw, ny in out:
if merged and merged[-1][2] == ny and merged[-1][0] + merged[-1][1] == nx:
merged[-1][1] += nw
else:
merged.append([nx, nw, ny])
return merged
def skyline_pack(items, W: int, H: int, gutter: int):
"""天际线（BL）装箱。返回 (placed, overflow_ids, segments, placed_area)。"""
nodes = [[0, W, 0]]
placed, overflow = [], []
for it in _order(items):
fw, fh = it["w"] + gutter, it["h"] + gutter
if fw > W or fh > H:
overflow.append(it["id"])
continue
pos = _skyline_find(nodes, fw, fh, H)
if pos is None:
overflow.append(it["id"])
continue
x, y = pos
placed.append({"id": it["id"], "x": x, "y": y, "w": it["w"], "h": it["h"]})
nodes = _skyline_add(nodes, x, y + fh, fw)
area = sum(p["w"] * p["h"] for p in placed)
return placed, sorted(overflow), len(nodes), area
def digest(placed) -> str:
"""布局摘要：每块 id@x,y 按 id 排序后拼接的 sha256 前 16 位。"""
lines = [f"{p['id']}@{p['x']},{p['y']}" for p in sorted(placed, key=lambda p: p["id"])]
return hashlib.sha256("\n".join(lines).encode("utf-8")).hexdigest()[:16]
def main() -> int:
spec = json.load(open(SPEC, encoding="utf-8"))
cfg = json.load(open(CFG, encoding="utf-8"))
os.makedirs(OUT, exist_ok=True)
at = spec["atlas"]
b_slots = atlas_slots(at["width"], at["height"], at["cell"])
b_placed, b_area = shelf_uniform(at["cell"], at["icons"], at["width"], at["height"])
baseline = {"slots": b_slots, "placed": b_placed, "usedArea": b_area,
"permille": (b_area * 1000) // (at["width"] * at["height"])}
items, gutter = cfg["items"], cfg["gutter"]
sweeps = []
for size in cfg["atlasSizes"]:
row = {"size": size}
for name, fn in (("shelf", shelf_pack), ("skyline", skyline_pack)):
placed, overflow, shelves, area = fn(items, size, size, gutter)
row[name] = {"placed": len(placed), "overflow": len(overflow), "shelves": shelves,
"placedArea": area, "permille": (area * 1000) // (size * size),
"digest": digest(placed)}
sweeps.append(row)
summary = {"project": cfg["project"], "itemCount": len(items),
"itemArea": sum(i["w"] * i["h"] for i in items), "gutter": gutter,
"baseline": baseline, "sweeps": sweeps}
with open(os.path.join(OUT, "ta05_pack.json"), "w", encoding="utf-8") as f:
json.dump(summary, f, ensure_ascii=False, indent=2, sort_keys=True)
f.write("\n")
print(f"baseline slots={b_slots} placed={b_placed} permille={baseline['permille']}")
print(f"itemCount={len(items)} itemArea={summary['itemArea']} gutter={gutter}")
for s in sweeps:
sh, sk = s["shelf"], s["skyline"]
print(f" {s['size']}x{s['size']}: "
f"shelf placed={sh['placed']} ovf={sh['overflow']} permille={sh['permille']} {sh['digest']} | "
f"skyline placed={sk['placed']} ovf={sk['overflow']} permille={sk['permille']} {sk['digest']}")
print("wrote out/ta05_pack.json")
return 0
if __name__ == "__main__":
sys.exit(main())
实跑输出（/opt/homebrew/bin/python3 sim/ta05_pack.py）：
baseline slots=256 placed=37 permille=144
itemCount=31 itemArea=461824 gutter=2
512x512: shelf placed=7 ovf=24 permille=613 f750a70cb92a2d97 | skyline placed=18 ovf=13 permille=871 429464f05bb95e70
1024x1024: shelf placed=31 ovf=0 permille=440 89556cb35c18a016 | skyline placed=31 ovf=0 permille=440 d0a6599fff85ed3e
2048x2048: shelf placed=31 ovf=0 permille=110 3c691d215bfa6778 | skyline placed=31 ovf=0 permille=110 da1720ea742f3bbf
wrote out/ta05_pack.json
三档读出来的结论很干脆：512 档 skyline 明显赢（18 块 vs 7 块，871‰ vs 613‰），因为货架装箱遇到 512×256 这种高块会把一整行浪费掉，而天际线能贴着已有轮廓塞；1024 与 2048 档两种算法打成平手（都是 31 块全放下），此时装箱率由「矩形总面积 ÷ 图集面积」决定，与算法无关——461824×1000 // 1048576 = 440，461824×1000 // 4194304 = 110。
注意 1024 档两种算法的装箱率相同但布局摘要不同（89556cb35c18a016 vs d0a6599fff85ed3e）——放下同样多的块，不代表放在同样的位置。这正是摘要比「装了几块」更强的证据：它锁的是每一块的坐标。
5.1.4 P 层：TS 内核
下面这段是 P 层内核，把同一套确定性装箱用 TypeScript 重写一遍，并复用共享真源 core/src/sp00/spec.ts 的 atlasSlots / shelfPack 复现基线。全整数、无随机、排序键与 Python 逐字对应，因此两侧的 placed / overflow / 装箱率 / 摘要必须逐位一致：
// file: core/src/ta05/pack.ts
// tier: P
// verify: node --test 'core/test/ta05_*.test.ts'
// 卷二 5.1：图集装箱算法的 TS 侧实现。复用共享真源 core/src/sp00/spec.ts 复现基线，再实现
// 确定性 shelf / skyline 两种装箱。全整数、无随机 → 与 sim/ta05_pack.py 逐位一致。
import { atlasSlots, shelfPack } from "../sp00/spec.ts";
export type Item = { id: string; w: number; h: number };
export type Placed = { id: string; x: number; y: number; w: number; h: number };
export { atlasSlots, shelfPack };
/** 确定性排序：高度降序 → 宽度降序 → id 升序（固定 tie-break，禁随机）。 */
function order(items: Item[]): Item[] {
return [...items].sort((a, b) => b.h - a.h || b.w - a.w || (a.id < b.id ? -1 : a.id > b.id ? 1 : 0));
}
/** 货架装箱。 */
export function shelfPackVar(items: Item[], W: number, H: number, gutter: number): {
placed: Placed[]; overflow: string[]; shelves: number; placedArea: number;
} {
let x = 0, y = 0, shelfH = 0, shelves = 0;
const placed: Placed[] = [], overflow: string[] = [];
for (const it of order(items)) {
const fw = it.w + gutter, fh = it.h + gutter;
if (fw > W || fh > H) { overflow.push(it.id); continue; }
if (x > 0 && x + fw > W) { y += shelfH; x = 0; shelfH = 0; }
if (y + fh > H) { overflow.push(it.id); continue; }
if (x === 0) shelves += 1;
placed.push({ id: it.id, x, y, w: it.w, h: it.h });
x += fw;
if (fh > shelfH) shelfH = fh;
}
const placedArea = placed.reduce((s, p) => s + p.w * p.h, 0);
return { placed, overflow: overflow.sort(), shelves, placedArea };
}
type Seg = [number, number, number]; // (x, width, topY)
/** 在天际线上找「最低 y，其次最左 x」的落点。 */
function skylineFind(nodes: Seg[], w: number, h: number, H: number): [number, number] | null {
let best: [number, number] | null = null;
const n = nodes.length;
for (let i = 0; i < n; i += 1) {
let y = nodes[i][2], left = w, j = i, ok = true;
while (left > 0) {
if (j >= n) { ok = false; break; }
if (nodes[j][2] > y) y = nodes[j][2];
if (y + h > H) { ok = false; break; }
left -= nodes[j][1];
j += 1;
}
if (!ok) continue;
const x = nodes[i][0];
if (best === null || y < best[1] || (y === best[1] && x < best[0])) best = [x, y];
}
return best;
}
/** 把 [x, x+w] 段抬到 top，裁剪重叠段 + 相邻同高合并。 */
function skylineAdd(nodes: Seg[], x: number, top: number, w: number): Seg[] {
const x2 = x + w;
const out: Seg[] = [];
for (const [nx, nw, ny] of nodes) {
const nx2 = nx + nw;
if (nx2 <= x || nx >= x2) { out.push([nx, nw, ny]); continue; }
if (nx < x) out.push([nx, x - nx, ny]);
if (nx2 > x2) out.push([x2, nx2 - x2, ny]);
}
out.push([x, w, top]);
out.sort((a, b) => a[0] - b[0]);
const merged: Seg[] = [];
for (const seg of out) {
const last = merged[merged.length - 1];
if (last && last[2] === seg[2] && last[0] + last[1] === seg[0]) last[1] += seg[1];
else merged.push([seg[0], seg[1], seg[2]]);
}
return merged;
}
/** 天际线（BL）装箱。 */
export function skylinePack(items: Item[], W: number, H: number, gutter: number): {
placed: Placed[]; overflow: string[]; segments: number; placedArea: number;
} {
let nodes: Seg[] = [[0, W, 0]];
const placed: Placed[] = [], overflow: string[] = [];
for (const it of order(items)) {
const fw = it.w + gutter, fh = it.h + gutter;
if (fw > W || fh > H) { overflow.push(it.id); continue; }
const pos = skylineFind(nodes, fw, fh, H);
if (pos === null) { overflow.push(it.id); continue; }
const [x, y] = pos;
placed.push({ id: it.id, x, y, w: it.w, h: it.h });
nodes = skylineAdd(nodes, x, y + fh, fw);
}
const placedArea = placed.reduce((s, p) => s + p.w * p.h, 0);
return { placed, overflow: overflow.sort(), segments: nodes.length, placedArea };
}
/** 装箱率千分比（整数地板除）。 */
export function permille(placedArea: number, size: number): number {
return Math.floor((placedArea * 1000) / (size * size));
}
5.1.5 P 层实跑与跨语言摘要
P 层测试读的是 S 层落盘的 out/ta05_pack.json（不是同一份源码），逐档断言 placed / overflow / 装箱率 / 摘要四项相等，并带一个确定性负例（把输入数组倒序后布局摘要必须不变）：
pack digest = 9544cf9987154167
✔ 复现共享真源基线：slots=256 placed=37 permille=144（逐位一致）
✔ 跨语言：shelf / skyline 的 placed/overflow/permille/digest 逐位一致
✔ 负例：排序锁死 → 打乱输入顺序，布局摘要必须不变
ℹ tests 3
ℹ pass 3
ℹ fail 0
pack digest = 9544cf9987154167 是测试自己按 size:shelfPlaced:skylinePlaced:skylinePermille 三档拼起来算的跨语言摘要，任何一侧的装箱结果变了一位它都会变。三档的摘要（f750a70c… / 89556cb3… / 3c691d21… 等）两侧完全相同，说明整数类逐位一致。
5.1.6 三条边界
- skyline 不是无脑更优。它只在「高矮悬殊、档位偏紧」时赢（512 档 18 vs 7）；一旦图集够大，两者都全放下，装箱率就退化成面积比。选算法的依据是目标档位下的溢出块数，不是「哪个名字更高级」。
- 装箱率不是越高越好。1024 档 440‰ 看起来「浪费了 56%」，但那 56% 是必须留的边角与 gutter——强行塞满会牺牲未来的可增补空间，反而逼出一次全量重打包。装箱率是决策依据，不是 KPI。
- X 层：真实的图集最终要由引擎/工具链按引擎特定的图集格式（含 padding、压缩、通道打包）烘出纹理，这一步需真实环境（DCC / 引擎 / 打包工具），命令行不可复现；本节只做几何装箱与整数账，不生成纹理。
一句话总结：装箱的正确性有两个条件——装得进去，以及每次都装在同一个地方。 前者是几何，后者是确定性，本节把两者都变成了可跑的整数断言。
阅读导航：上一节：4.3 资源清理与不可达资产 · 下一节：5.2 mip 链与压缩格式字节账 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。