kvas_engine/
voxel_mesh.rs

1//! Greedy solid-voxel mesher; density discontinuities retain separate faces.
2use crate::mesh::{MeshData, Vertex};
3use glam::Vec3;
4
5/// Merges coplanar exposed faces with equal density. Each cell is sampled once.
6/// A solid cuboid becomes six quads. Invalid parameters or >16M cells return an empty mesh.
7pub fn mesh_grid_greedy(dim: [usize; 3], cell: f32, origin: Vec3, threshold: f32, density: impl Fn(usize, usize, usize) -> f32) -> MeshData {
8    let mut mesh = MeshData::default();
9    let count = dim.iter().try_fold(1usize, |n, &d| n.checked_mul(d));
10    if dim.iter().any(|&d| d == 0 || d > 512) || count.is_none_or(|n| n > 16_000_000) || !cell.is_finite() || cell <= 0.0 || !origin.is_finite() || !threshold.is_finite() { return mesh; }
11    let mut values = Vec::with_capacity(count.unwrap());
12    for z in 0..dim[2] { for y in 0..dim[1] { for x in 0..dim[0] { values.push(density(x, y, z)); } } }
13    let sample = |p: [usize; 3]| values[(p[2] * dim[1] + p[1]) * dim[0] + p[0]];
14    for axis in 0..3 {
15        let u = (axis + 1) % 3; let v = (axis + 2) % 3;
16        let mut mask = vec![None::<(bool, u32)>; dim[u] * dim[v]];
17        for plane in 0..=dim[axis] {
18            for j in 0..dim[v] { for i in 0..dim[u] {
19                let mut p = [0; 3]; p[u] = i; p[v] = j;
20                let left = if plane > 0 { p[axis] = plane - 1; Some(sample(p)).filter(|d| d.is_finite() && *d > threshold) } else { None };
21                let right = if plane < dim[axis] { p[axis] = plane; Some(sample(p)).filter(|d| d.is_finite() && *d > threshold) } else { None };
22                mask[j * dim[u] + i] = match (left, right) { (Some(d), None) => Some((true, d.clamp(0.0, 1.0).to_bits())), (None, Some(d)) => Some((false, d.clamp(0.0, 1.0).to_bits())), _ => None };
23            } }
24            for j in 0..dim[v] {
25                let mut i = 0;
26                while i < dim[u] {
27                    let Some(key) = mask[j * dim[u] + i] else { i += 1; continue };
28                    let mut width = 1;
29                    while i + width < dim[u] && mask[j * dim[u] + i + width] == Some(key) { width += 1; }
30                    let mut height = 1;
31                    while j + height < dim[v] && (0..width).all(|x| mask[(j + height) * dim[u] + i + x] == Some(key)) { height += 1; }
32                    for y in j..j + height { for x in i..i + width { mask[y * dim[u] + x] = None; } }
33                    let mut p = Vec3::ZERO; p[axis] = plane as f32; p[u] = i as f32; p[v] = j as f32;
34                    let mut du = Vec3::ZERO; du[u] = width as f32;
35                    let mut dv = Vec3::ZERO; dv[v] = height as f32;
36                    let mut normal = Vec3::ZERO; normal[axis] = if key.0 { 1.0 } else { -1.0 };
37                    let base = mesh.vertices.len() as u32;
38                    for q in [p, p + du, p + du + dv, p + dv] { mesh.vertices.push(Vertex { pos: (origin + q * cell).to_array(), normal: normal.to_array(), uv: [f32::from_bits(key.1), 0.5] }); }
39                    if key.0 { mesh.indices.extend([base, base + 1, base + 2, base, base + 2, base + 3]); }
40                    else { mesh.indices.extend([base, base + 2, base + 1, base, base + 3, base + 2]); }
41                    i += width;
42                }
43            }
44        }
45    }
46    mesh
47}
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52    fn area(mesh: &MeshData) -> f32 {
53        mesh.indices.chunks_exact(3).map(|t| {
54            let a = Vec3::from(mesh.vertices[t[0] as usize].pos); let b = Vec3::from(mesh.vertices[t[1] as usize].pos); let c = Vec3::from(mesh.vertices[t[2] as usize].pos);
55            let cross = (b - a).cross(c - a);
56            assert!(cross.dot(Vec3::from(mesh.vertices[t[0] as usize].normal)) > 0.0);
57            cross.length() * 0.5
58        }).sum()
59    }
60    #[test]
61    fn greedy_cavity_density_winding_and_sampling_are_preserved() {
62        let calls = std::cell::Cell::new(0usize);
63        let mesh = mesh_grid_greedy([3, 3, 3], 1.0, Vec3::ZERO, 0.1, |x, y, z| {
64            calls.set(calls.get() + 1);
65            if x == 1 && y == 1 && z == 1 { 0.0 } else if x == 0 { 0.5 } else { 1.0 }
66        });
67        assert_eq!(calls.get(), 27); mesh.validate().unwrap();
68        assert_eq!(area(&mesh), 60.0, "outer shell and internal cavity");
69        assert!(mesh.vertices.iter().any(|v| v.uv[0] == 0.5));
70        let solid = mesh_grid_greedy([32, 32, 32], 1.0, Vec3::ZERO, 0.1, |_, _, _| 1.0);
71        assert_eq!(solid.indices.len(), 36); assert_eq!(area(&solid), 6.0 * 32.0 * 32.0);
72        assert!(mesh_grid_greedy([usize::MAX, 2, 2], 1.0, Vec3::ZERO, 0.5, |_, _, _| 1.0).vertices.is_empty());
73    }
74}
kvas_engine/voxel_mesh.rs

kvas_engine/
voxel_mesh.rs
