diff options
| -rw-r--r-- | src/ix3.c | 59 | ||||
| -rw-r--r-- | src/ix3.h | 2 | ||||
| -rw-r--r-- | src/test.c | 2 |
3 files changed, 40 insertions, 23 deletions
@@ -46,16 +46,12 @@ typedef struct ix3_node_t ix3_node_t; typedef struct ix3_object_t { list_head_t references; /* list of all ix3_node references to this object */ - list_head_t hits; /* node on hit list for non-point searches, to prevent potential double hits like when an object and search both span nodes */ - /* XXX: note this makes non-point searches non-reentrant! i.e. you can't perform another non-point search on the same ix3 - * from a search callback operating on the same ix3. TODO investigate efficient solutions. An obvious one is to simply put - * multiple of these nodes in every object and support a small number of simultaneous non-point searches, which may suffice. - */ v3f_t position; /* position of this object's AABB in space (may leave as 0 if .aabb is absolute) */ v3f_t origin; /* origin of position within object's AABB, 0,0 = center, -1,-1 = min 1,1 = max */ bb3f_t aabb; /* AABB of this object */ float aabb_len_sq; /* length(aabb.max - aabb.min)^2 TODO: this isn't utilized yet, optimization potential */ void *object; /* user handle linking this object to the index */ + list_head_t hits[]; /* hit list nodes for area (non-point) searches, sized by ix3->max_asip */ } ix3_object_t; typedef struct ix3_object_ref_t { @@ -79,6 +75,8 @@ typedef struct ix3_t { bb3f_t aabb; /* spatial bounds of ix3 root */ unsigned max_per_node; /* maximum number of objects to put in a node until max_depth reached */ unsigned max_depth; /* maximum depth of ix3 tree where nodes cease being divided further */ + unsigned max_asip; /* maximum area-searches-in-progress to allow */ + unsigned asip; /* area-search-in-progress count to index ix3_oject_t.hits and enforce max_asip */ ix3_node_t root; /* root node of ix3 octree */ } ix3_t; @@ -463,11 +461,20 @@ _fail: } +/* helper for computing the ix3_object_t size for the supplied ix3 */ +static inline size_t sizeof_object(const ix3_t *ix3) +{ + return sizeof(ix3_object_t) + ix3->max_asip * sizeof(list_head_t); +} + + /* Create a new ix3 index with bounds aabb, splitting nodes > max_per_node until max_depth * If the supplied aabb is NULL, a default one of -1,-1...1,1 is used. + * max_asip specifies the maximum number of area (non-point) searches to support on the ix3, + * a value of 0 disables *any* area searches, 2 is generally sufficient. * Returns NULL on failure. */ -ix3_t * ix3_new(bb3f_t *aabb, unsigned max_per_node, unsigned max_depth) +ix3_t * ix3_new(bb3f_t *aabb, unsigned max_per_node, unsigned max_depth, unsigned max_asip) { bb3f_t default_aabb = {{-1.f, -1.f, -1.f}, {1.f, 1.f, 1.f}}; ix3_t *ix3; @@ -484,6 +491,7 @@ ix3_t * ix3_new(bb3f_t *aabb, unsigned max_per_node, unsigned max_depth) ix3->aabb = *aabb; ix3->max_per_node = max_per_node; ix3->max_depth = max_depth; + ix3->max_asip = max_asip; ix3->node_pad = pad_new(sizeof(ix3_node_t) * 32, PAD_FLAGS_ZERO); if (!ix3->node_pad) @@ -493,7 +501,7 @@ ix3_t * ix3_new(bb3f_t *aabb, unsigned max_per_node, unsigned max_depth) if (!ix3->ref_pad) goto fail_ref_pad; - ix3->object_pad = pad_new(sizeof(ix3_object_t) * 32, PAD_FLAGS_ZERO); + ix3->object_pad = pad_new(sizeof_object(ix3) * 32, PAD_FLAGS_ZERO); if (!ix3->object_pad) goto fail_object_pad; @@ -552,12 +560,14 @@ ix3_object_t * ix3_object_new(ix3_t *ix3, v3f_t *object_position, v3f_t *object_ assert(object_aabb->min.y <= object_aabb->max.y); assert(object_aabb->min.z <= object_aabb->max.z); - o = pad_get(ix3->object_pad, sizeof(ix3_object_t)); + o = pad_get(ix3->object_pad, sizeof_object(ix3)); if (!o) return NULL; INIT_LIST_HEAD(&o->references); - INIT_LIST_HEAD(&o->hits); + for (int i = 0; i < ix3->max_asip; i++) + INIT_LIST_HEAD(&o->hits[i]); + if (object_position) o->position = *object_position; @@ -704,7 +714,7 @@ unsigned ix3_search_by_point(ix3_t *ix3, v3f_t *point, ix3_search_cb *cb, void * /* recursively search the specified node for objects overlapping with search_aabb, * add hits to the list @ hits. */ -static void search_node_by_aabb(ix3_node_t *node, bb3f_t *node_aabb, v3f_t *search_position, v3f_t *search_origin, bb3f_t *search_aabb, list_head_t *hits) +static void search_node_by_aabb(const ix3_t *ix3, ix3_node_t *node, bb3f_t *node_aabb, v3f_t *search_position, v3f_t *search_origin, bb3f_t *search_aabb, list_head_t *hits) { ix3_object_ref_t *ref, *_ref; @@ -720,7 +730,7 @@ static void search_node_by_aabb(ix3_node_t *node, bb3f_t *node_aabb, v3f_t *sear init_octrants(octrants, node_aabb, &node->center); for (i = 0; i < 8; i++) { if (aabb_overlap(NULL, NULL, &octrants[i], search_position, search_origin, search_aabb)) - search_node_by_aabb(&node->children[i], &octrants[i], search_position, search_origin, search_aabb, hits); + search_node_by_aabb(ix3, &node->children[i], &octrants[i], search_position, search_origin, search_aabb, hits); } return; @@ -730,7 +740,7 @@ static void search_node_by_aabb(ix3_node_t *node, bb3f_t *node_aabb, v3f_t *sear if (!aabb_overlap(&ref->object->position, &ref->object->origin, &ref->object->aabb, search_position, search_origin, search_aabb)) continue; - list_move_tail(&ref->object->hits, hits); + list_move_tail(&ref->object->hits[ix3->asip - 1], hits); } } @@ -745,9 +755,12 @@ unsigned ix3_search_by_aabb(ix3_t *ix3, v3f_t *search_position, v3f_t *search_or assert(ix3); assert(search_aabb); + assert(ix3->asip < ix3->max_asip); + + ix3->asip++; if (!aabb_overlap(NULL, NULL, &ix3->aabb, search_position, search_origin, search_aabb)) - return 0; + goto finish; /* XXX: for the aabb-based search a list of hits is first constructed, * this prevents multiple callbacks on the same object by first @@ -758,6 +771,7 @@ unsigned ix3_search_by_aabb(ix3_t *ix3, v3f_t *search_position, v3f_t *search_or * There are two unfortunate consquences to this approach: * 1. No nested/reentrant aabb searches on the same ix3, as the hit list * node is embedded in the ix3_object_t. + * XXX: ^^^ this is no longer the case since adding ix3->(max_)asip * 2. No way to terminate the search from the callback. * This may be mitigated by adding a limit count to the search * function, but that can't address scenarios where you want to @@ -772,10 +786,10 @@ unsigned ix3_search_by_aabb(ix3_t *ix3, v3f_t *search_position, v3f_t *search_or * it if not before calling the callback. This strikes me as very * heavyweight. */ - search_node_by_aabb(&ix3->root, &ix3->aabb, search_position, search_origin, search_aabb, &hits); + search_node_by_aabb(ix3, &ix3->root, &ix3->aabb, search_position, search_origin, search_aabb, &hits); - list_for_each_entry_safe(o, _o, &hits, hits) { - list_del_init(&o->hits); + list_for_each_entry_safe(o, _o, &hits, hits[ix3->asip - 1]) { + list_del_init(&o->hits[ix3->asip - 1]); if (cb) { ix3_search_status_t r; @@ -786,11 +800,7 @@ unsigned ix3_search_by_aabb(ix3_t *ix3, v3f_t *search_position, v3f_t *search_or n_hits++; case IX3_SEARCH_STOP_MISS: - /* XXX: this is necessary, the hits nodes must be kept movable */ - list_for_each_entry_safe(o, _o, &hits, hits) - list_del_init(&o->hits); - - return n_hits; + goto finish; case IX3_SEARCH_MORE_HIT: n_hits++; @@ -806,5 +816,12 @@ unsigned ix3_search_by_aabb(ix3_t *ix3, v3f_t *search_position, v3f_t *search_or n_hits++; } +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; } @@ -31,7 +31,7 @@ typedef enum ix3_search_status_t { typedef ix3_search_status_t (ix3_search_cb)(void *cb_context, ix3_object_t *ix3_object, v3f_t *ix3_object_position, bb3f_t *ix3_object_aabb, void *object); -ix3_t * ix3_new(bb3f_t *aabb, unsigned max_per_node, unsigned max_depth); +ix3_t * ix3_new(bb3f_t *aabb, unsigned max_per_node, unsigned max_depth, unsigned max_asip); void ix3_free(ix3_t *ix3); ix3_object_t * ix3_object_new(ix3_t *ix3, v3f_t *position, v3f_t *origin, bb3f_t *aabb, void *object); void ix3_reset(ix3_t *ix3); @@ -57,7 +57,7 @@ int main(int argc, char *argv[]) ix3_object_t *o, *j; ix3_t *ix3; - ix3 = ix3_new(NULL, 2, 8); + ix3 = ix3_new(NULL, 2, 8, 1); if (!ix3) { fprintf(stderr, "unable to create index\n"); return 1; |