*Instance support at dupliverts/faces

*Octree works nicely on hierarchic trees
	*the old code was quite destructive at the Isect variable
	 changing isec->start, end, vec..now it only changes isec->labda (and hit results)

Currently rendering a BVH of all objects, where each object has it own octree.

7 files changed, 327 insertions, 163 deletions

diff --git a/source/blender/render/intern/include/render_types.h b/source/blender/render/intern/include/render_types.h
index 4846fe8d0e4..88bf30bd9ef 100644
--- a/source/blender/render/intern/include/render_types.h
+++ b/source/blender/render/intern/include/render_types.h
@@ -54,6 +54,7 @@ struct GHash;
 struct RenderBuckets;
 struct ObjectInstanceRen;
 struct RayObject;
+struct RayFace;
 
 #define TABLEINITSIZE 1024
 #define LAMPINITSIZE 256
@@ -170,7 +171,7 @@ struct Render
 	
 	/* octree tables and variables for raytrace */
 	struct RayObject *raytree;
-	struct RayObject *rayfaces; /* TODO Temporary */
+	struct RayFace *rayfaces;
 
 	/* occlusion tree */
 	void *occlusiontree;
@@ -280,6 +281,12 @@ typedef struct ObjectRen {
 	int  actmtface, actmcol, bakemtface;
 
 	float obmat[4][4];	/* only used in convertblender.c, for instancing */
+
+	/* used on makeraytree */
+	struct RayObject *raytree;
+	struct RayFace *rayfaces;
+	struct ObjectInstanceRen *rayobi;
+	
 } ObjectRen;
 
 typedef struct ObjectInstanceRen {
@@ -297,6 +304,10 @@ typedef struct ObjectInstanceRen {
 
 	float *vectors;
 	int totvector;
+	
+	/* used on makeraytree */
+	struct RayObject *raytree;
+
 } ObjectInstanceRen;
 
 /* ------------------------------------------------------------------------- */
diff --git a/source/blender/render/intern/source/rayobject.c b/source/blender/render/intern/source/rayobject.c
index e622dd971ee..5fc70deaee7 100644
--- a/source/blender/render/intern/source/rayobject.c
+++ b/source/blender/render/intern/source/rayobject.c
@@ -128,10 +128,6 @@ static int intersect_rayface(RayFace *face, Isect *is)
 	if(is->orig.ob == face->ob && is->orig.face == face->face)
 		return 0;
 
-	/* disabled until i got real & fast cylinder checking, this code doesnt work proper for faster strands */
-	//	if(is->mode==RE_RAY_SHADOW && is->vlr->flag & R_STRAND) 
-	//		return intersection_strand(is);
-	
 
 	VECCOPY(co1, face->v1);
 	VECCOPY(co2, face->v2);
@@ -182,7 +178,7 @@ static int intersect_rayface(RayFace *face, Isect *is)
 			if(v<ISECT_EPSILON && (u + v) > -(1.0f+ISECT_EPSILON)) {
 				labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
 
-				if(labda>-ISECT_EPSILON && labda<1.0f+ISECT_EPSILON) {
+				if(labda>-ISECT_EPSILON && labda<is->labda) {
 					ok= 1;
 				}
 			}
@@ -210,7 +206,7 @@ static int intersect_rayface(RayFace *face, Isect *is)
 				if(v<ISECT_EPSILON && (u + v) >-(1.0f+ISECT_EPSILON)) {
 					labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12);
 					
-					if(labda>-ISECT_EPSILON && labda<1.0f+ISECT_EPSILON) {
+					if(labda>-ISECT_EPSILON && labda<is->labda) {
 						ok= 2;
 					}
 				}
@@ -250,9 +246,6 @@ static int intersect_rayface(RayFace *face, Isect *is)
 		}
 #endif
 
-		if(is->mode!=RE_RAY_SHADOW && labda > is->labda)
-			return 0;
-
 		is->isect= ok;	// wich half of the quad
 		is->labda= labda;
 		is->u= u; is->v= v;
@@ -274,10 +267,12 @@ int RE_rayobject_raycast(RayObject *r, Isect *i)
 		printf("Casting %d rays\n", casted_rays);
 
 	i->labda = 10000.0;
+/*
 	i->vec[0] *= i->labda;
 	i->vec[1] *= i->labda;
 	i->vec[2] *= i->labda;
 	i->labda = 1.0f;
+*/
 	i->dist = VecLength(i->vec);
 	
 	if(i->mode==RE_RAY_SHADOW && i->last_hit && RE_rayobject_intersect(i->last_hit, i))
diff --git a/source/blender/render/intern/source/rayobject_bvh.c b/source/blender/render/intern/source/rayobject_bvh.c
index 232b221fbdb..c5e0cca808c 100644
--- a/source/blender/render/intern/source/rayobject_bvh.c
+++ b/source/blender/render/intern/source/rayobject_bvh.c
@@ -66,7 +66,7 @@ RayObject *RE_rayobject_bvh_create(int size)
 	assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */	
 	
 	obj->rayobj.api = &bvh_api;
-	obj->bvh = BLI_bvhtree_new(size, FLT_EPSILON, 2, 6);
+	obj->bvh = BLI_bvhtree_new(size, FLT_EPSILON, 4, 6);
 	
 	INIT_MINMAX(obj->bb[0], obj->bb[1]);
 	return RayObject_unalign((RayObject*) obj);
@@ -83,9 +83,8 @@ static void bvh_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTr
 
 		if(isec->mode == RE_RAY_SHADOW)
 			hit->dist = 0;
-//		TODO
-//		else
-//			hit->dist = isec->labda;
+		else
+			hit->dist = isec->labda*isec->dist;
 	}
 }
 
@@ -99,7 +98,7 @@ static int  RayObject_bvh_intersect(RayObject *o, Isect *isec)
 	Normalize(dir);
 
 	hit.index = 0;
-	hit.dist = FLT_MAX; //TODO isec->labda;
+	hit.dist = isec->labda*isec->dist;
 	
 	return BLI_bvhtree_ray_cast(obj->bvh, isec->start, dir, 0.0, &hit, bvh_callback, isec);
 }
diff --git a/source/blender/render/intern/source/rayobject_instance.c b/source/blender/render/intern/source/rayobject_instance.c
index ba675dcb1e7..a5024e97450 100644
--- a/source/blender/render/intern/source/rayobject_instance.c
+++ b/source/blender/render/intern/source/rayobject_instance.c
@@ -51,22 +51,28 @@ typedef struct InstanceRayObject
 {
 	RayObject rayobj;
 	RayObject *target;
+
+	void *ob; //Object represented by this instance
+	void *target_ob; //Object represented by the inner RayObject, needed to handle self-intersection
+	
 	float global2target[4][4];
 	float target2global[4][4];
 	
 } InstanceRayObject;
 
 
-RayObject *RE_rayobject_instance_create(RayObject *target, float transform[][4])
+RayObject *RE_rayobject_instance_create(RayObject *target, float transform[][4], void *ob, void *target_ob)
 {
 	InstanceRayObject *obj= (InstanceRayObject*)MEM_callocN(sizeof(InstanceRayObject), "InstanceRayObject");
 	assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */	
 	
 	obj->rayobj.api = &instance_api;
 	obj->target = target;
+	obj->ob = ob;
+	obj->target_ob = target_ob;
 	
-	Mat4CpyMat4(obj->global2target, transform);
-	Mat4Invert(obj->target2global, obj->global2target);
+	Mat4CpyMat4(obj->target2global, transform);
+	Mat4Invert(obj->global2target, obj->target2global);
 	
 	return RayObject_unalign((RayObject*) obj);
 }
@@ -78,39 +84,54 @@ static int  RayObject_instance_intersect(RayObject *o, Isect *isec)
 	
 	InstanceRayObject *obj = (InstanceRayObject*)o;
 	int res;
-	float start[3], vec[3], labda_point[3], labda;
+	float start[3], vec[3], labda, dist;
+	int changed = 0;
+	
+	//TODO - this is disabling self intersection on instances
+	if(isec->orig.ob == obj->ob && obj->ob)
+	{
+		changed = 1;
+		isec->orig.ob = obj->target_ob;
+	}
 	
 	
 	VECCOPY( start, isec->start );
 	VECCOPY( vec  , isec->vec   );
 	labda = isec->labda;
-	VECADDFAC( labda_point, start, vec, labda );
-	
-	
+	dist  = isec->dist;
+
 	//Transform to target coordinates system
 	VECADD( isec->vec, isec->vec, isec->start );	
-	VecMat4MulVecfl(isec->start, obj->target2global, isec->start);
-	VecMat4MulVecfl(isec->vec  , obj->target2global, isec->vec);
-	VecMat4MulVecfl(labda_point, obj->target2global, labda_point);
-	isec->labda = VecLenf( isec->start, labda_point );
+
+	Mat4MulVecfl(obj->global2target, isec->start);
+	Mat4MulVecfl(obj->global2target, isec->vec  );
+
+	isec->dist = VecLenf( isec->start, isec->vec );
 	VECSUB( isec->vec, isec->vec, isec->start );
 	
+	isec->labda *= isec->dist / dist;
+	
 	//Raycast
 	res = RE_rayobject_intersect(obj->target, isec);
 
 	//Restore coordinate space coords
 	if(res == 0)
+	{
 		isec->labda = labda;
+		
+	}
 	else
 	{
-		VECADDFAC( labda_point, isec->start, isec->vec, isec->labda );
-		VecMat4MulVecfl(labda_point, obj->global2target, labda_point);
-		isec->labda = VecLenf( start, labda_point );
-		
+		isec->labda *= dist / isec->dist;
+		isec->hit.ob = obj->ob;
 	}
+	isec->dist = dist;
 	VECCOPY( isec->start, start );
-	VECCOPY( isec->vec, vec );
+	VECCOPY( isec->vec,   vec );
 	
+	if(changed)
+		isec->orig.ob = obj->ob;
+		
 	return res;
 }
 
@@ -123,17 +144,20 @@ static void RayObject_instance_free(RayObject *o)
 static void RayObject_instance_bb(RayObject *o, float *min, float *max)
 {
 	//TODO:
-	// *better bb.. calculated witouth rotations of bb
-	// *maybe cache that better fitted BB at the InstanceRayObject
+	// *better bb.. calculated without rotations of bb
+	// *maybe cache that better-fitted-BB at the InstanceRayObject
 	InstanceRayObject *obj = (InstanceRayObject*)o;
 
-	float m[3], M[3];
+	float m[3], M[3], t[3];
+	int i, j;
 	INIT_MINMAX(m, M);
 	RE_rayobject_merge_bb(obj->target, m, M);
 
-	VecMat4MulVecfl(m, obj->target2global, m);
-	VecMat4MulVecfl(M, obj->target2global, M);
-
-	DO_MINMAX(m, min, max);
-	DO_MINMAX(M, min, max);
+	//There must be a faster way than rotating all the 8 vertexs of the BB
+	for(i=0; i<8; i++)
+	{
+		for(j=0; j<3; j++) t[j] = i&(1<<j) ? M[j] : m[j];
+		Mat4MulVecfl(obj->target2global, t);
+		DO_MINMAX(t, min, max);
+	}
 }
diff --git a/source/blender/render/intern/source/rayobject_octree.c b/source/blender/render/intern/source/rayobject_octree.c
index 018c7735284..b715695dc10 100644
--- a/source/blender/render/intern/source/rayobject_octree.c
+++ b/source/blender/render/intern/source/rayobject_octree.c
@@ -636,7 +636,9 @@ static void RayObject_octree_done(RayObject *tree)
 	}
 
 	MEM_freeN(oc->ocface);
+	oc->ocface = NULL;
 	MEM_freeN(oc->ro_nodes);
+	oc->ro_nodes = NULL;
 	
 	printf("%f %f - %f\n", oc->min[0], oc->max[0], oc->ocfacx );
 	printf("%f %f - %f\n", oc->min[1], oc->max[1], oc->ocfacy );
@@ -820,9 +822,10 @@ static int RayObject_octree_intersect(RayObject *tree, Isect *is)
 	Octree *oc= (Octree*)tree;
 	Node *no;
 	OcVal ocval;
-	float vec1[3], vec2[3], end[3];
+	float vec1[3], vec2[3], start[3], end[3];
 	float u1,u2,ox1,ox2,oy1,oy2,oz1,oz2;
 	float labdao,labdax,ldx,labday,ldy,labdaz,ldz, ddalabda;
+	float olabda = 0;
 	int dx,dy,dz;	
 	int xo,yo,zo,c1=0;
 	int ocx1,ocx2,ocy1, ocy2,ocz1,ocz2;
@@ -838,35 +841,33 @@ static int RayObject_octree_intersect(RayObject *tree, Isect *is)
 	is->userdata= oc->userdata;
 #endif
 
+	VECCOPY( start, is->start );
 	VECADDFAC( end, is->start, is->vec, is->labda );
-	ldx= end[0] - is->start[0];
+	ldx= is->vec[0]*is->labda;
+	olabda = is->labda;
 	u1= 0.0f;
 	u2= 1.0f;
 	
 	/* clip with octree cube */
-	if(cliptest(-ldx, is->start[0]-oc->min[0], &u1,&u2)) {
-		if(cliptest(ldx, oc->max[0]-is->start[0], &u1,&u2)) {
-			ldy= end[1] - is->start[1];
-			if(cliptest(-ldy, is->start[1]-oc->min[1], &u1,&u2)) {
-				if(cliptest(ldy, oc->max[1]-is->start[1], &u1,&u2)) {
-					ldz = end[2] - is->start[2];
-					if(cliptest(-ldz, is->start[2]-oc->min[2], &u1,&u2)) {
-						if(cliptest(ldz, oc->max[2]-is->start[2], &u1,&u2)) {
+	if(cliptest(-ldx, start[0]-oc->min[0], &u1,&u2)) {
+		if(cliptest(ldx, oc->max[0]-start[0], &u1,&u2)) {
+			ldy= is->vec[1]*is->labda;
+			if(cliptest(-ldy, start[1]-oc->min[1], &u1,&u2)) {
+				if(cliptest(ldy, oc->max[1]-start[1], &u1,&u2)) {
+					ldz = is->vec[2]*is->labda;
+					if(cliptest(-ldz, start[2]-oc->min[2], &u1,&u2)) {
+						if(cliptest(ldz, oc->max[2]-start[2], &u1,&u2)) {
 							c1=1;
 							if(u2<1.0f) {
-								is->vec[0] = u2*ldx;
-								is->vec[1] = u2*ldy;
-								is->vec[2] = u2*ldz;
-
-								end[0]= is->start[0]+u2*ldx;
-								end[1]= is->start[1]+u2*ldy;
-								end[2]= is->start[2]+u2*ldz;
+								end[0] = start[0]+u2*ldx;
+								end[1] = start[1]+u2*ldy;
+								end[2] = start[2]+u2*ldz;
 							}
+
 							if(u1>0.0f) {
-								assert( 0 );
-								is->start[0]+=u1*ldx;
-								is->start[1]+=u1*ldy;
-								is->start[2]+=u1*ldz;
+								start[0] += u1*ldx;
+								start[1] += u1*ldy;
+								start[2] += u1*ldz;
 							}
 						}
 					}
@@ -881,9 +882,9 @@ static int RayObject_octree_intersect(RayObject *tree, Isect *is)
 	//ocread(oc, oc->ocres, 0, 0);
 
 	/* setup 3dda to traverse octree */
-	ox1= (is->start[0]-oc->min[0])*oc->ocfacx;
-	oy1= (is->start[1]-oc->min[1])*oc->ocfacy;
-	oz1= (is->start[2]-oc->min[2])*oc->ocfacz;
+	ox1= (start[0]-oc->min[0])*oc->ocfacx;
+	oy1= (start[1]-oc->min[1])*oc->ocfacy;
+	oz1= (start[2]-oc->min[2])*oc->ocfacz;
 	ox2= (end[0]-oc->min[0])*oc->ocfacx;
 	oy2= (end[1]-oc->min[1])*oc->ocfacy;
 	oz2= (end[2]-oc->min[2])*oc->ocfacz;
@@ -902,11 +903,11 @@ static int RayObject_octree_intersect(RayObject *tree, Isect *is)
 			vec1[0]= ox1; vec1[1]= oy1; vec1[2]= oz1;
 			vec2[0]= ox2; vec2[1]= oy2; vec2[2]= oz2;
 			calc_ocval_ray(&ocval, (float)ocx1, (float)ocy1, (float)ocz1, vec1, vec2);
-			is->labda = 1.0f;
 			if( testnode(oc, is, no, ocval) ) return 1;
 		}
 	}
 	else {
+		int found = 0;
 		//static int coh_ocx1,coh_ocx2,coh_ocy1, coh_ocy2,coh_ocz1,coh_ocz2;
 		float dox, doy, doz;
 		int eqval;
@@ -981,10 +982,15 @@ static int RayObject_octree_intersect(RayObject *tree, Isect *is)
 				vec2[2]= oz1-ddalabda*doz;
 				calc_ocval_ray(&ocval, (float)xo, (float)yo, (float)zo, vec1, vec2);
 
-				is->labda= ddalabda;
-				if( testnode(oc, is, no, ocval) ) return 1;
+				//is->labda = (u1+ddalabda*(u2-u1))*olabda;
+				if( testnode(oc, is, no, ocval) )
+					found = 1;
+
+				if(is->labda < (u1+ddalabda*(u2-u1))*olabda)
+					return found;
 			}
 
+
 			labdao= ddalabda;
 			
 			/* traversing ocree nodes need careful detection of smallest values, with proper
@@ -1052,8 +1058,6 @@ static int RayObject_octree_intersect(RayObject *tree, Isect *is)
 	}
 	
 	/* reached end, no intersections found */
-	is->hit.ob   = 0;
-	is->hit.face = NULL;
 	return 0;
 }	
 
diff --git a/source/blender/render/intern/source/rayshade.c b/source/blender/render/intern/source/rayshade.c
index 2eb545f7364..707af95aaef 100644
--- a/source/blender/render/intern/source/rayshade.c
+++ b/source/blender/render/intern/source/rayshade.c
@@ -71,16 +71,6 @@ extern struct Render R;
 /* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */
 
 #if 0
-static void vlr_face_coords(RayFace *face, float **v1, float **v2, float **v3, float **v4)
-{
-	VlakRen *vlr= (VlakRen*)face;
-
-	*v1 = (vlr->v1)? vlr->v1->co: NULL;
-	*v2 = (vlr->v2)? vlr->v2->co: NULL;
-	*v3 = (vlr->v3)? vlr->v3->co: NULL;
-	*v4 = (vlr->v4)? vlr->v4->co: NULL;
-}
-
 static int vlr_check_intersect(Isect *is, int ob, RayFace *face)
 {
 	ObjectInstanceRen *obi= RAY_OBJECT_GET((Render*)is->userdata, ob);
@@ -97,115 +87,239 @@ static int vlr_check_intersect(Isect *is, int ob, RayFace *face)
 	else
 		return (is->lay & obi->lay);
 }
+#endif
 
-static float *vlr_get_transform(void *userdata, int i)
+void freeraytree(Render *re)
 {
-	ObjectInstanceRen *obi= RAY_OBJECT_GET((Render*)userdata, i);
+	ObjectInstanceRen *obi;
+	
+	if(re->raytree)
+	{
+		RE_rayobject_free(re->raytree);
+		re->raytree = NULL;
+	}
+	if(re->rayfaces)
+	{
+		MEM_freeN(re->rayfaces);
+		re->rayfaces = NULL;
+	}
 
-	return (obi->flag & R_TRANSFORMED)? (float*)obi->mat: NULL;
+	for(obi=re->instancetable.first; obi; obi=obi->next)
+	{
+		ObjectRen *obr = obi->obr;
+		if(obr->raytree)
+		{
+			RE_rayobject_free(obr->raytree);
+			obr->raytree = NULL;
+		}
+		if(obr->rayfaces)
+		{
+			MEM_freeN(obr->rayfaces);
+			obr->rayfaces = NULL;
+		}
+		if(obi->raytree)
+		{
+			RE_rayobject_free(obi->raytree);
+			obi->raytree = NULL;
+		}
+	}
 }
-#endif
 
-void freeraytree(Render *re)
+static int is_raytraceable_vlr(Render *re, VlakRen *vlr)
 {
-	if(re->raytree) {
-		RE_rayobject_free(re->raytree);
-		re->raytree= NULL;
-		MEM_freeN( re->rayfaces );
+	if((re->flag & R_BAKE_TRACE) || (vlr->mat->mode & MA_TRACEBLE))
+	if((vlr->mat->mode & MA_WIRE)==0)
+		return 1;
+	return 0;
+}
+
+static int is_raytraceable(Render *re, ObjectInstanceRen *obi)
+{
+	int v;
+	ObjectRen *obr = obi->obr;
+
+	if(re->excludeob && obr->ob == re->excludeob)
+		return 0;
+
+	for(v=0;v<obr->totvlak;v++)
+	{
+		VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+		if(is_raytraceable_vlr(re, vlr))
+			return 1;
 	}
+	return 0;
 }
-void makeraytree(Render *re)
+
+RayObject* makeraytree_object(Render *re, ObjectInstanceRen *obi)
 {
-	ObjectInstanceRen *obi;
-	ObjectRen *obr;
-	VlakRen *vlr= NULL;
-	double lasttime= PIL_check_seconds_timer();
-	int v, totv = 0, totface = 0;
-	RayFace *faces, *cur_face;
-	int tot_quads = 0;
-
-	//TODO (for now octree only supports RayFaces so we need to create them)
-	//
-	//count faces
-	for(obi=re->instancetable.first; obi; obi=obi->next) {
-		obr= obi->obr;
-
-		if(re->excludeob && obr->ob == re->excludeob)
-			continue;
-
-		for(v=0;v<obr->totvlak;v++) {
-			if((v & 255)==0) vlr= obr->vlaknodes[v>>8].vlak;
-			else vlr++;
-			/* baking selected to active needs non-traceable too */
-			if((re->flag & R_BAKE_TRACE) || (vlr->mat->mode & MA_TRACEBLE)) {	
-				if((vlr->mat->mode & MA_WIRE)==0) {	
-					totface++;
-				}
+	//TODO
+	// out-of-memory safeproof
+	// break render
+	// update render stats
+	ObjectRen *obr = obi->obr;
+	
+	if(obr->raytree == NULL)
+	{
+		RayObject *raytree;
+		RayFace *face;
+		int v;
+		
+		//Count faces
+		int faces = 0;
+		for(v=0;v<obr->totvlak;v++)
+		{
+			VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+			if(is_raytraceable_vlr(re, vlr))
+				faces++;
+		}
+		assert( faces > 0 );
+
+		//Create Ray cast accelaration structure
+
+		//TODO dynamic ocres
+		raytree = obr->raytree = RE_rayobject_octree_create( re->r.ocres, faces );
+//		raytree = obr->raytree = RE_rayobject_bvh_create( faces );
+		face = obr->rayfaces = (RayFace*)MEM_callocN(faces*sizeof(RayFace), "ObjectRen faces");
+		obr->rayobi = obi;
+		
+		for(v=0;v<obr->totvlak;v++)
+		{
+			VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+			if(is_raytraceable_vlr(re, vlr))
+			{
+				face->v1 = vlr->v1->co;
+				face->v2 = vlr->v2->co;
+				face->v3 = vlr->v3->co;
+				face->v4 = vlr->v4 ? vlr->v4->co : NULL;
+				
+				face->ob   = obi;
+				face->face = vlr;
+				
+				RE_rayobject_add( raytree, (RayObject*)face++ );
 			}
 		}
+		RE_rayobject_done( raytree );
+	}
+
+
+	if(obi->flag & R_TRANSFORMED)
+	{
+		obi->raytree = RE_rayobject_instance_create( obr->raytree, obi->mat, obi, obi->obr->rayobi );
 	}
 	
-	printf("RE_rayobject_*_create( %d )\n", totface);
-//	re->raytree = RE_rayobject_octree_create( re->r.ocres, totface );
-	re->raytree = RE_rayobject_bvh_create( totface );
-	
-	//Fill rayfaces
-	re->rayfaces = (RayObject*)MEM_callocN(totface*sizeof(RayFace), "render faces");
-	cur_face = faces = (RayFace*)re->rayfaces;
-	
-	for(obi=re->instancetable.first; obi; obi=obi->next) {
-		obr= obi->obr;
+	if(obi->raytree) return obi->raytree;
+	return obi->obr->raytree;
+}
 
-		if(re->excludeob && obr->ob == re->excludeob)
-			continue;
+/*
+ * create an hierarchic raytrace structure with all objects
+ *
+ * R_TRANSFORMED objects instances reuse the same tree by using the rayobject_instance
+ */
+static void makeraytree_hier(Render *re)
+{
+	//TODO
+	// out-of-memory safeproof
+	// break render
+	// update render stats
 
-		for(v=0;v<obr->totvlak;v++) {
-			if((v & 255)==0)
-			{
-				double time= PIL_check_seconds_timer();
+	ObjectInstanceRen *obi;
+	int num_objects = 0;
 
-				vlr= obr->vlaknodes[v>>8].vlak;
+	re->i.infostr="Creating raytrace structure";
+	re->stats_draw(re->sdh, &re->i);
 
-				vlr= obr->vlaknodes[v>>8].vlak;
-				if(re->test_break(re->tbh))
-					break;
-				if(time-lasttime>1.0f) {
-					char str[32];
-					sprintf(str, "Filling Octree: %d", totv);
-					re->i.infostr= str;
-					re->stats_draw(re->sdh, &re->i);
-					re->i.infostr= NULL;
-					lasttime= time;
-				}
-			}
-			else vlr++;
-			/* baking selected to active needs non-traceable too */
-			if((re->flag & R_BAKE_TRACE) || (vlr->mat->mode & MA_TRACEBLE)) {	
-				if((vlr->mat->mode & MA_WIRE)==0) {	
-					cur_face->v1 = vlr->v1->co;
-					cur_face->v2 = vlr->v2->co;
-					cur_face->v3 = vlr->v3->co;
-					cur_face->v4 = vlr->v4 ? tot_quads++, vlr->v4->co : NULL;
-					
-					cur_face->ob   = (void*)obi;
-					cur_face->face = vlr;
-					
-					RE_rayobject_add( re->raytree, (RayObject*) cur_face );
-					cur_face++;
-				}
-			}
-		}
+	//Count number of objects
+	for(obi=re->instancetable.first; obi; obi=obi->next)
+	if(is_raytraceable(re, obi))
+		num_objects++;
+
+	//Create raytree
+	re->raytree = RE_rayobject_bvh_create( num_objects );
+	
+	for(obi=re->instancetable.first; obi; obi=obi->next)
+	if(is_raytraceable(re, obi))
+	{
+		RayObject *obj = makeraytree_object(re, obi);
+		RE_rayobject_add( re->raytree, obj );
+
+		if(re->test_break(re->tbh))
+			break;
 	}
 
-	printf("call RE_rayobject_done( %dtri, %dquads )\n", totface-tot_quads, tot_quads);
-	RE_rayobject_done( re->raytree );
-	printf("return RE_rayobject_done( )\n");
-//TODO	vlr_face_coords, vlr_check_intersect, vlr_get_transform, re);
+	if(!re->test_break(re->tbh))
+	{
+		RE_rayobject_done( re->raytree );
+	}
 
 	re->i.infostr= NULL;
 	re->stats_draw(re->sdh, &re->i);
 }
 
+/*
+ * create a single raytrace structure with all faces
+ */
+static void makeraytree_single(Render *re)
+{
+	ObjectInstanceRen *obi;
+	RayObject *raytree;
+	RayFace *face;
+	int faces = 0, obs = 0;
+
+	for(obi=re->instancetable.first; obi; obi=obi->next)
+	if(is_raytraceable(re, obi))
+	{
+		int v;
+		ObjectRen *obr = obi->obr;
+		obs++;
+		
+		assert((obi->flag & R_TRANSFORMED) == 0); //Not suported
+	
+		for(v=0;v<obr->totvlak;v++)
+		{
+			VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+			if(is_raytraceable_vlr(re, vlr))
+				faces++;
+		}
+	}
+	
+	//Create raytree
+	raytree = re->raytree	= RE_rayobject_octree_create(re->r.ocres, faces);
+	face	= re->rayfaces	= (RayFace*)MEM_callocN(faces*sizeof(RayFace), "Render ray faces");
+	
+	for(obi=re->instancetable.first; obi; obi=obi->next)
+	if(is_raytraceable(re, obi))
+	{
+		int v;
+		ObjectRen *obr = obi->obr;
+
+		for(v=0;v<obr->totvlak;v++)
+		{
+			VlakRen *vlr = obr->vlaknodes[v>>8].vlak + (v&255);
+			face->v1 = vlr->v1->co;
+			face->v2 = vlr->v2->co;
+			face->v3 = vlr->v3->co;
+			face->v4 = vlr->v4 ? vlr->v4->co : NULL;
+			
+			face->ob   = obi;
+			face->face = vlr;
+			
+			RE_rayobject_add( raytree, (RayObject*)face++ );
+		}
+	}
+	RE_rayobject_done( raytree );	
+}
+
+void makeraytree(Render *re)
+{
+	if(1)
+		makeraytree_hier(re);
+	else
+		makeraytree_single(re);
+}
+
+
+
 static void shade_ray(Isect *is, ShadeInput *shi, ShadeResult *shr)
 {
 	ObjectInstanceRen *obi= (ObjectInstanceRen*)is->hit.ob;
diff --git a/source/blender/render/intern/source/renderdatabase.c b/source/blender/render/intern/source/renderdatabase.c
index 621831fb341..5f21a0e2e1a 100644
--- a/source/blender/render/intern/source/renderdatabase.c
+++ b/source/blender/render/intern/source/renderdatabase.c
@@ -75,6 +75,7 @@
 #include "BKE_DerivedMesh.h"
 
 #include "RE_render_ext.h"	/* externtex */
+#include "RE_raytrace.h"
 
 #include "renderpipeline.h"
 #include "render_types.h"
@@ -872,13 +873,29 @@ void free_renderdata_tables(Render *re)
 			MEM_freeN(obr->mtface);
 		if(obr->mcol)
 			MEM_freeN(obr->mcol);
+			
+		if(obr->rayfaces)
+		{
+			MEM_freeN(obr->rayfaces);
+			obr->rayfaces = NULL;
+		}
+		if(obr->raytree)
+		{
+			RE_rayobject_free(obr->raytree);
+			obr->raytree = NULL;
+		}
 	}
 
 	if(re->objectinstance) {
 		for(obi=re->instancetable.first; obi; obi=obi->next)
+		{
 			if(obi->vectors)
 				MEM_freeN(obi->vectors);
 
+			if(obi->raytree)
+				RE_rayobject_free(obi->raytree);
+		}
+
 		MEM_freeN(re->objectinstance);
 		re->objectinstance= NULL;
 		re->totinstance= 0;