Revision: 21439
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21439
Author: jaguarandi
Date: 2009-07-08 22:04:40 +0200 (Wed, 08 Jul 2009)
Log Message:
-----------
*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
Modified Paths:
--------------
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
2009-07-08 19:39:37 UTC (rev 21438)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
2009-07-08 20:04:40 UTC (rev 21439)
@@ -86,11 +86,13 @@
};
+
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 @@
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 @@
*/
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)
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
2009-07-08 19:39:37 UTC (rev 21438)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
2009-07-08 20:04:40 UTC (rev 21439)
@@ -80,4 +80,7 @@
int rtbuild_median_split_largest_axis(RTBuilder *b, int nchilds);
+/* bb utils */
+float bb_area(float *min, float *max);
+
#endif
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
2009-07-08 19:39:37 UTC (rev 21438)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
2009-07-08 20:04:40 UTC (rev 21439)
@@ -400,6 +400,20 @@
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)
{
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
2009-07-08 19:39:37 UTC (rev 21438)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
2009-07-08 20:04:40 UTC (rev 21439)
@@ -53,6 +53,7 @@
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 @@
(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 @@
BVHNode *node_alloc, *node_next;
float *bb_alloc, *bb_next;
#endif
+ float cost;
RTBuilder *builder;
};
@@ -153,6 +156,12 @@
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 @@
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 @@
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 @@
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 @@
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_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 @@
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);
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
2009-07-08 19:39:37 UTC (rev 21438)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
2009-07-08 20:04:40 UTC (rev 21439)
@@ -216,6 +216,7 @@
struct CostObject
{
RayObject *obj;
+ float cost;
float bb[6];
};
@@ -278,6 +279,7 @@
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 @@
{
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 @@
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 @@
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 @@
}
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)
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
