*Added support to "BB hints" (which works like a BB version of LCTS - longest common transversing subtree)

It creates a tree cut after knowing that a given point will pass on a BB.
This tree cut is used to accelarate the rays casted from a given BB, eliminating unnecessary BB tests from root till the tree cut.

7 files changed, 161 insertions, 35 deletions

diff --git a/source/blender/render/extern/include/RE_raytrace.h b/source/blender/render/extern/include/RE_raytrace.h
index 4d0c0b1a88c..beae1b84b04 100644
--- a/source/blender/render/extern/include/RE_raytrace.h
+++ b/source/blender/render/extern/include/RE_raytrace.h
@@ -36,6 +36,7 @@ extern "C" {
 #endif
 
 
+#define RE_RAY_LCTS_MAX_SIZE	256
 #define RT_USE_LAST_HIT	/* last shadow hit is reused before raycasting on whole tree */
 //#define RT_USE_HINT			/* last hit object is reused before raycasting on whole tree */
 
@@ -76,7 +77,7 @@ extern RayCounter re_rc_counter[];
 /* Internals about raycasting structures can be found on intern/raytree.h */
 typedef struct RayObject RayObject;
 typedef struct Isect Isect;
-
+typedef struct RayHint RayHint;
 typedef struct RayTraceHint RayTraceHint;
 
 struct DerivedMesh;
@@ -87,6 +88,12 @@ void RE_rayobject_add    (RayObject *r, RayObject *);
 void RE_rayobject_done(RayObject *r);
 void RE_rayobject_free(RayObject *r);
 
+/* initializes an hint for optiming raycast where it is know that a ray will pass by the given BB often the origin point */
+void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max);
+
+/* initializes an hint for optiming raycast where it is know that a ray will be contained inside the given cone*/
+/* void RE_rayobject_hint_cone(RayObject *r, RayHint *hint, float *); */
+
 /* RayObject constructors */
 
 RayObject* RE_rayobject_octree_create(int ocres, int size);
@@ -97,6 +104,21 @@ RayObject* RE_rayobject_bvh_create(int size);		/* raytrace/rayobject_bvh.c */
 RayObject* RE_rayobject_vbvh_create(int size);		/* raytrace/rayobject_vbvh.c */
 RayObject* RE_rayobject_bih_create(int size);		/* rayobject_bih.c */
 
+typedef struct LCTSHint LCTSHint;
+struct LCTSHint
+{
+	int size;
+	RayObject *stack[RE_RAY_LCTS_MAX_SIZE];
+};
+
+struct RayHint
+{
+	union
+	{
+		LCTSHint lcts;
+	} data;
+};
+
 
 /* Ray Intersection */
 struct Isect
@@ -137,6 +159,8 @@ struct Isect
 
 	void *userdata;
 	
+	RayHint *hint;
+	
 #ifdef RE_RAYCOUNTER
 	RayCounter *raycounter;
 #endif
diff --git a/source/blender/render/intern/include/rayobject.h b/source/blender/render/intern/include/rayobject.h
index 16ebc537ef9..6f8debead19 100644
--- a/source/blender/render/intern/include/rayobject.h
+++ b/source/blender/render/intern/include/rayobject.h
@@ -98,6 +98,7 @@ 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 void (*RE_rayobject_hint_bb_callback)(RayObject *, RayHint *, float *, float *);
 
 typedef struct RayObjectAPI
 {
@@ -107,6 +108,7 @@ typedef struct RayObjectAPI
 	RE_rayobject_free_callback		free;
 	RE_rayobject_merge_bb_callback	bb;
 	RE_rayobject_cost_callback		cost;
+	RE_rayobject_hint_bb_callback	hint_bb;
 	
 } RayObjectAPI;
 
diff --git a/source/blender/render/intern/raytrace/bvh.h b/source/blender/render/intern/raytrace/bvh.h
index d9277f9a583..8f7e6111684 100644
--- a/source/blender/render/intern/raytrace/bvh.h
+++ b/source/blender/render/intern/raytrace/bvh.h
@@ -93,14 +93,13 @@ static void bvh_node_merge_bb(Node *node, float *min, float *max)
  */
 template<class Node> static inline void bvh_node_push_childs(Node *node, Isect *isec, Node **stack, int &stack_pos);
 
-template<class Node,int MAX_STACK_SIZE>
+template<class Node,int MAX_STACK_SIZE,bool TEST_ROOT>
 static int bvh_node_stack_raycast(Node *root, Isect *isec)
 {
 	Node *stack[MAX_STACK_SIZE];
 	int hit = 0, stack_pos = 0;
 		
-	//Assume the BB of root always succeed
-	if(1)
+	if(!TEST_ROOT && RayObject_isAligned(root))
 		bvh_node_push_childs(root, isec, stack, stack_pos);
 	else
 		stack[stack_pos++] = root;
diff --git a/source/blender/render/intern/raytrace/rayobject_bvh.cpp b/source/blender/render/intern/raytrace/rayobject_bvh.cpp
index 2c2a260df98..435c49cdc42 100644
--- a/source/blender/render/intern/raytrace/rayobject_bvh.cpp
+++ b/source/blender/render/intern/raytrace/rayobject_bvh.cpp
@@ -199,7 +199,7 @@ template<>
 int bvh_intersect<BVHTree>(BVHTree *obj, Isect* isec)
 {
 	if(RayObject_isAligned(obj->root))
-		return bvh_node_stack_raycast<BVHNode,64>(obj->root, isec);
+		return bvh_node_stack_raycast<BVHNode,64,true>(obj->root, isec);
 	else
 		return RE_rayobject_intersect( (RayObject*) obj->root, isec );
 }
diff --git a/source/blender/render/intern/raytrace/rayobject_vbvh.cpp b/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
index 305de145a72..ce3218c25fa 100644
--- a/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
+++ b/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
@@ -130,6 +130,7 @@ void bvh_update_bb(Node *node)
 
 static int tot_pushup   = 0;
 static int tot_pushdown = 0;
+static int tot_hints    = 0;
 
 template<class Node>
 void pushdown(Node *parent)
@@ -142,7 +143,7 @@ void pushdown(Node *parent)
 		Node *next = child->sibling;
 		Node **next_s_child = &child->sibling;
 		
-		assert(bb_fits_inside(parent->bb, parent->bb+3, child->bb, child->bb+3));
+		//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))
@@ -256,21 +257,93 @@ void bvh_done<BVHTree>(BVHTree *obj)
 template<int StackSize>
 int intersect(BVHTree *obj, Isect* isec)
 {
-	if(RayObject_isAligned(obj->root))
-		return bvh_node_stack_raycast<BVHNode,StackSize>(obj->root, isec);
+	if(isec->hint)
+	{
+		LCTSHint *lcts = (LCTSHint*)isec->hint;
+		isec->hint = 0;
+		
+		int hit = 0;
+		for(int i=0; i<lcts->size; i++)
+		{
+			BVHNode *node = (BVHNode*)lcts->stack[i];
+			if(RayObject_isAligned(node))
+				hit |= bvh_node_stack_raycast<BVHNode,StackSize,true>(node, isec);
+			else
+				hit |= RE_rayobject_intersect( (RayObject*)node, isec );
+			
+			if(hit && isec->mode == RE_RAY_SHADOW)
+				break;
+		}
+		isec->hint = (RayHint*)lcts;
+		return hit;
+	}
 	else
-		return RE_rayobject_intersect( (RayObject*) obj->root, isec );
+	{
+		if(RayObject_isAligned(obj->root))
+			return bvh_node_stack_raycast<BVHNode,StackSize,false>(obj->root, isec);
+		else
+			return RE_rayobject_intersect( (RayObject*) obj->root, isec );
+	}
 }
 
+template<class Node>
+void bvh_dfs_make_hint(Node *node, LCTSHint *hint, int reserve_space, float *min, float *max);
+
+template<class Node>
+void bvh_dfs_make_hint_push_siblings(Node *node, LCTSHint *hint, int reserve_space, float *min, float *max)
+{
+	if(!RayObject_isAligned(node))
+		hint->stack[hint->size++] = (RayObject*)node;
+	else
+	{
+		if(node->sibling)
+			bvh_dfs_make_hint_push_siblings(node->sibling, hint, reserve_space+1, min, max);
+
+		bvh_dfs_make_hint(node, hint, reserve_space, min, max);
+	}
+		
+	
+}
+
+template<class Node>
+void bvh_dfs_make_hint(Node *node, LCTSHint *hint, int reserve_space, float *min, float *max)
+{
+	assert( hint->size - reserve_space + 1 <= RE_RAY_LCTS_MAX_SIZE );
+	
+	if(hint->size - reserve_space + 1 == RE_RAY_LCTS_MAX_SIZE || !RayObject_isAligned(node))
+		hint->stack[hint->size++] = (RayObject*)node;
+	else
+	{
+		/* We are 100% sure the ray will be pass inside this node */
+		if(bb_fits_inside(node->bb, node->bb+3, min, max) )
+		{
+			bvh_dfs_make_hint_push_siblings(node->child, hint, reserve_space, min, max);
+		}
+		else
+		{
+			hint->stack[hint->size++] = (RayObject*)node;
+		}
+	}
+}
+
+template<class Tree>
+void bvh_hint_bb(Tree *tree, LCTSHint *hint, float *min, float *max)
+{
+	hint->size = 0;
+	bvh_dfs_make_hint( tree->root, hint, 0, min, max );
+	tot_hints++;
+}
 
 void bfree(BVHTree *tree)
 {
-	if(tot_pushup + tot_pushdown)
+	if(tot_pushup + tot_pushdown + tot_hints)
 	{
 		printf("tot pushups: %d\n", tot_pushup);
 		printf("tot pushdowns: %d\n", tot_pushdown);
+		printf("tot hints created: %d\n", tot_hints);
 		tot_pushup = 0;
 		tot_pushdown = 0;
+		tot_hints = 0;
 	}
 	bvh_free(tree);
 }
@@ -287,7 +360,8 @@ static RayObjectAPI make_api()
 //		(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>)
+		(RE_rayobject_cost_callback)	((float(*)(BVHTree*))      &bvh_cost<BVHTree>),
+		(RE_rayobject_hint_bb_callback)	((void(*)(BVHTree*,LCTSHint*,float*,float*)) &bvh_hint_bb<BVHTree>)
 	};
 	
 	return api;
diff --git a/source/blender/render/intern/source/rayobject.c b/source/blender/render/intern/source/rayobject.c
index 949b7afb5a0..2e63dc78c0e 100644
--- a/source/blender/render/intern/source/rayobject.c
+++ b/source/blender/render/intern/source/rayobject.c
@@ -414,6 +414,20 @@ float RE_rayobject_cost(RayObject *r)
 	else assert(0);
 }
 
+void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max)
+{
+	if(RayObject_isRayFace(r))
+	{
+		return;
+	}
+	else if(RayObject_isRayAPI(r))
+	{
+		r = RayObject_align( r );
+		return r->api->hint_bb( r, hint, min, max );
+	}
+	else assert(0);
+}
+
 #ifdef RE_RAYCOUNTER
 void RE_RC_INFO(RayCounter *info)
 {
diff --git a/source/blender/render/intern/source/rayshade.c b/source/blender/render/intern/source/rayshade.c
index 52edd7a7e27..66f564d4364 100644
--- a/source/blender/render/intern/source/rayshade.c
+++ b/source/blender/render/intern/source/rayshade.c
@@ -624,9 +624,7 @@ static void traceray(ShadeInput *origshi, ShadeResult *origshr, short depth, flo
 	isec.labda = dist_mir > 0 ? dist_mir : RE_RAYTRACE_MAXDIST;
 	isec.mode= RE_RAY_MIRROR;
 	isec.skip = RE_SKIP_VLR_NEIGHBOUR;
-#ifdef RT_USE_HINT
 	isec.hint = 0;
-#endif
 
 	isec.orig.ob   = obi;
 	isec.orig.face = vlr;
@@ -1532,9 +1530,10 @@ int ray_trace_shadow_rad(ShadeInput *ship, ShadeResult *shr)
 	isec.mode= RE_RAY_MIRROR;
 	isec.orig.ob   = ship->obi;
 	isec.orig.face = ship->vlr;
-#ifdef RT_USE_HINT
 	isec.hint = 0;
-#endif
+
+	VECCOPY(isec.start, ship->co);
+	
 	RE_RC_INIT(isec, shi);
 	
 	for(a=0; a<8*8; a++) {
@@ -1548,7 +1547,6 @@ int ray_trace_shadow_rad(ShadeInput *ship, ShadeResult *shr)
 			vec[2]-= vec[2];
 		}
 
-		VECCOPY(isec.start, ship->co);
 		VECCOPY(isec.vec, vec );
 		isec.labda = RE_RAYTRACE_MAXDIST;
 
@@ -1725,6 +1723,7 @@ static float *sphere_sampler(int type, int resol, int thread, int xs, int ys)
 static void ray_ao_qmc(ShadeInput *shi, float *shadfac)
 {
 	Isect isec;
+	RayHint point_hint;
 	QMCSampler *qsa=NULL;
 	float samp3d[3];
 	float up[3], side[3], dir[3], nrm[3];
@@ -1744,9 +1743,7 @@ static void ray_ao_qmc(ShadeInput *shi, float *shadfac)
 	isec.orig.ob   = shi->obi;
 	isec.orig.face = shi->vlr;
 	isec.skip = RE_SKIP_VLR_NEIGHBOUR;
-#ifdef RT_USE_HINT
 	isec.hint = 0;
-#endif
 
 	isec.hit.ob   = 0;
 	isec.hit.face = 0;
@@ -1756,6 +1753,11 @@ static void ray_ao_qmc(ShadeInput *shi, float *shadfac)
 	isec.mode= (R.wrld.aomode & WO_AODIST)?RE_RAY_SHADOW_TRA:RE_RAY_SHADOW;
 	isec.lay= -1;
 	
+	VECCOPY(isec.start, shi->co);		
+	RE_rayobject_hint_bb( R.raytree, &point_hint, isec.start, isec.start );
+	isec.hint = &point_hint;
+
+	
 	shadfac[0]= shadfac[1]= shadfac[2]= 0.0f;
 	
 	/* prevent sky colors to be added for only shadow (shadow becomes alpha) */
@@ -1793,6 +1795,7 @@ static void ray_ao_qmc(ShadeInput *shi, float *shadfac)
 
 	QMC_initPixel(qsa, shi->thread);
 	
+	
 	while (samples < max_samples) {
 
 		/* sampling, returns quasi-random vector in unit hemisphere */
@@ -1804,7 +1807,6 @@ static void ray_ao_qmc(ShadeInput *shi, float *shadfac)
 		
 		Normalize(dir);
 			
-		VECCOPY(isec.start, shi->co);
 		isec.vec[0] = -dir[0];
 		isec.vec[1] = -dir[1];
 		isec.vec[2] = -dir[2];
@@ -1872,6 +1874,7 @@ static void ray_ao_qmc(ShadeInput *shi, float *shadfac)
 static void ray_ao_spheresamp(ShadeInput *shi, float *shadfac)
 {
 	Isect isec;
+	RayHint point_hint;
 	float *vec, *nrm, div, bias, sh=0.0f;
 	float maxdist = R.wrld.aodist;
 	float dxyview[3];
@@ -1881,9 +1884,7 @@ static void ray_ao_spheresamp(ShadeInput *shi, float *shadfac)
 	isec.orig.ob   = shi->obi;
 	isec.orig.face = shi->vlr;
 	isec.skip = RE_SKIP_VLR_NEIGHBOUR;
-#ifdef RT_USE_HINT
 	isec.hint = 0;
-#endif
 
 	isec.hit.ob   = 0;
 	isec.hit.face = 0;
@@ -1893,6 +1894,9 @@ static void ray_ao_spheresamp(ShadeInput *shi, float *shadfac)
 	isec.mode= (R.wrld.aomode & WO_AODIST)?RE_RAY_SHADOW_TRA:RE_RAY_SHADOW;
 	isec.lay= -1;
 
+	VECCOPY(isec.start, shi->co);		
+	RE_rayobject_hint_bb( R.raytree, &point_hint, isec.start, isec.start );
+	isec.hint = &point_hint;
 
 	shadfac[0]= shadfac[1]= shadfac[2]= 0.0f;
 
@@ -1940,7 +1944,6 @@ static void ray_ao_spheresamp(ShadeInput *shi, float *shadfac)
 			actual++;
 			
 			/* always set start/vec/labda */
-			VECCOPY(isec.start, shi->co);
 			isec.vec[0] = -vec[0];
 			isec.vec[1] = -vec[1];
 			isec.vec[2] = -vec[2];
@@ -2058,7 +2061,10 @@ static void ray_shadow_qmc(ShadeInput *shi, LampRen *lar, float *lampco, float *
 	float adapt_thresh = lar->adapt_thresh;
 	int min_adapt_samples=4, max_samples = lar->ray_totsamp;
 	float *co;
-	int do_soft=1, full_osa=0;
+	int do_soft=1, full_osa=0, i;
+
+	float min[3], max[3];
+	RayHint bb_hint;
 
 	float jitco[RE_MAX_OSA][3];
 	int totjitco;
@@ -2089,10 +2095,18 @@ static void ray_shadow_qmc(ShadeInput *shi, LampRen *lar, float *lampco, float *
 		qsa = get_thread_qmcsampler(&R, shi->thread, SAMP_TYPE_HAMMERSLEY, max_samples);
 	
 	QMC_initPixel(qsa, shi->thread);
+
+	INIT_MINMAX(min, max);
+	for(i=0; i<totjitco; i++)
+	{
+		DO_MINMAX(jitco[i], min, max);
+	}
+	RE_rayobject_hint_bb( R.raytree, &bb_hint, min, max);
 	
+	isec->hint = &bb_hint;
+	isec->skip = RE_SKIP_VLR_NEIGHBOUR;
 	VECCOPY(vec, lampco);
 	
-	isec->skip = RE_SKIP_VLR_NEIGHBOUR;
 	while (samples < max_samples) {
 
 		isec->orig.ob   = shi->obi;
@@ -2215,6 +2229,7 @@ static void ray_shadow_jitter(ShadeInput *shi, LampRen *lar, float *lampco, floa
 	float *jitlamp;
 	float fac=0.0f, div=0.0f, vec[3];
 	int a, j= -1, mask;
+	RayHint point_hint;
 	
 	if(isec->mode==RE_RAY_SHADOW_TRA) {
 		shadfac[0]= shadfac[1]= shadfac[2]= shadfac[3]= 0.0f;
@@ -2231,6 +2246,12 @@ static void ray_shadow_jitter(ShadeInput *shi, LampRen *lar, float *lampco, floa
 	if(a==4) mask |= (mask>>4)|(mask>>8);
 	else if(a==9) mask |= (mask>>9);
 	
+	VECCOPY(isec->start, shi->co);		
+	isec->orig.ob   = shi->obi;
+	isec->orig.face = shi->vlr;
+	RE_rayobject_hint_bb( R.raytree, &point_hint, isec->start, isec->start );
+	isec->hint = &point_hint;
+	
 	while(a--) {
 		
 		if(R.r.mode & R_OSA) {
@@ -2242,19 +2263,15 @@ static void ray_shadow_jitter(ShadeInput *shi, LampRen *lar, float *lampco, floa
 			}
 		}
 		
-		isec->orig.ob   = shi->obi;
-		isec->orig.face = shi->vlr;
-		
 		vec[0]= jitlamp[0];
 		vec[1]= jitlamp[1];
 		vec[2]= 0.0f;
 		Mat3MulVecfl(lar->mat, vec);
 		
 		/* set start and vec */
-		VECCOPY(isec->start, shi->co);		
-		isec->vec[0] = vec[0]+lampco[0]-shi->co[0];
-		isec->vec[1] = vec[1]+lampco[1]-shi->co[1];
-		isec->vec[2] = vec[2]+lampco[2]-shi->co[2];
+		isec->vec[0] = vec[0]+lampco[0]-isec->start[0];
+		isec->vec[1] = vec[1]+lampco[1]-isec->start[1];
+		isec->vec[2] = vec[2]+lampco[2]-isec->start[2];
 		isec->labda = 1.0f;
 		isec->skip = RE_SKIP_VLR_NEIGHBOUR;
 		
@@ -2299,9 +2316,7 @@ void ray_shadow(ShadeInput *shi, LampRen *lar, float *shadfac)
 	RE_RC_INIT(isec, *shi);
 	if(shi->mat->mode & MA_SHADOW_TRA) isec.mode= RE_RAY_SHADOW_TRA;
 	else isec.mode= RE_RAY_SHADOW;
-#ifdef RT_USE_HINT
 	isec.hint = 0;
-#endif
 	
 	if(lar->mode & (LA_LAYER|LA_LAYER_SHADOW))
 		isec.lay= lar->lay;
@@ -2390,9 +2405,7 @@ static void ray_translucent(ShadeInput *shi, LampRen *lar, float *distfac, float
 	/* setup isec */
 	RE_RC_INIT(isec, *shi);
 	isec.mode= RE_RAY_SHADOW_TRA;
-#ifdef RT_USE_HINT
 	isec.hint = 0;
-#endif
 	
 	if(lar->mode & LA_LAYER) isec.lay= lar->lay; else isec.lay= -1;