### 2 unstable releases

0.2.0 | Nov 7, 2020 |
---|---|

0.1.0 | Oct 26, 2020 |

#**71** in Images

Used in building-blocks

**MIT**license

140KB

3K
SLoC

# Building Blocks

Building Blocks is a voxel library for real-time applications.

Supported use cases include:

- memory-efficient storage of voxel maps
- voxel map serialization
- generating meshes
- isosurface
- cubic / blocky
- height maps

- accelerated spatial queries
- ray casting
- range queries (TODO)

- procedural generation
- sampling signed distance fields
- generating height maps from fractal noise (TODO)

- pathfinding

## Short Code Example

The code below samples a signed distance field and generates a mesh from it.

`use` `building_blocks``::``{`
`prelude``::``*``,`
`mesh``::``{`SurfaceNetsBuffer`,` surface_nets`}``,`
`procgen``::``signed_distance_fields``::`sphere`,`
`}``;`
`let` center `=` PointN`(``[``25.``0``;` `3``]``)``;`
`let` radius `=` `10.``0``;`
`let` sphere_sdf `=` `sphere``(`center`,` radius`)``;`
`let` extent `=` `Extent3i``::`from_min_and_shape`(`PointN`(``[``0``;` `3``]``)``,` PointN`(``[``50``;` `3``]``)``)``;`
`let` `mut` samples `=` `Array3``::`fill_with`(`extent`,` `&`sphere_sdf`)``;`
`let` `mut` mesh_buffer `=` `SurfaceNetsBuffer``::`new`(``)``;`
`surface_nets``(``&`samples`,` samples`.``extent``(``)``,` `&``mut` mesh_buffer`)``;`

## Learning

The current best way to learn about the library is to read the documentation and examples. Clone the repo and run

`cargo`` doc`` --`open` --`all-features

There is plentiful documentation with examples.

Take a look in the

directory to see how Building Blocks can be used
in real applications.`examples /`

To run the benchmarks (using the "criterion" crate), go to the root of a crate
and run

.`cargo`` bench`

## Design Philosophy and Architecture

### Principles

The architecture of Building Blocks is driven by a few guiding principles:

**Real-Time Performance**- The primary use case for Building Blocks is using voxel technology within a video game. This means it needs to be fast. For example, we want to be able to generate meshes for millions of voxels per frame (16.6 ms).
- Critical algorithms must be benchmarked with Criterion so we can guide optimization with evidence.

**Composable APIs**- APIs are more powerful when they are generic. You will find many examples of generic APIs that require the input types to implement some traits.
- This is most prevalent in the storage crate, where we desire all of the
lattice map types to be accessible through the same core set of traits.
This results in a very powerful function,

, which works with all implementations of the`copy_extent`

and`ReadExtent`

traits.`WriteExtent`

**KISS (Keep It Simple Stupid)**- There are
*many*complex data structures and algorithms used in voxel technology. While they certainly all serve a purpose, it is not feasible for contributors to understand and implement all of them at the very inception of this project. - Any increase in complexity of this library, usually by adding a new data structure or algorithm, must solve a specific problem for end users. And we should find the simplest solution to that problem such that the increase in complexity is minimal.
- You might find your favorite voxel technology missing from the existing feature set or road map. This is probably just because no one has found a need for it yet. We are open to contributions, but keep the KISS principle in mind when considering what problem you are solving.

- There are
**Minimal Dependencies**- Rather than taking on large dependencies like nalgebra, ncollide, ndarray, etc, we will first try to implement the simplest version of what is needed ourselves.
- Integrations with 3rd party dependencies are exposed under feature flags to avoid bloat.
- There is always a judgement call when determining if we should take on a dependency. The main considerations are build time, difficulty of "rolling our own," and of course the full feature set and performance of the dependency.

### Architecture

Noting the above principles, here is a quick summary of the design decisions which brought about the current feature set:

**Mathematical Data Types**- A voxel world can be modeled mathematically as a function over a
3-dimensional integer lattice, i.e. with domain Z^3. Thus we have a

type which serves as the main coordinate set.`Point3i` - When considering a subset of the voxel world, in coordinates, we very
commonly desire an axis-aligned bounding box, which may contain any bounded
subset. It is very simple to iterate over all of the points in such a box,
find the intersection of two boxes, or check if the box contains a point. We
call these boxes by the name

.`Extent3i`

- A voxel world can be modeled mathematically as a function over a
3-dimensional integer lattice, i.e. with domain Z^3. Thus we have a
**Storage**- Any extent of the voxel world function can be simply represented as a
3-dimensional array. We call it

. Arrays contain some data at every point in some`Array3`

. The most common operations on arrays are iteration over extents and random access. These operations should be very fast, and we have benchmarks for them.`Extent3i` - Obviously we can't store an infinite voxel world, so we partition the
lattice into chunks, each of which is an

of the same cubic shape. The container for these chunks is called a`Array3`

.`ChunkMap3` - With both the

and`Array3`

serving similar purposes, we've made them implement a common set of traits for data access. This includes random access, iteration, and copying.`ChunkMap3` - When you have large voxel worlds, it's not feasible to store a lot of unique
data for every voxel. A common strategy is to have each voxel labeled with
some "type." If you only want to use a single byte for each voxel's type,
then you can have up to 255 types of voxels. Then each type can have a large
amount of data associated with it in a "palette" container. But we still
want to be able to use our common set of access traits to read the voxel
type data. Thus, we have a type called

which implements those traits.`TransformMap`

wraps some other lattice map, referred to as the "delegate," and any access will first go through the delegate, then be transformed by an arbitrary`TransformMap`

chosen by the programmer. This transformation closure is where we can access the palette based on the voxel type provided by the delegate map.`Fn``(`T`)``->`S - Even with only a couple bytes per voxel, we can still use up lots of memory
on large voxel maps. The simplest way to save memory without changing the
underlying array containers was to use compression inside of the

. So arrays now support an LZ4 compression scheme. While LZ4 has a very quick decompression rate, the`ChunkMap`

still keeps an LRU cache of uncompressed chunks for efficiency. Cache eviction and compression is done on-demand, so you can choose to ignore this feature if you are not worried about memory usage.`ChunkMap`

- Any extent of the voxel world function can be simply represented as a
3-dimensional array. We call it
**Meshing**- There are many ways of generating meshes from voxel data. You can make each occupied voxel into a cube, which gives the classis Minecraft aesthetic. Or you can store geometric information, commonly referred to as "signed distances" or "hermite data," at each voxel in order to approximate smooth surfaces. We would like to support both schemes.
- For cubic meshes, the fastest algorithm we know of to produce efficient meshes is coined as "Greedy Meshing" by the 0fps blog.
- For smooth meshes, the most pervasive algorithm is Marching Cubes. However, we found the Naive Surface Nets algorithm to be simpler to implement and just as efficient, if not moreso.
- We've also considered the Dual Contouring family of algorithms for smooth meshing. While they offer more control over the shape of a mesh, they are also more complex and thus expensive to compute. For now, we've decided not to pursue these algorithms, but we are open to any contributions in this area.
- While 3D voxel data is required for meshes with arbitrary topologies, one
can choose to constrain themselves to a simpler planar topology and reap
performance benefits, both in terms of space and time. A surface with planar
topology can be modeled with a 2-dimensional function commonly referred to
as a "height map." While we could represent a height map with an

where one of the dimensions has size 1, it leads to awkward code. Thus, we generalized all of the core data types to work in both 2 and 3 dimensions, which gives us the`Array3`

type, capable of cleanly representing a height map. We've also implemented a specialized meshing algorithm for height maps.`Array2`

**Accelerated Spatial Queries**- Our first voxel game prototypes utilized the ncollide3d crate and it's

(dynamic bounding volume tree) structure for doing raycasting. Unforunately, storing an`DBVT`

for every voxel cost us 6`AABB``<``f32``>`

s or 24 bytes per voxel. That simply doesn't scale. So as a replacement, we implemented the`f32`

and`Octree`

types. The`OctreeDBVT`

is essentially a hierarchical bitset, making it very memory efficient; it doesn't contain any voxel data, but it can tell you whether a`Octree`

is contained in the set. More importantly, it supports a visitor API that can be used for spatial queries like raycasting. Since the`Point3i`

has a limited size, we also provide the`Octree`

, which is essentially a`OctreeDBVT`

which may contain an arbitrary number of`DBVT`

s.`Octree`

requires taking on the`OctreeDBVT`

dependency. We decided this was acceptable for the time being, since we don't have spare time to implement our own efficient`ncollide3d`

.`DBVT`

- Our first voxel game prototypes utilized the ncollide3d crate and it's

## Roadmap

- v0.1: Publish on crates.io with enough core functionality to provide interesting examples in a popular Rust game engine (Bevy)

from height map`Octree`- procedurally generated heightmaps for terrain
- fractal noise
- hydraulic erosion

- Bevy integration
- ECS systems for dynamic meshing

- Rapier3d integration
- level of detail
- stitching chunks on LoD boundaries
- geomorphing

- GPU acceleration of core algorithms
- SIMD variants of core data types

#### Dependencies

~7.5MB

~120K SLoC