Greedy Meshing: 体素贪心网格化算法

Greedy Meshing 是体素游戏（Minecraft 类）的事实标准网格化算法，将共面且同材质的相邻体素面合并为最大可能的矩形，从而减少渲染的三角形数量。

算法原理

核心思想来自 Mikola Lysenko 在 0fps.net 的经典文章。算法按以下顺序扫描和合并：

顺序：从上→下，左→右
每个未被覆盖的面 → 取最宽可能的 quad → 尽量向上延伸高度

Jason Gedge 的动画视觉化展示了这一过程：在每个未被覆盖的位置，算法会尝试水平扩展宽度，然后在该宽度基础上垂直扩展高度，直到不能再合并为止。

性能对比

算法	速度	输出质量	典型场景
Naive	极快	最差（6面/体素）	< 1000 体素的编辑器预览
Face Culling	很快	一般（仅表面面）	实时更新频繁的场景
Greedy	~3× 耗时	最优（球形数据减面 67%）	体素地形、Minecraft 类游戏
Marching Cubes	中等	平滑表面（大量小三角）	医疗可视化、洞穴地形

block-mesh 库的实测数据：

• visible_block_faces：单核 ~4000万 quad/秒（2.5 GHz Intel i7）
• greedy_quads：约 3× 耗时，但输出 quad 数量约为球形数据的 1/3

Rust 实现

block-mesh 库

bonsairobo/block-mesh-rs 是体素网格化的事实标准库，被 126+ downstream 仓库使用。

核心 trait 系统：

• Voxel — 定义可见性（Empty / Opaque / Translucent）
• MergeVoxel — 定义合并等价性（材质、颜色等）
• ndshape::ConstShape — 编译时 3D 数组形状，支持 padding

典型代码模式（含 1-voxel boundary padding）：

use block_mesh::ndshape::{ConstShape, ConstShape3u32};
use block_mesh::{greedy_quads, GreedyQuadsBuffer, MergeVoxel, Voxel, VoxelVisibility, RIGHT_HANDED_Y_UP_CONFIG};
 
type ChunkShape = ConstShape3u32<18, 18, 18>; // 16³ + 1 padding each side
let mut buffer = GreedyQuadsBuffer::new(voxels.len());
 
greedy_quads(
    &voxels, &ChunkShape {},
    [0; 3], [17; 3],           // 迭代范围（排除 padding）
    &RIGHT_HANDED_Y_UP_CONFIG.faces,
    &mut buffer
);

bevy_voxel_world 的内部实现

bevy_voxel_world 使用类似 greedy 的面合并策略，但在 Bevy Task Pool 中并行执行，支持运行时增量更新而无需重新生成整个 mesh。

关键细节

与 Ambient Occlusion 的兼容性

合并面时需要考虑 AO 计算。如果两个相邻体素面的顶点 AO 值不同，它们不能被合并。这会降低 greedy 的有效性。

Binary Greedy Meshing（优化变种）

block-mesh-bgm 提供了基于二进制掩码的快速 greedy mesher，通过 bitwise 测试替换逐体素比较，适合高性能场景。

相关页面

• voxel-rendering — 体素渲染概念与技术谱系总览
• block-mesh — block-mesh crate 详解
• bevy_voxel_world — Bevy 全功能体素地形插件
• arpg-terrain-design — ARPG 地形设计（含体素地形章节）