diff options
| -rw-r--r-- | bench/libdimension/prtree.c | 6 | ||||
| -rw-r--r-- | libdimension/csg.c | 9 | ||||
| -rw-r--r-- | libdimension/prtree.c | 52 | ||||
| -rw-r--r-- | libdimension/prtree.h | 5 | ||||
| -rw-r--r-- | libdimension/raytrace.c | 5 | ||||
| -rw-r--r-- | tests/libdimension/prtree.c | 2 |
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; } |