summaryrefslogtreecommitdiffstats
path: root/libdimension
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2010-06-06 00:07:14 -0600
committerTavian Barnes <tavianator@gmail.com>2010-06-06 00:15:25 -0600
commit8452b0227e3b7bf6fc012309a49cd1a14de6ae3d (patch)
tree342842a50fb278dc20fe696e86fdde63b09c4626 /libdimension
parent6681e5e78772be7168b5ed2a5688d2e89ee4f5d5 (diff)
downloaddimension-8452b0227e3b7bf6fc012309a49cd1a14de6ae3d.tar.xz
New dmnsn_prtree_inside() function, rename dmnsn_prtree_search().
Diffstat (limited to 'libdimension')
-rw-r--r--libdimension/csg.c9
-rw-r--r--libdimension/prtree.c52
-rw-r--r--libdimension/prtree.h5
-rw-r--r--libdimension/raytrace.c5
4 files changed, 55 insertions, 16 deletions
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) {