[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [21421] branches/soc-2009-jaguarandi/ source/blender/render/intern/source/rayobject_bvh.c: Added local stack during bvh transversal

[André Pinto]

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;