Struct eightfold::Octree

pub struct Octree<T, Idx: TreeIndex> { /* private fields */ }

A data structure for partitioning data in a 3D space.

Implementations

impl<T: LeafMerge, Idx: TreeIndex> Octree<T, Idx>

pub fn merge_branch(&mut self, branch_idx: Idx) -> Result<&T, Error<'_, Idx>>where
    usize: AsPrimitive<Idx>,

Collapse a branch into a leaf by merging all descendant leaf data.

All merges occur between leaf data at the same depth.

impl<T: LeafSample + Clone, Idx: TreeIndex> Octree<T, Idx>

pub fn sample_branch(&self, branch_idx: Idx) -> Result<T, Error<'_, Idx>>

Return the merged leaf data of the descendants of a specific branch.

pub fn sample_at(&self, point: &NodePoint<Idx>) -> Option<T>where
    T: Clone,
    Idx: Shl<Idx, Output = Idx> + ShlAssign<Idx> + From<u8> + Shr<u8, Output = Idx> + ClosedMul + ShrAssign<u8>,

Return the merged leaf data at a specific point.

impl<T, Idx: TreeIndex> Octree<T, Idx>

pub fn slice(&self, index: Idx) -> Result<TreeSlice<'_, T, Idx>, Error<'_, Idx>>

pub fn as_slice(&self) -> TreeSlice<'_, T, Idx>

impl<T, Idx: TreeIndex> Octree<T, Idx>

pub fn max_grid_size() -> Idx

The maximum grid size representable by this Octree

pub fn new() -> Self

Construct a new tree with a void root.

pub fn depth_of_unchecked(&self, node: Idx) -> Idx

The depth of the node at a specified index.

Panics

• node ∉ self.proxies

pub fn depth_of(&self, node: Idx) -> Result<Idx, Error<'_, Idx>>

The depth of the node at a specified index.

pub fn branch(&mut self, target: Idx) -> Result<&[Idx; 8], Error<'_, Idx>>where
    usize: AsPrimitive<Idx>,
    u8: AsPrimitive<Idx>,
    Range<Idx>: Iterator,

Divide a voxel into a branch, returning the indices of the new branch’s children.

If the target voxel is already a branch, no changes are made and the existing branch’s children are returned.

The children of a branch are always stored and given in Octant order.

pub fn void(&mut self, target: Idx) -> Vec<T>

Clear a voxel and clean up any data it represented. Leaf data is returned as a Vec, if any is removed.

If the voxel is a branch, the branch’s children are voided as well.

pub fn set_leaf(&mut self, target: Idx, data: T) -> Vec<T>where
    usize: AsPrimitive<Idx>,

Set the leaf data of a voxel and, if extant, return its previous leaf data.

If the voxel is a branch, the branch is voided first.

pub fn grow(&mut self, oct: Octant) -> Result<Idx, Error<'_, Idx>>where
    u8: AsPrimitive<Idx>,
    usize: AsPrimitive<Idx>,

Grow a tree by adding a parent branch to the old root. The old root becomes the octth child of the new root.

See Also

• Octant

pub fn voxel_at_unchecked(&self, p: &VoxelPoint<Idx>) -> Idxwhere
    Idx: Shr<u8, Output = Idx> + ShrAssign<u8> + PartialOrd + From<u8> + Shl<Idx, Output = Idx>,

Get the index of the deepest voxel encompassing a specific VoxelPoint.

Panics

• p ∉ 0..self.grid_size()

pub fn voxel_at<'data>(
    &self,
    p: &'data VoxelPoint<Idx>
) -> Result<Idx, Error<'data, Idx>>where
    Idx: Shr<u8, Output = Idx> + ShrAssign<u8> + PartialOrd + From<u8> + Shl<Idx, Output = Idx>,

Get the index of the deepest voxel encompassing a specific VoxelPoint.

Errors

• p ∉ 0..self.grid_size()

pub fn node_at(&self, p: &NodePoint<Idx>) -> Idxwhere
    Idx: Shl<Idx, Output = Idx> + ShlAssign<Idx> + From<u8> + Shr<u8, Output = Idx> + ClosedMul + ShrAssign<u8>,

Get the index of the deepest voxel encompassing a specific NodePoint.

pub fn upcast<NIdx: TreeIndex>(self) -> Octree<T, NIdx>where
    usize: AsPrimitive<Idx>,
    Idx: AsPrimitive<NIdx>,

Convert this tree to one with a wider index type.

pub fn defragment(&mut self)where
    usize: AsPrimitive<Idx>,

Clean proxy & leaf data by removing empty entries and updating stored indices.

pub fn compress(&mut self)where
    usize: AsPrimitive<Idx>,

Defragment & reallocate self such that only enough memory to store self is allocated.

pub fn leaf_unordered(&self) -> impl Iterator<Item = &T>

Iterate through all leaf data, from oldest to newest.

pub fn node_point_of_unchecked(&self, index: Idx) -> NodePoint<Idx>where
    u8: AsPrimitive<Idx>,

pub fn node_point_of(&self, index: Idx) -> Result<NodePoint<Idx>, Error<'_, Idx>>where
    u8: AsPrimitive<Idx>,

Calculate the NodePoint of a specific node.

pub fn graft_unchecked(&mut self, other: Self, node: Idx)where
    usize: AsPrimitive<Idx>,

Self::graft, without error checks.

Panics

• node ∉ self.proxies

pub fn graft(&mut self, other: Self, node: Idx) -> Result<(), Error<'_, Idx>>where
    usize: AsPrimitive<Idx>,

Merge another tree as a branch of this tree.

node must be the index of a ProxyData::Void node.

Trait Implementations

impl<T: Debug, Idx: Debug + TreeIndex> Debug for Octree<T, Idx>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, Idx: TreeIndex> Default for Octree<T, Idx>

fn default() -> Self

Returns the “default value” for a type.

impl<T, Idx: TreeIndex> OctreeSlice<T, Idx> for Octree<T, Idx>

fn height(&self) -> Idx

The number of divisions within this octree.

This can be used to determine the dimensions of the voxel grid represented by the tree.

Examples

If self consists only of one node (the root), its height is 0. If the root is a branch, and each child of the root is a leaf (or void), then the tree’s height is 1. If the root branch has a terminal child branch, the tree’s height is 2.

fn root_idx(&self) -> Idx

Index of the root node.

fn height_from(&self, index: Idx) -> Idx

The height of a subtree, originating at a specific node.

fn leaf_dfi(&self) -> LeafIter<'_, T, Idx>

Depth-first iterator through all leafs, from deepest to shallowest & nearest to farthest (by Octant ordering).

fn grid_size(&self) -> Idx

The dimensions of the cubical voxel grid represented by this tree, as determined by the tree’s height.