libix2: introduce origin for anchoring position

also use v2f_t everywhere for positions instead of
the occasional float x, float y.

3 files changed, 62 insertions, 38 deletions

diff --git a/src/ix2.c b/src/ix2.c
index 9a93b46..24edece 100644
--- a/src/ix2.c
+++ b/src/ix2.c
@@ -44,6 +44,7 @@ typedef struct ix2_object_t {
 					 * 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 */
 	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 */
@@ -74,8 +75,9 @@ 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(v2f_t *aabb_position, aabb_t *aabb, v2f_t *point)
+static inline int aabb_contains_point(v2f_t *aabb_position, v2f_t *aabb_origin, aabb_t *aabb, v2f_t *point)
 {
+	v2f_t	scaled_origin = {};
 	v2f_t	position = {};
 
 	assert(aabb);
@@ -84,16 +86,21 @@ static inline int aabb_contains_point(v2f_t *aabb_position, aabb_t *aabb, v2f_t
 	if (!aabb_position)
 		aabb_position = &position;
 
-	if (point->x < (aabb_position->x + aabb->min.x))
+	if (aabb_origin) {
+		scaled_origin.x = (aabb->max.x - aabb->min.x) * .5f * aabb_origin->x;
+		scaled_origin.y = (aabb->max.y - aabb->min.y) * .5f * aabb_origin->y;
+	}
+
+	if (point->x < (aabb_position->x + scaled_origin.x + aabb->min.x))
 		return 0;
 
-	if (point->x > (aabb_position->x + aabb->max.x))
+	if (point->x > (aabb_position->x + scaled_origin.x + aabb->max.x))
 		return 0;
 
-	if (point->y < (aabb_position->y + aabb->min.y))
+	if (point->y < (aabb_position->y + scaled_origin.y + aabb->min.y))
 		return 0;
 
-	if (point->y > (aabb_position->y + aabb->max.y))
+	if (point->y > (aabb_position->y + scaled_origin.y + aabb->max.y))
 		return 0;
 	
 	return 1;
@@ -101,8 +108,9 @@ static inline int aabb_contains_point(v2f_t *aabb_position, aabb_t *aabb, v2f_t
 
 
 /* check if a and b overlap */
-static inline int aabb_overlap(v2f_t *a_position, aabb_t *a, v2f_t *b_position, aabb_t *b)
+static inline int aabb_overlap(v2f_t *a_position, v2f_t *a_origin, aabb_t *a, v2f_t *b_position, v2f_t *b_origin, aabb_t *b)
 {
+	v2f_t	a_scaled_origin = {}, b_scaled_origin = {};
 	v2f_t	position = {};
 
 	assert(a);
@@ -114,10 +122,20 @@ static inline int aabb_overlap(v2f_t *a_position, aabb_t *a, v2f_t *b_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));
+	if (a_origin) {
+		a_scaled_origin.x = (a->max.x - a->min.x) * .5f * a_origin->x;
+		a_scaled_origin.y = (a->max.y - a->min.y) * .5f * a_origin->y;
+	}
+
+	if (b_origin) {
+		b_scaled_origin.x = (b->max.x - b->min.x) * .5f * b_origin->x;
+		b_scaled_origin.y = (b->max.y - b->min.y) * .5f * b_origin->y;
+	}
+
+	return ((a->min.x + a_position->x + a_scaled_origin.x) <= (b->max.x + b_position->x + b_scaled_origin.x) &&
+		(a->max.x + a_position->x + a_scaled_origin.x) >= (b->min.x + b_position->x + b_scaled_origin.x) &&
+		(a->min.y + a_position->y + a_scaled_origin.y) <= (b->max.y + b_position->y + b_scaled_origin.y) &&
+		(a->max.y + a_position->y + a_scaled_origin.y) >= (b->min.y + b_position->y + b_scaled_origin.y));
 }
 
 
@@ -302,7 +320,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(NULL, &quadrants[i], &o->position, &o->aabb))
+			if (!aabb_overlap(NULL, NULL, &quadrants[i], &o->position, &o->origin, &o->aabb))
 				continue;
 
 			if (!add_object(ix2, depth, &node->children[i], &quadrants[i], o, &r))
@@ -348,7 +366,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(NULL, &quadrants[i], &object->position, &object->aabb))
+			if (!aabb_overlap(NULL, NULL, &quadrants[i], &object->position, &object->origin, &object->aabb))
 				continue;
 
 			if (!add_object(ix2, depth, &node->children[i], &quadrants[i], object, reference_cache))
@@ -417,8 +435,8 @@ void ix2_free(ix2_t *ix2)
 }
 
 
-/* Create and insert object spatially described by x,y,object_aabb into the index ix2 */
-ix2_object_t * ix2_object_new(ix2_t *ix2, float x, float y, aabb_t *object_aabb, void *object)
+/* Create and insert object spatially described by x,y,origin_x,origin_y,object_aabb into the index ix2 */
+ix2_object_t * ix2_object_new(ix2_t *ix2, v2f_t *object_position, v2f_t *object_origin, aabb_t *object_aabb, void *object)
 {
 	unsigned	depth = 0;
 	ix2_object_t	*o;
@@ -435,13 +453,17 @@ ix2_object_t * ix2_object_new(ix2_t *ix2, float x, float y, aabb_t *object_aabb,
 	INIT_LIST_HEAD(&o->references);
 	INIT_LIST_HEAD(&o->hits);
 
-	o->position.x = x;
-	o->position.y = y;
+	if (object_position)
+		o->position = *object_position;
+
+	if (object_origin)
+		o->origin = *object_origin;
+
 	o->aabb = *object_aabb;
 	o->object = object;
 	o->aabb_len_sq = aabb_len_sq(object_aabb);
 
-	if (!aabb_overlap(NULL, &ix2->aabb, &o->position, &o->aabb))
+	if (!aabb_overlap(NULL, NULL, &ix2->aabb, &o->position, &o->origin, &o->aabb))
 		return o;
 
 	return add_object(ix2, &depth, &ix2->root, &ix2->aabb, o, NULL);
@@ -465,7 +487,7 @@ void ix2_object_free(ix2_t *ix2, ix2_object_t *object)
 /* 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_object_move(ix2_t *ix2, ix2_object_t *object, float object_x, float object_y, aabb_t *object_aabb)
+ix2_object_t * ix2_object_move(ix2_t *ix2, ix2_object_t *object, v2f_t *object_position, v2f_t *object_origin, aabb_t *object_aabb)
 {
 	unsigned	depth = 0;
 
@@ -482,14 +504,18 @@ ix2_object_t * ix2_object_move(ix2_t *ix2, ix2_object_t *object, float object_x,
 	 */
 	unlink_object(object, NULL);
 
-	object->position.x = object_x;
-	object->position.y = object_y;
+	if (object_position)
+		object->position = *object_position;
+
+	if (object_origin)
+		object->origin = *object_origin;
+
 	if (object_aabb) {
 		object->aabb = *object_aabb;
 		object->aabb_len_sq = aabb_len_sq(object_aabb);
 	}
 
-	if (!aabb_overlap(NULL, &ix2->aabb, &object->position, &object->aabb))
+	if (!aabb_overlap(NULL, NULL, &ix2->aabb, &object->position, &object->origin, &object->aabb))
 		return object;
 
 	return add_object(ix2, &depth, &ix2->root, &ix2->aabb, object, NULL /* TODO */);
@@ -508,7 +534,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(NULL, &ix2->aabb, point))
+	if (!aabb_contains_point(NULL, NULL, &ix2->aabb, point))
 		return 0;
 
 	node = &ix2->root;
@@ -525,7 +551,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(NULL, &quadrants[i], point))
+			if (aabb_contains_point(NULL, NULL, &quadrants[i], point))
 				break;
 		}
 
@@ -535,7 +561,7 @@ 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->position, &ref->object->aabb, point))
+		if (!aabb_contains_point(&ref->object->position, &ref->object->origin, &ref->object->aabb, point))
 			continue;
 
 		if (cb) {
@@ -563,13 +589,12 @@ 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, v2f_t *search_position, 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, v2f_t *search_origin, 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);
 
@@ -579,8 +604,8 @@ static void search_node_by_aabb(ix2_node_t *node, aabb_t *node_aabb, v2f_t *sear
 
 		init_quadrants(quadrants, node_aabb, &node->center);
 		for (i = 0; i < 4; i++) {
-			if (aabb_overlap(NULL, &quadrants[i], search_position, search_aabb))
-				search_node_by_aabb(&node->children[i], &quadrants[i], search_position, search_aabb, hits);
+			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);
 		}
 
 		return;
@@ -588,7 +613,7 @@ static void search_node_by_aabb(ix2_node_t *node, aabb_t *node_aabb, v2f_t *sear
 
 
 	list_for_each_entry_safe(ref, _ref, &node->objects, objects) {
-		if (!aabb_overlap(&ref->object->position, &ref->object->aabb, search_position, search_aabb))
+		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);
@@ -598,17 +623,16 @@ static void search_node_by_aabb(ix2_node_t *node, aabb_t *node_aabb, v2f_t *sear
 
 /* 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, float x, float y, aabb_t *search_aabb, ix2_search_cb cb, void *cb_context)
+unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_origin, 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(NULL, &ix2->aabb, &position, search_aabb))
+	if (!aabb_overlap(NULL, NULL, &ix2->aabb, search_position, search_origin, search_aabb))
 		return 0;
 
 	/* XXX: for the aabb-based search a list of hits is first constructed,
@@ -634,7 +658,7 @@ unsigned ix2_search_by_aabb(ix2_t *ix2, float x, float y, aabb_t *search_aabb, i
 	 *   it if not before calling the callback.  This strikes me as very
 	 *   heavyweight.
 	 */
-	search_node_by_aabb(&ix2->root, &ix2->aabb, &position, search_aabb, &hits);
+	search_node_by_aabb(&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);
diff --git a/src/ix2.h b/src/ix2.h
index 7853e60..5f3b5cb 100644
--- a/src/ix2.h
+++ b/src/ix2.h
@@ -32,11 +32,11 @@ typedef ix2_search_status_t (*ix2_search_cb)(void *cb_context, ix2_object_t *ix2
 
 ix2_t * ix2_new(aabb_t *aabb, unsigned max_per_node, unsigned max_depth);
 void ix2_free(ix2_t *ix2);
-ix2_object_t * ix2_object_new(ix2_t *ix2, float x, float y, aabb_t *aabb, void *object);
+ix2_object_t * ix2_object_new(ix2_t *ix2, v2f_t *position, v2f_t *origin, aabb_t *aabb, void *object);
 void ix2_object_free(ix2_t *ix2, ix2_object_t *object);
-ix2_object_t * ix2_object_move(ix2_t *ix2, ix2_object_t *object, float object_x, float object_y, aabb_t *object_aabb);
+ix2_object_t * ix2_object_move(ix2_t *ix2, ix2_object_t *object, v2f_t *object_position, v2f_t *object_origin, 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, float x, float y, aabb_t *aabb, ix2_search_cb cb, void *arg);
+unsigned ix2_search_by_aabb(ix2_t *ix2, v2f_t *search_position, v2f_t *search_origin, aabb_t *search_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
diff --git a/src/test.c b/src/test.c
index 6a13af3..3cb27df 100644
--- a/src/test.c
+++ b/src/test.c
@@ -64,7 +64,7 @@ int main(int argc, char *argv[])
 	}
 
 	for (int i = 0; i < sizeof(objects) / sizeof(*objects); i++) {
-		objects[i].ix = ix2_object_new(ix2, 0, 0, &objects[i].aabb, &objects[i]);
+		objects[i].ix = ix2_object_new(ix2, NULL, NULL, &objects[i].aabb, &objects[i]);
 		if (!o) {
 			fprintf(stderr, "unable to insert object %i\n", i);
 			return 1;
@@ -86,7 +86,7 @@ int main(int argc, char *argv[])
 
 	for (int i = 0; i < sizeof(objects) / sizeof(*objects); i++) {
 		/* TODO: actually verify the expected objects are hit */
-		if (!ix2_search_by_aabb(ix2, 0, 0, &objects[i].aabb, cb, &objects[i])) {
+		if (!ix2_search_by_aabb(ix2, NULL, NULL, &objects[i].aabb, cb, &objects[i])) {
 			fprintf(stderr, "unable to lookup object %i by perfect aabb\n", i);
 			return 1;
 		}