building-blocks v0.6.0
Development Status Update
Since v0.5.0, my goal has been to provide tools for implementing level of detail (LoD) and using them in building-blocks-editor. This has taken me on an unexpected detour.
For context, the voxel type in building-blocks-editor looks like this:
struct Voxel {
distance: Sd8,
type_id: u8,
}With LoD, my plan was to downsample chunks into a ChunkPyramid (mipmap). I had this prototyped for voxels with just a signed distance component, but this left me wondering what I should do with the type_id. Just ignore it? Certainly it should not be treated the same by the sampler. In fact, I realized that I don't even have a good reason to downsample the type_id at the moment. Generalizing a bit, I realized that when you have multiple voxel components, you often have workflows that only need to sample a subset of components at a time. But when your voxel is a struct like this, you end up loading the entire thing into cache and wasting space. Of course, the lessons of the ECS paradigm and Structure of Arrays (SoA) dawned on me, and I realized that I should be treating the layout of voxel data a bit differently.
And so the main focus of this release has been what I am calling "multichannel" support. Read more below.
Release Highlights
Multichannel All the Things
TL;DR, now the Array type uses an underlying tuple of Channels, each with a separate flat layout. This means that arrays with multiple channels, like Array3x2<A, B> (an array with 3 spatial dimensions and 2 channels), are supported by multiple independent data channels, i.e. (Channel<A>, Channel<B>). Array supports up to 6 channels.
// Manually create channels for educational purpose.
let ch1 = Channel::fill(0, extent.num_points());
let ch2 = Channel::fill('a', extent.num_points());
let array = Array::new(extent, (ch1, ch2));
// Or use a more convenient constructor.
let array = Array3x2::fill(extent, (0, 'a'));Similarly, ChunkMap leverages this feature of arrays, and there are new types like ChunkHashMap3x2<A, B> and CompressibleChunkMap3x2<A, B> which support the same access patterns as arrays. Here's what it looks like to use a multichannel ChunkMap:
let ambient_values = (0, 'a');
let builder = ChunkMapBuilder3x2::new(CHUNK_SHAPE, ambient_values);
let mut map = builder.build_with_write_storage(
FastCompressibleChunkStorageNx2::with_bytes_compression(Lz4 { level: 10 }),
);
let iter_extent = Extent3i::from_min_and_shape(Point3i::fill(10), Point3i::fill(80));
assert_eq!(map.get_mut(Point3i::fill(1)), (&mut 0, &mut 'a'));
map.for_each_mut(&iter_extent, |_p, (num, letter)| {
*num = 1;
*letter = 'b';
});
let local_cache = LocalChunkCache::new();
let reader = map.reader(&local_cache);
assert_eq!(reader.get(Point3i::fill(1)), (0, 'a'));
assert_eq!(reader.get_ref(Point3i::fill(1)), (&0, &'a'));
reader.for_each(&iter_extent, |_p, (num, letter)| {
assert_eq!((num, letter), (1, 'b'));
});As you can see, everything works like it used to, including chunk compression, access traits, and copy_extent. You can even use TransformMap to project your multichannel map to a subset of channels!
let projection = TransformMap::new(&reader, |(num, _): (i32, char)| num);
projection.for_each(&iter_extent, |_p, num| assert_eq!(num, 1));Level of Detail
As I mentioned in the last release notes, level of detail is an important feature for scaling up voxel rendering solutions to large maps without wasting memory on high-resolution render resources that are far from the camera. As such, this release includes several new tools for implementing LOD.
While LOD support is very new, it might seem a little obtuse. As I continue integrating this code into the building-blocks editor, I will learn more about how the interface should be shaped. For now, the best resource for learning about this LOD code is the lod_terrain example.
ChunkPyramid and ChunkDownsampler
The core of the LOD solution is to support downsampling chunks into lower levels of detail. The ChunkPyramid is where these downsampled chunks can live. It can be thought of like a sparse mipmap; it is essentially just a vector of ChunkMaps. All of the levels have the same chunk shape, but at lower levels of detail, each chunk covers a larger area of the map (hence having a lower resolution).
Pyramids can be used with any ChunkDownsampler implementation; we currently have a PointDownsampler, which very simply takes one point from each 2x2x2 extent, and the SdfMeanDownsampler, which takes the mean of the signed distances in each 2x2x2 extent. However, ChunkPyramid is currently just a single-channel storage, so you can only downsample one channel per pyramid. This may change in the future. There is a provided workaround for downsampling one channel from a multichannel ChunkMap. You just need to provide a closure that wraps chunks in the proper TransformMap projection. There is a test of this in the chunk_pyramid module if you'd like to see how it's done.
OctreeChunkIndex
The recommended way of managing multiresolution data is to have a ChunkPyramid and a corresponding OctreeChunkIndex which tracks the set of chunks using an OctreeSet for every "super chunk." A super chunk is essentially just a chunk of space indexed by a single OctreeSet.
The reason for the index is for speeding up iteration over large regions of space. Rather than taking a large Extent and checking every single overlapping chunk key (requiring a hash), you can iterate over an OctreeSet, requiring only one hash per level of detail. It's very straightforward to construct an index by calling OctreeChunkIndex::index_chunk_map on a ChunkMap.
Sd8 and Sd16 Signed Distance Types
Previously most of the examples in the building-blocks repo used f32 for signed distances. However, much of the dynamic range of f32 is wasted in this particular use case, since samples of an SDF only need to represent the range [-1.0, 1.0] of distances from the isosurface; any samples further away are not used for surface extraction.
So now we have the Sd8 and Sd16 fixed precision data types, capable of representing numbers with precision 2 / 2^8 and 2 / 2^16 respectively. This will save a lot of space over f32s on large voxel maps.
New Examples
LOD Terrain
Now that we have preliminary support for LOD clipmaps, there is an example of this running in Bevy. And Bevy has a new WireframePlugin, which makes this example even cooler to look at. View it here.
Array Texture Materials
A common technique for texturing Minecraft-style voxels is to use a texture atlas in the form of an "array texture." This is essentially just a 3D texture where each layer has the texture for one block type. Thanks to a PR from @malmz, we now have an example of this!
Quad Mesh UVs
The "array texture" example also brought to light an issue with how UV coordinates were being generated for a Quad. Now Quad::simple_tex_coords has been moved to OrientedCubeFace::simple_tex_coords, and it supports flipping the U or V texture coordinate axes. This is useful for working with different graphics APIs, since OpenGL, Vulkan, and DirectX do not agree on the UV coordinate space.
A* Pathfinding
Thanks to a PR from @siler, the building_blocks_search crate now has an astar_path function for finding the optimal path between two points on a voxel grid.
Other Changes
Additions
ChunkMapBuilderhas become a trait. Feel free to implement your own builder. The providedChunkMapBuilderNxMworks for vanillaArraychunks.OctreeSet::add_extentandOctreeSet::subtract_extent. These are useful for efficiently adding or deleting large regions from a chunk index.
Modifications
- For small-key hash maps, the
fnvhasher has been replaced withahash, which is about 30% faster in our benchmarks. This improves random access performance onChunkMaps and also the overall performance ofOctreeSet. - The methods on
SerializableChunkshave changed to take an iterator of(key, chunk)pairs during serialization and fill a chunk storage on deserialization OctreeSet::emptyhas becomeOctreeSet::new_emptyand we now also haveOctreeSet::new_full- Access traits implemented on
Fntypes are now implemented on theFunctype, which is just a newtype for wrappingFn. This was necessary to avoid conflicting implementations.
Removals
- The
Chunktype has been replaced with theChunktrait. If you need extra metadata on your chunk type, you can implement theChunktrait. In order to use a custom chunk with theCompressibleChunkStorage, you also need to implement theCompression<Data=YourChunk>trait. FastChunkCompressionis no longer needed and has been removed.
Benchmark Results
These results come from running cargo bench --all on my PC with an Intel i5-4590 3.3 GHz CPU, using the stable rust v1.50 toolchain and LTO enabled. All benchmarks are single-threaded.
SHOW RESULTS
greedy_quads_terrace/8 time: [9.7631 us 9.9729 us 10.384 us]
greedy_quads_terrace/16 time: [65.749 us 66.223 us 66.648 us]
greedy_quads_terrace/32 time: [479.88 us 482.00 us 484.19 us]
greedy_quads_terrace/64 time: [3.7181 ms 3.7299 ms 3.7417 ms]
height_map_plane/8 time: [513.01 ns 516.43 ns 519.68 ns]
height_map_plane/16 time: [1.7189 us 1.7236 us 1.7291 us]
height_map_plane/32 time: [7.4892 us 7.5027 us 7.5169 us]
height_map_plane/64 time: [31.685 us 31.884 us 32.131 us]
surface_nets_sine_sdf/8 time: [14.929 us 15.055 us 15.180 us]
surface_nets_sine_sdf/16
time: [156.87 us 157.20 us 157.59 us]
surface_nets_sine_sdf/32
time: [1.1492 ms 1.1568 ms 1.1651 ms]
surface_nets_sine_sdf/64
time: [9.6957 ms 9.7798 ms 9.8669 ms]
sphere_surface/8 time: [12.738 us 12.816 us 12.905 us]
sphere_surface/16 time: [103.64 us 104.24 us 105.00 us]
sphere_surface/32 time: [791.39 us 796.47 us 801.70 us]
flood_fill_sphere/16 time: [321.93 us 322.25 us 322.61 us]
flood_fill_sphere/32 time: [2.1499 ms 2.1569 ms 2.1648 ms]
flood_fill_sphere/64 time: [15.533 ms 15.647 ms 15.764 ms]
array_for_each_stride/16
time: [1.8162 us 1.8305 us 1.8439 us]
array_for_each_stride/32
time: [16.931 us 16.960 us 16.994 us]
array_for_each_stride/64
time: [154.09 us 155.21 us 156.32 us]
array_for_each_point/16 time: [2.7757 us 2.7983 us 2.8215 us]
array_for_each_point/32 time: [25.216 us 25.398 us 25.568 us]
array_for_each_point/64 time: [204.42 us 205.38 us 206.55 us]
array_for_each_point_and_stride/16
time: [3.6217 us 3.6543 us 3.6864 us]
array_for_each_point_and_stride/32
time: [33.404 us 33.456 us 33.512 us]
array_for_each_point_and_stride/64
time: [304.74 us 306.71 us 308.61 us]
array_point_indexing/16 time: [4.9270 us 4.9656 us 5.0093 us]
array_point_indexing/32 time: [45.621 us 45.844 us 46.110 us]
array_point_indexing/64 time: [402.73 us 405.25 us 408.02 us]
array_copy/16 time: [2.0235 us 2.0354 us 2.0504 us]
array_copy/32 time: [18.726 us 18.750 us 18.779 us]
array_copy/64 time: [154.43 us 154.61 us 154.81 us]
chunk_hash_map_for_each_point/16
time: [3.8854 us 3.8886 us 3.8921 us]
chunk_hash_map_for_each_point/32
time: [30.728 us 30.814 us 30.909 us]
chunk_hash_map_for_each_point/64
time: [246.98 us 248.12 us 249.30 us]
chunk_hash_map_point_indexing/16
time: [53.407 us 53.604 us 53.825 us]
chunk_hash_map_point_indexing/32
time: [437.93 us 441.17 us 444.57 us]
chunk_hash_map_point_indexing/64
time: [3.4068 ms 3.4142 ms 3.4227 ms]
chunk_hash_map_visit_chunks_sparse/128
time: [7.4325 us 7.4942 us 7.5567 us]
chunk_hash_map_visit_chunks_sparse/256
time: [72.727 us 73.037 us 73.395 us]
chunk_hash_map_visit_chunks_sparse/512
time: [1.6484 ms 1.6653 ms 1.6819 ms]
chunk_hash_map_copy/16 time: [1.6828 us 1.6924 us 1.7037 us]
chunk_hash_map_copy/32 time: [12.555 us 12.655 us 12.758 us]
chunk_hash_map_copy/64 time: [106.73 us 107.89 us 109.23 us]
compressible_chunk_map_point_indexing/16
time: [57.566 us 57.898 us 58.251 us]
compressible_chunk_map_point_indexing/32
time: [482.42 us 486.15 us 489.81 us]
compressible_chunk_map_point_indexing/64
time: [3.7446 ms 3.7674 ms 3.7899 ms]
decompress_array_with_bincode_lz4/16
time: [13.053 us 13.150 us 13.250 us]
decompress_array_with_bincode_lz4/32
time: [96.656 us 97.476 us 98.356 us]
decompress_array_with_bincode_lz4/64
time: [813.80 us 820.56 us 827.36 us]
decompress_array_with_fast_lz4/16
time: [5.5177 us 5.5565 us 5.5943 us]
decompress_array_with_fast_lz4/32
time: [32.380 us 32.426 us 32.477 us]
decompress_array_with_fast_lz4/64
time: [253.46 us 254.01 us 254.60 us]
octree_from_array3_sphere/16
time: [20.653 us 20.673 us 20.694 us]
octree_from_array3_sphere/32
time: [154.54 us 155.86 us 157.27 us]
octree_from_array3_sphere/64
time: [1.1856 ms 1.1967 ms 1.2083 ms]
octree_from_array3_full/16
time: [15.459 us 15.479 us 15.501 us]
octree_from_array3_full/32
time: [122.86 us 122.99 us 123.13 us]
octree_from_array3_full/64
time: [990.73 us 991.75 us 992.84 us]
octree_visit_branches_and_leaves_of_sphere/16
time: [6.0710 us 6.0827 us 6.0972 us]
octree_visit_branches_and_leaves_of_sphere/32
time: [43.059 us 43.208 us 43.387 us]
octree_visit_branches_and_leaves_of_sphere/64
time: [145.64 us 145.82 us 146.02 us]
octree_visit_branch_and_leaf_nodes_of_sphere/16
time: [14.560 us 14.576 us 14.594 us]
octree_visit_branch_and_leaf_nodes_of_sphere/32
time: [85.230 us 85.339 us 85.461 us]
octree_visit_branch_and_leaf_nodes_of_sphere/64
time: [310.08 us 310.36 us 310.65 us]
point_downsample3/16 time: [1.0997 us 1.1035 us 1.1078 us]
point_downsample3/32 time: [8.3239 us 8.3351 us 8.3484 us]
point_downsample3/64 time: [64.942 us 65.026 us 65.122 us]
sdf_mean_downsample3/16 time: [10.986 us 10.998 us 11.012 us]
sdf_mean_downsample3/32 time: [84.638 us 84.742 us 84.861 us]
sdf_mean_downsample3/64 time: [668.83 us 669.47 us 670.19 us]
sdf_mean_downsample_chunk_pyramid_with_index/1
time: [56.661 us 56.731 us 56.809 us]
sdf_mean_downsample_chunk_pyramid_with_index/2
time: [133.42 us 133.57 us 133.73 us]
sdf_mean_downsample_chunk_pyramid_with_index/4
time: [826.90 us 827.86 us 829.00 us]
sdf_mean_downsample_chunk_pyramid_with_index/8
time: [6.4673 ms 6.4744 ms 6.4824 ms]