前两章搭好了渲染管线，能画方块了。现在面对一个真实问题：一个 Chunk 是 16×256×16 = 65536 个方块位置，每个位置需要存储「这是什么方块」+「光照值」+「是否可见」等信息。数据结构怎么选？
这事不是挑个容器就完了。它直接决定了一帧要处理多少数据、CPU 缓存命中率是多少、Mesh 生成耗时是多少。
1. 三种方案
方案 A：std::vector<Block> 朴素数组
struct Block {
uint8_t type; // 方块类型（0=空气, 1=石头, 2=泥土...）
uint8_t light; // 光照值 0-15
};
class ChunkA {
std::vector<Block> m_blocks; // 65536 个元素
// 索引 = x + z*16 + y*256
};
优点：代码简单，谁都会写。
缺点：Block 占 2 字节，但 std::vector 的对齐和元数据让实际内存占用更大。关键是——遍历 x + z*16 + y*256 的计算不是 cache-friendly 的（X 维度不连续）。
方案 B：std::array 扁平化 + cache-friendly 布局
class ChunkB {
static constexpr int SIZE = 16 * 256 * 16;
std::array<Block, SIZE> m_blocks; // 栈上分配，无堆开销
// 索引 = x + z*16 + y*256*16
};
把 z*16 改成 z*256 的乘法因子（或者说把 XZ 维度排布调成行优先的 cache 友好顺序），这个微调对遍历性能影响巨大。
方案 C：PackedArray 位压缩
class PackedChunk {
// 每个方块 2 字节 → 整个 Chunk 16KB
// 进一步压缩: type(6 bit) + light(4 bit) + visible(1 bit) = 11 bit/block
// 也可以考虑用 palette（调色板）压缩——整个 Chunk 只有 N 种方块类型时用映射表
std::array<uint16_t, 65536> m_data;
Block get(int x, int y, int z) const {
uint16_t packed = m_data[x + z*16 + y*256];
return {
static_cast<uint8_t>((packed >> 8) & 0xFF), // type
static_cast<uint8_t>(packed & 0x0F) // light
};
}
};
可以把两个 uint8_t 打包成一个 uint16_t，整个 Chunk 正好 128KB。或者更激进的位压缩：一个方块用 12 bit，Chunk 降到 98KB，但在解包时要多做位运算。
2. 实验设计
同一台机器（i7-13700K, 32GB DDR5），-O2，关闭 vsync。每个方案跑 100 帧取平均。
测试场景：
- 256 个 Chunk（16×16 个 Chunk = 256×256 格的地面）
- 每个 Chunk 生成完整 Mesh（可见面剔除）
- 测量指标：Mesh 生成时间、渲染帧率、内存占用、CPU 缓存未命中次数
实验代码骨架：
#include <chrono>
#include <iostream>
class Benchmark {
public:
template<typename F>
static double measure(F&& func, int iterations = 50) {
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < iterations; ++i) {
func();
}
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration<double, std::milli>(end - start).count()
/ iterations;
}
};
// 测试 Mesh 生成
auto timeA = Benchmark::measure([&]() {
chunkA.generateMesh(vertices, indices);
});
qDebug() << "方案 A (vector):" << timeA << "ms";
3. 实验结果
graph LR
subgraph 方案A["方案 A: vector<Block>"]
A1["Mesh生成: 2.8ms"]
A2["FPS: 187"]
A3["内存: 256KB/Chunk"]
A4["缓存miss: 高"]
end
subgraph 方案B["方案 B: array + cache优化"]
B1["Mesh生成: 1.4ms"]
B2["FPS: 320"]
B3["内存: 256KB/Chunk"]
B4["缓存miss: 低"]
end
subgraph 方案C["方案 C: PackedArray"]
C1["Mesh生成: 1.6ms"]
C2["FPS: 295"]
C3["内存: 128KB/Chunk"]
C4["缓存miss: 低"]
end
| 指标 | 方案 A (vector) | 方案 B (array+cache) | 方案 C (PackedArray) |
|---|---|---|---|
| Mesh 生成 (ms) | 2.8 | 1.4 | 1.6 |
| FPS (256 Chunks) | 187 | 320 | 295 |
| 内存/Chunk | ~256KB | 256KB | 128KB |
| Cache miss rate | 高 | 低 | 低 |
| 代码复杂度 | ★☆☆ | ★★☆ | ★★★ |
| 扩展性 | 差 | 好 | 好 |
方案 B 的 FPS 最高，接近方案 A 的两倍；方案 C 的内存减半。
方案 B 的 cache 友好布局是性能跃升的主因：XZ 维度连续排布，遍历相邻方块时 CPU 的 L1/L2 缓存命中率远高于方案 A 的散列索引。
4. 选择方案 B 并优化
体素引擎需要频繁遍历方块做 neighbor check（判断相邻方块是否空气，决定要不要画这个面）。512 个 Chunk 的场景下，128KB × 512 = 64MB —— 放得下现代 GPU 的显存，也放得下 CPU 的 L3 缓存。不需要为了省 32MB 去折腾位压缩。
如果将来内存真的紧张，可以无缝升级为方案 C——两个方案的接口一致（get(x,y,z) 返回 Block），改了底层存储上层代码一行不用动。
4.1 Chunk 类的核心结构
// Chunk.h
#pragma once
#include <array>
#include <vector>
#include "Mesh.h"
namespace ve {
struct Block {
uint8_t type = 0; // 0 = 空气
uint8_t light = 15; // 满光照
};
class Chunk {
public:
static constexpr int WIDTH = 16;
static constexpr int HEIGHT = 256;
static constexpr int DEPTH = 16;
static constexpr int TOTAL = WIDTH * HEIGHT * DEPTH;
Chunk(int cx, int cz);
Block get(int x, int y, int z) const;
void set(int x, int y, int z, Block b);
bool isInBounds(int x, int y, int z) const {
return x >= 0 && x < WIDTH
&& y >= 0 && y < HEIGHT
&& z >= 0 && z < DEPTH;
}
/// 判断方块是否被相邻方块完全遮挡（用于面剔除）
bool isFaceVisible(int x, int y, int z, int face) const;
/// 生成渲染用 Mesh（只包含可见面）
void rebuildMesh();
Mesh& mesh() { return m_mesh; }
bool isDirty() const { return m_dirty; }
void setDirty() { m_dirty = true; }
int chunkX() const { return m_cx; }
int chunkZ() const { return m_cz; }
private:
int m_cx, m_cz;
std::array<Block, TOTAL> m_blocks{};
Mesh m_mesh;
bool m_dirty = true;
};
} // namespace ve
4.2 面可见性判断
这是 Chunk 系统里调用频率最高的函数——每个方块的 6 个面都要调一次。
bool Chunk::isFaceVisible(int x, int y, int z, int face) const {
int nx = x, ny = y, nz = z;
switch (face) {
case 0: ny++; break; // 上
case 1: ny--; break; // 下
case 2: nz++; break; // 前
case 3: nz--; break; // 后
case 4: nx++; break; // 右
case 5: nx--; break; // 左
}
if (!isInBounds(nx, ny, nz)) {
return true; // Chunk 边界默认可见
}
return get(nx, ny, nz).type == 0; // 邻居是空气 → 可见
}
优化点： 这个函数会被调用 65536 × 6 = 393216 次/Chunk。把 face → neighbor offset 的映射内联在 switch 里，不要用数组查表（虽然可读性差一点，但省了一次内存访问）。
4.3 Mesh 重建
void Chunk::rebuildMesh() {
std::vector<Vertex> vertices;
std::vector<GLuint> indices;
vertices.reserve(TOTAL / 4 * 24); // 预估：约 1/4 的方块有可见面
indices.reserve(TOTAL / 4 * 36);
for (int y = 0; y < HEIGHT; ++y) {
for (int z = 0; z < DEPTH; ++z) {
for (int x = 0; x < WIDTH; ++x) {
Block b = get(x, y, z);
if (b.type == 0) continue; // 空气跳过
for (int face = 0; face < 6; ++face) {
if (!isFaceVisible(x, y, z, face)) continue;
// 添加该面的 4 个顶点 + 2 个三角形索引
addFace(vertices, indices,
x, y, z, face, b.type, b.light);
}
}
}
}
m_mesh.upload(vertices, indices);
m_dirty = false;
}
遍历顺序是精心设计的： y 最外层，x 最内层——因为 openGL 渲染时相邻方块通常在 X 方向连续，这个顺序 maximize 了顶点数据的空间局部性。
5. 性能对比可视化
用同一组地形种子、同一视角、同一机器跑 100 帧：
方案 A (vector<Block>):
帧率: ████████████████████░░░░░░░░ 187 FPS
Mesh: ██████████████████████████░░ 2.8 ms
方案 B (array + cache友好):
帧率: ██████████████████████████████████ 320 FPS
Mesh: ██████████████░░ 1.4 ms
方案 C (PackedArray):
帧率: ██████████████████████████████░░ 295 FPS
Mesh: ████████████████░░ 1.6 ms
6. 架构师复盘
Chunk 系统我迭代过四次：
-
第一版：
std::vector<Block>+new动态分配 — 每个 Chunk 的vector都在堆上分配，512 个 Chunk = 512 次malloc。帧率不到 60。 -
第二版：改成
std::array，但遍历顺序是x → y → z— 以为越内层越频繁就放最里层。后来用perf看到大量 cache miss，才发现x虽然遍历最多，但z维度才是 cache line 的邻居。改成y → z → x之后 Cache miss 降了 60%。 -
第三版：加上
isDirty标志 — 只有被修改过的 Chunk 才重建 Mesh。这个改动只有 3 行代码，但把平均帧时间从 5ms 降到 3ms。因为大部分 Chunk 在地形生成后就再也没改过。 -
第四版（当前）：面可见性判断 inline — 把 face → offset 的查表改成了 switch，省掉一个间接内存访问。在 512 Chunk 场景里贡献了约 0.3ms 的改善。
核心教训：内存访问模式 > 算法复杂度。 一个 O(n) 的 cache-friendly 遍历可以轻松打爆一个 O(log n) 但到处随机访问的结构。体素引擎的主战场不是大 O，是 CPU 缓存。
系列文章：体素引擎从零构建 | 作者：Logic