Module building_blocks_storage::chunk::map

A sparse lattice map made of up array chunks. Designed for random access. Supports multiple levels of detail.

Level of Detail

All chunks have the same shape, but the voxel size doubles at every level. Most of the time, you will just manipulate the data at LOD0, but if you need to downsample this to save resources where coarser resolution is acceptable, then you can use a ChunkDownsampler and the ChunkMap::downsample_* methods to populate higher levels.

NOTE: If you want your downsampled data to have different number of channels than LOD0, then you will need to store the downsampled chunks in a different ChunkMap. You will need to use specialized methods for this use case:

• ChunkMap::downsample_external_chunk
• ChunkMap::downsample_chunks_with_lod0_and_index

Indexing and Iteration

The data can either be addressed by ChunkKey with the get_chunk* methods or by individual points using the Get* and ForEach* trait impls on a ChunkMapLodView. At a given level of detail, the key for a chunk is the minimum point in that chunk, which is always a multiple of the chunk shape. Chunk shape dimensions must be powers of 2, which allows for efficiently calculating a chunk minimum from any point in the chunk.

If you require iteration over large, but very sparse regions, you might want an additional OctreeChunkIndex to track the set of occupied chunks. Traversing that index can be faster than doing hash map lookups on all of the possible chunks in a region.

When using multiple levels of detail, it’s generally useful to have an OctreeChunkIndex that tracks the chunk occupancy. This helps with specific types of traversal, like for downsampling or detecting clipmap updates.

Chunk Storage

ChunkMap<N, T, Bldr, Store> depends on a backing chunk storage Store, which can implement some of ChunkReadStorage or ChunkWriteStorage. A storage can be as simple as a HashMap, which provides good performance for both iteration and random access. It could also be something more memory efficient like FastCompressibleChunkStorage or CompressibleChunkStorageReader, which perform nearly as well but involve some extra management of the cache.

Serialization

In order to efficiently serialize a ChunkMap, you can first use SerializableChunks::from_iter to create a compact serializable representation. It will compress the bincode representation of the chunks.

Example ChunkHashMap Usage

use building_blocks_core::prelude::*;
use building_blocks_storage::prelude::*;

let chunk_shape = Point3i::fill(16);
let ambient_value = 0;
let builder = ChunkMapBuilder3x1::new(chunk_shape, ambient_value);
let mut map = builder.build_with_hash_map_storage();

// We need to focus on a specific level of detail to use the access traits.
let mut lod0 = map.lod_view_mut(0);

// Although we only write 3 points, 3 whole dense chunks will be inserted.
let write_points = [Point3i::fill(-100), Point3i::ZERO, Point3i::fill(100)];
for &p in write_points.iter() {
    *lod0.get_mut(p) = 1;
}

// Even though the map is sparse, we can get the smallest extent that bounds all of the occupied
// chunks in LOD0.
let bounding_extent = map.bounding_extent(0);

// Now we can read back the values.
let lod0 = map.lod_view(0);
lod0.for_each(&bounding_extent, |p, value| {
    if write_points.iter().position(|pw| p == *pw) != None {
        assert_eq!(value, 1);
    } else {
        // The points that we didn't write explicitly got an ambient value when the chunk was
        // inserted. Also any points in `bounding_extent` that don't have a chunk will also take
        // the ambient value.
        assert_eq!(value, 0);
    }
});

// You can also access individual points like you can with an `Array`. This is
// slower than iterating, because it hashes the chunk coordinates for every access.
for &p in write_points.iter() {
    assert_eq!(lod0.get(p), 1);
}
assert_eq!(lod0.get(Point3i::fill(1)), 0);

// Sometimes you need to implement very fast algorithms (like kernel-based methods) that do a
// lot of random access. In this case it's most efficient to use `Stride`s, but `ChunkMap`
// doesn't support random indexing by `Stride`. Instead, assuming that your query spans multiple
// chunks, you should copy the extent into a dense map first. (The copy is fast).
let query_extent = Extent3i::from_min_and_shape(Point3i::fill(10), Point3i::fill(32));
let mut dense_map = Array3x1::fill(query_extent, ambient_value);
copy_extent(&query_extent, &lod0, &mut dense_map);

Example CompressibleChunkMap Usage

let chunk_shape = Point3i::fill(16);
let ambient_value = 0;
let builder = ChunkMapBuilder3x1::new(chunk_shape, ambient_value);
let mut map = builder.build_with_write_storage(
    FastCompressibleChunkStorageNx1::with_bytes_compression(Lz4 { level: 10 })
);
let mut lod0 = map.lod_view_mut(0);

// You can write voxels the same as any other `ChunkMap`. As chunks are created, they will be placed in an LRU cache.
let write_points = [Point3i::fill(-100), Point3i::ZERO, Point3i::fill(100)];
for &p in write_points.iter() {
    *lod0.get_mut(p) = 1;
}

// Save some space by compressing the least recently used chunks. On further access to the compressed chunks, they will get
// decompressed and cached.
map.storage_mut().compress_lru();

// In order to use the read-only access traits, you need to construct a `CompressibleChunkStorageReader`.
let local_cache = LocalChunkCache3::new();
let reader = map.reader(&local_cache);

let bounding_extent = reader.bounding_extent(0);
reader.lod_view(0).for_each(&bounding_extent, |p, value| {
    if write_points.iter().position(|pw| p == *pw) != None {
        assert_eq!(value, 1);
    } else {
        assert_eq!(value, 0);
    }
});

// For efficient caching, you should flush your local cache back into the main storage when you are done with it.
map.storage_mut().flush_local_cache(local_cache);

Re-exports

pub use builder::*;

pub use lod_view::*;

pub use sampling::*;

Modules

builder

lod_view

sampling

Structs

AmbientExtent

An extent that takes the same value everywhere.

ChunkMap

A lattice map made up of same-shaped Array chunks. For each level of detail, it takes a value at every possible PointN, because accesses made outside of the stored chunks will return some ambient value specified on creation.

Traits

Chunk

One piece of a chunked lattice map.

Type Definitions

ChunkMap2

A 2-dimensional ChunkMap.

ChunkMap2x1

A 2-dimensional, single-channel ChunkMap.

ChunkMap3

A 3-dimensional ChunkMap.

ChunkMap3x1

A 3-dimensional, single-channel ChunkMap.

ChunkMapNx1

An N-dimensional, single-channel ChunkMap.