libix3: initial commit

This is a straightforward 3D conversion of libix2, the API is
completely unchanged aside from dimensional types going from
2->3.

Rather than a quadtree with 4 children per parent, this uses an
octree with 8 children.  Otherwise it's basically identical to
libix2.

5 files changed, 1146 insertions, 0 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
new file mode 100644
index 0000000..53fe025
--- /dev/null
+++ b/src/Makefile.am
@@ -0,0 +1,2 @@
+noinst_LIBRARIES = libix3.a
+libix3_a_SOURCES = list.h ix3.c ix3.h
diff --git a/src/ix3.c b/src/ix3.c
new file mode 100644
index 0000000..c1bd212
--- /dev/null
+++ b/src/ix3.c
@@ -0,0 +1,748 @@
+/*
+ *  Copyright (C) 2018  Vito Caputo - <vcaputo@pengaru.com>
+ *
+ *  This program is free software: you can redistribute it and/or modify it
+ *  under the terms of the GNU General Public License version 3 as published
+ *  by the Free Software Foundation.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* 3d spatial index - implemented as an octree
+ *
+ * This has been adapted directly from libix2 @ git://git.pengaru.com/libix2
+ * by replacing the quadtree with an octree and adding a third dimension to all
+ * dimensional types.  It probably wouldn't be too difficult to share some of
+ * the code between these projects, but it really isn't large enough to bother.
+ */
+
+/* There are various outstanding TODO items littered throughout this code,
+ * it's usable as-is but by no means finished or optimized.
+ */
+
+#include <assert.h>
+#include <stdlib.h>
+
+#include "ix3.h"
+#include "list.h"
+
+typedef struct v3f_t {
+	float	x, y, z;
+} v3f_t;
+
+typedef struct bb3f_t {
+	v3f_t	min, max;
+} bb3f_t;
+
+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 */
+} ix3_object_t;
+
+typedef struct ix3_object_ref_t {
+	list_head_t	objects;	/* node on ix3_node objects list */
+	list_head_t	references;	/* node on ix3_object references list */
+	ix3_object_t	*object;	/* object being referenced */
+	ix3_node_t	*node;		/* node referencing object */
+} ix3_object_ref_t;
+
+struct ix3_node_t {
+	v3f_t		center;		/* spatial center point of ix3_node */
+	ix3_node_t	*children;	/* array of 8 child octrants when not a leaf, NULL when a leaf */
+	unsigned	n_objects;	/* number of objects in leaf when !children */
+	list_head_t	objects;	/* list of all objects in leaf when !children */
+};
+
+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 */
+	ix3_node_t	root;		/* root node of ix3 octree */
+} ix3_t;
+
+static ix3_object_t * add_object(ix3_t *ix3, unsigned *depth, ix3_node_t *node, bb3f_t *node_aabb, ix3_object_t *object, ix3_object_ref_t **reference_cache);
+
+
+/* Check if point resides within aabb */
+static inline int aabb_contains_point(v3f_t *aabb_position, v3f_t *aabb_origin, bb3f_t *aabb, v3f_t *point)
+{
+	v3f_t	scaled_origin = {};
+	v3f_t	position = {};
+
+	assert(aabb);
+	assert(point);
+
+	if (!aabb_position)
+		aabb_position = &position;
+
+	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;
+		scaled_origin.z = (aabb->max.z - aabb->min.z) * .5f * aabb_origin->z;
+	}
+
+	if (point->x < (aabb_position->x + scaled_origin.x + aabb->min.x))
+		return 0;
+
+	if (point->x > (aabb_position->x + scaled_origin.x + aabb->max.x))
+		return 0;
+
+	if (point->y < (aabb_position->y + scaled_origin.y + aabb->min.y))
+		return 0;
+
+	if (point->y > (aabb_position->y + scaled_origin.y + aabb->max.y))
+		return 0;
+
+	if (point->z < (aabb_position->z + scaled_origin.z + aabb->min.z))
+		return 0;
+
+	if (point->z > (aabb_position->z + scaled_origin.z + aabb->max.z))
+		return 0;
+
+	return 1;
+}
+
+
+/* check if a and b overlap */
+static inline int aabb_overlap(v3f_t *a_position, v3f_t *a_origin, bb3f_t *a, v3f_t *b_position, v3f_t *b_origin, bb3f_t *b)
+{
+	v3f_t	a_scaled_origin = {}, b_scaled_origin = {};
+	v3f_t	position = {};
+
+	assert(a);
+	assert(b);
+
+	if (!a_position)
+		a_position = &position;
+
+	if (!b_position)
+		b_position = &position;
+
+	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;
+		a_scaled_origin.z = (a->max.z - a->min.z) * .5f * a_origin->z;
+	}
+
+	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;
+		b_scaled_origin.z = (b->max.z - b->min.z) * .5f * b_origin->z;
+	}
+
+	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) &&
+		(a->min.z + a_position->z + a_scaled_origin.z) <= (b->max.z + b_position->z + b_scaled_origin.z) &&
+		(a->max.z + a_position->z + a_scaled_origin.z) >= (b->min.z + b_position->z + b_scaled_origin.z));
+}
+
+
+/* initialize a node centered in aabb */
+static void init_node(ix3_node_t *node, bb3f_t *aabb)
+{
+	assert(node);
+	assert(aabb);
+
+	INIT_LIST_HEAD(&node->objects);
+
+	node->center.x = aabb->min.x;
+	node->center.y = aabb->min.y;
+	node->center.z = aabb->min.z;
+	node->center.x += .5f * (aabb->max.x - aabb->min.x);
+	node->center.y += .5f * (aabb->max.y - aabb->min.y);
+	node->center.z += .5f * (aabb->max.z - aabb->min.z);
+}
+
+
+/* initialize an octrants bb3f_t array from a parent node aabb and center point */
+static void init_octrants(bb3f_t *octrants, bb3f_t *parent_aabb, v3f_t *octrants_center)
+{
+	assert(octrants);
+	assert(parent_aabb);
+	assert(octrants_center);
+
+/*
+	+-+-+\
+	|0|1|-+-+ 
+	+-+-+4|5|  
+	|2|3|-+-+ 
+	+-+-+6|7| 
+	    \-+-+  
+*/           
+	octrants[0].min.x = parent_aabb->min.x;
+	octrants[0].min.y = octrants_center->y;
+	octrants[0].min.z = octrants_center->z;
+	octrants[0].max.x = octrants_center->x;
+	octrants[0].max.y = parent_aabb->max.y;
+	octrants[0].max.z = parent_aabb->max.z;
+
+	octrants[1].min.x = octrants_center->x;
+	octrants[1].min.y = octrants_center->y;
+	octrants[1].min.z = octrants_center->z;
+	octrants[1].max.x = parent_aabb->max.x;
+	octrants[1].max.y = parent_aabb->max.y;
+	octrants[1].max.z = parent_aabb->max.z;
+
+	octrants[2].min.x = parent_aabb->min.x;
+	octrants[2].min.y = parent_aabb->min.y;
+	octrants[2].min.z = octrants_center->z;
+	octrants[2].max.x = octrants_center->x;
+	octrants[2].max.y = octrants_center->y;
+	octrants[2].max.z = parent_aabb->max.z;
+
+	octrants[3].min.x = octrants_center->x;
+	octrants[3].min.y = parent_aabb->min.y;
+	octrants[3].min.z = octrants_center->z;
+	octrants[3].max.x = parent_aabb->max.x;
+	octrants[3].max.y = octrants_center->y;
+	octrants[3].max.z = parent_aabb->max.z;
+
+	octrants[4].min.x = parent_aabb->min.x;
+	octrants[4].min.y = octrants_center->y;
+	octrants[4].min.z = parent_aabb->min.z;
+	octrants[4].max.x = octrants_center->x;
+	octrants[4].max.y = parent_aabb->max.y;
+	octrants[4].max.z = octrants_center->z;
+
+	octrants[5].min.x = octrants_center->x;
+	octrants[5].min.y = octrants_center->y;
+	octrants[5].min.z = parent_aabb->min.z;
+	octrants[5].max.x = parent_aabb->max.x;
+	octrants[5].max.y = parent_aabb->max.y;
+	octrants[5].max.z = octrants_center->z;
+
+	octrants[6].min.x = parent_aabb->min.x;
+	octrants[6].min.y = parent_aabb->min.y;
+	octrants[6].min.z = parent_aabb->min.z;
+	octrants[6].max.x = octrants_center->x;
+	octrants[6].max.y = octrants_center->y;
+	octrants[6].max.z = octrants_center->z;
+
+	octrants[7].min.x = octrants_center->x;
+	octrants[7].min.y = parent_aabb->min.y;
+	octrants[7].min.z = parent_aabb->min.z;
+	octrants[7].max.x = parent_aabb->max.x;
+	octrants[7].max.y = octrants_center->y;
+	octrants[7].max.z = octrants_center->z;
+}
+
+
+/* Unlink a single object reference, disconnecting it from the object and node */
+static void unlink_object_ref(ix3_object_ref_t *ref)
+{
+	assert(ref);
+
+	/* TODO: is there an actual need to maintain and detect the unlinked state w/NULL ptrs? */
+	if (!ref->node)
+		return;
+
+	list_del(&ref->objects);
+	list_del(&ref->references);
+	ref->node->n_objects--;
+	ref->object = NULL;
+	ref->node = NULL;
+}
+
+
+/* Unlink an object from the index, unlinking all node references.
+ * If references_cache is NULL, all unlinked references are freed.
+ * Otherwise, the unlinked references are added to the references_cache list.
+ */
+static void unlink_object(ix3_object_t *object, list_head_t *references_cache)
+{
+	ix3_object_ref_t	*ref, *_ref;
+
+	assert(object);
+
+	list_for_each_entry_safe(ref, _ref, &object->references, references) {
+		unlink_object_ref(ref);
+
+		if (references_cache) {
+			list_add_tail(&ref->references, references_cache);
+			continue;
+		}
+
+		free(ref);
+	}
+}
+
+
+/* Link an object into a node.
+ * If ref is not NULL, it's an existing reference to move to a new node rather than allocating a new one.
+ * Returns the reference on success, NULL on failure
+ * On falure the supplied object is left intact.
+ */
+static ix3_object_ref_t * link_object(ix3_object_t *object, ix3_node_t *node, ix3_object_ref_t **cached_ref)
+{
+	ix3_object_ref_t	*ref = NULL;
+
+	assert(object);
+	assert(node);
+
+	if (cached_ref && *cached_ref) {
+		ref = *cached_ref;
+		*cached_ref = NULL;
+		unlink_object_ref(ref);
+	}
+
+	if (!ref)
+		ref = calloc(1, sizeof(ix3_object_ref_t));
+
+	if (!ref)
+		return NULL;
+
+	list_add_tail(&ref->references, &object->references);
+	list_add_tail(&ref->objects, &node->objects);
+	ref->object = object;
+	ref->node = node;
+	node->n_objects++;
+
+	return ref;
+}
+
+
+/* Compute the diagonal length of the aabb, leaving it squared */
+static inline float aabb_len_sq(bb3f_t *aabb)
+{
+	float	len_sq;
+
+	assert(aabb);
+
+	/* TODO: import the full v3f.h and do this with v3f_sub() && v3f_dot()? */
+	len_sq = (aabb->max.x - aabb->min.x) * (aabb->max.x - aabb->min.x);
+	len_sq += (aabb->max.y - aabb->min.y) * (aabb->max.y - aabb->min.y);
+	len_sq += (aabb->max.z - aabb->min.z) * (aabb->max.z - aabb->min.z);
+
+	return len_sq;
+}
+
+
+/* remove an object */
+static void remove_object(ix3_object_t *object)
+{
+	assert(object);
+
+	unlink_object(object, NULL);
+	free(object);
+}
+
+
+/* Split node and distribute objects referenced from node->objects into a
+ * newly created node->children.
+ */
+ix3_node_t * split_node(ix3_t *ix3, unsigned *depth, ix3_node_t *node, bb3f_t *node_aabb)
+{
+	bb3f_t			octrants[8];
+	ix3_object_ref_t	*r, *_r;
+	int			i;
+
+	assert(ix3);
+	assert(depth);
+	assert(node);
+	assert(!node->children);
+	assert(node_aabb);
+
+	/* allocate and setup the children nodes */
+	node->children = calloc(8, sizeof(ix3_node_t));
+	if (!node->children)
+		goto _fail;
+
+	init_octrants(octrants, node_aabb, &node->center);
+	for (i = 0; i < 8; i++)
+		init_node(&node->children[i], &octrants[i]);
+
+	/* distribute objects across node->children, removing node->objects
+	 * references along the way.  The references are supplied
+	 */
+	list_for_each_entry_safe(r, _r, &node->objects, objects) {
+		ix3_object_t	*o = r->object;
+
+		/* XXX: this can probably be done more efficiently */
+		for (i = 0; i < 8; i++) {
+			if (!aabb_overlap(NULL, NULL, &octrants[i], &o->position, &o->origin, &o->aabb))
+				continue;
+
+			if (!add_object(ix3, depth, &node->children[i], &octrants[i], o, &r))
+				goto _fail;
+		}
+	}
+
+	return node->children;
+
+_fail:
+	/* TODO: some kind of cleanup? */
+	return NULL;
+}
+
+
+/* Add a member object to the space described by node && node_aabb
+ *
+ * This function may need to divide nodes and/or recur.
+ *
+ * Since it may need to allocate memory for object references via
+ * link_object(), and may need to allocate space for children
+ * nodes, it may fail.
+ *
+ * As an optimization, a list of object refs may be supplied in object_refs for
+ * use when linking the object.
+ *
+ * On failure NULL is returned and object is freed (including all its references).
+ * On success the supplied object is simply returned, with potentialy new references added.
+ */
+static ix3_object_t * add_object(ix3_t *ix3, unsigned *depth, ix3_node_t *node, bb3f_t *node_aabb, ix3_object_t *object, ix3_object_ref_t **reference_cache)
+{
+	assert(ix3);
+	assert(depth);
+	assert(node);
+	assert(node_aabb);
+	assert(object);
+
+	/* If not a leaf, simply recur on overlapping children */
+	if (node->children) {
+		bb3f_t	octrants[8];
+		int	i;
+
+		*depth++;
+		init_octrants(octrants, node_aabb, &node->center);
+		for (i = 0; i < 8; i++) {
+			if (!aabb_overlap(NULL, NULL, &octrants[i], &object->position, &object->origin, &object->aabb))
+				continue;
+
+			if (!add_object(ix3, depth, &node->children[i], &octrants[i], object, reference_cache))
+				goto _fail;
+		}
+		*depth--;
+
+		return object;
+	}
+
+
+	/* Node is a leaf, optimistically link the object to the node */
+	if (!link_object(object, node, reference_cache))
+		goto _fail;
+
+
+	/* If the node is overflowing, split it */
+	if (node->n_objects > ix3->max_per_node && *depth < ix3->max_depth) {
+		*depth++;
+		if (!split_node(ix3, depth, node, node_aabb))
+			goto _fail;
+		*depth--;
+	}
+
+	return object;
+
+_fail:
+	remove_object(object);
+
+	return NULL;
+}
+
+
+/* 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.
+ * Returns NULL on failure.
+ */
+ix3_t * ix3_new(bb3f_t *aabb, unsigned max_per_node, unsigned max_depth)
+{
+	bb3f_t	default_aabb = {{-1.f, -1.f, -1.f}, {1.f, 1.f, 1.f}};
+	ix3_t	*ix3;
+
+	if (!aabb)
+		aabb = &default_aabb;
+
+	ix3 = calloc(1, sizeof(ix3_t));
+	if (!ix3)
+		return NULL;
+
+	init_node(&ix3->root, aabb);
+
+	ix3->aabb = *aabb;
+	ix3->max_per_node = max_per_node;
+	ix3->max_depth = max_depth;
+
+	return ix3;
+}
+
+
+/* Free the index ix3 and everything associated with it */
+/* Note the external objects which have been indexed are not freed */
+void ix3_free(ix3_t *ix3)
+{
+	/* TODO: free everything */
+	free(ix3);
+}
+
+
+/* Create and insert object spatially described by x,y,origin_x,origin_y,object_aabb into the index ix3 */
+ix3_object_t * ix3_object_new(ix3_t *ix3, v3f_t *object_position, v3f_t *object_origin, bb3f_t *object_aabb, void *object)
+{
+	unsigned	depth = 0;
+	ix3_object_t	*o;
+
+	assert(ix3);
+	assert(object_aabb);
+	assert(object_aabb->min.x <= object_aabb->max.x);
+	assert(object_aabb->min.y <= object_aabb->max.y);
+	assert(object_aabb->min.z <= object_aabb->max.z);
+
+	o = calloc(1, sizeof(ix3_object_t));
+	if (!o)
+		return NULL;
+
+	INIT_LIST_HEAD(&o->references);
+	INIT_LIST_HEAD(&o->hits);
+
+	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, NULL, &ix3->aabb, &o->position, &o->origin, &o->aabb))
+		return o;
+
+	return add_object(ix3, &depth, &ix3->root, &ix3->aabb, o, NULL);
+}
+
+
+/* Remove object from the index ix3 and free it. */
+/* This may be either the object handle returned by ix3_node_insert(), or
+ * the handle supplied to ix3_search_cb().
+ */
+void ix3_object_free(ix3_t *ix3, ix3_object_t *object)
+{
+	assert(ix3);
+	assert(object);
+
+	remove_object(object);
+}
+
+
+/* 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? */
+ix3_object_t * ix3_object_move(ix3_t *ix3, ix3_object_t *object, v3f_t *object_position, v3f_t *object_origin, bb3f_t *object_aabb)
+{
+	unsigned	depth = 0;
+
+	assert(ix3);
+	assert(object);
+	assert(!object_aabb || object_aabb->min.x <= object_aabb->max.x);
+	assert(!object_aabb || object_aabb->min.y <= object_aabb->max.y);
+	assert(!object_aabb || object_aabb->min.z <= object_aabb->max.z);
+
+	/* TODO FIXME: cache and reuse the references, requires changing
+	 * add_object to receive a list of cached references rather than the
+	 * singleton it currently expects.
+	 * unlink_object() already knows how to leave those references on a
+	 * supplied list head which is currently NULL.
+	 */
+	unlink_object(object, NULL);
+
+	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, NULL, &ix3->aabb, &object->position, &object->origin, &object->aabb))
+		return object;
+
+	return add_object(ix3, &depth, &ix3->root, &ix3->aabb, object, NULL /* TODO */);
+}
+
+
+/* Search for objects overlapping a point in index ix3. */
+/* Returns number of cb calls performed on hits, if cb is NULL calls will be skipped but hits still counted for return. */
+unsigned ix3_search_by_point(ix3_t *ix3, v3f_t *point, ix3_search_cb cb, void *cb_context)
+{
+	unsigned		n_hits = 0;
+	ix3_object_ref_t	*ref, *_ref;
+	ix3_node_t		*node;
+	bb3f_t			node_aabb;
+
+	assert(ix3);
+	assert(point);
+
+	if (!aabb_contains_point(NULL, NULL, &ix3->aabb, point))
+		return 0;
+
+	node = &ix3->root;
+	node_aabb = ix3->aabb;
+
+	/* find the leaf node containing point */
+	while (node->children) {
+		bb3f_t	octrants[8];
+		int	i;
+
+		/* TODO: this can be done more efficiently -
+		 * by simply comparing point to the center and
+		 * deriving the index from that
+		 */
+		init_octrants(octrants, &node_aabb, &node->center);
+		for (i = 0; i < 8; i++) {
+			if (aabb_contains_point(NULL, NULL, &octrants[i], point))
+				break;
+		}
+
+		node = &node->children[i];
+		node_aabb = octrants[i];
+	}
+
+	/* search the leaf for matches */
+	list_for_each_entry_safe(ref, _ref, &node->objects, objects) {
+		if (!aabb_contains_point(&ref->object->position, &ref->object->origin, &ref->object->aabb, point))
+			continue;
+
+		if (cb) {
+			ix3_search_status_t	r;
+			ix3_object_t		*o = ref->object;
+
+			r = cb(cb_context, o, &o->position, &o->aabb, o->object);
+			if (r == IX3_SEARCH_STOP) {
+				n_hits++;
+				break;
+			}
+
+			if (r == IX3_SEARCH_IGNORE)
+				continue;
+		}
+
+		n_hits++;
+	}
+
+
+	return n_hits;
+}
+
+
+/* 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)
+{
+	ix3_object_ref_t	*ref, *_ref;
+
+	assert(node);
+	assert(node_aabb);
+	assert(search_aabb);
+	assert(hits);
+
+	if (node->children) {
+		bb3f_t	octrants[8];
+		int	i;
+
+		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);
+		}
+
+		return;
+	}
+
+
+	list_for_each_entry_safe(ref, _ref, &node->objects, objects) {
+		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);
+	}
+}
+
+
+/* Search for objects overlapping an aabb in index ix3. */
+/* Returns number of cb calls performed on hits, if cb is NULL calls will be skipped but hits still counted for return. */
+unsigned ix3_search_by_aabb(ix3_t *ix3, v3f_t *search_position, v3f_t *search_origin, bb3f_t *search_aabb, ix3_search_cb cb, void *cb_context)
+{
+	unsigned	n_hits = 0;
+	LIST_HEAD	(hits);
+	ix3_object_t	*o, *_o;
+
+	assert(ix3);
+	assert(search_aabb);
+
+	if (!aabb_overlap(NULL, NULL, &ix3->aabb, search_position, search_origin, search_aabb))
+		return 0;
+
+	/* XXX: for the aabb-based search a list of hits is first constructed,
+	 * this prevents multiple callbacks on the same object by first
+	 * allowing those multiple hits to simply move the object within the
+	 * hits list.  In a separate pass the hits are processed with the
+	 * callbacks.
+	 *
+	 * 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.
+	 * 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
+	 *    terminate the search on something arbitrary like after the first
+	 *    hit of a specific object type.
+	 *
+	 * TODO: investigate alternative solutions.  Obvious options:
+	 * - Putting more than one hit list node in every object for limited
+	 *   nesting.  
+	 * - Maintain a per-search hash-table which gets accessed before
+	 *   every callback to see if the object has been seen already, adding
+	 *   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);
+
+	list_for_each_entry_safe(o, _o, &hits, hits) {
+		list_del_init(&o->hits);
+
+		if (cb) {
+			ix3_search_status_t	r;
+
+			r = cb(cb_context, o, &o->position, &o->aabb, o->object);
+			if (r == IX3_SEARCH_STOP) {
+				n_hits++;
+				break;
+			}
+
+			if (r == IX3_SEARCH_IGNORE)
+				continue;
+		}
+
+		n_hits++;
+	}
+
+	/* just in case the search was aborted, finish deleting these nodes */
+	/* FIXME: this whole hit list thing is pretty janky */
+	list_for_each_entry_safe(o, _o, &hits, hits)
+		list_del_init(&o->hits);
+
+	return n_hits;
+}
diff --git a/src/ix3.h b/src/ix3.h
new file mode 100644
index 0000000..5a8d2b1
--- /dev/null
+++ b/src/ix3.h
@@ -0,0 +1,43 @@
+/*
+ *  Copyright (C) 2018  Vito Caputo - <vcaputo@pengaru.com>
+ *
+ *  This program is free software: you can redistribute it and/or modify it
+ *  under the terms of the GNU General Public License version 3 as published
+ *  by the Free Software Foundation.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _IX3_H
+#define _IX3_H
+
+typedef struct ix3_object_t ix3_object_t;
+typedef struct ix3_t ix3_t;
+typedef struct bb3f_t bb3f_t;
+typedef struct v3f_t v3f_t;
+
+typedef enum ix3_search_status_t {
+	IX3_SEARCH_STOP,
+	IX3_SEARCH_IGNORE,
+	IX3_SEARCH_CONTINUE
+} 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);
+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_object_free(ix3_t *ix3, ix3_object_t *object);
+ix3_object_t * ix3_object_move(ix3_t *ix3, ix3_object_t *object, v3f_t *object_position, v3f_t *object_origin, bb3f_t *object_aabb);
+int ix3_object_aabb_overlap(ix3_t *ix3, ix3_object_t *object, v3f_t *aabb_position, v3f_t *aabb_origin, bb3f_t *aabb);
+unsigned ix3_search_by_point(ix3_t *ix3, v3f_t *point, ix3_search_cb cb, void *arg);
+unsigned ix3_search_by_aabb(ix3_t *ix3, v3f_t *search_position, v3f_t *search_origin, bb3f_t *search_aabb, ix3_search_cb cb, void *arg);
+unsigned ix3_search_by_ray(ix3_t *ix3, v3f_t *origin, v3f_t *direction, ix3_search_cb cb, void *arg);
+
+#endif
diff --git a/src/list.h b/src/list.h
new file mode 100644
index 0000000..48bca36
--- /dev/null
+++ b/src/list.h
@@ -0,0 +1,252 @@
+#ifndef __LIST_H
+#define __LIST_H
+
+/* linux kernel linked list interface */
+
+/*
+ * Simple doubly linked list implementation.
+ *
+ * Some of the internal functions ("__xxx") are useful when
+ * manipulating whole lists rather than single entries, as
+ * sometimes we already know the next/prev entries and we can
+ * generate better code by using them directly rather than
+ * using the generic single-entry routines.
+ */
+
+typedef struct list_head {
+	struct list_head *next, *prev;
+} list_head_t;
+
+#define LIST_HEAD_INIT(name) { &(name), &(name) }
+
+#define LIST_HEAD(name) \
+	struct list_head name = LIST_HEAD_INIT(name)
+
+#define INIT_LIST_HEAD(ptr) do { \
+	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
+} while (0)
+
+/*
+ * Insert a new entry between two known consecutive entries. 
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_add(struct list_head *new,
+			      struct list_head *prev,
+			      struct list_head *next)
+{
+	next->prev = new;
+	new->next = next;
+	new->prev = prev;
+	prev->next = new;
+}
+
+/**
+ * list_add - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ */
+static inline void list_add(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head, head->next);
+}
+
+/**
+ * list_add_tail - add a new entry
+ * @new: new entry to be added
+ * @head: list head to add it before
+ *
+ * Insert a new entry before the specified head.
+ * This is useful for implementing queues.
+ */
+static inline void list_add_tail(struct list_head *new, struct list_head *head)
+{
+	__list_add(new, head->prev, head);
+}
+
+/*
+ * Delete a list entry by making the prev/next entries
+ * point to each other.
+ *
+ * This is only for internal list manipulation where we know
+ * the prev/next entries already!
+ */
+static inline void __list_del(struct list_head *prev, struct list_head *next)
+{
+	next->prev = prev;
+	prev->next = next;
+}
+
+/**
+ * list_del - deletes entry from list.
+ * @entry: the element to delete from the list.
+ * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
+ */
+static inline void list_del(struct list_head *entry)
+{
+	__list_del(entry->prev, entry->next);
+	entry->next = (void *) 0;
+	entry->prev = (void *) 0;
+}
+
+/**
+ * list_del_init - deletes entry from list and reinitialize it.
+ * @entry: the element to delete from the list.
+ */
+static inline void list_del_init(struct list_head *entry)
+{
+	__list_del(entry->prev, entry->next);
+	INIT_LIST_HEAD(entry); 
+}
+
+/**
+ * list_move - delete from one list and add as another's head
+ * @list: the entry to move
+ * @head: the head that will precede our entry
+ */
+static inline void list_move(struct list_head *list, struct list_head *head)
+{
+        __list_del(list->prev, list->next);
+        list_add(list, head);
+}
+
+/**
+ * list_move_tail - delete from one list and add as another's tail
+ * @list: the entry to move
+ * @head: the head that will follow our entry
+ */
+static inline void list_move_tail(struct list_head *list,
+				  struct list_head *head)
+{
+        __list_del(list->prev, list->next);
+        list_add_tail(list, head);
+}
+
+/**
+ * list_empty - tests whether a list is empty
+ * @head: the list to test.
+ */
+static inline int list_empty(struct list_head *head)
+{
+	return head->next == head;
+}
+
+static inline void __list_splice(struct list_head *list,
+				 struct list_head *head)
+{
+	struct list_head *first = list->next;
+	struct list_head *last = list->prev;
+	struct list_head *at = head->next;
+
+	first->prev = head;
+	head->next = first;
+
+	last->next = at;
+	at->prev = last;
+}
+
+/**
+ * list_splice - join two lists
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ */
+static inline void list_splice(struct list_head *list, struct list_head *head)
+{
+	if (!list_empty(list))
+		__list_splice(list, head);
+}
+
+/**
+ * list_splice_init - join two lists and reinitialise the emptied list.
+ * @list: the new list to add.
+ * @head: the place to add it in the first list.
+ *
+ * The list at @list is reinitialised
+ */
+static inline void list_splice_init(struct list_head *list,
+				    struct list_head *head)
+{
+	if (!list_empty(list)) {
+		__list_splice(list, head);
+		INIT_LIST_HEAD(list);
+	}
+}
+
+/**
+ * list_entry - get the struct for this entry
+ * @ptr:	the &struct list_head pointer.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_entry(ptr, type, member) \
+	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
+
+/**
+ * list_for_each	-	iterate over a list
+ * @pos:	the &struct list_head to use as a loop counter.
+ * @head:	the head for your list.
+ */
+#define list_for_each(pos, head) \
+	for (pos = (head)->next; pos != (head); \
+        	pos = pos->next)
+/**
+ * list_for_each_prev	-	iterate over a list backwards
+ * @pos:	the &struct list_head to use as a loop counter.
+ * @head:	the head for your list.
+ */
+#define list_for_each_prev(pos, head) \
+	for (pos = (head)->prev; pos != (head); \
+        	pos = pos->prev)
+        	
+/**
+ * list_for_each_safe	-	iterate over a list safe against removal of list entry
+ * @pos:	the &struct list_head to use as a loop counter.
+ * @n:		another &struct list_head to use as temporary storage
+ * @head:	the head for your list.
+ */
+#define list_for_each_safe(pos, n, head) \
+	for (pos = (head)->next, n = pos->next; pos != (head); \
+		pos = n, n = pos->next)
+
+/**
+ * list_for_each_entry	-	iterate over list of given type
+ * @pos:	the type * to use as a loop counter.
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_for_each_entry(pos, head, member)				\
+	for (pos = list_entry((head)->next, typeof(*pos), member);	\
+	     &pos->member != (head); 					\
+	     pos = list_entry(pos->member.next, typeof(*pos), member))
+
+/**
+ * list_for_each_entry_prev	-	iterate over list of given type backwards
+ * @pos:	the type * to use as a loop counter.
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_for_each_entry_prev(pos, head, member)				\
+	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
+	     &pos->member != (head); 					\
+	     pos = list_entry(pos->member.prev, typeof(*pos), member))
+
+
+/**
+ * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * @pos:	the type * to use as a loop counter.
+ * @n:		another type * to use as temporary storage
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_for_each_entry_safe(pos, n, head, member)			\
+	for (pos = list_entry((head)->next, typeof(*pos), member),	\
+		n = list_entry(pos->member.next, typeof(*pos), member);	\
+	     &pos->member != (head); 					\
+	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
+
+
+#endif
diff --git a/src/test.c b/src/test.c
new file mode 100644
index 0000000..7c0389e
--- /dev/null
+++ b/src/test.c
@@ -0,0 +1,101 @@
+/*
+ *  Copyright (C) 2018  Vito Caputo - <vcaputo@pengaru.com>
+ *
+ *  This program is free software: you can redistribute it and/or modify it
+ *  under the terms of the GNU General Public License version 3 as published
+ *  by the Free Software Foundation.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#include <assert.h>
+#include <stdio.h>
+
+#include <ix3.h>
+
+typedef struct v3f_t {
+	float	x, y, z;
+} v3f_t;
+
+typedef struct bb3f_t {
+	v3f_t	min, max;
+} bb3f_t;
+
+
+ix3_search_status_t cb(void *cb_context, ix3_object_t *ix3_object, v3f_t *ix3_object_position, bb3f_t *ix3_object_aabb, void *object)
+{
+	fprintf(stderr, "found %p ix3_object=%p ix3_object_aabb=%f,%f,%f ... %f,%f,%f\n", cb_context, ix3_object,
+		ix3_object_aabb->min.x, ix3_object_aabb->min.y, ix3_object_aabb->min.z,
+		ix3_object_aabb->max.x, ix3_object_aabb->max.y, ix3_object_aabb->max.z);
+
+	return IX3_SEARCH_CONTINUE;
+}
+
+typedef struct object_t {
+	bb3f_t		aabb;
+	ix3_object_t	*ix;
+} object_t;
+
+int main(int argc, char *argv[])
+{
+	object_t	objects[] = {
+				{ .aabb = {{ -1.f, -1.f, -1.f }, { 1.f, 1.f, 1.f }} },
+				{ .aabb = {{ -.2f, -.2f, -.2f }, { -.1f, -.1f, -.1f }} },
+				{ .aabb = {{ -.2f, .2f, -.2f }, { -.1f, .3f, -.1f }} },
+				{ .aabb = {{ .1f, .1f, .1f }, { .2f, .2f, .2f }} },
+				{ .aabb = {{ -.2f, -.2f, -.2f }, { .1f, .1f, .1f }} },
+				{ .aabb = {{ -.1f, -.1f, -.1f }, { .2f, .2f, .2f }} },
+			};
+
+	ix3_object_t	*o, *j;
+	ix3_t		*ix3;
+
+	ix3 = ix3_new(NULL, 2, 8);
+	if (!ix3) {
+		fprintf(stderr, "unable to create index\n");
+		return 1;
+	}
+
+	for (int i = 0; i < sizeof(objects) / sizeof(*objects); i++) {
+		objects[i].ix = ix3_object_new(ix3, NULL, NULL, &objects[i].aabb, &objects[i]);
+		if (!o) {
+			fprintf(stderr, "unable to insert object %i\n", i);
+			return 1;
+		}
+	}
+
+	for (int i = 0; i < sizeof(objects) / sizeof(*objects); i++) {
+		/* TODO: actually verify the expected objects are hit */
+		if (!ix3_search_by_point(ix3, &objects[i].aabb.min, cb, &objects[i])) {
+			fprintf(stderr, "unable to lookup object %i by min point\n", i);
+			return 1;
+		}
+
+		if (!ix3_search_by_point(ix3, &objects[i].aabb.max, cb, &objects[i])) {
+			fprintf(stderr, "unable to lookup object %i by max point\n", i);
+			return 1;
+		}
+	}
+
+	for (int i = 0; i < sizeof(objects) / sizeof(*objects); i++) {
+		/* TODO: actually verify the expected objects are hit */
+		if (!ix3_search_by_aabb(ix3, NULL, NULL, &objects[i].aabb, cb, &objects[i])) {
+			fprintf(stderr, "unable to lookup object %i by perfect aabb\n", i);
+			return 1;
+		}
+	}
+
+	for (int i = 0; i < sizeof(objects) / sizeof(*objects); i++)
+		ix3_object_free(ix3, objects[i].ix);
+
+	ix3_free(ix3);
+
+	return 0;
+}