Revision: 21421 http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21421 Author: jaguarandi Date: 2009-07-08 12:40:26 +0200 (Wed, 08 Jul 2009)
Log Message: ----------- Added local stack during bvh transversal Modified Paths: -------------- branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c 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 10:27:18 UTC (rev 21420) +++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c 2009-07-08 10:40:26 UTC (rev 21421) @@ -37,6 +37,7 @@ #include "rayobject_rtbuild.h" #include "rayobject.h" +#define DFS_STACK_SIZE 64 #define DYNAMIC_ALLOC //#define SPLIT_OVERLAP_MEAN_LONGEST_AXIS /* objects mean split on the longest axis, childs BB are allowed to overlap */ @@ -47,6 +48,7 @@ typedef struct BVHTree BVHTree; static int bvh_intersect(BVHTree *obj, Isect *isec); +static int bvh_intersect_stack(BVHTree *obj, Isect *isec); static void bvh_add(BVHTree *o, RayObject *ob); static void bvh_done(BVHTree *o); static void bvh_free(BVHTree *o); @@ -54,7 +56,11 @@ static RayObjectAPI bvh_api = { +#ifdef DFS_STACK_SIZE + (RE_rayobject_raycast_callback) bvh_intersect_stack, +#else (RE_rayobject_raycast_callback) bvh_intersect, +#endif (RE_rayobject_add_callback) bvh_add, (RE_rayobject_done_callback) bvh_done, (RE_rayobject_free_callback) bvh_free, @@ -150,6 +156,55 @@ /* * Tree transverse */ +static int dfs_raycast_stack(BVHNode *root, Isect *isec) +{ + BVHNode *stack[DFS_STACK_SIZE]; + int hit = 0, stack_pos = 0; + + stack[stack_pos++] = root; + + while(stack_pos) + { + BVHNode *node = stack[--stack_pos]; + if(RayObject_isAligned(node)) + { + if(RE_rayobject_bb_intersect(isec, (const float*)node->bb) != FLT_MAX) + { + //push nodes in reverse visit order + if(isec->idot_axis[node->split_axis] < 0.0f) + { + int i; + for(i=0; i<BVH_NCHILDS; i++) + if(node->child[i] == 0) break; + else stack[stack_pos++] = node->child[i]; + } + else + { + int i; + for(i=0; i<BVH_NCHILDS; i++) + if(node->child[i] != 0) stack[stack_pos++] = node->child[i]; + else break; + } + assert(stack_pos <= DFS_STACK_SIZE); + } + } + else + { + hit |= RE_rayobject_intersect( (RayObject*)node, isec); + if(hit && isec->mode == RE_RAY_SHADOW) return hit; + } + } + return hit; +} + +static int bvh_intersect_stack(BVHTree *obj, Isect *isec) +{ + if(RayObject_isAligned(obj->root)) + return dfs_raycast_stack(obj->root, isec); + else + return RE_rayobject_intersect( (RayObject*)obj->root, isec); +} + static int dfs_raycast(BVHNode *node, Isect *isec) { int hit = 0; _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org http://lists.blender.org/mailman/listinfo/bf-blender-cvs