[−][src]Crate kdtree_ray
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="0.1.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, BoundingBox, 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 BoundingBox for Triangle { fn bounding_box(&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(min, max) } } fn main() { // Kdtree creation let triangles: Vec<Triangle> = vec![/* ... */]; let kdtree = KDtree::new(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
AABB | Axis-aligned bounding box is defined by two positions. |
KDtree | The KD-tree data structure stores the elements implementing BoundingBox. |
Traits
BoundingBox | BoundingBox trait is needed to use a KD-tree. |