Voxel Data Structure (Runtime)
本文介绍体素系统在运行时的各种数据结构实现方式，包括它们的优缺点和适用场景。
| Name | Large Worlds | Fast Edits | Fast Ray Tracing |
|---|---|---|---|
| Flat Grid | ✅ | ||
| Hierarchy Grid | ✅ | ✅ | |
| Octree/SVO/DAG | ✅ | 🆗 | |
| Brickmap | ✅ | ✅ | |
| SDF | ✅ |
I. Flat Grid (big array)
扁平网格是最简单直观的体素数据结构实现方式。它将整个体素空间表示为一个数组。
相比于语言内的三维数组，我们推荐用1维数组 因为你可以快速线性遍历(简单 缓存友好) 以及多维映射方式也由你决定 而不受语言决定 并且通用性/可移植性更好 比如把他传到GPU 他就是一块内存。另外你也可以只用一个整数表示某个坐标 而无需xyz三个
// 一维数组表示三维体素空间
let voxel_grid = [Voxel; LEN_X * LEN_Y * LEN_Z];
// 将三维坐标(x,y,z)映射到一维索引
let local_idx = x + z * LEN_X + y * LEN_X * LEN_Y;
let voxel = voxel_grid[local_idx];优点
- 实现简单直观
- 随机访问性能极佳（O(1)）
- 内存布局连续，缓存友好
- 适合GPU并行处理
缺点
- 内存占用巨大（O(n³)），限制了可加载的世界大小
- 大量空气块/相同块没被省略，造成内存浪费
- 射线追踪需要遍历所有体素
适用场景
- 小规模体素场景
- 需要频繁随机访问的场景
- 对内存效率要求不高的原型开发
- 需要简单实现的场景
区块系统是一种将世界分割成固定大小块的数据结构，是现代体素游戏中最常用的实现方式。它解决了扁平网格无法处理大世界的问题，通过动态加载和卸载区块来实现无限世界。
1. 垂直区块 (Vertical Chunk)
垂直区块是一种特殊的区块系统，其中区块在XZ平面上是正方形，但在Y轴（垂直方向）上延伸整个世界高度。典型的尺寸是16x256x16。
注：Minecraft是垂直区块系统的典型代表。在1.20版本之前使用16x256x16的区块大小（之后改为384格高，顶部和底部各增加64格）。不过Minecraft内部仍然使用16³的"Section"结构来存储和渲染，空区块不会占用内存。
优点
垂直连贯性
- 光照计算准确：顶部遮挡物（如屋顶）的阴影可以正确投射到下方
- 地形生成优化：可以准确判断地表位置，便于生物群系生成
- 物理模拟流畅：玩家从高处落下时不会出现加载卡顿
内存管理简单
- 区块大小固定，便于内存分配和回收
- 空区块可以完全跳过，节省内存
缺点
扩展性受限
- Y轴高度固定，难以支持超大地形变化
- 无法实现真正的无限高度世界
性能开销
- 横向移动时需要加载大量垂直区块
- 高空区域即使没有内容也会占用内存
灵活性不足
- 难以实现动态LOD
- 不支持不同区域使用不同的区块大小
2. 方形区块 (Cubical Chunk)
方形区块在XYZ三个维度上大小相等，通常使用16³或32³的尺寸。这种设计让Y轴也能像XZ轴一样实现"无限"扩展。
优点
真正的无限世界
- 支持任意高度的地形
- 可以实现多层世界（如天堂、地狱等）
灵活的内存管理
- 按需加载：只加载视野范围内的区块
- 支持动态LOD：远处区块可以使用低精度表示
更好的性能
- 横向移动时只需加载必要的区块
- 支持更细粒度的内存控制
垂直连贯性的解决方案
LOD系统
- 使用多级LOD缓存远处区块
- 动态调整区块精度
区块引用系统
- 维护相邻区块的快速访问指针
- 实现区块间的快速遍历
预加载机制
- 根据玩家移动方向预加载区块
- 使用后台线程进行区块生成
区块尺寸选择
区块尺寸通常选择2的幂次方（如8、16、32），原因如下：
性能优化
- 可以使用位运算加速计算
- 便于实现区块边界对齐
内存对齐
- 有利于CPU缓存命中
- 便于实现内存池管理
区块位置计算优化
以16³区块为例，可以使用位运算优化计算：
// 乘16
fn mul16(x: i32) -> i32 { x << 4 }
// 除16
fn div16(x: i32) -> i32 { x >> 4 }
// 模16
fn mod16(x: i32) -> i32 { x & 15 }
// 向下取整到16的倍数
fn floor16(x: i32) -> i32 { x & (!15) }注意：在现代计算机中，这些优化可能不是性能瓶颈，实际应用中应优先考虑代码可读性。
III. 稀疏八叉树 (Sparse Voxel Octree, SVO)
稀疏八叉树是一种层次化的数据结构，通过递归地将空间分割成八个子空间来组织体素数据。这种结构特别适合处理稀疏的体素数据。
优点
内存效率
- 只存储非空体素，节省内存空间
- 支持不同分辨率的体素混合存储
无限细节
- 理论上支持任意精度的体素细节
- 适合存储复杂的几何形状
射线追踪优化
- 层次结构加速射线相交测试
- 支持高效的遮挡剔除
CSG操作
- 便于实现布尔运算
- 支持复杂的体素编辑操作
缺点
访问效率
- 随机访问需要遍历树结构
- 邻居查找相对复杂
内存开销
- 指针结构占用额外内存
- 可能导致缓存不友好
动态更新
- 修改操作可能触发树的重构
- 不适合频繁更新的场景
适用场景
- 静态场景存储
- 需要高精度细节的场景
- 光线追踪渲染
- 复杂的体素编辑操作
技术细节
SVO主要适用于可变大小的体素系统，而不是Minecraft这样固定大小的体素系统。虽然也可以用于固定大小体素，但会面临一些挑战：
- 特殊方块处理：如栅栏、草等非完整方块
- 动态内容：实体、粒子效果等难以集成
- 区块大小限制：在小区块内使用SVO可能无法充分发挥其优势
在GPU端使用SVO时，主要用于光线追踪和全局光照计算，而不是基础几何渲染。对于基础渲染，传统的网格光栅化可能更有效率。
IV. 距离场 (Signed Distance Field, SDF)
距离场是一种表示几何形状的数学方法，通过定义空间中每个点到最近表面的距离来表示形状。在体素系统中，SDF提供了一种连续的空间表示方式。
优点
连续表示
- 支持平滑的几何形状
- 便于实现变形和动画
高效渲染
- 支持光线步进渲染
- 适合实时渲染应用
CSG操作
- 支持复杂的布尔运算
- 便于实现形状组合
内存效率
- 可以压缩存储
- 支持多分辨率表示
缺点
精度限制
- 离散化可能损失细节
- 不适合表示复杂纹理
计算开销
- 距离场计算可能复杂
- 实时更新成本高
应用场景
- 程序化地形生成
- 实时体素编辑
- 物理模拟
- 特殊效果渲染
注：VoxelFarm使用SVO<SDF>的组合，实现了无限细节、远距离快速加载和CSG操作等功能。