summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorVito Caputo <vcaputo@pengaru.com>2018-12-14 03:59:20 -0800
committerVito Caputo <vcaputo@pengaru.com>2018-12-14 03:59:20 -0800
commit6935461dbb1355b2df62c8694a07b6b9ad309bf2 (patch)
treecf55181c5dbbce2d797102b53b673e1a3943f724
parent8269bfb5dc9448b7e245b2edf01e741ded3bab1c (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.c58
-rw-r--r--src/ix2.h2
-rw-r--r--src/test.c2
3 files changed, 39 insertions, 23 deletions
diff --git a/src/ix2.c b/src/ix2.c
index a7aea16..e87cf2c 100644
--- a/src/ix2.c
+++ b/src/ix2.c
@@ -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;
}
diff --git a/src/ix2.h b/src/ix2.h
index 2785f36..d41216e 100644
--- a/src/ix2.h
+++ b/src/ix2.h
@@ -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);
diff --git a/src/test.c b/src/test.c
index 1d14a98..89bd671 100644
--- a/src/test.c
+++ b/src/test.c
@@ -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;
© 2021 All Rights Reserved