[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [21592] branches/soc-2009-jaguarandi/ source/blender: Just another experimental stuff to optimize the expected number of BB test on bvh trees
André Pinto
andresusanopinto at gmail.com
Wed Jul 15 01:08:55 CEST 2009
Revision: 21592
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21592
Author: jaguarandi
Date: 2009-07-15 01:08:55 +0200 (Wed, 15 Jul 2009)
Log Message:
-----------
Just another experimental stuff to optimize the expected number of BB test on bvh trees
*tree pushdowns after the pushsups :P (its still not local optimum)
Modified Paths:
--------------
branches/soc-2009-jaguarandi/source/blender/blenlib/intern/BLI_memarena.c
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
Modified: branches/soc-2009-jaguarandi/source/blender/blenlib/intern/BLI_memarena.c
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/blenlib/intern/BLI_memarena.c 2009-07-14 22:32:14 UTC (rev 21591)
+++ branches/soc-2009-jaguarandi/source/blender/blenlib/intern/BLI_memarena.c 2009-07-14 23:08:55 UTC (rev 21592)
@@ -95,3 +95,4 @@
return ptr;
}
+
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-14 22:32:14 UTC (rev 21591)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h 2009-07-14 23:08:55 UTC (rev 21592)
@@ -92,6 +92,7 @@
float bb_area(float *min, float *max);
float bb_volume(float *min, float *max);
int bb_largest_axis(float *min, float *max);
+int bb_fits_inside(float *outer_min, float *outer_max, float *inner_min, float *inner_max); /* only returns 0 if merging inner and outerbox would create a box larger than outer box */
#ifdef __cplusplus
}
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp 2009-07-14 22:32:14 UTC (rev 21591)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp 2009-07-14 23:08:55 UTC (rev 21592)
@@ -529,3 +529,15 @@
return 2;
}
}
+
+int bb_fits_inside(float *outer_min, float *outer_max, float *inner_min, float *inner_max)
+{
+ int i;
+ for(i=0; i<3; i++)
+ if(outer_min[i] > inner_min[i]) return 0;
+
+ for(i=0; i<3; i++)
+ if(outer_max[i] < inner_max[i]) return 0;
+
+ return 1;
+}
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp 2009-07-14 22:32:14 UTC (rev 21591)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp 2009-07-14 23:08:55 UTC (rev 21592)
@@ -128,6 +128,41 @@
}
+static int tot_pushup = 0;
+static int tot_pushdown = 0;
+
+template<class Node>
+void pushdown(Node *parent)
+{
+ Node **s_child = &parent->child;
+ Node * child = parent->child;
+
+ while(child && RayObject_isAligned(child))
+ {
+ Node *next = child->sibling;
+
+ assert(bb_fits_inside(parent->bb, parent->bb+3, child->bb, child->bb+3));
+
+ for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
+ if(child != i && bb_fits_inside(i->bb, i->bb+3, child->bb, child->bb+3))
+ {
+// todo optimize (hsould the one with the smallest area
+// float ia = bb_area(i->bb, i->bb+3)
+// if(child->i)
+ *s_child = child->sibling;
+ child->sibling = i->child;
+ i->child = child;
+
+ tot_pushdown++;
+ break;
+ }
+ child = next;
+ }
+
+ for(Node *i = parent->child; RayObject_isAligned(i) && i; i = i->sibling)
+ pushdown( i );
+}
+
template<class Tree, class Node, class Builder>
Node *bvh_rearrange(Tree *tree, Builder *builder, float *cost)
{
@@ -177,6 +212,7 @@
rtbuild_get_child(&b, i, &tmp);
childs.push(tmp);
}
+ tot_pushup++;
}
else
@@ -207,38 +243,76 @@
obj->root = bvh_rearrange<BVHTree,BVHNode,RTBuilder>( obj, obj->builder, &obj->cost );
+ pushdown(obj->root);
obj->cost = 1.0;
rtbuild_free( obj->builder );
obj->builder = NULL;
}
-template<>
-int bvh_intersect<BVHTree>(BVHTree *obj, Isect* isec)
+template<int StackSize>
+int intersect(BVHTree *obj, Isect* isec)
{
if(RayObject_isAligned(obj->root))
- return bvh_node_stack_raycast<BVHNode,DFS_STACK_SIZE>(obj->root, isec);
+ return bvh_node_stack_raycast<BVHNode,StackSize>(obj->root, isec);
else
return RE_rayobject_intersect( (RayObject*) obj->root, isec );
}
+
+void bfree(BVHTree *tree)
+{
+ if(tot_pushup + tot_pushdown)
+ {
+ printf("tot pushups: %d\n", tot_pushup);
+ printf("tot pushdowns: %d\n", tot_pushdown);
+ tot_pushup = 0;
+ tot_pushdown = 0;
+ }
+ bvh_free(tree);
+}
+
/* the cast to pointer function is needed to workarround gcc bug: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11407 */
-static RayObjectAPI bvh_api =
+template<int STACK_SIZE>
+static RayObjectAPI make_api()
{
- (RE_rayobject_raycast_callback) ((int(*)(BVHTree*,Isect*)) &bvh_intersect<BVHTree>),
- (RE_rayobject_add_callback) ((void(*)(BVHTree*,RayObject*)) &bvh_add<BVHTree>),
- (RE_rayobject_done_callback) ((void(*)(BVHTree*)) &bvh_done<BVHTree>),
- (RE_rayobject_free_callback) ((void(*)(BVHTree*)) &bvh_free<BVHTree>),
- (RE_rayobject_merge_bb_callback)((void(*)(BVHTree*,float*,float*)) &bvh_bb<BVHTree>),
- (RE_rayobject_cost_callback) ((float(*)(BVHTree*)) &bvh_cost<BVHTree>)
-};
+ static RayObjectAPI api =
+ {
+ (RE_rayobject_raycast_callback) ((int(*)(BVHTree*,Isect*)) &intersect<STACK_SIZE>),
+ (RE_rayobject_add_callback) ((void(*)(BVHTree*,RayObject*)) &bvh_add<BVHTree>),
+ (RE_rayobject_done_callback) ((void(*)(BVHTree*)) &bvh_done<BVHTree>),
+// (RE_rayobject_free_callback) ((void(*)(BVHTree*)) &bvh_free<BVHTree>),
+ (RE_rayobject_free_callback) ((void(*)(BVHTree*)) &bfree),
+ (RE_rayobject_merge_bb_callback)((void(*)(BVHTree*,float*,float*)) &bvh_bb<BVHTree>),
+ (RE_rayobject_cost_callback) ((float(*)(BVHTree*)) &bvh_cost<BVHTree>)
+ };
+
+ return api;
+}
+static RayObjectAPI* get_api(int maxstacksize)
+{
+// static RayObjectAPI bvh_api16 = make_api<16>();
+// static RayObjectAPI bvh_api32 = make_api<32>();
+// static RayObjectAPI bvh_api64 = make_api<64>();
+ static RayObjectAPI bvh_api128 = make_api<128>();
+ static RayObjectAPI bvh_api256 = make_api<256>();
+
+// if(maxstacksize <= 16 ) return &bvh_api16;
+// if(maxstacksize <= 32 ) return &bvh_api32;
+// if(maxstacksize <= 64 ) return &bvh_api64;
+ if(maxstacksize <= 128) return &bvh_api128;
+ if(maxstacksize <= 256) return &bvh_api256;
+ assert(maxstacksize <= 256);
+ return 0;
+}
+
RayObject *RE_rayobject_vbvh_create(int size)
{
BVHTree *obj= (BVHTree*)MEM_callocN(sizeof(BVHTree), "BVHTree");
assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */
- obj->rayobj.api = &bvh_api;
+ obj->rayobj.api = get_api(DFS_STACK_SIZE);
obj->root = NULL;
obj->node_arena = NULL;
More information about the Bf-blender-cvs
mailing list