New dmnsn_prtree_inside() function, rename dmnsn_prtree_search().

6 files changed, 59 insertions, 20 deletions

diff --git a/bench/libdimension/prtree.c b/bench/libdimension/prtree.c
index 904d3ef..1f1c5dd 100644
--- a/bench/libdimension/prtree.c
+++ b/bench/libdimension/prtree.c
@@ -75,14 +75,14 @@ main()
   });
   printf("dmnsn_new_prtree(): %ld\n", sandglass.grains);
 
-  /* dmnsn_prtree_search() */
+  /* dmnsn_prtree_intersection() */
   ray.x0 = dmnsn_new_vector(0.0, 0.0, -2.0);
   ray.n  = dmnsn_new_vector(0.0, 0.0, 1.0);
 
   sandglass_bench_fine(&sandglass, {
-    dmnsn_prtree_search(tree, ray, &intersection);
+    dmnsn_prtree_intersection(tree, ray, &intersection);
   });
-  printf("dmnsn_prtree_search(): %ld\n", sandglass.grains);
+  printf("dmnsn_prtree_intersection(): %ld\n", sandglass.grains);
 
   /* Cleanup */
   dmnsn_delete_prtree(tree);
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) {
diff --git a/tests/libdimension/prtree.c b/tests/libdimension/prtree.c
index 9ea8a1e..3738652 100644
--- a/tests/libdimension/prtree.c
+++ b/tests/libdimension/prtree.c
@@ -74,7 +74,7 @@ main()
     dmnsn_new_vector(0.0, 0.0, 1.0)
   );
 
-  if (!dmnsn_prtree_search(prtree, ray, &intersection)) {
+  if (!dmnsn_prtree_intersection(prtree, ray, &intersection)) {
     fprintf(stderr, "--- Didn't find intersection! ---\n");
     return EXIT_FAILURE;
   }