[−][src]Module building_blocks_storage::chunk_map
A sparse lattice map made of up array chunks.
Addressing
The data can either be addressed by chunk key with the get_chunk*
methods or by individual points using the Get*
and
ForEach*
trait impls. The map of chunks uses Point3i
keys. 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 key from any point in the chunk.
Chunk Storage
ChunkMap<N, T, Meta, 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 CompressibleChunkStorage
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 SerializableChunkMap::from_chunk_map
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 ambient_value = 0; let builder = ChunkMapBuilder { chunk_shape: PointN([16; 3]), // components must be powers of 2 ambient_value, default_chunk_metadata: (), // chunk metadata is optional }; let mut map = builder.build_with_hash_map_storage(); // Although we only write 3 points, 3 whole dense chunks will be inserted. let write_points = [PointN([-100; 3]), PointN([0; 3]), PointN([100; 3])]; for p in write_points.iter() { *map.get_mut(&p) = 1; } // Even though the map is sparse, we can get the smallest extent that bounds all of the occupied // chunks. let bounding_extent = map.bounding_extent(); // Now we can read back the values. map.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 a `ArrayN`. This is // slower than iterating, because it hashes the chunk coordinates for every access. for p in write_points.iter() { assert_eq!(map.get(p), 1); } assert_eq!(map.get(&PointN([1, 1, 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(PointN([10; 3]), PointN([32; 3])); let mut dense_map = Array3::fill(query_extent, ambient_value); copy_extent(&query_extent, &map, &mut dense_map);
Example CompressibleChunkMap
Usage
let mut map = builder.build(CompressibleChunkStorage::new(Lz4 { level: 10 })); // 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 = [PointN([-100; 3]), PointN([0; 3]), PointN([100; 3])]; for p in write_points.iter() { *map.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 = LocalChunkCache::new(); let reader = map.storage().reader(&local_cache); let reader_map = builder.build(reader); let bounding_extent = reader_map.bounding_extent(); reader_map.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);
Structs
AmbientExtent | An extent that takes the same value everywhere. |
Chunk | One piece of a chunked lattice map. Contains both some generic metadata and the data for each point in the chunk extent. |
ChunkIndexer | Translates from lattice coordinates to chunk key space. |
ChunkMap | A lattice map made up of same-shaped |
ChunkMapBuilder | A few pieces of info used within the |
CompressedLocation | An index into a compressed chunk slab. |
CompressibleChunkStorage | A two-tier chunk storage. The first tier is an LRU cache of uncompressed |
CompressibleChunkStorageReader | An object for reading from |
CompressibleChunkStorageReaderIntoIter | |
FastChunkCompression | A |
FastCompressedChunk | The target of |
LocalCache | A cache with a very specific niche. When reading from shared, two-tier storage, if you miss the cache and need to fetch from
the cold tier, then you also need a place to store the fetched data. Rather than doing interior mutation of the storage,
which requires synchronization, the fetched data can be stored in a thread-local cache, the |
LruCache | A cache that tracks the Least Recently Used element for next eviction. |
LruCacheEntries | |
LruCacheIntoIter | |
SerializableChunkMap | A simple chunk map format for serialization. All chunks are serialized with |
Enums
CacheEntry |
Traits
ChunkReadStorage | Methods for reading |
ChunkShape | |
ChunkWriteStorage | Methods for writing |
IterChunkKeys |
Type Definitions
ArrayChunkCopySrc | |
ArrayChunkCopySrcIter | |
BincodeChunkCompression | |
BincodeCompressedChunk | |
Chunk2 | A 2-dimensional |
Chunk3 | A 3-dimensional |
ChunkCopySrc | |
ChunkHashMap | A |
ChunkHashMap2 | A 2-dimensional |
ChunkHashMap3 | A 3-dimensional |
ChunkMap2 | A 2-dimensional |
ChunkMap3 | A 3-dimensional |
ChunkMapBuilder2 | A 2-dimensional |
ChunkMapBuilder3 | A 3-dimensional |
CompressedChunks | |
CompressibleChunkMap | A |
CompressibleChunkMap2 | A 2-dimensional |
CompressibleChunkMap3 | A 3-dimensional |
CompressibleChunkMapReader | A |
CompressibleChunkMapReader2 | 2-dimensional |
CompressibleChunkMapReader3 | 3-dimensional |
CompressibleChunkStorage2 | 2-dimensional |
CompressibleChunkStorage3 | 3-dimensional |
CompressibleChunkStorageReader2 | 2-dimensional |
CompressibleChunkStorageReader3 | 3-dimensional |
FnvLruCache | An |
LocalChunkCache | A |
LocalChunkCache2 | A |
LocalChunkCache3 | A |
LruCacheKeys | |
LruChunkCacheEntries | |
LruChunkCacheIntoIter | |
LruChunkCacheKeys | |
MaybeCompressedChunk | |
MaybeCompressedChunk2 | |
MaybeCompressedChunk3 | |
MaybeCompressedChunkRef | |
MaybeCompressedChunkRef2 | |
MaybeCompressedChunkRef3 |