#gamedev #3d #geometry #mesh #voxel #blocks #rendering

building_blocks_mesh

Fast meshing algorithms for voxel data structures

9 releases (breaking)

0.7.1 Sep 23, 2021
0.7.0 Jun 14, 2021
0.6.0 Mar 21, 2021
0.5.0 Feb 8, 2021
0.1.0 Oct 26, 2020

#1282 in Math

Download history 50/week @ 2023-10-28 25/week @ 2023-11-04 24/week @ 2023-11-11 26/week @ 2023-11-18 54/week @ 2023-11-25 32/week @ 2023-12-02 22/week @ 2023-12-09 34/week @ 2023-12-16 41/week @ 2023-12-23 20/week @ 2023-12-30 25/week @ 2024-01-06 24/week @ 2024-01-13 26/week @ 2024-01-20 52/week @ 2024-01-27 14/week @ 2024-02-03 52/week @ 2024-02-10

147 downloads per month
Used in building-blocks

MIT license

415KB
9K SLoC

Algorithms for generating triangle meshes from:

  • height maps
  • signed distance fields
  • voxel occupancy grids

All of the algorithms are designed to be used with a ChunkMap, such that each chunk will have its own mesh. In order to update the mesh for a chunk, you must copy not only the chunk, but also some adjacent points, into an array before running the meshing algorithm.

An example of updating chunk meshes for a height map is shown below. The same general pattern applies to all meshing algorithms, where you:

  1. get the desired chunk extent
  2. pad the extent for a particular meshing algorithm
  3. copy that extent into an array
  4. mesh that array
use building_blocks_core::prelude::*;
use building_blocks_storage::prelude::*;
use building_blocks_mesh::height_map::*;

use std::collections::HashSet;

let chunk_shape = PointN([16; 2]);
let builder = ChunkMapBuilder2x1::new(chunk_shape, 0.0);
let mut map = builder.build_with_hash_map_storage();

// ...mutate one or more of the chunks...

let mutated_chunk_keys = [PointN([0; 2]), PointN([16; 2])];

// For each mutated chunk, and any adjacent chunk, the mesh will need to be updated.
let mut chunk_keys_to_update: HashSet<Point2i> = HashSet::new();
let offsets = Point2i::moore_offsets();
for chunk_key in mutated_chunk_keys.into_iter() {
    chunk_keys_to_update.insert(*chunk_key);
    for offset in offsets.iter() {
        chunk_keys_to_update.insert(*chunk_key + *offset * chunk_shape);
    }
}

// Now we generate mesh vertices for each chunk.
for chunk_key in chunk_keys_to_update.into_iter() {
    // It's crucial that we pad the chunk so we have access to adjacent points during meshing.
    let padded_chunk_extent = padded_height_map_chunk_extent(
        &map.indexer.extent_for_chunk_with_min(chunk_key)
    );
    let mut padded_chunk = Array2x1::fill(padded_chunk_extent, 0.0);
    copy_extent(&padded_chunk_extent, &map.lod_view(0), &mut padded_chunk);

    let mut hm_buffer = HeightMapMeshBuffer::default();
    triangulate_height_map(&padded_chunk, &padded_chunk_extent, &mut hm_buffer);
    // Do something with the mesh output...
}

All of the meshing algorithms are generic enough to work with an array wrapped in a TransformMap.

#
struct OtherHeight(f32);

impl Height for OtherHeight {
    fn height(&self) -> f32 { self.0 }
}

let extent = Extent2i::from_min_and_shape(PointN([0; 2]), PointN([50; 2]));
let array = Array2x1::fill(extent, 0.0);
let tfm_array = TransformMap::new(&array, |h: f32| OtherHeight(h));
let mut hm_buffer = HeightMapMeshBuffer::default();
triangulate_height_map(&tfm_array, &extent, &mut hm_buffer);

Dependencies

~2.4–3.5MB
~69K SLoC