libix3: support nested area searches

In 3D game engine use, it's convenient to be able to construct an ix3
for a model's mesh, in the model's local coordinate system.  This
model may then be instanced any number of times in the world via
matrix transformations.

When such instances are collidable objects and encounter eachother in
the world, it becomes necessary to perform nested area searches on the
same ix3.

The existing code only allowed for a single area search on a given
ix3 at a time.  This code changes that to a limit supplied to
ix3_new() as "max_asip" for "area searches in progress".

In scenarios where only point searches will be performed, 0 may be
supplied to save memory over the previous implementation.  A value
of 2 is satisfactory for my existing 3D game use cases, but any value
is supported, it just takes more memory in the ix3_object_t struct.

3 files changed, 40 insertions, 23 deletions

diff --git a/src/ix3.c b/src/ix3.c
index ab5af8c..8b6e64f 100644
--- a/src/ix3.c
+++ b/src/ix3.c
@@ -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;
 }
diff --git a/src/ix3.h b/src/ix3.h
index 8739bf3..99c1530 100644
--- a/src/ix3.h
+++ b/src/ix3.h
@@ -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);
diff --git a/src/test.c b/src/test.c
index 0110197..abb2c1c 100644
--- a/src/test.c
+++ b/src/test.c
@@ -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;