#voxel

building_blocks_mesh

Fast meshing algorithms for voxel data structures

9 releases (breaking)

0.7.1 Sep 23, 2021
0.7.0 Jun 14, 2021
0.6.0 Mar 21, 2021
0.5.0 Feb 8, 2021
0.1.0 Oct 26, 2020

#317 in Data structures

Download history 28/week @ 2022-08-07 20/week @ 2022-08-14 21/week @ 2022-08-21 10/week @ 2022-08-28 45/week @ 2022-09-04 16/week @ 2022-09-11 13/week @ 2022-09-18 19/week @ 2022-09-25 30/week @ 2022-10-02 13/week @ 2022-10-09 11/week @ 2022-10-16 20/week @ 2022-10-23 32/week @ 2022-10-30 36/week @ 2022-11-06 20/week @ 2022-11-13 15/week @ 2022-11-20

109 downloads per month
Used in building-blocks

MIT license

415KB
9K SLoC

building-blocks

Crates.io Docs.rs license Crates.io Discord

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

Project Status

This crate is in maintenance mode. I have extracted the most useful features into their own crates with fewer overall dependencies. Rather than providing generic APIs centered around a bespoke Array type, the new crates provide simpler APIs that only require slice [T] data.

The list of new crates is here: https://github.com/stars/bonsairobo/lists/my-stack

There are currently no plans to resume development on building-blocks, and users should consider migrating to the new crates. These crates will be actively maintained as their development is driven by the feldspar project.

LOD Terrain

We focus on generally useful data structures and algorithms. Features include:

  • 2D and 3D data storage
    • Array with structure-of-arrays (SoA) storage of multiple data channels per spatial dimension
    • ChunkTree is a quadtree (2D) or octree (3D) with generic chunks and chunk storage
    • ChunkDb for compressed, persistent voxel worlds, backed by the sled embedded database
  • level of detail
    • ChunkDownsampler trait controls how new samples are generated from LOD N into LOD N+1
    • ChunkTree can act as a clipmap for keeping high detail close to a focal point, generating events to trigger:
      • chunk generation / loading
      • chunk split / merge when desired sample rate changes
      • chunk eviction
  • mesh generation
    • Surface Nets isosurface extraction
    • Minecraft-style greedy meshing
    • height maps
  • spatial queries
    • ray and ball casting against octrees with ncollide3d
    • Amanatides and Woo ray grid traversal
    • pathfinding
  • procedural generation
    • sampling signed distance fields
    • constructive solid geometry with sdfu

Short Code Example

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

use building_blocks::{
    core::sdfu::{Sphere, SDF},
    prelude::*,
    mesh::{SurfaceNetsBuffer, surface_nets},
};

let center = Point3f::fill(25.0);
let radius = 10.0;
let sphere_sdf = Sphere::new(radius).translate(center);

let extent = Extent3i::from_min_and_shape(Point3i::ZERO, Point3i::fill(50));
let mut samples = Array3x1::fill_with(extent, |p| sphere_sdf.dist(Point3f::from(p)));

let mut mesh_buffer = SurfaceNetsBuffer::default();
let voxel_size = 2.0; // length of the edge of a voxel
let estimate_normals = true; // use the SDF to estimate normals instead of flat shading
surface_nets(&samples, samples.extent(), voxel_size, estimate_normals, &mut mesh_buffer);

Learning

Design and Architecture

There is a terse design doc that gives an overview of design decisions made concerning the current architecture. You might find this useful as a high-level summary of the most important pieces of code.

Docs and Examples

The current best way to learn about the library is to read the documentation and examples. For the latest stable docs, look here. For the latest unstable docs, clone the repo and run

cargo doc --open

There is plentiful documentation with examples. Take a look in the examples/ directory to see how Building Blocks can be used in real applications.

Getting Started

This library is organized into several crates. The most fundamental are:

  • core: lattice point and extent data types
  • storage: storage for lattice maps, i.e. functions defined on Z^2 and Z^3

Then you get extra bits of functionality from the others:

  • mesh: 3D mesh generation algorithms
  • search: search algorithms on lattice maps

To learn the basics about lattice maps, start with these doc pages:

Benchmarks

To run the benchmarks (using the "criterion" crate), go to the root of a crate and run cargo bench. As of version 0.5.0, all benchmark results are posted in the release notes.

Configuration

LTO

It is highly recommended that you enable link-time optimization when using building-blocks. It will improve the performance of critical algorithms like meshing by up to 2x. Just add this to your Cargo.toml:

[profile.release]
lto = "thin"

Cargo Features

Building Blocks is organized into several crates, some of which are hidden behind features, and some have features themselves, which get re-exported by the top-level crate. Some features are enabled by default. You can avoid taking unnecessary dependencies by declaring default-features = false in your Cargo.toml:

[dependencies.building-blocks]
version = "0.7"
default-features = false
features = ["foo", "bar"]

Math Type Conversions

The PointN types have conversions to/from glam, nalgebra, cgmath and mint types by enabling the corresponding feature.

Compression Backends and WASM

Chunk compression supports two backends out of the box: Lz4 and Snappy. They are enabled with the "lz4" and "snappy" features. "lz4" is the default, but it relies on a C++ library, so it's not compatible with WASM. But Snappy is pure Rust, so it can! Just use default-features = false and add "snappy" to you features list.

Chunk Databases

For persistent voxel worlds that support edits, it's useful to have an embedded database for crash-consistent save state. We've chosen to use the sled crate. When you enable the sled feature, you will get access to a ChunkDb type that supports reading and writing compressed chunk data. And because sled does not yet support incremental backups (AKA snapshots), we've also implemented our own snapshot scheme in a separate sled-snapshots crate which backs a VersionedChunkDb. This database schema only stores the changes (deltas) between versions, so you don't have to store an entire map in every save.

VOX Files

".VOX" files are supported via the vox-format crate. Enable the vox-format feature to get the VoxModelBuffer trait impl for Array3x1, which allows you to read VOX files directly into an array.

Images

Arrays can be converted to ImageBuffers and constructed from GenericImageViews from the image crate. Enable the image feature to expose the generic encode_image function and From<Im> where Im: GenericImageView impl.

Signed Distance Field Utilities (sdfu)

The sdfu crate provides convenient APIs for constructive solid geometry operations. By enabling this feature, the PointN types will implement the sdfu::mathtypes traits in order to be used with these APIs. The sdfu crate also gets exported under building_blocks::core::sdfu.

Development

We prioritize work according to the project board.

If you'd like to make a contribution, please first read the design philosophy and contribution guidelines.

License: MIT

Dependencies

~2.1–3MB
~63K SLoC