*Added support for variable cost per RayObject

Suposedly usefull for creating trees of objects (where objects have very diferent size-NumFaces and shape-BB)
Altought the implemented costs maybe not be very correct (for now), as i didnt cared about following a specific "corrected" model

5 files changed, 66 insertions, 10 deletions

diff --git a/source/blender/render/intern/include/rayobject.h b/source/blender/render/intern/include/rayobject.h
index c611e2ceca2..de36a1e4888 100644
--- a/source/blender/render/intern/include/rayobject.h
+++ b/source/blender/render/intern/include/rayobject.h
@@ -86,11 +86,13 @@ struct RayObject
 	
 };
 
+
 typedef int  (*RE_rayobject_raycast_callback)(RayObject *, Isect *);
-typedef void (*RE_rayobject_add_callback)(RayObject *, RayObject *);
+typedef void (*RE_rayobject_add_callback)(RayObject *raytree, RayObject *rayobject);
 typedef void (*RE_rayobject_done_callback)(RayObject *);
 typedef void (*RE_rayobject_free_callback)(RayObject *);
 typedef void (*RE_rayobject_merge_bb_callback)(RayObject *, float *min, float *max);
+typedef float (*RE_rayobject_cost_callback)(RayObject *);
 
 typedef struct RayObjectAPI
 {
@@ -99,6 +101,7 @@ typedef struct RayObjectAPI
 	RE_rayobject_done_callback		done;
 	RE_rayobject_free_callback		free;
 	RE_rayobject_merge_bb_callback	bb;
+	RE_rayobject_cost_callback		cost;
 	
 } RayObjectAPI;
 
@@ -128,6 +131,12 @@ int RE_rayobject_intersect(RayObject *r, Isect *i);
  */
 float RE_rayobject_bb_intersect(const Isect *i, const float *bb);
 
+/*
+ * Returns the expected cost of raycast on this node, primitives have a cost of 1
+ */
+float RE_rayobject_cost(RayObject *r);
+
+
 #define ISECT_EPSILON ((float)FLT_EPSILON)
 
 
diff --git a/source/blender/render/intern/include/rayobject_rtbuild.h b/source/blender/render/intern/include/rayobject_rtbuild.h
index f27005a2fa7..6fef18433b9 100644
--- a/source/blender/render/intern/include/rayobject_rtbuild.h
+++ b/source/blender/render/intern/include/rayobject_rtbuild.h
@@ -80,4 +80,7 @@ int rtbuild_median_split(RTBuilder *b, float *separators, int nchilds, int axis)
 int rtbuild_median_split_largest_axis(RTBuilder *b, int nchilds);
 
 
+/* bb utils */
+float bb_area(float *min, float *max);
+
 #endif
diff --git a/source/blender/render/intern/source/rayobject.c b/source/blender/render/intern/source/rayobject.c
index 247eb952429..949b7afb5a0 100644
--- a/source/blender/render/intern/source/rayobject.c
+++ b/source/blender/render/intern/source/rayobject.c
@@ -400,6 +400,20 @@ void RE_rayobject_merge_bb(RayObject *r, float *min, float *max)
 	else assert(0);
 }
 
+float RE_rayobject_cost(RayObject *r)
+{
+	if(RayObject_isRayFace(r))
+	{
+		return 1.0;
+	}
+	else if(RayObject_isRayAPI(r))
+	{
+		r = RayObject_align( r );
+		return r->api->cost( r );
+	}
+	else assert(0);
+}
+
 #ifdef RE_RAYCOUNTER
 void RE_RC_INFO(RayCounter *info)
 {
diff --git a/source/blender/render/intern/source/rayobject_bvh.c b/source/blender/render/intern/source/rayobject_bvh.c
index a5158d96acc..d0e0e8b6dc5 100644
--- a/source/blender/render/intern/source/rayobject_bvh.c
+++ b/source/blender/render/intern/source/rayobject_bvh.c
@@ -53,6 +53,7 @@ static void bvh_add(BVHTree *o, RayObject *ob);
 static void bvh_done(BVHTree *o);
 static void bvh_free(BVHTree *o);
 static void bvh_bb(BVHTree *o, float *min, float *max);
+static float bvh_cost(BVHTree *o);
 
 static RayObjectAPI bvh_api =
 {
@@ -64,7 +65,8 @@ static RayObjectAPI bvh_api =
 	(RE_rayobject_add_callback)     bvh_add,
 	(RE_rayobject_done_callback)    bvh_done,
 	(RE_rayobject_free_callback)    bvh_free,
-	(RE_rayobject_merge_bb_callback)bvh_bb
+	(RE_rayobject_merge_bb_callback)bvh_bb,
+	(RE_rayobject_cost_callback)	bvh_cost
 };
 
 typedef struct BVHNode BVHNode;
@@ -91,6 +93,7 @@ struct BVHTree
 	BVHNode *node_alloc, *node_next;
 	float *bb_alloc, *bb_next;
 #endif
+	float cost;
 	RTBuilder *builder;
 
 };
@@ -153,6 +156,12 @@ static void bvh_bb(BVHTree *obj, float *min, float *max)
 	bvh_merge_bb(obj->root, min, max);
 }
 
+static float bvh_cost(BVHTree *obj)
+{
+	assert(obj->cost >= 0.0);
+	return obj->cost;
+}
+
 /*
  * Tree transverse
  */
@@ -336,8 +345,9 @@ static int child_id(int pid, int nchild)
 	return pid*BVH_NCHILDS+(2-BVH_NCHILDS)+nchild;
 }
 
-static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid)
+static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid, float *cost)
 {
+	*cost = 0;
 	if(rtbuild_size(builder) == 0)
 		return 0;
 
@@ -361,6 +371,7 @@ static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid)
 			for(; i<BVH_NCHILDS; i++)
 				parent->child[i] = 0;
 
+			*cost = bb_area(parent->bb, parent->bb+3)*RE_rayobject_cost(child);
 			return parent;
 		}
 		else
@@ -368,6 +379,8 @@ static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid)
 			assert(!RayObject_isAligned(child));
 			//Its a sub-raytrace structure, assume it has it own raycast
 			//methods and adding a Bounding Box arround is unnecessary
+
+			*cost = RE_rayobject_cost(child);
 			return (BVHNode*)child;
 		}
 	}
@@ -392,12 +405,16 @@ static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *builder, int nid)
 		parent->split_axis = builder->split_axis;
 		for(i=0; i<nc; i++)
 		{
-			parent->child[i] = bvh_rearrange( tree, rtbuild_get_child(builder, i, &tmp), child_id(nid,i) );
+			float tcost;
+			parent->child[i] = bvh_rearrange( tree, rtbuild_get_child(builder, i, &tmp), child_id(nid,i), &tcost );
 			bvh_merge_bb(parent->child[i], parent->bb, parent->bb+3);
+			
+			*cost += tcost;
 		}
 		for(; i<BVH_NCHILDS; i++)
 			parent->child[i] = 0;
 
+		*cost *= bb_area(parent->bb, parent->bb+3);
 		return parent;
 	}
 }
@@ -412,7 +429,6 @@ static void bvh_info(BVHTree *obj)
 static void bvh_done(BVHTree *obj)
 {
 
-
 #ifdef DYNAMIC_ALLOC
 	int needed_nodes = (rtbuild_size(obj->builder)+1)*2;
 	if(needed_nodes > BLI_MEMARENA_STD_BUFSIZE)
@@ -437,7 +453,7 @@ static void bvh_done(BVHTree *obj)
 	obj->bb_next  = obj->bb_alloc;
 #endif
 	
-	obj->root = bvh_rearrange( obj, obj->builder, 1 );
+	obj->root = bvh_rearrange( obj, obj->builder, 1, &obj->cost );
 	
 #ifndef DYNAMIC_ALLOC
 	assert(obj->node_alloc+needed_nodes >= obj->node_next);
diff --git a/source/blender/render/intern/source/rayobject_rtbuild.c b/source/blender/render/intern/source/rayobject_rtbuild.c
index 688b3a920b4..2d5afe28600 100644
--- a/source/blender/render/intern/source/rayobject_rtbuild.c
+++ b/source/blender/render/intern/source/rayobject_rtbuild.c
@@ -216,6 +216,7 @@ typedef struct CostObject CostObject;
 struct CostObject
 {
 	RayObject *obj;
+	float cost;
 	float bb[6];
 };
 
@@ -278,6 +279,7 @@ int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds)
 	else
 	{
 		float bcost = FLT_MAX;
+		float childrens_cost = 0;
 		int i, axis, baxis, boffset, k, try_axis[3];
 		CostObject *cost   = MEM_mallocN( sizeof(CostObject)*size, "RTBuilder.HeuristicObjectSplitter" );
 		float      *acc_bb = MEM_mallocN( sizeof(float)*6*size, "RTBuilder.HeuristicObjectSplitterBB" );
@@ -286,12 +288,14 @@ int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds)
 		{
 			cost[i].obj = b->begin[i];
 			INIT_MINMAX(cost[i].bb, cost[i].bb+3);
-			RE_rayobject_merge_bb(b->begin[i], cost[i].bb, cost[i].bb+3);
+			RE_rayobject_merge_bb(cost[i].obj, cost[i].bb, cost[i].bb+3);
+			cost[i].cost = RE_rayobject_cost(cost[i].obj);
+			childrens_cost += cost[i].cost;
 		}
 		
 		if(b->child_sorted_axis >= 0 && b->child_sorted_axis < 3)
 		{
-			try_axis[0] = b->child_sorted_axis;
+			try_axis[0] =  b->child_sorted_axis;
 			try_axis[1] = (b->child_sorted_axis+1)%3;
 			try_axis[2] = (b->child_sorted_axis+2)%3;
 		}
@@ -304,8 +308,11 @@ int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds)
 		
 		for(axis=try_axis[k=0]; k<3; axis=try_axis[++k])
 		{
+			float left_cost, right_cost;
 			float other_bb[6];
 
+
+
 			costobject_sort(cost, cost+size, axis);
 			for(i=size-1; i>=0; i--)
 			{
@@ -330,18 +337,22 @@ int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds)
 			INIT_MINMAX(other_bb, other_bb+3);
 			DO_MIN( cost[0].bb,   other_bb   );
 			DO_MAX( cost[0].bb+3, other_bb+3 );
+			left_cost  = cost[0].cost;
+			right_cost = childrens_cost-cost[0].cost;
+			if(right_cost < 0) right_cost = 0;
 
 			for(i=1; i<size; i++)
 			{
 				//Worst case heuristic (cost of each child is linear)
 				float hcost, left_side, right_side;
 				
-				left_side = bb_area(other_bb, other_bb+3)*(i+logf(i));
-				right_side= bb_area(acc_bb+i*6, acc_bb+i*6+3)*(size-i+logf(size-i));
+				left_side = bb_area(other_bb, other_bb+3)*left_cost;		//(i+logf(i));
+				right_side= bb_area(acc_bb+i*6, acc_bb+i*6+3)*right_cost;	//(size-i+logf(size-i));
 				
 				if(left_side > bcost) break;	//No way we can find a better heuristic in this axis
 
 				hcost = left_side+right_side;
+				assert(hcost >= 0);
 				if( hcost < bcost
 				|| (hcost == bcost && axis < baxis)) //this makes sure the tree built is the same whatever is the order of the sorting axis
 				{
@@ -351,6 +362,9 @@ int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds)
 				}
 				DO_MIN( cost[i].bb,   other_bb   );
 				DO_MAX( cost[i].bb+3, other_bb+3 );
+				left_cost  += cost[i].cost;
+				right_cost -= cost[i].cost;
+				if(right_cost < 0.0f) right_cost = 0.0;
 			}
 			
 			if(baxis == axis)