/*
 *  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 <pad.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 */
	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 {
	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 {
	pad_t		*node_pad;	/* ix3_node_t allocator */
	pad_t		*ref_pad;	/* ix3_object_ref_t allocator */
	pad_t		*object_pad;	/* ix3_object_t allocator */
	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;

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);

	node->children = NULL;
	INIT_LIST_HEAD(&node->objects);
	node->n_objects = 0;

	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;
		}

		pad_put(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_t *ix3, 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 = pad_get(ix3->ref_pad, 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);
	pad_put(object);
}


/* Split node and distribute objects referenced from node->objects into a
 * newly created node->children.
 */
static 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 = pad_get(ix3->node_pad, 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(ix3, 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;
}


/* 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, unsigned max_asip)
{
	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)
		goto fail_ix3;

	init_node(&ix3->root, aabb);

	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)
		goto fail_node_pad;

	ix3->ref_pad = pad_new(sizeof(ix3_object_ref_t) * 128, PAD_FLAGS_ZERO);
	if (!ix3->ref_pad)
		goto fail_ref_pad;

	ix3->object_pad = pad_new(sizeof_object(ix3) * 32, PAD_FLAGS_ZERO);
	if (!ix3->object_pad)
		goto fail_object_pad;

	return ix3;

fail_object_pad:
	pad_free(ix3->ref_pad);
fail_ref_pad:
	pad_free(ix3->node_pad);
fail_node_pad:
	free(ix3);
fail_ix3:
	return NULL;
}


/* Reset the index ix3 to its state as-returned by ix3_new()
 *
 * Note this doesn't free memory, it just discards the index while keeping all
 * the memory around in the caches for efficient reuse.
 */
void ix3_reset(ix3_t *ix3)
{
	assert(ix3);

	pad_reset(ix3->node_pad);
	pad_reset(ix3->ref_pad);
	pad_reset(ix3->object_pad);

	init_node(&ix3->root, &ix3->aabb);
}


/* 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)
{
	assert(ix3);

	pad_free(ix3->node_pad);
	pad_free(ix3->ref_pad);
	pad_free(ix3->object_pad);
	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 = pad_get(ix3->object_pad, sizeof_object(ix3));
	if (!o)
		return NULL;

	INIT_LIST_HEAD(&o->references);
	for (int i = 0; i < ix3->max_asip; i++)
		INIT_LIST_HEAD(&o->hits[i]);

	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_object_cb_t().
 */
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_object_cb_t *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);
			switch (r) {
			case IX3_SEARCH_STOP_HIT:
				n_hits++;

			case IX3_SEARCH_STOP_MISS:
				return n_hits;

			case IX3_SEARCH_MORE_HIT:
				n_hits++;

			case IX3_SEARCH_MORE_MISS:
				continue;

			default:
				assert(0);
			}
		}

		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(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;

	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(ix3, &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[ix3->asip - 1], 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_object_cb_t *cb, void *cb_context)
{
	unsigned	n_hits = 0;
	LIST_HEAD	(hits);
	ix3_object_t	*o, *_o;

	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))
		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
	 * 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.
	 *    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
	 *    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, &ix3->root, &ix3->aabb, search_position, search_origin, search_aabb, &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;

			r = cb(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);
			}
		}

		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;
}