Struct collision::dbvt::DynamicBoundingVolumeTree
[−]
[src]
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 implementsTreeValue
, 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,
[src]
T: TreeValue,
T::Bound: Clone + Contains<T::Bound> + Union<T::Bound, Output = T::Bound> + SurfaceArea,
pub fn new() -> Self
[src]
Create a new tree.
Type parameters:
T
: A type that implementsTreeValue
, 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, andSurfaceArea
.
pub fn size(&self) -> usize
[src]
Return the number of nodes in the tree.
pub fn height(&self) -> u32
[src]
Return the height of the root node. Leafs are considered to have height 1.
pub fn values(&self) -> &Vec<(usize, T)>
[src]
Get an immutable list of all values in the tree.
Returns
A immutable reference to the Vec
of values in the tree.
pub fn values_mut(&mut self) -> &mut Vec<(usize, T)>
[src]
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.
pub fn reindex_values(&mut self)
[src]
Reindex the values list, making sure that nodes in the tree point to the correct entry in the values list.
Complexity is O(n).
pub fn clear(&mut self)
[src]
Clear the tree.
Will remove all nodes and their values.
pub fn value_index(&self, node_index: usize) -> Option<usize>
[src]
Return the value index for the given node index.
pub fn query<V>(&self, visitor: &mut V) -> Vec<(&T, V::Result)> where
V: Visitor<Bound = T::Bound>,
[src]
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^2 n).
Parameters:
visitor
: The visitor to check for bounding volume tests.
Type parameters:
V
: Type that implements ofVisitor
Returns
Will return a list of tuples of values accepted and the result returned by the visitor for the acceptance test.
pub fn query_for_indices<V>(&self, visitor: &mut V) -> Vec<(usize, V::Result)> where
V: Visitor<Bound = T::Bound>,
[src]
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^2 n).
Parameters:
visitor
: The visitor to check for bounding volume tests.
Type parameters:
V
: Type that implements ofVisitor
Returns
Will return a list of tuples of value indices accepted and the result returned by the visitor for the acceptance test.
pub fn update_node(&mut self, node_index: usize, new_value: T)
[src]
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 updatenew_value
: the new value to write in that node
pub fn flag_updated(&mut self, node_index: usize)
[src]
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
pub fn update(&mut self)
[src]
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.
pub fn tick(&mut self)
[src]
Utility method to perform updates and refitting. Should be called once per frame.
pub fn insert(&mut self, value: T) -> usize
[src]
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^2 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.
pub fn remove(&mut self, node_index: usize) -> Option<T>
[src]
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^2 n).
Parameters
node_index
: index of the leaf to remove
Returns
If a value was removed, the value is returned, otherwise None.
pub fn do_refit(&mut self)
[src]
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^2 n), where m is the number of nodes in the refit list.
Trait Implementations
impl<T> Default for DynamicBoundingVolumeTree<T> where
T: TreeValue,
[src]
T: TreeValue,
impl<T> Debug for DynamicBoundingVolumeTree<T> where
T: TreeValue,
T::Bound: Debug,
[src]
T: TreeValue,
T::Bound: Debug,