Struct vox_geometry_rust::bvh3::Bvh3

pub struct Bvh3<T: Clone> { /* fields omitted */ }

Bounding Volume Hierarchy (BVH) in 3D

This class implements the classic bounding volume hierarchy structure in 3D. It implements IntersectionQueryEngine3 in order to support box/ray intersection tests. Also, NearestNeighborQueryEngine3 is implemented to provide nearest neighbor query.

Implementations

impl<T: Clone> Bvh3<T>

pub fn new() -> Bvh3<T>

Default constructor.

use vox_geometry_rust::bvh3::Bvh3;
use vox_geometry_rust::vector3::Vector3D;
let bvh:Bvh3<Vector3D> = Bvh3::new();
assert_eq!(bvh.number_of_nodes(), 0);

pub fn build(&mut self, items: &Vec<T>, item_bounds: &Vec<BoundingBox3D>)

Builds bounding volume hierarchy.

use vox_geometry_rust::bvh3::Bvh3;
use vox_geometry_rust::vector3::Vector3D;
use vox_geometry_rust::bounding_box3::BoundingBox3D;
let mut bvh:Bvh3<Vector3D> = Bvh3::new();

let points:Vec<Vector3D> = vec![Vector3D::new_default(), Vector3D::new(1.0, 1.0, 1.0)];
let mut rootBounds = BoundingBox3D::new_default();
let bounds = (0..points.len()).map(|index|{
    let c = points[index];
    let mut aabb = BoundingBox3D::new(c, c);
    aabb.expand(0.1);
    rootBounds.merge_box(&aabb);
    return aabb.clone();
}).collect();

bvh.build(&points, &bounds);

assert_eq!(2, bvh.number_of_items());
assert_eq!(points[0], *bvh.item(0));
assert_eq!(points[1], *bvh.item(1));
assert_eq!(3, bvh.number_of_nodes());
assert_eq!(1, bvh.children(0).0);
assert_eq!(2, bvh.children(0).1);
assert_eq!(bvh.is_leaf(0), false);
assert_eq!(bvh.is_leaf(1), true);
assert_eq!(bvh.is_leaf(2), true);
assert_eq!(rootBounds.lower_corner, bvh.node_bound(0).lower_corner);
assert_eq!(rootBounds.upper_corner, bvh.node_bound(0).upper_corner);
assert_eq!(bounds[0].lower_corner, bvh.node_bound(1).lower_corner);
assert_eq!(bounds[0].upper_corner, bvh.node_bound(1).upper_corner);
assert_eq!(bounds[1].lower_corner, bvh.node_bound(2).lower_corner);
assert_eq!(bounds[1].upper_corner, bvh.node_bound(2).upper_corner);

pub fn clear(&mut self)

Clears all the contents of this instance.

pub fn number_of_items(&self) -> usize

Returns the number of items.

pub fn item(&self, i: usize) -> &T

Returns the item at \p i.

pub fn number_of_nodes(&self) -> usize

Returns the number of nodes.

pub fn children(&self, i: usize) -> (usize, usize)

Returns the children indices of \p i-th node.

pub fn is_leaf(&self, i: usize) -> bool

Returns true if \p i-th node is a leaf node.

pub fn node_bound(&self, i: usize) -> BoundingBox3D

Returns bounding box of \p i-th node.

pub fn bounding_box(&self) -> BoundingBox3D

Returns bounding box of every items.

pub fn item_of_node(&self, i: usize) -> usize

Returns item of \p i-th node.

Trait Implementations

impl<T: Clone> IntersectionQueryEngine3<T> for Bvh3<T>

fn intersects_aabb<Callback>(
    &self,
    aabb: &BoundingBox3D,
    test_func: &mut Callback
) -> bool where
    Callback: BoxIntersectionTestFunc3<T>, 

use vox_geometry_rust::bvh3::Bvh3;
use vox_geometry_rust::vector3::Vector3D;
use vox_geometry_rust::bounding_box3::BoundingBox3D;
use vox_geometry_rust::unit_tests_utils::*;
use vox_geometry_rust::nearest_neighbor_query_engine3::*;
use vox_geometry_rust::intersection_query_engine3::IntersectionQueryEngine3;
let mut bvh:Bvh3<Vector3D> = Bvh3::new();

let mut overlaps_func = |pt:&Vector3D, bbox:&BoundingBox3D| {
    let mut aabb = BoundingBox3D::new(*pt, *pt);
    aabb.expand(0.1);
    return bbox.overlaps(&aabb);
};

let num_samples = get_number_of_sample_points3();
let points = (0..num_samples).map(|index| Vector3D::new_lst(get_sample_points3()[index])).collect();

let bounds = (0..num_samples).map(|index| {
    let c = Vector3D::new_lst(get_sample_points3()[index]);
    let mut aabb = BoundingBox3D::new(c, c);
    aabb.expand(0.1);
    aabb
}).collect();

bvh.build(&points, &bounds);

let test_box = BoundingBox3D::new(Vector3D::new(0.25, 0.15, 0.3), Vector3D::new(0.5, 0.6, 0.4));
let mut has_overlaps = false;
for i in 0..num_samples {
    has_overlaps |= overlaps_func(&Vector3D::new_lst(get_sample_points3()[i]), &test_box);
}

assert_eq!(has_overlaps, bvh.intersects_aabb(&test_box, &mut overlaps_func));

let test_box3 = BoundingBox3D::new(Vector3D::new(0.3, 0.2, 0.1), Vector3D::new(0.6, 0.5, 0.4));
has_overlaps = false;
for i in 0..num_samples {
    has_overlaps |= overlaps_func(&Vector3D::new_lst(get_sample_points3()[i]), &test_box3);
}

assert_eq!(has_overlaps, bvh.intersects_aabb(&test_box3, &mut overlaps_func));

fn intersects_ray<Callback>(
    &self,
    ray: &Ray3D,
    test_func: &mut Callback
) -> bool where
    Callback: RayIntersectionTestFunc3<T>, 

use vox_geometry_rust::bvh3::Bvh3;
use vox_geometry_rust::vector3::Vector3D;
use vox_geometry_rust::bounding_box3::BoundingBox3D;
use vox_geometry_rust::ray3::Ray3D;
use vox_geometry_rust::unit_tests_utils::*;
use vox_geometry_rust::nearest_neighbor_query_engine3::*;
use vox_geometry_rust::intersection_query_engine3::IntersectionQueryEngine3;
let mut bvh:Bvh3<BoundingBox3D> = Bvh3::new();

let mut intersects_func = |a:&BoundingBox3D, ray:&Ray3D| {
        return a.intersects(ray);
};

let num_samples = get_number_of_sample_points3();
let items = (0..num_samples / 2).map(|index| {
    let c = Vector3D::new_lst(get_sample_points3()[index]);
    let mut aabb = BoundingBox3D::new(c, c);
    aabb.expand(0.1);
    aabb
}).collect();

bvh.build(&items, &items);

for i in 0..num_samples / 2 {
    let ray = Ray3D::new(Vector3D::new_lst(get_sample_dirs3()[i + num_samples / 2]),
                         Vector3D::new_lst(get_sample_dirs3()[i + num_samples / 2]));
    // ad-hoc search
    let mut ans_ints = false;
    for j in 0..num_samples / 2 {
        if intersects_func(&items[j], &ray) {
            ans_ints = true;
            break;
        }
    }

    // bvh search
    let oct_ints = bvh.intersects_ray(&ray, &mut intersects_func);

    assert_eq!(ans_ints, oct_ints);
}

fn for_each_intersecting_item_aabb<Callback, Visitor>(
    &self,
    aabb: &BoundingBox3D,
    test_func: &mut Callback,
    visitor_func: &mut Visitor
) where
    Callback: BoxIntersectionTestFunc3<T>,
    Visitor: IntersectionVisitorFunc3<T>, 

use vox_geometry_rust::bvh3::Bvh3;
use vox_geometry_rust::vector3::Vector3D;
use vox_geometry_rust::bounding_box3::BoundingBox3D;
use vox_geometry_rust::unit_tests_utils::*;
use vox_geometry_rust::nearest_neighbor_query_engine3::*;
use vox_geometry_rust::intersection_query_engine3::IntersectionQueryEngine3;
let mut bvh:Bvh3<Vector3D> = Bvh3::new();

let mut overlaps_func = |pt:&Vector3D, bbox:&BoundingBox3D| {
        return bbox.contains(pt);
};

let overlaps_func3 = |pt:&Vector3D, bbox:&BoundingBox3D| {
        return bbox.contains(pt);
};

let num_samples = get_number_of_sample_points3();
let points = (0..num_samples).map(|index| Vector3D::new_lst(get_sample_points3()[index])).collect();

let bounds = (0..num_samples).map(|index| {
    let c = Vector3D::new_lst(get_sample_points3()[index]);
    let mut aabb = BoundingBox3D::new(c, c);
    aabb.expand(0.1);
    aabb
}).collect();

bvh.build(&points, &bounds);

let test_box = BoundingBox3D::new(Vector3D::new(0.3, 0.2, 0.1), Vector3D::new(0.6, 0.5, 0.4));
let mut num_overlaps = 0;
for i in 0..num_samples {
    num_overlaps += overlaps_func(&Vector3D::new_lst(get_sample_points3()[i]), &test_box) as usize;
}

let mut measured = 0;
bvh.for_each_intersecting_item_aabb(&test_box, &mut overlaps_func, &mut |pt:&Vector3D| {
    assert_eq!(overlaps_func3(pt, &test_box), true);
    measured += 1;
});

assert_eq!(num_overlaps, measured);

fn closest_intersection<Callback>(
    &self,
    ray: &Ray3D,
    test_func: &mut Callback
) -> ClosestIntersectionQueryResult3<T> where
    Callback: GetRayIntersectionFunc3<T>, 

use vox_geometry_rust::bvh3::Bvh3;
use vox_geometry_rust::vector3::Vector3D;
use vox_geometry_rust::bounding_box3::BoundingBox3D;
use vox_geometry_rust::ray3::Ray3D;
use vox_geometry_rust::unit_tests_utils::*;
use vox_geometry_rust::nearest_neighbor_query_engine3::*;
use vox_geometry_rust::intersection_query_engine3::*;
let mut bvh:Bvh3<BoundingBox3D> = Bvh3::new();

let mut intersects_func = |a:&BoundingBox3D, ray:&Ray3D| {
    let bbox_result = a.closest_intersection(ray);
    return if bbox_result.is_intersecting {
         bbox_result.t_near
    } else {
         f64::MAX
    };
};

let num_samples = get_number_of_sample_points3();
let items = (0..num_samples / 2).map(|index| {
    let c = Vector3D::new_lst(get_sample_points3()[index]);
    let mut aabb = BoundingBox3D::new(c, c);
    aabb.expand(0.1);
    aabb
}).collect();

bvh.build(&items, &items);

for i in 0..num_samples / 2 {
    let ray = Ray3D::new(Vector3D::new_lst(get_sample_points3()[i + num_samples / 2]),
                         Vector3D::new_lst(get_sample_dirs3()[i + num_samples / 2]));
        // ad-hoc search
    let mut ans_ints:ClosestIntersectionQueryResult3<BoundingBox3D> = ClosestIntersectionQueryResult3::new();
    for j in 0..num_samples / 2 {
        let dist = intersects_func(&items[j], &ray);
        if dist < ans_ints.distance {
            ans_ints.distance = dist;
            ans_ints.item = Some(bvh.item(j).clone());
        }
    }

    // bvh search
    let bvh_ints = bvh.closest_intersection(&ray, &mut intersects_func);

    assert_eq!(ans_ints.distance, bvh_ints.distance);
    let ans_aabb = ans_ints.item.unwrap_or(BoundingBox3D::new_default());
    let oct_aabb = bvh_ints.item.unwrap_or(BoundingBox3D::new_default());
    assert_eq!(ans_aabb.upper_corner, oct_aabb.upper_corner);
    assert_eq!(ans_aabb.lower_corner, oct_aabb.lower_corner);
}

fn for_each_intersecting_item_ray<Callback, Visitor>(
    &self,
    ray: &Ray3D,
    test_func: &mut Callback,
    visitor_func: &mut Visitor
) where
    Callback: RayIntersectionTestFunc3<T>,
    Visitor: IntersectionVisitorFunc3<T>, 

Invokes \p visitor_func for every intersecting items.

impl<T: Clone> NearestNeighborQueryEngine3<T> for Bvh3<T>

fn nearest<Callback>(
    &self,
    pt: &Vector3D,
    distance_func: &mut Callback
) -> NearestNeighborQueryResult3<T> where
    Callback: NearestNeighborDistanceFunc3<T>, 

use vox_geometry_rust::bvh3::Bvh3;
use vox_geometry_rust::vector3::Vector3D;
use vox_geometry_rust::bounding_box3::BoundingBox3D;
use vox_geometry_rust::unit_tests_utils::*;
use vox_geometry_rust::nearest_neighbor_query_engine3::*;
let mut bvh:Bvh3<Vector3D> = Bvh3::new();

let mut distance_func = |a:&Vector3D, b:&Vector3D| {
        return a.distance_to(*b);
    };

let num_samples = get_number_of_sample_points3();
let points = (0..num_samples).map(|index| Vector3D::new_lst(get_sample_points3()[index])).collect();

let bounds = (0..num_samples).map(|index| {
    let c = Vector3D::new_lst(get_sample_points3()[index]);
    let mut aabb = BoundingBox3D::new(c, c);
    aabb.expand(0.1);
    aabb
}).collect();

bvh.build(&points, &bounds);

let test_pt = Vector3D::new(0.5, 0.5, 0.5);
let nearest = bvh.nearest(&test_pt, &mut distance_func);
let mut answer_idx = 0;
let mut best_dist = test_pt.distance_to(points[answer_idx]);
for i in 1..num_samples {
let dist = test_pt.distance_to(Vector3D::new_lst(get_sample_points3()[i]));
    if dist < best_dist {
        best_dist = dist;
        answer_idx = i;
    }
}

assert_eq!(nearest.item.unwrap(), *bvh.item(answer_idx));