diff options
| -rw-r--r-- | src/ix3.c | 140 | ||||
| -rw-r--r-- | src/ix3.h | 2 |
2 files changed, 142 insertions, 0 deletions
@@ -824,3 +824,143 @@ finish: return n_hits; } + + +/* recursively search the specified node for objects with all aabb's being + * filtered by aabb_cb, add hits to the list @ hits. + */ +static int search_node_by_aabb_cb(ix3_t *ix3, ix3_node_t *node, bb3f_t *node_aabb, ix3_aabb_cb_t *aabb_cb, void *aabb_cb_context, list_head_t *hits) +{ + ix3_object_ref_t *ref; + + assert(node); + assert(node_aabb); + assert(aabb_cb); + assert(hits); + + if (node->children) { + bb3f_t octrants[8]; + int i; + + init_octrants(octrants, node_aabb, &node->center); + for (i = 0; i < 8; i++) { + switch (aabb_cb(aabb_cb_context, &octrants[i])) { + case IX3_SEARCH_STOP_HIT: + (void) search_node_by_aabb_cb(ix3, &node->children[i], &octrants[i], aabb_cb, aabb_cb_context, hits); + + case IX3_SEARCH_STOP_MISS: + return 0; + + case IX3_SEARCH_MORE_HIT: + if (!search_node_by_aabb_cb(ix3, &node->children[i], &octrants[i], aabb_cb, aabb_cb_context, hits)) + return 0; + + case IX3_SEARCH_MORE_MISS: + continue; + + default: + assert(0); + } + } + + return 1; + } + + list_for_each_entry(ref, &node->objects, objects) { + switch (aabb_cb(aabb_cb_context, &ref->object->aabb)) { + case IX3_SEARCH_STOP_HIT: + list_move_tail(&ref->object->hits[ix3->asip - 1], hits); + + case IX3_SEARCH_STOP_MISS: + return 0; + + case IX3_SEARCH_MORE_HIT: + list_move_tail(&ref->object->hits[ix3->asip - 1], hits); + + case IX3_SEARCH_MORE_MISS: + continue; + + default: + assert(0); + } + } + + return 1; +} + + +/* Search ix3 using an AABB filter callback + * + * This is basically identical to ix3_search_by_aabb(), but with the aabb + * traversal test abstracted behind a user-supplied calllback; aabb_cb + * + * The ix3_search_status_t return type enum is reused by ix3_aabb_cb_t, their + * meaning is as one would expect: + * + * IX3_SEARCH_STOP_MISS: Do not enter the current AABB, and stop further + * searching. + * + * IX3_SEARCH_STOP_HIT: Enter the current AABB, but stop afterwards (no + * parents, no siblings). + * + * IX3_SEARCH_MORE_MISS: Do not enter the current AABB, but continue + * searching siblings/parents if present. + * + * IX3_SEARCH_MORE_HIT: Enter the current AABB, and continue searching + * siblings/parents if present. + */ +unsigned ix3_search_by_aabb_cb(ix3_t *ix3, ix3_aabb_cb_t *aabb_cb, void *aabb_cb_context, ix3_object_cb_t *object_cb, void *object_cb_context) +{ + unsigned n_hits = 0; + LIST_HEAD (hits); + ix3_object_t *o, *_o; + ix3_search_status_t r; + + assert(ix3); + assert(aabb_cb); + assert(ix3->asip < ix3->max_asip); + + ix3->asip++; + + r = aabb_cb(aabb_cb_context, &ix3->aabb); + if (r == IX3_SEARCH_MORE_MISS || r == IX3_SEARCH_STOP_MISS) + goto finish; + + (void) search_node_by_aabb_cb(ix3, &ix3->root, &ix3->aabb, aabb_cb, aabb_cb_context, &hits); + + list_for_each_entry_safe(o, _o, &hits, hits[ix3->asip - 1]) { + list_del_init(&o->hits[ix3->asip - 1]); + + if (!object_cb) { + n_hits++; + continue; + } + + r = object_cb(object_cb_context, o, &o->position, &o->aabb, o->object); + switch (r) { + case IX3_SEARCH_STOP_HIT: + n_hits++; + + case IX3_SEARCH_STOP_MISS: + goto finish; + + case IX3_SEARCH_MORE_HIT: + n_hits++; + + case IX3_SEARCH_MORE_MISS: + continue; + + default: + assert(0); + } + } + +finish: + /* XXX: this is necessary, the hits nodes must be kept movable */ + list_for_each_entry_safe(o, _o, &hits, hits[ix3->asip - 1]) + list_del_init(&o->hits[ix3->asip - 1]); + + ix3->asip--; + + return n_hits; +} @@ -30,6 +30,7 @@ typedef enum ix3_search_status_t { } ix3_search_status_t; typedef ix3_search_status_t (ix3_object_cb_t)(void *cb_context, ix3_object_t *ix3_object, v3f_t *ix3_object_position, bb3f_t *ix3_object_aabb, void *object); +typedef ix3_search_status_t (ix3_aabb_cb_t)(void *cb_context, const bb3f_t *ix3_node_aabb); ix3_t * ix3_new(bb3f_t *aabb, unsigned max_per_node, unsigned max_depth, unsigned max_asip); void ix3_free(ix3_t *ix3); @@ -41,5 +42,6 @@ int ix3_object_aabb_overlap(ix3_t *ix3, ix3_object_t *object, v3f_t *aabb_positi unsigned ix3_search_by_point(ix3_t *ix3, v3f_t *point, ix3_object_cb_t *cb, void *arg); unsigned ix3_search_by_aabb(ix3_t *ix3, v3f_t *search_position, v3f_t *search_origin, bb3f_t *search_aabb, ix3_object_cb_t *cb, void *arg); unsigned ix3_search_by_ray(ix3_t *ix3, v3f_t *origin, v3f_t *direction, ix3_object_cb_t *cb, void *arg); +unsigned ix3_search_by_aabb_cb(ix3_t *ix3, ix3_aabb_cb_t *aabb_cb, void *aabb_cb_context, ix3_object_cb_t *object_cb, void *object_cb_context); #endif |