aboutsummaryrefslogtreecommitdiff
path: root/src/world/container/tree.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/world/container/tree.rs')
-rw-r--r--src/world/container/tree.rs157
1 files changed, 157 insertions, 0 deletions
diff --git a/src/world/container/tree.rs b/src/world/container/tree.rs
new file mode 100644
index 0000000..9bdbba1
--- /dev/null
+++ b/src/world/container/tree.rs
@@ -0,0 +1,157 @@
+use crate::world::{Hittable, Intersection};
+use crate::core::{Bound3f, Ray};
+use crate::{Float, INFTY};
+
+use std::sync::Arc;
+
+enum NodeType {
+ Empty,
+ Leaf(Arc<dyn Hittable>),
+ Full(Arc<Node>, Arc<Node>),
+}
+
+pub struct Node {
+ nt: NodeType,
+ area: Bound3f,
+}
+
+pub type HittableTree = Node;
+
+impl Node {
+ pub fn new() -> Self {
+ Self::default()
+ }
+
+ fn new_leaf(h: Arc<dyn Hittable>) -> Arc<Self> {
+ let b = h.bounding_box();
+
+ Arc::new(Self {
+ nt: NodeType::Leaf(h),
+ area: b,
+ })
+ }
+
+ pub fn add(&mut self, op: Box<dyn Hittable>) {
+ let new = self.nt.add(op);
+ if let Some(t) = new {
+ self.nt = t;
+ }
+
+ self.area = match &self.nt {
+ NodeType::Empty => Bound3f::EMPTY,
+ NodeType::Leaf(h) => h.bounding_box(),
+ NodeType::Full(n1, n2) => n1.area.combine(&n2.area),
+ };
+ }
+
+ /// Check how good a bound will fit
+ ///
+ /// Smaller value is better
+ fn score(&self, op: &Bound3f) -> Float {
+ self.area.combine(&op).area()
+ }
+
+ pub fn print(&self, d: u32) {
+ for _ in 0..d {
+ print!(" ");
+ }
+ match &self.nt {
+ NodeType::Empty => println!("Empty"),
+ NodeType::Leaf(_) => println!("Leaf"),
+ NodeType::Full(n1, n2) => {
+ println!("Full");
+ n1.print(d+1);
+ n2.print(d+1);
+ }
+ }
+ }
+}
+
+impl Hittable for Node {
+ fn intersect(&self, ray: &Ray) -> Option<Intersection> {
+ if !self.area.intersect(ray, 0.0, INFTY) {
+ println!("YAAH");
+ return None;
+ }
+ println!("BOOO");
+
+ match &self.nt {
+ NodeType::Empty => None,
+ NodeType::Leaf(h) => {
+ println!("Leaf");
+ h.intersect(ray)
+ },
+
+ NodeType::Full(o1, o2) => {
+ println!("FULL");
+ // Check intersect for sub nodes
+ let i1 = o1.intersect(ray);
+ let i2 = o2.intersect(ray);
+
+ match (i1, i2) {
+ // Two intersections, take the smallest
+ (Some(i1), Some(i2)) => {
+ if i1.t < i2.t {
+ Some(i1)
+ } else {
+ Some(i2)
+ }
+ },
+
+ // One of them intersect
+ (None, Some(i)) => Some(i),
+ (Some(i), None) => Some(i),
+
+ // None of them intersect
+ _ => None,
+ }
+ }
+ }
+ }
+
+ fn bounding_box(&self) -> Bound3f {
+ self.area.clone()
+ }
+}
+
+impl NodeType {
+ fn add(&mut self, op: Box<dyn Hittable>) -> Option<Self> {
+ let opb = op.bounding_box();
+
+ match self {
+ // Empty node create a new one
+ NodeType::Empty => Some(NodeType::Leaf(Arc::from(op))),
+
+ // Promote a node from a leaf
+ NodeType::Leaf(on) => Some(NodeType::Full(
+ Node::new_leaf(Arc::from(op)), Node::new_leaf(on.clone()))),
+
+ // Pass the object to the one with the largest overlap
+ NodeType::Full(o1, o2) => {
+ // Find overlaps
+ let op1 = o1.score(&opb);
+ let op2 = o2.score(&opb);
+
+ // Compare and pass it along
+ let co = if op1 < op2 {
+ o1
+ } else {
+ o2
+ };
+
+ Arc::get_mut(co).unwrap().add(op);
+
+ None
+ }
+ }
+ }
+}
+
+impl Default for Node {
+ fn default() -> Self {
+ Self {
+ nt: NodeType::Empty,
+ area: Bound3f::EMPTY,
+ }
+ }
+}