Struct collision::dbvt::DynamicBoundingVolumeTree

pub struct DynamicBoundingVolumeTree<T> where
    T: TreeValue,  { /* fields omitted */ }

A dynamic bounding volume tree, index based (not pointer based).

The following invariants are true:

• A branch node must have exactly two children.
• Only leaf nodes contain user data.

Internal nodes may have incorrect bounding volumes and height after insertion, removal and updates to values in the tree. These will be fixed during refitting, which is done by calling do_refit. This function should ideally not be called more than once per frame.

The main heuristic used for insertion and tree rotation, is surface area of the bounding volume.

Updating of values in the tree, can either be performed by using the values function to get a mutable iterator over the values in the tree, or by using update_node. It is recommended to use the latter when possible. If the former is used, reindex_values must be called if the order of the values is changed in any way.

Type parameters:

• T: A type that implements TreeValue, and is usable in the tree. Needs to be able to store the node index of itself, and handle its own bound and fattened bound.

Examples

use cgmath::{Point2, Vector2, InnerSpace};
use collision::{Aabb, Aabb2, Ray2};
use collision::dbvt::{DynamicBoundingVolumeTree, TreeValue, ContinuousVisitor};

#[derive(Debug, Clone)]
struct Value {
    pub id: u32,
    pub aabb: Aabb2<f32>,
    fat_aabb: Aabb2<f32>,
}

impl Value {
    pub fn new(id: u32, aabb: Aabb2<f32>) -> Self {
        Self {
            id,
            fat_aabb : aabb.add_margin(Vector2::new(3., 3.)),
            aabb,
        }
    }
}

impl TreeValue for Value {
    type Bound = Aabb2<f32>;

    fn bound(&self) -> &Aabb2<f32> {
        &self.aabb
    }

    fn get_bound_with_margin(&self) -> Aabb2<f32> {
        self.fat_aabb.clone()
    }
}

fn aabb2(minx: f32, miny: f32, maxx: f32, maxy: f32) -> Aabb2<f32> {
   Aabb2::new(Point2::new(minx, miny), Point2::new(maxx, maxy))
}

fn main() {
    let mut tree = DynamicBoundingVolumeTree::<Value>::new();
    tree.insert(Value::new(10, aabb2(5., 5., 10., 10.)));
    tree.insert(Value::new(11, aabb2(21., 14., 23., 16.)));
    tree.do_refit();

    let ray = Ray2::new(Point2::new(0., 0.), Vector2::new(-1., -1.).normalize());
    let mut visitor = ContinuousVisitor::<Ray2<f32>, Value>::new(&ray);
    assert_eq!(0, tree.query(&mut visitor).len());

    let ray = Ray2::new(Point2::new(6., 0.), Vector2::new(0., 1.).normalize());
    let mut visitor = ContinuousVisitor::<Ray2<f32>, Value>::new(&ray);
    let results = tree.query(&mut visitor);
    assert_eq!(1, results.len());
    assert_eq!(10, results[0].0.id);
    assert_eq!(Point2::new(6., 5.), results[0].1);
}

Methods

impl<T> DynamicBoundingVolumeTree<T> where
    T: TreeValue,
    T::Bound: Clone + Contains<T::Bound> + Union<T::Bound, Output = T::Bound> + SurfaceArea, 

fn new() -> Self

Create a new tree.

Type parameters:

• T: A type that implements TreeValue, and is usable in the tree. Needs to be able to store the node index of itself, and handle its own bound and fattened bound.
• T::Bound: Bounding volume type that implements the following collision-rs traits: Contains on itself, Union on itself, and SurfaceArea.

fn size(&self) -> usize

Return the number of nodes in the tree.

fn height(&self) -> u32

Return the height of the root node. Leafs are considered to have height 1.

fn values(&self) -> &Vec<(usize, T)>

Get an immutable list of all values in the tree.

Returns

A immutable reference to the Vec of values in the tree.

fn values_mut(&mut self) -> &mut Vec<(usize, T)>

Get a mutable list of all values in the tree.

Do not insert or remove values directly in this list, instead use insert and remove on the tree. It is allowed to change the order of the values, but when doing so it is required to use reindex_values after changing the order, and before any other operation is performed on the tree. Otherwise the internal consistency of the tree will be broken.

Do not change the first value in the tuple, this is the node index of the value, and without that the tree will not function.

Returns

A mutable reference to the Vec of values in the tree.

fn reindex_values(&mut self)

Reindex the values list, making sure that nodes in the tree point to the correct entry in the values list.

Complexity is O(n).

fn clear(&mut self)

Clear the tree.

Will remove all nodes and their values.

fn value_index(&self, node_index: usize) -> Option<usize>

Return the value index for the given node index.

fn query<V>(&self, visitor: &mut V) -> Vec<(&T, V::Result)> where
    V: Visitor<Bound = T::Bound>, 

Query the tree for all leafs that the given visitor accepts.

Will do a depth first search of the tree and pass all bounding volumes on the way to the visitor.

This function have approximate complexity O(log² n).

Parameters:

• visitor: The visitor to check for bounding volume tests.

Type parameters:

• V: Type that implements of Visitor

Returns

Will return a list of tuples of values accepted and the result returned by the visitor for the acceptance test.

fn query_for_indices<V>(&self, visitor: &mut V) -> Vec<(usize, V::Result)> where
    V: Visitor<Bound = T::Bound>, 

Query the tree for all leafs that the given visitor accepts.

Will do a depth first search of the tree and pass all bounding volumes on the way to the visitor.

This function have approximate complexity O(log² n).

Parameters:

• visitor: The visitor to check for bounding volume tests.

Type parameters:

• V: Type that implements of Visitor

Returns

Will return a list of tuples of value indices accepted and the result returned by the visitor for the acceptance test.

fn update_node(&mut self, node_index: usize, new_value: T)

Update a node in the tree with a new value.

The node will be fed its node_index after updating in the tree, so there is no need to add that manually in the value.

Will cause the node to be updated and be flagged as updated, which will cause update to process the node the next time it is called.

Parameters

• node_index: index of the node to update
• new_value: the new value to write in that node

fn flag_updated(&mut self, node_index: usize)

Flag a node as having been updated (moved/rotated).

Will cause update to process the node the next time it is called.

Parameters

• node_index: the node index of the updated node

fn update(&mut self)

Go through the updated list and check the fat bounds in the tree.

After updating values in the values list, it is possible that some of the leafs values have outgrown their fat bounds. If so, they may need to be moved in the tree. This is done during refitting.

Note that no parents have their bounds/height updated directly by this function, instead do_refit should be called after all insert/remove/updates have been performed this frame.

fn tick(&mut self)

Utility method to perform updates and refitting. Should be called once per frame.

Will in turn call update, followed by do_refit.

fn insert(&mut self, value: T) -> usize

Insert a value into the tree.

This will search the tree for the best leaf to pair the value up with, using the surface area of the value's bounding volume as the main heuristic. Will always cause a new branch node and a new leaf node (containing the given value) to be added to the tree. This is to keep the invariant of branches always having 2 children true.

This function should have approximate complexity O(log² n).

Note that no parents have their bounds/height updated directly by this function, instead do_refit should be called after all insert/remove/updates have been performed this frame.

Parameters

• value: The value to insert into the tree.

Returns

The node index of the inserted value. This value should never change after insertion.

fn remove(&mut self, node_index: usize) -> Option<T>

Remove the node with the given node index.

The reason this function takes the node index and not a reference to the value, is because the only way to get at the values in the tree is by doing a mutable borrow, making this function unusable.

If the given node index points to a non-leaf, this function is effectively a nop. Else the leaf node and it's parent branch node will be removed, and the leaf nodes sibling will take the place of the parent branch node in the tree.

Note that no parents have their bounds/height updated directly by this function, instead do_refit should be called after all insert/remove/updates have been performed this frame.

This function should have approximate complexity O(log² n).

Parameters

• node_index: index of the leaf to remove

Returns

If a value was removed, the value is returned, otherwise None.

fn do_refit(&mut self)

Go through the list of nodes marked for refitting, update their bounds/heights and check if any of them need to be rotated to new locations.

This method have worst case complexity O(m * log² n), where m is the number of nodes in the refit list.

Trait Implementations

impl<T> Debug for DynamicBoundingVolumeTree<T> where
    T: TreeValue,
    T::Bound: Debug, 

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

Formats the value using the given formatter.