diff options
author | Vito Caputo <vcaputo@pengaru.com> | 2018-12-14 03:59:20 -0800 |
---|---|---|
committer | Vito Caputo <vcaputo@pengaru.com> | 2018-12-14 03:59:20 -0800 |
commit | 6935461dbb1355b2df62c8694a07b6b9ad309bf2 (patch) | |
tree | cf55181c5dbbce2d797102b53b673e1a3943f724 | |
parent | 8269bfb5dc9448b7e245b2edf01e741ded3bab1c (diff) |
libix2: support nested area searches
See 6ea78c53 in libix3 for more info, this replicates the change to
keep them in something resembling API parity.
-rw-r--r-- | src/ix2.c | 58 | ||||
-rw-r--r-- | src/ix2.h | 2 | ||||
-rw-r--r-- | src/test.c | 2 |
3 files changed, 39 insertions, 23 deletions
@@ -40,16 +40,12 @@ typedef struct ix2_node_t ix2_node_t; typedef struct ix2_object_t { list_head_t references; /* list of all ix2_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 ix2 - * from a search callback operating on the same ix2. 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. - */ v2f_t position; /* position of this object's AABB in space (may leave as 0 if .aabb is absolute) */ v2f_t origin; /* origin of position within object's AABB, 0,0 = center, -1,-1 = min 1,1 = max */ bb2f_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 ix2->max_asip */ } ix2_object_t; typedef struct ix2_object_ref_t { @@ -73,6 +69,8 @@ typedef struct ix2_t { bb2f_t aabb; /* spatial bounds of ix2 root */ unsigned max_per_node; /* maximum number of objects to put in a node until max_depth reached */ unsigned max_depth; /* maximum depth of ix2 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 ix2_oject_t.hits and enforce max_asip */ ix2_node_t root; /* root node of ix2 quadtree */ } ix2_t; @@ -405,11 +403,20 @@ _fail: } +/* helper for computing the ix2_object_t size for the supplied ix2 */ +static inline size_t sizeof_object(const ix2_t *ix2) +{ + return sizeof(ix2_object_t) + ix2->max_asip * sizeof(list_head_t); +} + + /* Create a new ix2 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 ix2, + * a value of 0 disables *any* area searches, 2 is generally sufficient. * Returns NULL on failure. */ -ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth) +ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth, unsigned max_asip) { bb2f_t default_aabb = {{-1.f, -1.f}, {1.f, 1.f}}; ix2_t *ix2; @@ -426,6 +433,7 @@ ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth) ix2->aabb = *aabb; ix2->max_per_node = max_per_node; ix2->max_depth = max_depth; + ix2->max_asip = max_asip; ix2->node_pad = pad_new(sizeof(ix2_node_t) * 8, PAD_FLAGS_ZERO); if (!ix2->node_pad) @@ -435,7 +443,7 @@ ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth) if (!ix2->ref_pad) goto fail_ref_pad; - ix2->object_pad = pad_new(sizeof(ix2_object_t) * 32, PAD_FLAGS_ZERO); + ix2->object_pad = pad_new(sizeof_object(ix2) * 32, PAD_FLAGS_ZERO); if (!ix2->object_pad) goto fail_object_pad; @@ -493,12 +501,13 @@ ix2_object_t * ix2_object_new(ix2_t *ix2, v2f_t *object_position, v2f_t *object_ assert(object_aabb->min.x <= object_aabb->max.x); assert(object_aabb->min.y <= object_aabb->max.y); - o = pad_get(ix2->object_pad, sizeof(ix2_object_t)); + o = pad_get(ix2->object_pad, sizeof_object(ix2)); if (!o) return NULL; INIT_LIST_HEAD(&o->references); - INIT_LIST_HEAD(&o->hits); + for (int i = 0; i < ix2->max_asip; i++) + INIT_LIST_HEAD(&o->hits[i]); if (object_position) o->position = *object_position; @@ -644,7 +653,7 @@ unsigned ix2_search_by_point(ix2_t *ix2, v2f_t *point, ix2_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(ix2_node_t *node, bb2f_t *node_aabb, v2f_t *search_position, v2f_t *search_origin, bb2f_t *search_aabb, list_head_t *hits) +static void search_node_by_aabb(const ix2_t *ix2, ix2_node_t *node, bb2f_t *node_aabb, v2f_t *search_position, v2f_t *search_origin, bb2f_t *search_aabb, list_head_t *hits) { ix2_object_ref_t *ref, *_ref; @@ -660,7 +669,7 @@ static void search_node_by_aabb(ix2_node_t *node, bb2f_t *node_aabb, v2f_t *sear init_quadrants(quadrants, node_aabb, &node->center); for (i = 0; i < 4; i++) { if (aabb_overlap(NULL, NULL, &quadrants[i], search_position, search_origin, search_aabb)) - search_node_by_aabb(&node->children[i], &quadrants[i], search_position, search_origin, search_aabb, hits); + search_node_by_aabb(ix2, &node->children[i], &quadrants[i], search_position, search_origin, search_aabb, hits); } return; @@ -670,7 +679,7 @@ static void search_node_by_aabb(ix2_node_t *node, bb2f_t *node_aabb, v2f_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[ix2->asip - 1], hits); } } @@ -685,9 +694,12 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_or assert(ix2); assert(search_aabb); + assert(ix2->asip < ix2->max_asip); + + ix2->asip++; if (!aabb_overlap(NULL, NULL, &ix2->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 @@ -698,6 +710,7 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_or * There are two unfortunate consquences to this approach: * 1. No nested/reentrant aabb searches on the same ix2, as the hit list * node is embedded in the ix2_object_t. + * XXX: ^^^ this is no longer the case since adding ix2->(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 @@ -712,10 +725,10 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_or * it if not before calling the callback. This strikes me as very * heavyweight. */ - search_node_by_aabb(&ix2->root, &ix2->aabb, search_position, search_origin, search_aabb, &hits); + search_node_by_aabb(ix2, &ix2->root, &ix2->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[ix2->asip - 1]) { + list_del_init(&o->hits[ix2->asip - 1]); if (cb) { ix2_search_status_t r; @@ -726,11 +739,7 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_or n_hits++; case IX2_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 IX2_SEARCH_MORE_HIT: n_hits++; @@ -746,5 +755,12 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_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[ix2->asip - 1]) + list_del_init(&o->hits[ix2->asip - 1]); + + ix2->asip--; + return n_hits; } @@ -31,7 +31,7 @@ typedef enum ix2_search_status_t { typedef ix2_search_status_t (ix2_search_cb)(void *cb_context, ix2_object_t *ix2_object, v2f_t *ix2_object_position, bb2f_t *ix2_object_aabb, void *object); -ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth); +ix2_t * ix2_new(bb2f_t *aabb, unsigned max_per_node, unsigned max_depth, unsigned max_asip); void ix2_reset(ix2_t *ix2); void ix2_free(ix2_t *ix2); ix2_object_t * ix2_object_new(ix2_t *ix2, v2f_t *position, v2f_t *origin, bb2f_t *aabb, void *object); @@ -57,7 +57,7 @@ int main(int argc, char *argv[]) ix2_object_t *o, *j; ix2_t *ix2; - ix2 = ix2_new(&aabb, 2, 8); + ix2 = ix2_new(&aabb, 2, 8, 1); if (!ix2) { fprintf(stderr, "unable to create index\n"); return 1; |