1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//! A crate which exports rays, axis-aligned bounding boxes, and binary bounding
//! volume hierarchies.
//!
//! ## About
//!
//! This crate can be used for applications which contain intersection computations of rays
//! with primitives. For this purpose a binary tree [`Bvh`](bvh::Bvh) (Bounding Volume Hierarchy) is of great
//! use if the scene which the ray traverses contains a huge number of primitives. With a [`Bvh`](bvh::Bvh) the
//! intersection test complexity is reduced from O(n) to O(log2(n)) at the cost of building
//! the [`Bvh`](bvh::Bvh) once in advance. This technique is especially useful in ray/path tracers. For
//! use in a shader this module also exports a flattening procedure, which allows for
//! iterative traversal of the [`Bvh`](bvh::Bvh).
//!
//! ## Note
//!
//! If you are concerned about performance and do not mind using nightly, it is recommended to
//! use the `simd` feature as it introduces explicitly written simd to optimize certain areas
//! of the BVH.
//!
//! ## Example
//!
//! ```
//! use bvh::aabb::{Aabb, Bounded};
//! use bvh::bounding_hierarchy::{BHShape, BoundingHierarchy};
//! use bvh::bvh::Bvh;
//! use nalgebra::{Point3, Vector3};
//! use bvh::ray::Ray;
//!
//! let origin = Point3::new(0.0,0.0,0.0);
//! let direction = Vector3::new(1.0,0.0,0.0);
//! let ray = Ray::new(origin, direction);
//!
//! struct Sphere {
//! position: Point3<f32>,
//! radius: f32,
//! node_index: usize,
//! }
//!
//! impl Bounded<f32,3> for Sphere {
//! fn aabb(&self) -> Aabb<f32,3> {
//! let half_size = Vector3::new(self.radius, self.radius, self.radius);
//! let min = self.position - half_size;
//! let max = self.position + half_size;
//! Aabb::with_bounds(min, max)
//! }
//! }
//!
//! impl BHShape<f32,3> for Sphere {
//! fn set_bh_node_index(&mut self, index: usize) {
//! self.node_index = index;
//! }
//!
//! fn bh_node_index(&self) -> usize {
//! self.node_index
//! }
//! }
//!
//! let mut spheres = Vec::new();
//! for i in 0..1000u32 {
//! let position = Point3::new(i as f32, i as f32, i as f32);
//! let radius = (i % 10) as f32 + 1.0;
//! spheres.push(Sphere {
//! position: position,
//! radius: radius,
//! node_index: 0,
//! });
//! }
//!
//! let bvh = Bvh::build_par(&mut spheres);
//! let hit_sphere_aabbs = bvh.traverse(&ray, &spheres);
//! ```
//!
//! ## Features
//!
//! - `serde` (default **disabled**) - adds `Serialize` and `Deserialize` implementations for some types
//! - `simd` (default **disabled**) - adds explicitly written SIMD instructions for certain architectures (requires nightly)
//!
extern crate std;
extern crate test;
extern crate alloc;
doctest!;