block-mesh Rust Library

The block-mesh library provides two primary algorithms for generating meshes from voxel data:

1. visible_block_faces: A very fast algorithm that produces suboptimal meshes (more triangles).
2. greedy_quads: A slightly slower algorithm that produces more optimal meshes by merging adjacent faces into larger quads, resulting in significantly fewer triangles.

To use these, you must implement the Voxel and MergeVoxel traits on your data type and provide a shape (using the ndshape crate) and a configuration (like RIGHT_HANDED_Y_UP_CONFIG).

use block_mesh::ndshape::{ConstShape, ConstShape3u32};
use block_mesh::{greedy_quads, GreedyQuadsBuffer, MergeVoxel, Voxel, VoxelVisibility, RIGHT_HANDED_Y_UP_CONFIG};

#[derive(Clone, Copy, Eq, PartialEq)]
struct BoolVoxel(bool);

const EMPTY: BoolVoxel = BoolVoxel(false);
const FULL: BoolVoxel = BoolVoxel(true);

impl Voxel for BoolVoxel {
    fn get_visibility(&self) -> VoxelVisibility {
        if *self == EMPTY {
            VoxelVisibility::Empty
        } else {
            VoxelVisibility::Opaque
        }
    }
}

impl MergeVoxel for BoolVoxel {
    type MergeValue = Self;
    type MergeValueFacingNeighbour = Self;

    fn merge_value(&self) -> Self::MergeValue {
        *self
    }

    fn merge_value_facing_neighbour(&self) -> Self::MergeValueFacingNeighbour {
        *self
    }
}

// A 16^3 chunk with 1-voxel boundary padding.
type ChunkShape = ConstShape3u32<18, 18, 18>;

let mut voxels = [EMPTY; ChunkShape::SIZE as usize];
// ... populate voxels ...

let mut buffer = GreedyQuadsBuffer::new(voxels.len());
greedy_quads(
    &voxels,
    &ChunkShape {},
    [0; 3], // min bounds
    [17; 3], // max bounds
    &RIGHT_HANDED_Y_UP_CONFIG.faces,
    &mut buffer
);

To use the greedy_quads algorithm, you must:

1. Define a type that implements the Voxel trait (to define visibility) and the MergeVoxel trait (to define how voxels merge during the greedy pass).
2. Define the shape of your voxel data using ndshape (e.g., ConstShape3u32).
3. Initialize a GreedyQuadsBuffer with the capacity of your voxel array.
4. Call greedy_quads providing the voxel data, the shape, the bounding box (min/max coordinates), a face configuration (like RIGHT_HANDED_Y_UP_CONFIG), and the buffer.

use block_mesh::ndshape::{ConstShape, ConstShape3u32};
use block_mesh::{greedy_quads, GreedyQuadsBuffer, MergeVoxel, Voxel, VoxelVisibility, RIGHT_HANDED_Y_UP_CONFIG};

#[derive(Clone, Copy, Eq, PartialEq)]
struct BoolVoxel(bool);

const EMPTY: BoolVoxel = BoolVoxel(false);
const FULL: BoolVoxel = BoolVoxel(true);

impl Voxel for BoolVoxel {
    fn get_visibility(&self) -> VoxelVisibility {
        if *self == EMPTY {
            VoxelVisibility::Empty
        } else {
            VoxelVisibility::Opaque
        }
    }
}

impl MergeVoxel for BoolVoxel {
    type MergeValue = Self;
    type MergeValueFacingNeighbour = Self;

    fn merge_value(&self) -> Self::MergeValue {
        *self
    }

    fn merge_value_facing_neighbour(&self) -> Self::MergeValueFacingNeighbour {
        *self
    }
}

// A 16^3 chunk with 1-voxel boundary padding.
type ChunkShape = ConstShape3u32<18, 18, 18>;

// This chunk will cover just a single octant of a sphere SDF (radius 15).
let mut voxels = [EMPTY; ChunkShape::SIZE as usize];
for i in 0..ChunkShape::SIZE {
    let [x, y, z] = ChunkShape::delinearize(i);
    voxels[i as usize] = if ((x * x + y * y + z * z) as f32).sqrt() < 15.0 {
        FULL
    } else {
        EMPTY
    };
}

let mut buffer = GreedyQuadsBuffer::new(voxels.len());
greedy_quads(
    &voxels,
    &ChunkShape {},
    [0; 3], // Min bounds
    [17; 3], // Max bounds
    &RIGHT_HANDED_Y_UP_CONFIG.faces,
    &mut buffer
);

// Some quads were generated.
assert!(buffer.quads.num_quads() > 0);

To customize how cube faces are merged into quads during the greedy meshing process, implement the MergeStrategy trait. This allows you to define the logic for determining the width and height of a quad based on voxel data.

MergeStrategy Trait

MergeStrategy defines the interface for finding the dimensions of a quad.

• type Voxel: The type of voxel data being processed.
• unsafe fn find_quad(...) -> (u32, u32): Determines the width and height of the quad starting at min_index.

Parameters for find_quad:

• min_index: The linear index for the minimum voxel in this quad.
• max_width: The maximum possible width for the quad.
• max_height: The maximum possible height for the quad.
• face_strides: A FaceStrides struct containing indexing offsets.
• voxels: The slice of voxel data.
• visited: A bitmask (&[bool]) indicating which voxels have already been meshed.

# Safety Note Implementations of find_quad may use unchecked indexing of voxels for performance. You must ensure that the arguments provided to the function are correct to avoid undefined behavior from out-of-bounds access.

pub trait MergeStrategy {
    type Voxel;

    unsafe fn find_quad(
        min_index: u32,
        max_width: u32,
        max_height: u32,
        face_strides: &FaceStrides,
        voxels: &[Self::Voxel],
        visited: &[bool],
    ) -> (u32, u32)
    where
        Self::Voxel: Voxel;
}

The OrientedBlockFace struct provides metadata used to perform geometric calculations for one of the six possible cube faces. It handles the relationship between the face's normal direction and its local UV axes (U and V). This is essential for generating mesh positions, normals, indices, and texture coordinates for voxel-based rendering.

Key capabilities include:

• Calculating 3D mesh positions and normals based on a voxel_size.
• Generating vertex indices for two triangles (a quad) with correct winding order.
• Computing UV texture coordinates for a quad, supporting texture flipping.
• Determining the signed normal vector of the face.

use crate::geometry::face::OrientedBlockFace;
use crate::{SignedAxis, UnorientedQuad};

// Example: Creating a canonical face from a signed axis
let face = OrientedBlockFace::canonical(SignedAxis::new(Axis::X, 1));

// Example: Getting mesh positions for a quad
let quad = UnorientedQuad { ... };
let positions = face.quad_mesh_positions(&quad, 1.0);

// Example: Getting vertex indices for a mesh starting at index 0
let indices = face.quad_mesh_indices(0);

The greedy_quads function implements the Mikola Lysenko algorithm to generate large quads from a voxel volume. It reduces the number of polygons by merging adjacent voxel faces that share the same properties.

Parameters:

• voxels: A slice of your voxel data (must implement MergeVoxel).
• voxels_shape: The shape/dimensions of the voxel array (must implement Shape<3, Coord = u32>).
• min: The minimum [u32; 3] coordinate of the bounding box to mesh.
• max: The maximum [u32; 3] coordinate of the bounding box to mesh.
• faces: A slice of 6 OrientedBlockFace objects representing the possible directions of faces.
• output: A mutable reference to a GreedyQuadsBuffer where the resulting UnorientedQuads will be stored.

use block_mesh::{greedy_quads, GreedyQuadsBuffer, RIGHT_HANDED_Y_UP_CONFIG};

// Assuming 'voxels' and 'shape' are already defined
let mut buffer = GreedyQuadsBuffer::new(voxels.len());

greedy_quads(
    &voxels,
    &shape,
    [0, 0, 0],      // min
    [32, 32, 32],   // max
    &RIGHT_HANDED_Y_UP_CONFIG.faces,
    &mut buffer,
);

The AxisPermutation enum defines the six possible mappings from a local coordinate system {N, U, V} to the global {X, Y, Z} axes. This is used to define how faces are oriented in space.

Permutations are categorized into:

• Even permutations: Xyz, Zxy, Yzx (return sign() of 1).
• Odd permutations: Zyx, Xzy, Yxz (return sign() of -1).

Key methods:

• even_with_normal_axis(axis: Axis): Returns an even permutation based on the provided normal axis.
• odd_with_normal_axis(axis: Axis): Returns an odd permutation based on the provided normal axis.
• sign(): Returns 1 for even permutations and -1 for odd permutations.
• axes(): Returns the three Axis values in the order specified by the permutation.

use block_mesh::geometry::{Axis, AxisPermutation};

let xyz = AxisPermutation::Xyz;
let axes = xyz.axes(); // [Axis::X, Axis::Y, Axis::Z]
let s = xyz.sign(); // 1

let even = AxisPermutation::even_with_normal_axis(Axis::Y); // AxisPermutation::Yzx