diff options
Diffstat (limited to 'libdimension')
| -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 |
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) { |