Module building_blocks_storage::octree

The OctreeSet type is a memory-efficient set of points organized hierarchically.

Use Cases

The OctreeSet has many uses.

One possible use case is to construct one using OctreeSet::from_array3, then insert it into an OctreeDBVT in order to perform spatial queries like raycasting.

You might also use an OctreeSet as a chunk index, where each point represents a single chunk. This representation is useful for level of detail algorithms like clipmap traversal because inner nodes may correspond to downsampled chunks stored in a separate structure.

Traversal

OctreeSet supports two modes of traversal. One is using the visitor pattern via OctreeVisitor. You can either visit just the branches and leaves, or you can also visit full sub-octants of a leaf octant.

Nested Traversal

use building_blocks_core::prelude::*;
use building_blocks_storage::{octree::*, prelude::*};

let extent = Extent3i::from_min_and_shape(PointN([0; 3]), PointN([32; 3]));
let voxels = Array3::fill(extent, true); // boring example
let octree = OctreeSet::from_array3(&voxels, Extent3i::from_min_and_shape(PointN([8; 3]), PointN([16; 3])));

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 |_location: &Location| {
            VisitStatus::Continue
        });

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

The other form of traversal is "node-based," which is slightly less efficient and more manual but also more flexible. See the OctreeSet::root_node, OctreeSet::child_node, and OctreeNode documentation for details.

Structs

Location	An opaque handle for users to visit a sub-octree of an OctreeSet.
Octant	A cube-shaped extent which is an octant at some level of an octree. As a leaf node, it represents a totally full set of points.
OctreeNode	Represents a single non-empty octant in the octree. Used for manual traversal by calling OctreeSet::get_child.
OctreeSet	A sparse set of voxel coordinates (3D integer points). Supports spatial queries.

Enums

VisitStatus

Traits

OctreeVisitor