diff options
Diffstat (limited to 'src/ix2.c')
-rw-r--r-- | src/ix2.c | 58 |
1 files changed, 37 insertions, 21 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; } |