use smaller type for kdopbvh - this change was made as a size optimization, and I moved back to ints since there were many int comparisons.

now define axis_t and an unsugned char.

2 files changed, 84 insertions, 58 deletions

diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index 8d0d4943ebe..8441413fba9 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -97,7 +97,7 @@ void BLI_bvhtree_update_tree(BVHTree *tree);
 /* collision/overlap: check two trees if they overlap, alloc's *overlap with length of the int return value */
 BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int *result);
 
-float BLI_bvhtree_getepsilon(BVHTree *tree);
+float BLI_bvhtree_getepsilon(const BVHTree *tree);
 
 /* find nearest node to the given coordinates
  * (if nearest is given it will only search nodes where square distance is smaller than nearest->dist) */
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index bdaf59c88d8..dbd614bb1a4 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -43,6 +43,8 @@
 
 #define MAX_TREETYPE 32
 
+typedef unsigned char axis_t;
+
 typedef struct BVHNode {
 	struct BVHNode **children;
 	struct BVHNode *parent; /* some user defined traversed need that */
@@ -53,6 +55,7 @@ typedef struct BVHNode {
 	char main_axis; /* Axis used to split this node */
 } BVHNode;
 
+/* keep under 26 bytes for speed purposes */
 struct BVHTree {
 	BVHNode **nodes;
 	BVHNode *nodearray;     /* pre-alloc branch nodes */
@@ -61,16 +64,24 @@ struct BVHTree {
 	float epsilon;          /* epslion is used for inflation of the k-dop	   */
 	int totleaf;            /* leafs */
 	int totbranch;
-	int start_axis, stop_axis;  /* KDOP_AXES array indices according to axis */
+	axis_t start_axis, stop_axis;  /* KDOP_AXES array indices according to axis */
+	axis_t axis;              /* kdop type (6 => OBB, 7 => AABB, ...) */
 	char tree_type;         /* type of tree (4 => quadtree) */
-	char axis;              /* kdop type (6 => OBB, 7 => AABB, ...) */
 };
 
+/* optimization, ensure we stay small */
+#if (defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 406))  /* gcc4.6 only */
+	_Static_assert(
+	        (sizeof(void *) == 8 && sizeof(BVHTree) <= 48) ||
+	        (sizeof(void *) == 4 && sizeof(BVHTree) <= 32),
+	        "over sized");
+#endif
+
 typedef struct BVHOverlapData {
 	BVHTree *tree1, *tree2; 
 	BVHTreeOverlap *overlap; 
 	int i, max_overlap; /* i is number of overlaps */
-	int start_axis, stop_axis;
+	axis_t start_axis, stop_axis;
 } BVHOverlapData;
 
 typedef struct BVHNearestData {
@@ -113,6 +124,15 @@ static float KDOP_AXES[13][3] = {
 	{0, 1.0, -1.0}
 };
 
+MINLINE axis_t min_axis(axis_t a, axis_t b)
+{
+	return (a < b) ? a : b;
+}
+MINLINE axis_t max_axis(axis_t a, axis_t b)
+{
+	return (b < a) ? a : b;
+}
+
 #if 0
 
 /*
@@ -374,24 +394,25 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, const float *co, int
 {
 	float newminmax;
 	float *bv = node->bv;
-	int i, k;
+	int k;
+	axis_t axis_iter;
 	
 	/* don't init boudings for the moving case */
 		if (!moving) {
-		for (i = tree->start_axis; i < tree->stop_axis; i++) {
-			bv[2 * i] = FLT_MAX;
-			bv[2 * i + 1] = -FLT_MAX;
+		for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
+			bv[2 * axis_iter] = FLT_MAX;
+			bv[2 * axis_iter + 1] = -FLT_MAX;
 		}
 	}
 	
 	for (k = 0; k < numpoints; k++) {
 		/* for all Axes. */
-		for (i = tree->start_axis; i < tree->stop_axis; i++) {
-			newminmax = dot_v3v3(&co[k * 3], KDOP_AXES[i]);
-			if (newminmax < bv[2 * i])
-				bv[2 * i] = newminmax;
-			if (newminmax > bv[(2 * i) + 1])
-				bv[(2 * i) + 1] = newminmax;
+		for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
+			newminmax = dot_v3v3(&co[k * 3], KDOP_AXES[axis_iter]);
+			if (newminmax < bv[2 * axis_iter])
+				bv[2 * axis_iter] = newminmax;
+			if (newminmax > bv[(2 * axis_iter) + 1])
+				bv[(2 * axis_iter) + 1] = newminmax;
 		}
 	}
 }
@@ -400,25 +421,25 @@ static void create_kdop_hull(BVHTree *tree, BVHNode *node, const float *co, int
 static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end)
 {
 	float newmin, newmax;
-	int i, j;
 	float *bv = node->bv;
+	int j;
+	axis_t axis_iter;
 
-	
-	for (i = tree->start_axis; i < tree->stop_axis; i++) {
-		bv[2 * i] = FLT_MAX;
-		bv[2 * i + 1] = -FLT_MAX;
+	for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
+		bv[(2 * axis_iter)] = FLT_MAX;
+		bv[(2 * axis_iter) + 1] = -FLT_MAX;
 	}
 
 	for (j = start; j < end; j++) {
 		/* for all Axes. */
-		for (i = tree->start_axis; i < tree->stop_axis; i++) {
-			newmin = tree->nodes[j]->bv[(2 * i)];   
-			if ((newmin < bv[(2 * i)]))
-				bv[(2 * i)] = newmin;
- 
-			newmax = tree->nodes[j]->bv[(2 * i) + 1];
-			if ((newmax > bv[(2 * i) + 1]))
-				bv[(2 * i) + 1] = newmax;
+		for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
+			newmin = tree->nodes[j]->bv[(2 * axis_iter)];
+			if ((newmin < bv[(2 * axis_iter)]))
+				bv[(2 * axis_iter)] = newmin;
+
+			newmax = tree->nodes[j]->bv[(2 * axis_iter) + 1];
+			if ((newmax > bv[(2 * axis_iter) + 1]))
+				bv[(2 * axis_iter) + 1] = newmax;
 		}
 	}
 
@@ -451,23 +472,24 @@ static char get_largest_axis(float *bv)
  * join the children on the parent BV */
 static void node_join(BVHTree *tree, BVHNode *node)
 {
-	int i, j;
-	
-	for (i = tree->start_axis; i < tree->stop_axis; i++) {
-		node->bv[2 * i] = FLT_MAX;
-		node->bv[2 * i + 1] = -FLT_MAX;
+	int i;
+	axis_t axis_iter;
+
+	for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
+		node->bv[(2 * axis_iter)] = FLT_MAX;
+		node->bv[(2 * axis_iter) + 1] = -FLT_MAX;
 	}
 	
 	for (i = 0; i < tree->tree_type; i++) {
 		if (node->children[i]) {
-			for (j = tree->start_axis; j < tree->stop_axis; j++) {
+			for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
 				/* update minimum */
-				if (node->children[i]->bv[(2 * j)] < node->bv[(2 * j)])
-					node->bv[(2 * j)] = node->children[i]->bv[(2 * j)];
+				if (node->children[i]->bv[(2 * axis_iter)] < node->bv[(2 * axis_iter)])
+					node->bv[(2 * axis_iter)] = node->children[i]->bv[(2 * axis_iter)];
 
 				/* update maximum */
-				if (node->children[i]->bv[(2 * j) + 1] > node->bv[(2 * j) + 1])
-					node->bv[(2 * j) + 1] = node->children[i]->bv[(2 * j) + 1];
+				if (node->children[i]->bv[(2 * axis_iter) + 1] > node->bv[(2 * axis_iter) + 1])
+					node->bv[(2 * axis_iter) + 1] = node->children[i]->bv[(2 * axis_iter) + 1];
 			}
 		}
 		else
@@ -482,10 +504,12 @@ static void node_join(BVHTree *tree, BVHNode *node)
 static void bvhtree_print_tree(BVHTree *tree, BVHNode *node, int depth)
 {
 	int i;
+	axis_t axis_iter;
+
 	for (i = 0; i < depth; i++) printf(" ");
 	printf(" - %d (%ld): ", node->index, node - tree->nodearray);
-	for (i = 2 * tree->start_axis; i < 2 * tree->stop_axis; i++)
-		printf("%.3f ", node->bv[i]);
+	for (axis_iter = 2 * tree->start_axis; axis_iter < 2 * tree->stop_axis; axis_iter++)
+		printf("%.3f ", node->bv[axis_iter]);
 	printf("\n");
 
 	for (i = 0; i < tree->tree_type; i++)
@@ -923,7 +947,7 @@ void BLI_bvhtree_balance(BVHTree *tree)
 
 int BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
 {
-	int i;
+	axis_t axis_iter;
 	BVHNode *node = NULL;
 
 	/* insert should only possible as long as tree->totbranch is 0 */
@@ -942,9 +966,9 @@ int BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoint
 	node->index = index;
 
 	/* inflate the bv with some epsilon */
-	for (i = tree->start_axis; i < tree->stop_axis; i++) {
-		node->bv[(2 * i)] -= tree->epsilon; /* minimum */
-		node->bv[(2 * i) + 1] += tree->epsilon; /* maximum */
+	for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
+		node->bv[(2 * axis_iter)] -= tree->epsilon; /* minimum */
+		node->bv[(2 * axis_iter) + 1] += tree->epsilon; /* maximum */
 	}
 
 	return 1;
@@ -954,8 +978,8 @@ int BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoint
 /* call before BLI_bvhtree_update_tree() */
 int BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
 {
-	int i;
 	BVHNode *node = NULL;
+	axis_t axis_iter;
 	
 	/* check if index exists */
 	if (index > tree->totleaf)
@@ -969,9 +993,9 @@ int BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const f
 		create_kdop_hull(tree, node, co_moving, numpoints, 1);
 	
 	/* inflate the bv with some epsilon */
-	for (i = tree->start_axis; i < tree->stop_axis; i++) {
-		node->bv[(2 * i)]     -= tree->epsilon; /* minimum */
-		node->bv[(2 * i) + 1] += tree->epsilon; /* maximum */
+	for (axis_iter = tree->start_axis; axis_iter < tree->stop_axis; axis_iter++) {
+		node->bv[(2 * axis_iter)]     -= tree->epsilon; /* minimum */
+		node->bv[(2 * axis_iter) + 1] += tree->epsilon; /* maximum */
 	}
 
 	return 1;
@@ -991,7 +1015,7 @@ void BLI_bvhtree_update_tree(BVHTree *tree)
 		node_join(tree, *index);
 }
 
-float BLI_bvhtree_getepsilon(BVHTree *tree)
+float BLI_bvhtree_getepsilon(const BVHTree *tree)
 {
 	return tree->epsilon;
 }
@@ -1001,7 +1025,7 @@ float BLI_bvhtree_getepsilon(BVHTree *tree)
  * BLI_bvhtree_overlap
  *
  * overlap - is it possible for 2 bv's to collide ? */
-static int tree_overlap(BVHNode *node1, BVHNode *node2, int start_axis, int stop_axis)
+static int tree_overlap(BVHNode *node1, BVHNode *node2, axis_t start_axis, axis_t stop_axis)
 {
 	float *bv1 = node1->bv;
 	float *bv2 = node2->bv;
@@ -1081,8 +1105,8 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int
 	
 	/* fast check root nodes for collision before doing big splitting + traversal */
 	if (!tree_overlap(tree1->nodes[tree1->totleaf], tree2->nodes[tree2->totleaf],
-	                  min_ii(tree1->start_axis, tree2->start_axis),
-	                  min_ii(tree1->stop_axis, tree2->stop_axis)))
+	                  min_axis(tree1->start_axis, tree2->start_axis),
+	                  min_axis(tree1->stop_axis, tree2->stop_axis)))
 		return NULL;
 
 	data = MEM_callocN(sizeof(BVHOverlapData *) * tree1->tree_type, "BVHOverlapData_star");
@@ -1096,8 +1120,8 @@ BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, unsigned int
 		data[j]->tree2 = tree2;
 		data[j]->max_overlap = MAX2(tree1->totleaf, tree2->totleaf);
 		data[j]->i = 0;
-		data[j]->start_axis = min_ii(tree1->start_axis, tree2->start_axis);
-		data[j]->stop_axis  = min_ii(tree1->stop_axis,  tree2->stop_axis);
+		data[j]->start_axis = min_axis(tree1->start_axis, tree2->start_axis);
+		data[j]->stop_axis  = min_axis(tree1->stop_axis,  tree2->stop_axis);
 	}
 
 #pragma omp parallel for private(j) schedule(static)
@@ -1301,9 +1325,10 @@ static void bfs_find_nearest(BVHNearestData *data, BVHNode *node)
 #endif
 
 
-int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
+int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *nearest,
+                             BVHTree_NearestPointCallback callback, void *userdata)
 {
-	int i;
+	axis_t axis_iter;
 
 	BVHNearestData data;
 	BVHNode *root = tree->nodes[tree->totleaf];
@@ -1315,8 +1340,8 @@ int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *n
 	data.callback = callback;
 	data.userdata = userdata;
 
-	for (i = data.tree->start_axis; i != data.tree->stop_axis; i++) {
-		data.proj[i] = dot_v3v3(data.co, KDOP_AXES[i]);
+	for (axis_iter = data.tree->start_axis; axis_iter != data.tree->stop_axis; axis_iter++) {
+		data.proj[axis_iter] = dot_v3v3(data.co, KDOP_AXES[axis_iter]);
 	}
 
 	if (nearest) {
@@ -1476,7 +1501,8 @@ static void iterative_raycast(BVHRayCastData *data, BVHNode *node)
 }
 #endif
 
-int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
+int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit,
+                         BVHTree_RayCastCallback callback, void *userdata)
 {
 	int i;
 	BVHRayCastData data;