[−][src]Module building_blocks_storage::chunk_map
A memory-efficient sparse lattice map made of up array chunks.
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.
The chunk map supports chunk compression, and an LRU cache stores chunks after they are
decompressed. Because reading a chunk may result in decompression, we will eventually want to
mutate the cache in order to store that chunk. If you need to read from the map without mutating
it, the const get_chunk*
methods take a LocalChunkCache
. To read individual points, you can
use the ChunkMapReader
, which also uses a LocalChunkCache
. A LocalChunkCache
can be
written back to the ChunkMap
using the flush_chunk_cache
method.
Example Usage
use building_blocks_core::prelude::*; use building_blocks_storage::prelude::*; let chunk_shape = PointN([16; 3]); // components must be powers of 2 let ambient_value = 0; let default_chunk_meta = (); // chunk metadata is optional let mut map = ChunkMap3::new( chunk_shape, ambient_value, default_chunk_meta, FastLz4 { level: 10 } ); // Although we only write 3 points, 3 whole dense chunks will be inserted and cached. let write_points = [PointN([-100; 3]), PointN([0; 3]), PointN([100; 3])]; for p in write_points.iter() { *map.get_mut(&p) = 1; } // Maybe we are tight on memory. Repetitive maps are very compressible. In a game // setting, you would probably have a system dedicated to monitoring the memory usage and // compressing chunks when appropriate. map.compress_lru_chunk(); // 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 without mutating the map by using local caching. Compressed // chunks will be decompressed into our local cache. let local_cache = LocalChunkCache3::new(); let reader = ChunkMapReader3::new(&map, &local_cache); reader.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); } }); // It's safe to gather up some const chunk references. The reader will reuse our local cache. let mut chunk_refs = Vec::new(); for chunk_key in reader.chunk_keys() { chunk_refs.push(reader.get_chunk(*chunk_key)); } // You can also access individual points like you can with a `ArrayN`. This is about // 10x slower than iterating, because it hashes the chunk coordinates for every access. for p in write_points.iter() { assert_eq!(reader.get(p), 1); } assert_eq!(reader.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, &reader, &mut dense_map); // When you're done accessing the map, you should flush you local cache. This is not strictly // necessary, but it makes the caching more efficient. map.flush_chunk_cache(local_cache);
Structs
AmbientExtent | An extent that takes the same value everywhere. |
Chunk | One piece of the |
ChunkMap | A lattice map made up of same-shaped |
ChunkMapReader | A thread-local reader of a |
FastCompressedChunk | |
SerializableChunkMap | Call |
Traits
ChunkShape |
Functions
chunk_keys_for_extent | Returns an iterator over all chunk keys for chunks that overlap the given extent. |
extent_for_chunk_at_key | Returns the extent of the chunk at |