Crate kdtree_ray

Expand description

This crate is a fast implementation of KD-tree for raytracer (or other rendering method using ray).

It’s based on this paper written by Ingo Wald and Vlastimil Havran.

Installation

``````[dependencies]
kdtree-ray="1.2.1"
``````

Usage & Tips

To create a KD-tree you only need to implement the BoundingBox on the object.

If you’re doing a raytracer each mesh could contain a KD-tree of triangles. Since `KDtree` his implementing `BoundingBox` itself you can create a KDtree of meshes in your scene.

Example

``````use cgmath::*;
use kdtree_ray::{AABB, Bounded, KDTree};
struct Triangle(Vector3<f32>, Vector3<f32>, Vector3<f32>);

// To use the KDTree on an object you need first to implement the BoundingBox trait.
impl Bounded for Triangle {
fn bound(&self) -> AABB {
let min = Vector3::new(
self.0.x.min(self.1.x).min(self.2.x),
self.0.y.min(self.1.y).min(self.2.y),
self.0.z.min(self.1.z).min(self.2.z),
);
let max = Vector3::new(
self.0.x.max(self.1.x).max(self.2.x),
self.0.y.max(self.1.y).max(self.2.y),
self.0.z.max(self.1.z).max(self.2.z),
);
AABB::new(min, max)
}
}

// Kdtree creation
let triangle = Triangle(Vector3::zero(), Vector3::zero(), Vector3::zero());
let triangles: Vec<Triangle> = vec![triangle, /* ... */];
let kdtree = KDTree::build(&triangles);

// Get a reduced list of triangles that a ray could intersect
let ray_origin = Vector3::zero();
let ray_direction = Vector3::new(1., 0., 0.);
let candidates_triangles = kdtree.intersect(&ray_origin, &ray_direction);``````

Structs

• Axis-aligned bounding box is defined by two positions.
• Configuration for the builder.
• The KD-tree data structure.

Traits

• Your shapes needs to implement `Bounded` trait to build a KD-tree around it.