Improved build time on BLI_kdopbvh

Its now faster than raytree (both on build and query)

Things tryed:
 X=>Y=>Z=>X split (reduces build time.. but increases query time)
 bucket sorts
	(initial sorts for fast usage of bucket take a long time)
	(nth is linear.. so its quite fast already)

Best times archieve with:
 *usage of 4-ary trees.. reduces build time and tree size but didnt decreased query time
 *quads are on the same node instead of splitting in 2 tris..
	(this actually turned on speedup on query time.. since tree size is reduced by a factor of 2)
 *test ray-bb before ray-primitive gives better times on both tris and quads

Notes:
 measures where made projecting a sphere from inside the head of suzanne.

1 files changed, 9 insertions, 6 deletions

diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index d84a9d09d4b..73bc3e6a9bc 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -520,6 +520,8 @@ static void bvh_div_nodes(BVHTree *tree, BVHNode *node, int start, int end, char
 	
 	// Determine which axis to split along
 	laxis = get_largest_axis(node->bv);
+	//laxis = (lastaxis + 2) % tree->axis; // XYZ split
+
 	node->main_axis = laxis/2;
 	
 	// split nodes along longest axis
@@ -543,7 +545,7 @@ static void bvh_div_nodes(BVHTree *tree, BVHNode *node, int start, int end, char
 			if(tend != end)
 				partition_nth_element(tree->nodes, start, end, tend, laxis);
 			refit_kdop_hull(tree, tnode, start, tend);
-			bvh_div_nodes(tree, tnode, start, tend, laxis);
+			bvh_div_nodes(tree, tnode, start, tend, laxis); // not called on XYZ split
 		}
 		node->totnode++;
 	}
@@ -613,9 +615,10 @@ void BLI_bvhtree_balance(BVHTree *tree)
 	tree->totbranch++;
 	
 	// refit root bvh node
-	refit_kdop_hull(tree, tree->nodes[tree->totleaf], 0, tree->totleaf);
+	refit_kdop_hull(tree, tree->nodes[tree->totleaf], 0, tree->totleaf);  // not called on XYZ split
 	// create + balance tree
 	bvh_div_nodes(tree, tree->nodes[tree->totleaf], 0, tree->totleaf, 0);
+	//BLI_bvhtree_update_tree(tree); // XYZ split
 	
 	// verify_tree(tree);
 }
@@ -1009,16 +1012,16 @@ static float ray_nearest_hit(BVHRayCastData *data, BVHNode *node)
 static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
 {
 	int i;
-	float dist;
-
-	dist = ray_nearest_hit(data, node);
 
+	//ray-bv is really fast.. and simple tests revealed its worth to test it
+	//before calling the ray-primitive functions
+	float dist = ray_nearest_hit(data, node);
 	if(dist >= data->hit.dist) return;
 
 	if(node->totnode == 0)
 	{
 		if(data->callback)
-			dist = data->callback(data->userdata, node->index, &data->ray, &data->hit);
+			data->callback(data->userdata, node->index, &data->ray, &data->hit);
 		else
 		{
 			data->hit.index	= node->index;