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"] }

Optimizations:

• Unsigned arithmetics, bitwise operations.
• Tree structure is represented by flat, reusable pools. 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

Run benchmark:

cargo bench --all-features

Examples

Simple

You have to specify the type for the internal tree 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