[−][src]Module collision::dbvt
A dynamic bounding volume tree implementation, 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
.
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.
The trait TreeValue
needs to be implemented for a type to be usable
in the tree.
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); }
Structs
ContinuousVisitor | Visitor for doing continuous intersection testing on the DBVT. |
DiscreteVisitor | Visitor for doing discrete intersection testing on the DBVT. |
DynamicBoundingVolumeTree | A dynamic bounding volume tree, index based (not pointer based). |
FrustumVisitor | Visitor for doing frustum intersection testing on the DBVT. |
TreeValueWrapped | Value together with bounding volume, for use with DBVT. |
Traits
TreeValue | Trait that needs to be implemented for any value that is to be used in the
|
Visitor | Visitor trait used for querying the tree. |
Functions
query_ray | Query the given tree for all values that intersects the given ray. |
query_ray_closest | Query the given tree for the closest value that intersects the given ray. |