use bevy::asset::RenderAssetUsages;
use bevy::mesh::{Indices, Mesh, MeshVertexAttribute, PrimitiveTopology, VertexFormat};
use crate::chunk::{CHUNK_SIZE, Chunk, VOXEL_SIZE};
use crate::voxel::VoxelType;
pub const ATTRIBUTE_TEXTURE_LAYER: MeshVertexAttribute =
MeshVertexAttribute::new("Vertex_TextureLayer", 988540919, VertexFormat::Uint32);
pub(crate) struct FaceDir {
pub axis: usize,
pub positive: bool,
pub u_axis: usize,
pub v_axis: usize,
normal: [f32; 3],
}
pub(crate) const FACE_DIRS: [FaceDir; 6] = [
FaceDir {
axis: 1,
positive: true,
u_axis: 0,
v_axis: 2,
normal: [0.0, 1.0, 0.0],
},
FaceDir {
axis: 1,
positive: false,
u_axis: 0,
v_axis: 2,
normal: [0.0, -1.0, 0.0],
},
FaceDir {
axis: 0,
positive: true,
u_axis: 2,
v_axis: 1,
normal: [1.0, 0.0, 0.0],
},
FaceDir {
axis: 0,
positive: false,
u_axis: 2,
v_axis: 1,
normal: [-1.0, 0.0, 0.0],
},
FaceDir {
axis: 2,
positive: true,
u_axis: 0,
v_axis: 1,
normal: [0.0, 0.0, 1.0],
},
FaceDir {
axis: 2,
positive: false,
u_axis: 0,
v_axis: 1,
normal: [0.0, 0.0, -1.0],
},
];
#[inline]
pub(crate) fn super_voxel<V: VoxelType>(
chunk: &Chunk<V>,
sx: usize,
sy: usize,
sz: usize,
step: usize,
) -> V {
let mut first_visible = V::air();
for dx in 0..step {
for dy in 0..step {
for dz in 0..step {
let x = sx + dx;
let y = sy + dy;
let z = sz + dz;
if x < CHUNK_SIZE && y < CHUNK_SIZE && z < CHUNK_SIZE {
let v = chunk.get(x, y, z);
if v.is_solid() {
return v; }
if first_visible.color()[3] == 0.0 && v.color()[3] > 0.0 {
first_visible = v; }
}
}
}
}
first_visible
}
pub fn generate_chunk_mesh<V: VoxelType>(chunk: &Chunk<V>, step: usize) -> Mesh {
crate::profile_span!("voxel::mesh::greedy");
build_mesh(chunk, step, &default_face_visible::<V>)
}
#[inline]
fn default_face_visible<V: VoxelType>(
chunk: &Chunk<V>,
x: usize,
y: usize,
z: usize,
face: &FaceDir,
step: usize,
) -> bool {
let (nx, ny, nz) = neighbor_coords(x, y, z, face, step);
if nx >= CHUNK_SIZE || ny >= CHUNK_SIZE || nz >= CHUNK_SIZE {
return true;
}
let neighbor = super_voxel(chunk, nx, ny, nz, step);
!neighbor.is_solid() || neighbor.color()[3] < 1.0
}
#[inline]
fn neighbor_coords(
x: usize,
y: usize,
z: usize,
face: &FaceDir,
step: usize,
) -> (usize, usize, usize) {
let mut result = [x, y, z];
if face.positive {
result[face.axis] = result[face.axis].wrapping_add(step);
} else {
result[face.axis] = result[face.axis].wrapping_sub(step);
}
(result[0], result[1], result[2])
}
#[allow(clippy::type_complexity)]
pub(crate) fn build_mesh<V: VoxelType>(
chunk: &Chunk<V>,
step: usize,
face_visible: &dyn Fn(&Chunk<V>, usize, usize, usize, &FaceDir, usize) -> bool,
) -> Mesh {
let size = CHUNK_SIZE / step;
let mut positions: Vec<[f32; 3]> = Vec::new();
let mut normals: Vec<[f32; 3]> = Vec::new();
let mut uvs: Vec<[f32; 2]> = Vec::new();
let mut colors: Vec<[f32; 4]> = Vec::new();
let mut texture_layers: Vec<u32> = Vec::new();
let mut indices: Vec<u32> = Vec::new();
let mut mask: Vec<Option<(V, u8)>> = vec![None; size * size];
for (face_index, face) in FACE_DIRS.iter().enumerate() {
for d in 0..size {
build_mask(chunk, face, d, step, size, &mut mask, face_visible);
greedy_merge(
chunk,
&mut mask,
size,
face,
face_index,
d,
step,
&mut positions,
&mut normals,
&mut uvs,
&mut colors,
&mut texture_layers,
&mut indices,
);
}
}
Mesh::new(
PrimitiveTopology::TriangleList,
RenderAssetUsages::default(),
)
.with_inserted_attribute(Mesh::ATTRIBUTE_POSITION, positions)
.with_inserted_attribute(Mesh::ATTRIBUTE_NORMAL, normals)
.with_inserted_attribute(Mesh::ATTRIBUTE_UV_0, uvs)
.with_inserted_attribute(Mesh::ATTRIBUTE_COLOR, colors)
.with_inserted_attribute(ATTRIBUTE_TEXTURE_LAYER, texture_layers)
.with_inserted_indices(Indices::U32(indices))
}
#[allow(clippy::type_complexity)]
#[inline]
fn build_mask<V: VoxelType>(
chunk: &Chunk<V>,
face: &FaceDir,
d: usize,
step: usize,
size: usize,
mask: &mut [Option<(V, u8)>],
face_visible: &dyn Fn(&Chunk<V>, usize, usize, usize, &FaceDir, usize) -> bool,
) {
for v in 0..size {
for u in 0..size {
let (x, y, z) = slice_to_chunk(face, d * step, u * step, v * step);
let voxel = super_voxel(chunk, x, y, z, step);
let has_color = voxel.color()[3] > 0.0;
if has_color && face_visible(chunk, x, y, z, face, step) {
let state = chunk.get_state(x, y, z);
mask[v * size + u] = Some((voxel, state));
} else {
mask[v * size + u] = None;
}
}
}
}
#[inline]
fn slice_to_chunk(face: &FaceDir, d: usize, u: usize, v: usize) -> (usize, usize, usize) {
let mut coords = [0usize; 3];
coords[face.axis] = d;
coords[face.u_axis] = u;
coords[face.v_axis] = v;
(coords[0], coords[1], coords[2])
}
#[allow(clippy::too_many_arguments)] fn greedy_merge<V: VoxelType>(
chunk: &Chunk<V>,
mask: &mut [Option<(V, u8)>],
size: usize,
face: &FaceDir,
face_index: usize,
d: usize,
step: usize,
positions: &mut Vec<[f32; 3]>,
normals: &mut Vec<[f32; 3]>,
uvs: &mut Vec<[f32; 2]>,
colors: &mut Vec<[f32; 4]>,
texture_layers: &mut Vec<u32>,
indices: &mut Vec<u32>,
) {
for v in 0..size {
let mut u = 0;
while u < size {
let (voxel, state) = match mask[v * size + u] {
Some(entry) => entry,
None => {
u += 1;
continue;
}
};
let mut width = 1;
while u + width < size && mask[v * size + u + width] == Some((voxel, state)) {
width += 1;
}
let mut height = 1;
'outer: while v + height < size {
for du in 0..width {
if mask[(v + height) * size + u + du] != Some((voxel, state)) {
break 'outer;
}
}
height += 1;
}
for dv in 0..height {
for du in 0..width {
mask[(v + dv) * size + u + du] = None;
}
}
emit_quad(
chunk,
face,
face_index,
d,
u,
v,
width,
height,
step,
voxel,
state,
positions,
normals,
uvs,
colors,
texture_layers,
indices,
);
u += width;
}
}
}
#[inline]
fn ao_neighbor_solid<V: VoxelType>(chunk: &Chunk<V>, coords: [usize; 3]) -> bool {
if coords[0] >= CHUNK_SIZE || coords[1] >= CHUNK_SIZE || coords[2] >= CHUNK_SIZE {
return false;
}
chunk.get(coords[0], coords[1], coords[2]).is_solid()
}
#[inline]
fn compute_ao(side1: bool, side2: bool, corner: bool) -> f32 {
match side1 as u8 + side2 as u8 + corner as u8 {
0 => 1.0,
1 => 0.8,
2 => 0.6,
_ => 0.4,
}
}
#[inline]
fn vertex_ao<V: VoxelType>(
chunk: &Chunk<V>,
face: &FaceDir,
d_voxel: usize,
cu_voxel: usize,
cv_voxel: usize,
) -> f32 {
let mut s1 = [0usize; 3];
s1[face.axis] = d_voxel;
s1[face.u_axis] = cu_voxel.wrapping_sub(1);
s1[face.v_axis] = cv_voxel;
let side1 = ao_neighbor_solid(chunk, s1);
let mut s2 = [0usize; 3];
s2[face.axis] = d_voxel;
s2[face.u_axis] = cu_voxel;
s2[face.v_axis] = cv_voxel.wrapping_sub(1);
let side2 = ao_neighbor_solid(chunk, s2);
let mut sc = [0usize; 3];
sc[face.axis] = d_voxel;
sc[face.u_axis] = cu_voxel.wrapping_sub(1);
sc[face.v_axis] = cv_voxel.wrapping_sub(1);
let corner = ao_neighbor_solid(chunk, sc);
compute_ao(side1, side2, corner)
}
#[allow(clippy::too_many_arguments)] #[inline]
fn emit_quad<V: VoxelType>(
chunk: &Chunk<V>,
face: &FaceDir,
face_index: usize,
d: usize,
u: usize,
v: usize,
width: usize,
height: usize,
step: usize,
voxel: V,
state: u8,
positions: &mut Vec<[f32; 3]>,
normals: &mut Vec<[f32; 3]>,
uvs: &mut Vec<[f32; 2]>,
colors: &mut Vec<[f32; 4]>,
texture_layers: &mut Vec<u32>,
indices: &mut Vec<u32>,
) {
let s = step as f32 * VOXEL_SIZE;
let d_pos = if face.positive {
(d as f32 + 1.0) * s
} else {
d as f32 * s
};
let ao_depth: usize = if face.positive {
(d + 1) * step
} else {
d * step.wrapping_sub(1) };
let ao_depth = if !face.positive && d == 0 {
usize::MAX } else {
ao_depth
};
let u_start = u as f32 * s;
let v_start = v as f32 * s;
let u_end = (u + width) as f32 * s;
let v_end = (v + height) as f32 * s;
let ao_v0 = vertex_ao(chunk, face, ao_depth, u * step, v * step);
let ao_v1 = vertex_ao(chunk, face, ao_depth, (u + width) * step, v * step);
let ao_v2 = vertex_ao(
chunk,
face,
ao_depth,
(u + width) * step,
(v + height) * step,
);
let ao_v3 = vertex_ao(chunk, face, ao_depth, u * step, (v + height) * step);
let corners = [
(u_start, v_start, ao_v0),
(u_end, v_start, ao_v1),
(u_end, v_end, ao_v2),
(u_start, v_end, ao_v3),
];
let base_idx = positions.len() as u32;
let srgb = voxel.color();
let to_linear = |c: f32| -> f32 {
if c <= 0.04045 {
c / 12.92
} else {
((c + 0.055) / 1.055).powf(2.4)
}
};
let base_color = [
to_linear(srgb[0]),
to_linear(srgb[1]),
to_linear(srgb[2]),
srgb[3],
];
let layer = voxel.texture_layer_for_state(face_index, state);
for &(cu, cv, ao) in &corners {
let mut pos = [0.0f32; 3];
pos[face.axis] = d_pos;
pos[face.u_axis] = cu;
pos[face.v_axis] = cv;
positions.push(pos);
normals.push(face.normal);
colors.push([
base_color[0] * ao,
base_color[1] * ao,
base_color[2] * ao,
base_color[3],
]);
texture_layers.push(layer);
}
uvs.push([0.0, 0.0]);
uvs.push([1.0, 0.0]);
uvs.push([1.0, 1.0]);
uvs.push([0.0, 1.0]);
let ao_flip = ao_v0 + ao_v2 < ao_v1 + ao_v3;
let ccw = face.positive != (face.axis == 2);
match (ccw, ao_flip) {
(true, false) => {
indices.push(base_idx);
indices.push(base_idx + 2);
indices.push(base_idx + 1);
indices.push(base_idx);
indices.push(base_idx + 3);
indices.push(base_idx + 2);
}
(true, true) => {
indices.push(base_idx);
indices.push(base_idx + 3);
indices.push(base_idx + 1);
indices.push(base_idx + 1);
indices.push(base_idx + 3);
indices.push(base_idx + 2);
}
(false, false) => {
indices.push(base_idx);
indices.push(base_idx + 1);
indices.push(base_idx + 2);
indices.push(base_idx);
indices.push(base_idx + 2);
indices.push(base_idx + 3);
}
(false, true) => {
indices.push(base_idx);
indices.push(base_idx + 1);
indices.push(base_idx + 3);
indices.push(base_idx + 1);
indices.push(base_idx + 2);
indices.push(base_idx + 3);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::voxel::DefaultVoxel;
use bevy::mesh::VertexAttributeValues;
fn vertex_count(mesh: &Mesh) -> usize {
match mesh.attribute(Mesh::ATTRIBUTE_POSITION).expect("positions") {
VertexAttributeValues::Float32x3(v) => v.len(),
_ => panic!("unexpected attribute type"),
}
}
fn index_count(mesh: &Mesh) -> usize {
match mesh.indices().expect("indices") {
Indices::U32(idx) => idx.len(),
_ => panic!("expected U32 indices"),
}
}
#[test]
fn empty_chunk_produces_empty_mesh() {
let chunk = Chunk::<DefaultVoxel>::new();
let mesh = generate_chunk_mesh(&chunk, 1);
assert_eq!(
vertex_count(&mesh),
0,
"empty chunk should produce 0 vertices"
);
}
#[test]
fn fully_solid_chunk_produces_six_quads() {
let mut chunk = Chunk::<DefaultVoxel>::new();
for x in 0..CHUNK_SIZE {
for y in 0..CHUNK_SIZE {
for z in 0..CHUNK_SIZE {
chunk.set(x, y, z, DefaultVoxel::Rock);
}
}
}
let mesh = generate_chunk_mesh(&chunk, 1);
assert_eq!(
vertex_count(&mesh),
24,
"fully solid chunk should have 24 vertices (4 per face x 6 faces)"
);
assert_eq!(
index_count(&mesh),
36,
"fully solid chunk should have 36 indices (6 per face x 6 faces)"
);
}
#[test]
fn single_voxel_produces_six_faces() {
let mut chunk = Chunk::<DefaultVoxel>::new();
chunk.set(0, 0, 0, DefaultVoxel::Rock);
let mesh = generate_chunk_mesh(&chunk, 1);
assert_eq!(
vertex_count(&mesh),
24,
"single voxel should have 24 vertices (4 per face x 6 faces)"
);
assert_eq!(
index_count(&mesh),
36,
"single voxel should have 36 indices (6 per face x 6 faces)"
);
}
#[test]
fn lod_mesh_has_fewer_vertices() {
let mut chunk = Chunk::<DefaultVoxel>::new();
for x in 0..CHUNK_SIZE {
for y in 0..CHUNK_SIZE {
for z in 0..CHUNK_SIZE {
if (x + y + z) % 2 == 0 {
chunk.set(x, y, z, DefaultVoxel::Rock);
} else {
chunk.set(x, y, z, DefaultVoxel::IronOre);
}
}
}
}
let mesh_lod0 = generate_chunk_mesh(&chunk, 1);
let mesh_lod1 = generate_chunk_mesh(&chunk, 2);
let count_lod0 = vertex_count(&mesh_lod0);
let count_lod1 = vertex_count(&mesh_lod1);
assert!(
count_lod1 < count_lod0,
"LOD 1 ({count_lod1} verts) should have fewer vertices than LOD 0 ({count_lod0} verts)"
);
}
}