From 8452b0227e3b7bf6fc012309a49cd1a14de6ae3d Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Sun, 6 Jun 2010 00:07:14 -0600
Subject: New dmnsn_prtree_inside() function, rename dmnsn_prtree_search().

---
 libdimension/csg.c      |  9 +++------
 libdimension/prtree.c   | 52 +++++++++++++++++++++++++++++++++++++++++++------
 libdimension/prtree.h   |  5 +++--
 libdimension/raytrace.c |  5 +++--
 4 files changed, 55 insertions(+), 16 deletions(-)

(limited to 'libdimension')

diff --git a/libdimension/csg.c b/libdimension/csg.c
index ee77739..0f6c4c1 100644
--- a/libdimension/csg.c
+++ b/libdimension/csg.c
@@ -46,17 +46,14 @@ dmnsn_csg_union_intersection_fn(const dmnsn_object *csg,
                                 dmnsn_intersection *intersection)
 {
   dmnsn_prtree *prtree = csg->ptr;
-  return dmnsn_prtree_search(prtree, line, intersection);
+  return dmnsn_prtree_intersection(prtree, line, intersection);
 }
 
 static bool
 dmnsn_csg_union_inside_fn(const dmnsn_object *csg, dmnsn_vector point)
 {
-  DMNSN_ARRAY_FOREACH (dmnsn_object **, child, csg->children) {
-    if (((*child)->inside_fn)(*child, point))
-      return true;
-  }
-  return false;
+  dmnsn_prtree *prtree = csg->ptr;
+  return dmnsn_prtree_inside(prtree, point);
 }
 
 static void
diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index 7fcc8ab..e42748e 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -592,8 +592,9 @@ dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_bounding_box box, double t)
 }
 
 static void
-dmnsn_prtree_search_recursive(const dmnsn_prtree_node *node, dmnsn_line ray,
-                              dmnsn_intersection *intersection, double *t)
+dmnsn_prtree_intersection_recursive(const dmnsn_prtree_node *node,
+                                    dmnsn_line ray,
+                                    dmnsn_intersection *intersection, double *t)
 {
   for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
     if (!node->children[i])
@@ -611,15 +612,16 @@ dmnsn_prtree_search_recursive(const dmnsn_prtree_node *node, dmnsn_line ray,
           }
         }
       } else {
-        dmnsn_prtree_search_recursive(node->children[i], ray, intersection, t);
+        dmnsn_prtree_intersection_recursive(node->children[i], ray,
+                                            intersection, t);
       }
     }
   }
 }
 
 bool
-dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray,
-                    dmnsn_intersection *intersection)
+dmnsn_prtree_intersection(const dmnsn_prtree *tree, dmnsn_line ray,
+                          dmnsn_intersection *intersection)
 {
   double t = INFINITY;
 
@@ -636,8 +638,46 @@ dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray,
 
   /* Search the bounded objects */
   if (dmnsn_ray_box_intersection(ray, tree->root->bounding_box, t)) {
-    dmnsn_prtree_search_recursive(tree->root, ray, intersection, &t);
+    dmnsn_prtree_intersection_recursive(tree->root, ray, intersection, &t);
   }
 
   return !isinf(t);
 }
+
+static bool
+dmnsn_prtree_inside_recursive(const dmnsn_prtree_node *node, dmnsn_vector point)
+{
+  for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
+    if (!node->children[i])
+      break;
+
+    if (dmnsn_bounding_box_contains(node->bounding_boxes[i], point)) {
+      if (node->is_leaf) {
+        dmnsn_object *object = node->children[i];
+        if ((*object->inside_fn)(object, point))
+          return true;
+      } else {
+        if (dmnsn_prtree_inside_recursive(node->children[i], point))
+          return true;
+      }
+    }
+  }
+
+  return false;
+}
+
+bool
+dmnsn_prtree_inside(const dmnsn_prtree *tree, dmnsn_vector point)
+{
+  /* Search the unbounded objects */
+  DMNSN_ARRAY_FOREACH (dmnsn_object **, object, tree->unbounded) {
+    if ((*(*object)->inside_fn)(*object, point))
+      return true;
+  }
+
+  /* Search the bounded objects */
+  if (dmnsn_bounding_box_contains(tree->root->bounding_box, point))
+    return dmnsn_prtree_inside_recursive(tree->root, point);
+
+  return false;
+}
diff --git a/libdimension/prtree.h b/libdimension/prtree.h
index eab359d..30ecbd6 100644
--- a/libdimension/prtree.h
+++ b/libdimension/prtree.h
@@ -50,7 +50,8 @@ typedef struct dmnsn_prtree {
 dmnsn_prtree *dmnsn_new_prtree(const dmnsn_array *objects);
 void dmnsn_delete_prtree(dmnsn_prtree *tree);
 
-bool dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray,
-                         dmnsn_intersection *intersection);
+bool dmnsn_prtree_intersection(const dmnsn_prtree *tree, dmnsn_line ray,
+                               dmnsn_intersection *intersection);
+bool dmnsn_prtree_inside(const dmnsn_prtree *tree, dmnsn_vector point);
 
 #endif /* DIMENSION_IMPL_PRTREE_H */
diff --git a/libdimension/raytrace.c b/libdimension/raytrace.c
index e10a7c0..8c47b0e 100644
--- a/libdimension/raytrace.c
+++ b/libdimension/raytrace.c
@@ -269,7 +269,7 @@ dmnsn_raytrace_light_ray(const dmnsn_raytrace_state *state,
   while (reclevel) {
     dmnsn_intersection shadow_caster;
     bool shadow_casted
-      = dmnsn_prtree_search(state->prtree, shadow_ray, &shadow_caster);
+      = dmnsn_prtree_intersection(state->prtree, shadow_ray, &shadow_caster);
 
     if (!shadow_casted || shadow_caster.t > 1.0) {
       break;
@@ -425,7 +425,8 @@ dmnsn_raytrace_shoot(dmnsn_raytrace_state *state, dmnsn_line ray)
   --state->reclevel;
 
   dmnsn_intersection intersection;
-  bool intersected = dmnsn_prtree_search(state->prtree, ray, &intersection);
+  bool intersected
+    = dmnsn_prtree_intersection(state->prtree, ray, &intersection);
 
   dmnsn_color color = state->scene->background;
   if (intersected) {
-- 
cgit v1.2.3