libix2: introduce AABB-independent object position

Much like libstage nodes can now have their position set using relative
AABBs, it's convenient to have the same paradigm in libix2.

2 files changed, 61 insertions, 38 deletions

diff --git a/src/ix2.c b/src/ix2.c
index 04513e1..79aa7ab 100644
--- a/src/ix2.c
+++ b/src/ix2.c
@@ -43,6 +43,7 @@ typedef struct ix2_object_t {
 					 * 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) */
 	aabb_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 */
@@ -73,21 +74,26 @@ static ix2_object_t * add_object(ix2_t *ix2, unsigned *depth, ix2_node_t *node,
 
 
 /* Check if point resides within aabb */
-static inline int aabb_contains_point(aabb_t *aabb, v2f_t *point)
+static inline int aabb_contains_point(v2f_t *aabb_position, aabb_t *aabb, v2f_t *point)
 {
+	v2f_t	position = {};
+
 	assert(aabb);
 	assert(point);
 
-	if (point->x < aabb->min.x)
+	if (!aabb_position)
+		aabb_position = &position;
+
+	if (point->x < (aabb_position->x + aabb->min.x))
 		return 0;
 
-	if (point->x > aabb->max.x)
+	if (point->x > (aabb_position->x + aabb->max.x))
 		return 0;
 
-	if (point->y < aabb->min.y)
+	if (point->y < (aabb_position->y + aabb->min.y))
 		return 0;
 
-	if (point->y > aabb->max.y)
+	if (point->y > (aabb_position->y + aabb->max.y))
 		return 0;
 	
 	return 1;
@@ -95,15 +101,23 @@ static inline int aabb_contains_point(aabb_t *aabb, v2f_t *point)
 
 
 /* check if a and b overlap */
-static inline int aabb_overlap(aabb_t *a, aabb_t *b)
+static inline int aabb_overlap(v2f_t *a_position, aabb_t *a, v2f_t *b_position, aabb_t *b)
 {
+	v2f_t	position = {};
+
 	assert(a);
 	assert(b);
 
-	return (a->min.x <= b->max.x &&
-		a->max.x >= b->min.x &&
-		a->min.y <= b->max.y &&
-		a->max.y >= b->min.y);
+	if (!a_position)
+		a_position = &position;
+
+	if (!b_position)
+		b_position = &position;
+
+	return ((a->min.x + a_position->x) <= (b->max.x + b_position->x) &&
+		(a->max.x + a_position->x) >= (b->min.x + b_position->x) &&
+		(a->min.y + a_position->y) <= (b->max.y + b_position->y) &&
+		(a->max.y + a_position->y) >= (b->min.y + b_position->y));
 }
 
 
@@ -288,7 +302,7 @@ ix2_node_t * split_node(ix2_t *ix2, unsigned *depth, ix2_node_t *node, aabb_t *n
 
 		/* XXX: this can probably be done more efficiently */
 		for (i = 0; i < 4; i++) {
-			if (!aabb_overlap(&quadrants[i], &o->aabb))
+			if (!aabb_overlap(NULL, &quadrants[i], &o->position, &o->aabb))
 				continue;
 
 			if (!add_object(ix2, depth, &node->children[i], &quadrants[i], o, &r))
@@ -334,7 +348,7 @@ static ix2_object_t * add_object(ix2_t *ix2, unsigned *depth, ix2_node_t *node,
 		*depth++;
 		init_quadrants(quadrants, node_aabb, &node->center);
 		for (i = 0; i < 4; i++) {
-			if (!aabb_overlap(&quadrants[i], &object->aabb))
+			if (!aabb_overlap(NULL, &quadrants[i], &object->position, &object->aabb))
 				continue;
 
 			if (!add_object(ix2, depth, &node->children[i], &quadrants[i], object, reference_cache))
@@ -404,7 +418,7 @@ void ix2_free(ix2_t *ix2)
 
 
 /* Insert object spatially described by object_aabb into the index ix2 */
-ix2_object_t * ix2_insert_object(ix2_t *ix2, aabb_t *object_aabb, void *object)
+ix2_object_t * ix2_insert_object(ix2_t *ix2, float x, float y, aabb_t *object_aabb, void *object)
 {
 	unsigned	depth = 0;
 	ix2_object_t	*o;
@@ -421,11 +435,13 @@ ix2_object_t * ix2_insert_object(ix2_t *ix2, aabb_t *object_aabb, void *object)
 	INIT_LIST_HEAD(&o->references);
 	INIT_LIST_HEAD(&o->hits);
 
+	o->position.x = x;
+	o->position.y = y;
 	o->aabb = *object_aabb;
 	o->object = object;
 	o->aabb_len_sq = aabb_len_sq(object_aabb);
 
-	if (!aabb_overlap(&ix2->aabb, object_aabb))
+	if (!aabb_overlap(NULL, &ix2->aabb, &o->position, &o->aabb))
 		return o;
 
 	return add_object(ix2, &depth, &ix2->root, &ix2->aabb, o, NULL);
@@ -445,18 +461,18 @@ void ix2_remove_object(ix2_t *ix2, ix2_object_t *object)
 }
 
 
-/* Move already inserted object to new aabb. */
+/* Move already inserted object to new position and optional aabb. */
+/* If object_aabb is omitted, only the x,y coordinates are updated */
 /* Returns object on success, NULL on failure. */
 /* On failure object is removed and freed. XXX: change to leave where it was? */
-ix2_object_t * ix2_move_object(ix2_t *ix2, ix2_object_t *object, aabb_t *object_aabb)
+ix2_object_t * ix2_move_object(ix2_t *ix2, ix2_object_t *object, float object_x, float object_y, aabb_t *object_aabb)
 {
 	unsigned	depth = 0;
 
 	assert(ix2);
 	assert(object);
-	assert(object_aabb);
-	assert(object_aabb->min.x <= object_aabb->max.x);
-	assert(object_aabb->min.y <= object_aabb->max.y);
+	assert(!object_aabb || object_aabb->min.x <= object_aabb->max.x);
+	assert(!object_aabb || object_aabb->min.y <= object_aabb->max.y);
 
 	/* TODO FIXME: cache and reuse the references, requires changing
 	 * add_object to receive a list of cached references rather than the
@@ -466,10 +482,14 @@ ix2_object_t * ix2_move_object(ix2_t *ix2, ix2_object_t *object, aabb_t *object_
 	 */
 	unlink_object(object, NULL);
 
-	object->aabb = *object_aabb;
-	object->aabb_len_sq = aabb_len_sq(object_aabb);
+	object->position.x = object_x;
+	object->position.y = object_y;
+	if (object_aabb) {
+		object->aabb = *object_aabb;
+		object->aabb_len_sq = aabb_len_sq(object_aabb);
+	}
 
-	if (!aabb_overlap(&ix2->aabb, object_aabb))
+	if (!aabb_overlap(NULL, &ix2->aabb, &object->position, &object->aabb))
 		return object;
 
 	return add_object(ix2, &depth, &ix2->root, &ix2->aabb, object, NULL /* TODO */);
@@ -488,7 +508,7 @@ unsigned ix2_search_by_point(ix2_t *ix2, v2f_t *point, ix2_search_cb cb, void *c
 	assert(ix2);
 	assert(point);
 
-	if (!aabb_contains_point(&ix2->aabb, point))
+	if (!aabb_contains_point(NULL, &ix2->aabb, point))
 		return 0;
 
 	node = &ix2->root;
@@ -505,7 +525,7 @@ unsigned ix2_search_by_point(ix2_t *ix2, v2f_t *point, ix2_search_cb cb, void *c
 		 */
 		init_quadrants(quadrants, &node_aabb, &node->center);
 		for (i = 0; i < 4; i++) {
-			if (aabb_contains_point(&quadrants[i], point))
+			if (aabb_contains_point(NULL, &quadrants[i], point))
 				break;
 		}
 
@@ -515,13 +535,14 @@ unsigned ix2_search_by_point(ix2_t *ix2, v2f_t *point, ix2_search_cb cb, void *c
 
 	/* search the leaf for matches */
 	list_for_each_entry_safe(ref, _ref, &node->objects, objects) {
-		if (!aabb_contains_point(&ref->object->aabb, point))
+		if (!aabb_contains_point(&ref->object->position, &ref->object->aabb, point))
 			continue;
 
 		if (cb) {
 			ix2_search_status_t	r;
+			ix2_object_t		*o = ref->object;
 
-			r = cb(cb_context, ref->object, &ref->object->aabb, ref->object->object);
+			r = cb(cb_context, o, &o->position, &o->aabb, o->object);
 			if (r == IX2_SEARCH_STOP)
 				break;
 
@@ -540,12 +561,13 @@ unsigned ix2_search_by_point(ix2_t *ix2, v2f_t *point, ix2_search_cb cb, void *c
 /* 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, aabb_t *node_aabb, aabb_t *search_aabb, list_head_t *hits)
+static void search_node_by_aabb(ix2_node_t *node, aabb_t *node_aabb, v2f_t *search_position, aabb_t *search_aabb, list_head_t *hits)
 {
 	ix2_object_ref_t	*ref, *_ref;
 
 	assert(node);
 	assert(node_aabb);
+	assert(search_position);
 	assert(search_aabb);
 	assert(hits);
 
@@ -555,8 +577,8 @@ static void search_node_by_aabb(ix2_node_t *node, aabb_t *node_aabb, aabb_t *sea
 
 		init_quadrants(quadrants, node_aabb, &node->center);
 		for (i = 0; i < 4; i++) {
-			if (aabb_overlap(&quadrants[i], search_aabb))
-				search_node_by_aabb(&node->children[i], &quadrants[i], search_aabb, hits);
+			if (aabb_overlap(NULL, &quadrants[i], search_position, search_aabb))
+				search_node_by_aabb(&node->children[i], &quadrants[i], search_position, search_aabb, hits);
 		}
 
 		return;
@@ -564,7 +586,7 @@ static void search_node_by_aabb(ix2_node_t *node, aabb_t *node_aabb, aabb_t *sea
 
 
 	list_for_each_entry_safe(ref, _ref, &node->objects, objects) {
-		if (!aabb_overlap(&ref->object->aabb, search_aabb))
+		if (!aabb_overlap(&ref->object->position, &ref->object->aabb, search_position, search_aabb))
 			continue;
 
 			list_move_tail(&ref->object->hits, hits);
@@ -574,16 +596,17 @@ static void search_node_by_aabb(ix2_node_t *node, aabb_t *node_aabb, aabb_t *sea
 
 /* Search for objects overlapping an aabb in index ix2. */
 /* Returns number of cb calls performed on hits, if cb is NULL calls will be skipped but hits still counted for return. */
-unsigned ix2_search_by_aabb(ix2_t *ix2, aabb_t *search_aabb, ix2_search_cb cb, void *cb_context)
+unsigned ix2_search_by_aabb(ix2_t *ix2, float x, float y, aabb_t *search_aabb, ix2_search_cb cb, void *cb_context)
 {
 	unsigned	n_hits = 0;
 	LIST_HEAD	(hits);
 	ix2_object_t	*o, *_o;
+	v2f_t		position = {.x = x, .y = y};
 
 	assert(ix2);
 	assert(search_aabb);
 
-	if (!aabb_overlap(&ix2->aabb, search_aabb))
+	if (!aabb_overlap(NULL, &ix2->aabb, &position, search_aabb))
 		return 0;
 
 	/* XXX: for the aabb-based search a list of hits is first constructed,
@@ -609,7 +632,7 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, aabb_t *search_aabb, ix2_search_cb cb, v
 	 *   it if not before calling the callback.  This strikes me as very
 	 *   heavyweight.
 	 */
-	search_node_by_aabb(&ix2->root, &ix2->aabb, search_aabb, &hits);
+	search_node_by_aabb(&ix2->root, &ix2->aabb, &position, search_aabb, &hits);
 
 	list_for_each_entry_safe(o, _o, &hits, hits) {
 		list_del_init(&o->hits);
@@ -617,7 +640,7 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, aabb_t *search_aabb, ix2_search_cb cb, v
 		if (cb) {
 			ix2_search_status_t	r;
 
-			r = cb(cb_context, o, &o->aabb, o->object);
+			r = cb(cb_context, o, &o->position, &o->aabb, o->object);
 			if (r == IX2_SEARCH_STOP)
 				break;
 
diff --git a/src/ix2.h b/src/ix2.h
index 345a310..54bcd46 100644
--- a/src/ix2.h
+++ b/src/ix2.h
@@ -28,15 +28,15 @@ typedef enum ix2_search_status_t {
 	IX2_SEARCH_CONTINUE
 } ix2_search_status_t;
 
-typedef ix2_search_status_t (*ix2_search_cb)(void *cb_context, ix2_object_t *ix2_object, aabb_t *ix2_object_aabb, void *object);
+typedef ix2_search_status_t (*ix2_search_cb)(void *cb_context, ix2_object_t *ix2_object, v2f_t *ix2_object_position, aabb_t *ix2_object_aabb, void *object);
 
 ix2_t * ix2_new(aabb_t *aabb, unsigned max_per_node, unsigned max_depth);
 void ix2_free(ix2_t *ix2);
-ix2_object_t * ix2_insert_object(ix2_t *ix2, aabb_t *aabb, void *object);
+ix2_object_t * ix2_insert_object(ix2_t *ix2, float x, float y, aabb_t *aabb, void *object);
 void ix2_remove_object(ix2_t *ix2, ix2_object_t *object);
-ix2_object_t * ix2_move_object(ix2_t *ix2, ix2_object_t *object, aabb_t *aabb);
+ix2_object_t * ix2_move_object(ix2_t *ix2, ix2_object_t *object, float object_x, float object_y, aabb_t *object_aabb);
 unsigned ix2_search_by_point(ix2_t *ix2, v2f_t *point, ix2_search_cb cb, void *arg);
-unsigned ix2_search_by_aabb(ix2_t *ix2, aabb_t *aabb, ix2_search_cb cb, void *arg);
+unsigned ix2_search_by_aabb(ix2_t *ix2, float x, float y, aabb_t *aabb, ix2_search_cb cb, void *arg);
 unsigned ix2_search_by_ray(ix2_t *ix2, v2f_t *origin, v2f_t *direction, ix2_search_cb cb, void *arg);
 
 #endif