Crate oktree

Fast octree implementation.

Able to operate with Position or Volume data.

Could be used with the Bevy game engine or as a standalone tree.

Available methods:

• Unsigned operations

  • Insertion
  • Removing
  • Searching

• Floating point operations (Bevy integration)

  • Ray casting
  • Bouning sphere and bounding box intersection

To enable bevy integrations:

[dependencies]
oktree = { version = "0.5.0", features = ["bevy"] }

Intersection methods are not available without this feature.

Optimizations:

• Unsigned arithmetics, bitwise operations.
• Tree structure is represented by flat, reusable Pool. Removed data is marked only.
• Few memory allocations. smallvec and heapless structures are used.
• No smart pointers (Rc, RefCell e.t.c)

Compensation for the inconvenience is perfomance.

Benchmark

Octree dimensions: 4096x4096x4096

Operation	Quantity	Time
insertion	65536 cells	21 ms
removing	65536 cells	1.5 ms
find	65536 searches in 65536 cells	12 ms
ray intersection	4096 rays against 65536 cells	37 ms
sphere intersection	4096 spheres against 65536 cells	8 ms
box intersection	4096 boxes against 65536 cells	7 ms

Run benchmark:

cargo bench --all-features

Examples

Simple

You have to specify the type for the internal Octree structure.

It must be any Unsigned type (u8, u16, u32, u64, u128 or usize).

Implement Position or Volume for the handled type, so that it can return it’s spatial coordinates.

use bevy::math::{
    bounding::{Aabb3d, BoundingSphere, RayCast3d},
    Dir3, Vec3,
};
use oktree::prelude::*;

fn main() -> Result<(), TreeError> {
    let aabb = Aabb::new(TUVec3::splat(16), 16u8);
    let mut tree = Octree::from_aabb_with_capacity(aabb?, 10);

    let c1 = DummyCell::new(TUVec3::splat(1u8));
    let c2 = DummyCell::new(TUVec3::splat(8u8));

    let c1_id = tree.insert(c1)?;
    let c2_id = tree.insert(c2)?;

    // Searching by position
    assert_eq!(tree.find(&TUVec3::new(1, 1, 1)), Some(c1_id));
    assert_eq!(tree.find(&TUVec3::new(8, 8, 8)), Some(c2_id));
    assert_eq!(tree.find(&TUVec3::new(1, 2, 8)), None);
    assert_eq!(tree.find(&TUVec3::splat(100)), None);

    // Searching for the ray intersection
    let ray = RayCast3d::new(Vec3::new(1.5, 7.0, 1.9), Dir3::NEG_Y, 100.0);

    // Hit!
    assert_eq!(
        tree.ray_cast(&ray),
        HitResult {
            element: Some(ElementId(0)),
            distance: 5.0
        }
    );

    assert_eq!(tree.remove(ElementId(0)), Ok(()));

    // Miss!
    assert_eq!(
        tree.ray_cast(&ray),
        HitResult {
            element: None,
            distance: 0.0
        }
    );

    let c1 = DummyCell::new(TUVec3::splat(1u8));
    let c1_id = tree.insert(c1)?;

    // Aabb intersection
    let aabb = Aabb3d::new(Vec3::splat(2.0), Vec3::splat(2.0));
    assert_eq!(tree.intersect(&aabb), vec![c1_id]);

    // Sphere intersection
    let sphere = BoundingSphere::new(Vec3::splat(2.0), 2.0);
    assert_eq!(tree.intersect(&sphere), vec![c1_id]);
     
    Ok(())
}

struct DummyCell {
    position: TUVec3<u8>,
}

impl Position for DummyCell {
    type U = u8;
    fn position(&self) -> TUVec3<u8> {
        self.position
    }
}

impl DummyCell {
    fn new(position: TUVec3<u8>) -> Self {
        DummyCell { position }
    }
}

Bevy

Run bevy visual example:

cargo run --release --example bevy_tree --all-features

no_std

no_std is supported, but you steel need to specify a global allocator.

See example with a custom allocator.

Run no_std example

cargo run --no-default-features --features bevy --example no_std

Contribution guide

Feature and pull requests are welcomed.

1. Clone the Oktree repo

git clone https://github.com/exor2008/oktree

2. Implement awesome feature

3. Run tests

cargo test --all-targets --all-features --release

4. Make sure clippy is happy

cargo clippy --all-targets --all-features

5. Run examples

cargo run --all-features --example simple
cargo run --all-features --example bevy_tree
cargo run --no-default-features --features bevy --example no_std

6. Run benchmark

cargo bench --all-features

7. Check the docs:

cargo doc --no-deps --open --all-features

8. Start pull request

Modules

bevy_integration

Bevy game engine integrations.

bounding

Bounding primitives.

intersect_with

Helper functions with a custom intersection closure.

node

Node implementation.

pool

Pool implementation.

prelude

Crate’s core types reimports.

tree

Octree implementation

Structs

ElementId

Index tree.elements with it. Stored type element will be returned.

NodeId

Index tree.nodes with it.

Enums

TreeError

Enum of all possible errors of the octree’s operations.

Traits

Position

Implement to represent your object as a point in a tree

Volume

Implement to represent your object as a volume in a tree.