libix3: add ix3_search_by_aabb_cb()

This exposes a callback interface for supplying the AABB overlap
test used to determine node traversal and object filtering.

In advanced use cases like transformed 3D inersection testing of
two ix3 instances one needs to run user-supplied code in the
tree traversal with the node AABBs provided for e.g. transformed
searches against another ix3.

Other than the new ix3_aabb_cb_t hook, its use is identical to
ix3_search_by_aabb().

1 files changed, 140 insertions, 0 deletions

diff --git a/src/ix3.c b/src/ix3.c
index f135cdd..81a71c3 100644
--- a/src/ix3.c
+++ b/src/ix3.c
@@ -824,3 +824,143 @@ finish:
 
 	return n_hits;
 }
+
+
+/* recursively search the specified node for objects with all aabb's being
+ * filtered by aabb_cb, add hits to the list @ hits.
+ */
+static int search_node_by_aabb_cb(ix3_t *ix3, ix3_node_t *node, bb3f_t *node_aabb, ix3_aabb_cb_t *aabb_cb, void *aabb_cb_context, list_head_t *hits)
+{
+	ix3_object_ref_t	*ref;
+
+	assert(node);
+	assert(node_aabb);
+	assert(aabb_cb);
+	assert(hits);
+
+	if (node->children) {
+		bb3f_t	octrants[8];
+		int	i;
+
+		init_octrants(octrants, node_aabb, &node->center);
+		for (i = 0; i < 8; i++) {
+			switch (aabb_cb(aabb_cb_context, &octrants[i])) {
+			case IX3_SEARCH_STOP_HIT:
+				(void) search_node_by_aabb_cb(ix3, &node->children[i], &octrants[i], aabb_cb, aabb_cb_context, hits);
+
+			case IX3_SEARCH_STOP_MISS:
+				return 0;
+
+			case IX3_SEARCH_MORE_HIT:
+				if (!search_node_by_aabb_cb(ix3, &node->children[i], &octrants[i], aabb_cb, aabb_cb_context, hits))
+					return 0;
+
+			case IX3_SEARCH_MORE_MISS:
+				continue;
+
+			default:
+				assert(0);
+			}
+		}
+
+		return 1;
+	}
+
+	list_for_each_entry(ref, &node->objects, objects) {
+		switch (aabb_cb(aabb_cb_context, &ref->object->aabb)) {
+		case IX3_SEARCH_STOP_HIT:
+			list_move_tail(&ref->object->hits[ix3->asip - 1], hits);
+
+		case IX3_SEARCH_STOP_MISS:
+			return 0;
+
+		case IX3_SEARCH_MORE_HIT:
+			list_move_tail(&ref->object->hits[ix3->asip - 1], hits);
+
+		case IX3_SEARCH_MORE_MISS:
+			continue;
+
+		default:
+			assert(0);
+		}
+	}
+
+	return 1;
+}
+
+
+/* Search ix3 using an AABB filter callback
+ *
+ * This is basically identical to ix3_search_by_aabb(), but with the aabb
+ * traversal test abstracted behind a user-supplied calllback; aabb_cb
+ *
+ * The ix3_search_status_t return type enum is reused by ix3_aabb_cb_t, their
+ * meaning is as one would expect:
+ *
+ * IX3_SEARCH_STOP_MISS: Do not enter the current AABB, and stop further
+ * searching.
+ *
+ * IX3_SEARCH_STOP_HIT: Enter the current AABB, but stop afterwards (no
+ * parents, no siblings).
+ *
+ * IX3_SEARCH_MORE_MISS: Do not enter the current AABB, but continue
+ * searching siblings/parents if present.
+ *
+ * IX3_SEARCH_MORE_HIT: Enter the current AABB, and continue searching
+ * siblings/parents if present.
+ */
+unsigned ix3_search_by_aabb_cb(ix3_t *ix3, ix3_aabb_cb_t *aabb_cb, void *aabb_cb_context, ix3_object_cb_t *object_cb, void *object_cb_context)
+{
+	unsigned		n_hits = 0;
+	LIST_HEAD		(hits);
+	ix3_object_t		*o, *_o;
+	ix3_search_status_t	r;
+
+	assert(ix3);
+	assert(aabb_cb);
+	assert(ix3->asip < ix3->max_asip);
+
+	ix3->asip++;
+
+	r = aabb_cb(aabb_cb_context, &ix3->aabb);
+	if (r == IX3_SEARCH_MORE_MISS || r == IX3_SEARCH_STOP_MISS)
+		goto finish;
+
+	(void) search_node_by_aabb_cb(ix3, &ix3->root, &ix3->aabb, aabb_cb, aabb_cb_context, &hits);
+
+	list_for_each_entry_safe(o, _o, &hits, hits[ix3->asip - 1]) {
+		list_del_init(&o->hits[ix3->asip - 1]);
+
+		if (!object_cb) {
+			n_hits++;
+			continue;
+		}
+
+		r = object_cb(object_cb_context, o, &o->position, &o->aabb, o->object);
+		switch (r) {
+		case IX3_SEARCH_STOP_HIT:
+			n_hits++;
+
+		case IX3_SEARCH_STOP_MISS:
+			goto finish;
+
+		case IX3_SEARCH_MORE_HIT:
+			n_hits++;
+
+		case IX3_SEARCH_MORE_MISS:
+			continue;
+
+		default:
+			assert(0);
+		}
+	}
+
+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;
+}