Skip to content
This repository has been archived by the owner on Nov 13, 2023. It is now read-only.

building-blocks v0.5.0
Compare
Choose a tag to compare
@bonsairobo bonsairobo released this 08 Feb 04:18
· 813 commits to main since this release
v0.5.0
2d47e8f

Development Status Update

It's been a while since the last release in December. I hope everyone enjoyed their holidays!

Level of Detail Prototype

TL;DR: Check out this video: https://www.youtube.com/watch?v=6vSz86w3Zjk

My recent focus has been on implementing a level of detail scheme for voxel meshes. If you're not familiar with the problem, generating voxel meshes using the same grid resolution everywhere on a very large map, you will quickly run out of GPU resources, and it's very wasteful, because terrain in the distance will only take up a small number of pixels with many many triangles.

At first, I was looking into using adaptive distance fields and a recursive dual contouring algorithm for meshing. After putting a lot of time into this on the adf-experiment branch, I wasn't pleased with the performance; it was significantly slower than the array-based surface_nets meshing. Although I did learn a lot about meshing across varying levels of detail. Perhaps I will come back to this idea later.

My next idea was to use a clipmap of chunks at varying levels of detail, which would allow me to continue meshing arrays. This required a few new features:

  1. Chunk downsampling
  2. An octree of chunks to do optimal detection of LOD changes as the camera moves
  3. Transition meshing on LOD boundaries

(1) and (2) are mostly done, and you can see how they work in the lod-terrain prototype:

https://www.youtube.com/watch?v=6vSz86w3Zjk

The code for this prototype is mostly found here: https://github.com/bonsairobo/lod-terrain

It relies on the experiment-clipmap branch of the building-blocks repo. The transition meshing is yet to be implemented, and so you can occasionally see some hairline cracks in the LOD terrain. Once I'm happy with the prototype, the plan is to integrate this LOD scheme into the building-blocks-editor, then merge the experiment-clipmap branch into main to provide some code to make managing LOD simple.

Release Highlights

Octree Improvements

In order to facilitate the clipmap, many improvements have been made to the OctreeSet data structure. It is now possible to visit sub-octants of full octants with an OctreeVisitor, and the Location type enables a "nested visitor" pattern, which is used to great effect in the clipmap code. This allows you to use one closure to locate a subtree, then run a separate closure on that subtree, like so:

octree.visit_branches_and_leaves(&mut |location: &Location| {
    if some_condition(location) {
        // Found a particular subtree, now narrow the search using a different algorithm.
        location.visit_all_octants(&octree, &mut |sub_location: &Location| {
            do_something(sub_location.octant());

            VisitStatus::Continue
        });

        VisitStatus::ExitEarly
    } else {
        VisitStatus::Continue
    }
});

ArrayN Generic Storage

Arrays can now be created with any kind of slice storage that implements Deref<[T]> or DerefMut<[T]>.

let mut data = [1; 64 * 64 * 64];
let extent = Extent3i::from_min_and_shape(Point3i::ZERO, PointN([64; 3]));
let mut stack_array = Array3::new(extent, &mut data[..]);

More PointN Ops

Point2i and Point3i now support some vectorized logical operations, like Shl, Shr, BitAnd, BitOr, BitXor, Not, etc.

sdfu Integration

The signed_distances module has been superceded by an integration with the sdfu crate. Now you can create complex SDFs and easily sample them:

use building_blocks::core::sdfu;

let sdf = sdfu::Sphere::new(0.45)
        .subtract(sdfu::Box::new(PointN([0.25, 0.25, 1.5])))
        .union_smooth(
            sdfu::Sphere::new(0.3).translate(PointN([0.3, 0.3, 0.0])),
            0.1,
        )
        .union_smooth(
            sdfu::Sphere::new(0.3).translate(PointN([-0.3, 0.3, 0.0])),
            0.1,
        );

sdfu

Amanatides and Woo Ray Casting

Because it was simple and I thought some people might want to use it, I implemented the algorithm from this paper. Now you can easily traverse a grid along a given ray like so:

let mut traversal = GridRayTraversal3::new(start, velocity);
while some_condition(traversal.current_voxel()) {
    traversal.step();
}

Change Log

Additions

  • The traits in sdfu::mathtypes have been implemented for Point3f. sdfu is now the recommended solution for constructing complex SDFs. See the examples.
  • GetRef and ForEachRef traits which provide access to &T in a lattice map
  • GridRayTraversal2 and GridRayTraversal3 are implementations of the Amanatides and Woo algorithm
  • New APIs for octrees:
    • OctreeSet::add_extent (TODO: subtract_extent)
    • OctreeSet::visit_all_octants
    • Octant::visit_self_and_descendants
  • von_neumann_flood_fill3 is a slightly optimized 3D flood fill using scanline search
  • greedy_quads now supports transparent voxels via the IsOpaque trait
  • Several math operations have been implemented for PointN, including
    • Mul<Self> (and made scalar multiplication symmetric)
    • Rem
    • Shl, Shr
    • BitAnd, BitOr, BitXor, Not
    • min_component and max_component (via MinMaxComponent trait)
  • PointN::fill lets you construct a point with all dimensions at the same value
  • Some new APIs for ChunkMap:
    • visit_chunks
    • visit_mut_chunks
    • visit_occupied_chunks
    • visit_occupied_mut_chunks
    • get_mut_chunk_or_insert_ambient
  • CompressibleChunkMap::reader allows for easy construction of a CompressibleChunkMapReader.

Modifications

  • ArrayN is now generic over the storage of its values, as long as the storage implements Deref<[T]> or DerefMut<[T]>. This means you can use any kind of slice pointer: &[T], &mut [T], Box<[T]>, Rc<[T]>, Arc<[T]>, Cow<[T]>, etc.
  • The (Octant, bool) parameters in OctreeVisitor have been replaced with Location to enable the "nested visitor" pattern
  • OctreeSet::visit has been renamed to OctreeSet::visit_branches_and_leaves to differentiate from OctreeSet::visit_all_octants
  • ChunkMap can now only be constructed via the ChunkMapBuilder. This was done to ensure that ChunkMap isn't accidentally created with a storage type that doesn't satisfy the ChunkReadStorage or ChunkWriteStorage traits.
  • For simplicity and consistency, wherever possible, we now pass PointN as a parameter by move/copy instead of by borrow.
  • A MergeStrategy trait has been extracted from greedy_quads in an effort to provide more generic forms of quad merging. This will eventually be used to support certain kinds of voxel lighting algorithms.
  • Surface normal estimation in surface_nets has been improved by using bilinear interpolation of the distance field's partial derivatives, based on where the surface positions is located within a voxel.
  • The SignedDistance trait is now a supertrait of Into<f32>
  • surface_nets now takes a voxel_size parameter to scale the mesh positions

Removals

  • The building_blocks_vox crate has been removed. Functionality now lives in building_blocks_storage because it allows us to define the decode_vox method directly on Array3<VoxColor>.
  • The building_blocks_image crate has been removed. Functionality now lives in building_blocks_storage because it allows us to impl From<Im> for Array2.
  • The building_blocks_procgen crate has been removed. It only had some common signed distance functions, and these have been replaced with the sdfu integration.
  • Some ChunkMap methods were deemed unnecessary or trivial:
    • get_chunk_containing_point
    • get_mut_chunk_containing_point
    • get_mut_point_or_insert_chunk_with

Benchmark Results

I'm going to start posting the criterion benchmark results so it's easier to see performance changes between releases.

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.49 toolchain and LTO enabled. All benchmarks are single-threaded.

greedy_quads_terrace/8  time:   [10.854 us 10.879 us 10.908 us]
greedy_quads_terrace/16 time:   [71.589 us 71.679 us 71.768 us]
greedy_quads_terrace/32 time:   [518.32 us 518.98 us 519.69 us]
greedy_quads_terrace/64 time:   [4.1920 ms 4.2008 ms 4.2101 ms]

height_map_plane/8      time:   [435.84 ns 436.48 ns 437.12 ns]
height_map_plane/16     time:   [1.7318 us 1.7340 us 1.7363 us]
height_map_plane/32     time:   [8.4769 us 8.4862 us 8.4960 us]
height_map_plane/64     time:   [31.885 us 31.974 us 32.078 us]

surface_nets_sine_sdf/8 time:   [12.561 us 12.577 us 12.594 us]
surface_nets_sine_sdf/16
                        time:   [147.24 us 147.44 us 147.65 us]
surface_nets_sine_sdf/32
                        time:   [1.0928 ms 1.0946 ms 1.0966 ms]
surface_nets_sine_sdf/64
                        time:   [9.5181 ms 9.5401 ms 9.5633 ms]

sphere_surface/8        time:   [14.841 us 14.856 us 14.874 us]
sphere_surface/16       time:   [114.60 us 114.74 us 114.88 us]
sphere_surface/32       time:   [863.09 us 864.74 us 866.56 us]

flood_fill_sphere/16    time:   [406.85 us 407.23 us 407.62 us]
flood_fill_sphere/32    time:   [2.7514 ms 2.7549 ms 2.7586 ms]
flood_fill_sphere/64    time:   [20.050 ms 20.076 ms 20.102 ms]

array_for_each_stride/16
                        time:   [1.7999 us 1.8022 us 1.8045 us]
array_for_each_stride/32
                        time:   [16.952 us 16.972 us 16.991 us]
array_for_each_stride/64
                        time:   [147.88 us 148.08 us 148.32 us]

array_for_each_point/16 time:   [13.486 us 13.502 us 13.518 us]
array_for_each_point/32 time:   [131.28 us 131.42 us 131.56 us]
array_for_each_point/64 time:   [1.1749 ms 1.1836 ms 1.1924 ms]

array_for_each_point_and_stride/16
                        time:   [3.9392 us 3.9436 us 3.9481 us]
array_for_each_point_and_stride/32
                        time:   [38.403 us 38.442 us 38.482 us]
array_for_each_point_and_stride/64
                        time:   [337.60 us 337.91 us 338.23 us]

array_point_indexing/16 time:   [4.0816 us 4.0862 us 4.0907 us]
array_point_indexing/32 time:   [42.641 us 42.689 us 42.741 us]
array_point_indexing/64 time:   [350.70 us 351.01 us 351.34 us]

array_copy/16           time:   [2.1374 us 2.1396 us 2.1419 us]
array_copy/32           time:   [18.777 us 18.798 us 18.819 us]
array_copy/64           time:   [477.50 us 477.97 us 478.44 us]

chunk_hash_map_for_each_point/16
                        time:   [20.676 us 20.702 us 20.731 us]
chunk_hash_map_for_each_point/32
                        time:   [165.35 us 165.50 us 165.66 us]
chunk_hash_map_for_each_point/64
                        time:   [1.3206 ms 1.3218 ms 1.3231 ms]

chunk_hash_map_point_indexing/16
                        time:   [133.67 us 133.78 us 133.90 us]
chunk_hash_map_point_indexing/32
                        time:   [1.1237 ms 1.1255 ms 1.1277 ms]
chunk_hash_map_point_indexing/64
                        time:   [8.3298 ms 8.3408 ms 8.3521 ms]

chunk_hash_map_copy/16  time:   [1.6897 us 1.6915 us 1.6934 us]
chunk_hash_map_copy/32  time:   [12.277 us 12.292 us 12.306 us]
chunk_hash_map_copy/64  time:   [103.57 us 103.71 us 103.86 us]

compressible_chunk_map_point_indexing/16
                        time:   [134.74 us 134.86 us 134.98 us]
compressible_chunk_map_point_indexing/32
                        time:   [1.1032 ms 1.1041 ms 1.1051 ms]
compressible_chunk_map_point_indexing/64
                        time:   [8.3600 ms 8.3708 ms 8.3820 ms]

decompress_array_with_bincode_lz4/16
                        time:   [28.234 us 28.281 us 28.329 us]
decompress_array_with_bincode_lz4/32
                        time:   [142.74 us 142.93 us 143.13 us]
decompress_array_with_bincode_lz4/64
                        time:   [1.1786 ms 1.1815 ms 1.1847 ms]

decompress_array_with_fast_lz4/16
                        time:   [5.1769 us 5.1860 us 5.1964 us]
decompress_array_with_fast_lz4/32
                        time:   [32.425 us 32.532 us 32.645 us]
decompress_array_with_fast_lz4/64
                        time:   [263.51 us 264.54 us 265.67 us]

octree_from_array3_sphere/16
                        time:   [23.403 us 23.435 us 23.467 us]
octree_from_array3_sphere/32
                        time:   [170.15 us 170.34 us 170.54 us]
octree_from_array3_sphere/64
                        time:   [1.2522 ms 1.2532 ms 1.2544 ms]

octree_from_array3_full/16
                        time:   [16.656 us 16.673 us 16.691 us]
octree_from_array3_full/32
                        time:   [132.79 us 132.94 us 133.10 us]
octree_from_array3_full/64
                        time:   [1.0669 ms 1.0680 ms 1.0692 ms]

octree_visit_all_octants_of_sphere/16
                        time:   [7.7433 us 7.7551 us 7.7673 us]
octree_visit_all_octants_of_sphere/32
                        time:   [63.031 us 63.116 us 63.203 us]
octree_visit_all_octants_of_sphere/64
                        time:   [209.16 us 209.62 us 210.08 us]

octree_visit_all_octant_nodes_of_sphere/16
                        time:   [14.173 us 14.187 us 14.200 us]
octree_visit_all_octant_nodes_of_sphere/32
                        time:   [101.78 us 101.88 us 101.98 us]
octree_visit_all_octant_nodes_of_sphere/64
                        time:   [353.05 us 354.28 us 355.62 us]
Assets 2
Loading