Crate block_mesh

Fast algorithms for generating voxel block meshes.

Two algorithms are included:

• visible_block_faces: very fast but suboptimal meshes
• greedy_quads: not quite as fast, but far fewer triangles are generated

Benchmarks show that visible_block_faces generates about 40 million quads per second on a single core of a 2.5 GHz Intel Core i7. Assuming spherical input data, greedy_quads can generate a more optimal version of the same mesh with 1/3 of the quads, but it takes about 3 times longer. To run the benchmarks yourself, cd bench/ && cargo bench.

Example Code

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;

    fn merge_value(&self) -> Self::MergeValue {
        *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],
    [17; 3],
    &RIGHT_HANDED_Y_UP_CONFIG.faces,
    &mut buffer
);

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

Re-exports

pub use ilattice;

pub use ndshape;

Modules

geometry

Voxel geometry and coordinate systems.

Structs

FaceStrides

GreedyQuadsBuffer

Contains the output from the greedy_quads algorithm. The quads can be used to generate a mesh. See the methods on OrientedBlockFace and UnorientedQuad for details.

OrientedBlockFace

Metadata that’s used to aid in the geometric calculations for one of the 6 possible cube faces.

QuadBuffer

QuadCoordinateConfig

A configuration of XYZ –> NUV axis mappings and orientations of the cube faces for a given coordinate system.

UnitQuadBuffer

UnorientedQuad

The minimum voxel and size of a quad, without an orientation. To get the actual corners of the quad, combine with an [OrientedBlockFace].

UnorientedUnitQuad

A quad covering a single voxel (just a single block face), without an orientation. To get the actual corners of the quad, combine with an [OrientedBlockFace].

VoxelMerger

Enums

Axis

Either the X, Y, or Z axis.

AxisPermutation

One of the six possible {N, U, V} –> {X, Y, Z} mappings.

SignedAxis

Either the -X, +X, -Y, +Y, -Z, or +Z axis.

VoxelVisibility

Describes how this voxel influences mesh generation.

Constants

RIGHT_HANDED_Y_UP_CONFIG

Coordinate configuration for a right-handed coordinate system with Y up.

Traits

MergeStrategy

A strategy for merging cube faces into quads.

MergeVoxel

Voxel

Implement on your voxel types to inform the library how to generate geometry for this voxel.

Functions

greedy_quads

The “Greedy Meshing” algorithm described by Mikola Lysenko in the 0fps article.

greedy_quads_with_merge_strategy

Run the greedy meshing algorithm with a custom quad merging strategy using the MergeStrategy trait.

visible_block_faces

A fast and simple meshing algorithm that produces a single quad for every visible face of a block.

visible_block_faces_with_voxel_view

Same as visible_block_faces, with the additional ability to interpret the array as some other type. Use this if you want to mesh the same array multiple times with different sets of voxels being visible.