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 DynamicBoundingVolumeTree.
Visitor	Visitor trait used for querying the tree.

Functions

query_ray_closest

Query the given tree for the closest value that intersects the given ray.