kdtree_ray/
lib.rs

1#![deny(missing_docs)]
2
3//! This crate is a fast implementation of [KD-tree](https://en.wikipedia.org/wiki/K-d_tree)
4//! for raytracer (or other rendering method using ray).
5//!
6//! It's based on this [paper](http://www.irisa.fr/prive/kadi/Sujets_CTR/kadi/Kadi_sujet2_article_Kdtree.pdf)
7//! written by *Ingo Wald* and *Vlastimil Havran*.
8//!
9//! # Installation
10//!
11//! ```toml
12//! [dependencies]
13//! kdtree-ray="1.2.1"
14//! ```
15//!
16//! # Usage & Tips
17//!
18//! To create a [KD-tree](struct.KDtree.html) you only need to implement
19//! the [BoundingBox](trait.BoundingBox.html) on the object.
20//!
21//! If you're doing a raytracer each mesh could contain a KD-tree of triangles.
22//! Since `KDtree` his implementing `BoundingBox` itself you can create a KDtree
23//! of meshes in your scene.
24//!
25//! # Example
26//!
27//! ```
28//! use cgmath::*;
29//! use kdtree_ray::{AABB, Bounded, KDTree};
30//! struct Triangle(Vector3<f32>, Vector3<f32>, Vector3<f32>);
31//!
32//! // To use the KDTree on an object you need first to implement the BoundingBox trait.
33//! impl Bounded for Triangle {
34//!   fn bound(&self) -> AABB {
35//!     let min = Vector3::new(
36//!       self.0.x.min(self.1.x).min(self.2.x),
37//!       self.0.y.min(self.1.y).min(self.2.y),
38//!       self.0.z.min(self.1.z).min(self.2.z),
39//!     );
40//!     let max = Vector3::new(
41//!       self.0.x.max(self.1.x).max(self.2.x),
42//!       self.0.y.max(self.1.y).max(self.2.y),
43//!       self.0.z.max(self.1.z).max(self.2.z),
44//!     );
45//!     AABB::new(min, max)
46//!   }
47//! }
48//!
49//! // Kdtree creation
50//! let triangle = Triangle(Vector3::zero(), Vector3::zero(), Vector3::zero());
51//! let triangles: Vec<Triangle> = vec![triangle, /* ... */];
52//! let kdtree = KDTree::build(&triangles);
53//!
54//! // Get a reduced list of triangles that a ray could intersect
55//! let ray_origin = Vector3::zero();
56//! let ray_direction = Vector3::new(1., 0., 0.);
57//! let candidates_triangles = kdtree.intersect(&ray_origin, &ray_direction);
58//! ```
59mod aabb;
60mod candidate;
61mod config;
62mod kdnode;
63mod kdtree;
64mod plane;
65mod ray;
66
67pub use aabb::*;
68pub use config::BuilderConfig;
69pub use kdtree::KDTree;
70
71type Point3 = cgmath::Vector3<f32>;
72type Vector3 = cgmath::Vector3<f32>;
73
74#[macro_use]
75extern crate enum_map;
kdtree_ray/lib.rs

kdtree_ray/
lib.rs
