Crate kdtree_ray[][src]

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.2"

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),
    );
    [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

KDtree

The KD-tree data structure stores the elements implementing BoundingBox.

Traits

BoundingBox

BoundingBox trait is needed to use a KD-tree.

Type Definitions

AABB

Axis-aligned bounding box is defined by two positions.