[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [20816] branches/soc-2009-jaguarandi/ source/blender: *ray<->bb hit optimization...

[André Pinto]

Revision: 20816
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=20816
Author:   jaguarandi
Date:     2009-06-11 20:25:29 +0200 (Thu, 11 Jun 2009)

Log Message:
-----------
*ray<->bb hit optimization... just to make it "slightly" faster :P

Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
[http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]

*for now it breaks shrinkwrap or other stuff that relies on sphere-raycast of BLI_kdopbvh.

Modified Paths:
--------------
    branches/soc-2009-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
    branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.c

Modified: branches/soc-2009-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c	2009-06-11 18:19:08 UTC (rev 20815)
+++ branches/soc-2009-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c	2009-06-11 18:25:29 UTC (rev 20816)
@@ -101,6 +101,8 @@
 
 	BVHTreeRay    ray;
 	float ray_dot_axis[13];
+	float idot_axis[13];
+	int index[6];
 
 	BVHTreeRayHit hit;
 } BVHRayCastData;
@@ -1404,6 +1406,7 @@
  * raycast is done by performing a DFS on the BVHTree and saving the closest hit
  */
 
+
 //Determines the distance that the ray must travel to hit the bounding volume of the given node
 static float ray_nearest_hit(BVHRayCastData *data, BVHNode *node)
 {
@@ -1443,13 +1446,40 @@
 	return low;
 }
 
+//Determines the distance that the ray must travel to hit the bounding volume of the given node
+//Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe
+//[http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]
+//
+//TODO this doens't has data->ray.radius in consideration
+static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node)
+{
+	const float *bv = node->bv;
+	float dist;
+	
+	float t1x = (bv[data->index[0]] - data->ray.origin[0]) * data->idot_axis[0];
+	float t2x = (bv[data->index[1]] - data->ray.origin[0]) * data->idot_axis[0];
+	float t1y = (bv[data->index[2]] - data->ray.origin[1]) * data->idot_axis[1];
+	float t2y = (bv[data->index[3]] - data->ray.origin[1]) * data->idot_axis[1];
+	float t1z = (bv[data->index[4]] - data->ray.origin[2]) * data->idot_axis[2];
+	float t2z = (bv[data->index[5]] - data->ray.origin[2]) * data->idot_axis[2];
+
+	if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return FLT_MAX;
+	if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return FLT_MAX;
+	if(t1x > data->hit.dist || t1y > data->hit.dist || t1z > data->hit.dist) return FLT_MAX;
+
+	dist = t1x;
+	if (t1y > dist) dist = t1y;
+    if (t1z > dist) dist = t1z;
+	return dist;
+}
+
 static void dfs_raycast(BVHRayCastData *data, BVHNode *node)
 {
 	int i;
 
 	//ray-bv is really fast.. and simple tests revealed its worth to test it
 	//before calling the ray-primitive functions
-	float dist = ray_nearest_hit(data, node);
+	float dist = fast_ray_nearest_hit(data, node);
 	if(dist >= data->hit.dist) return;
 
 	if(node->totnode == 0)
@@ -1503,9 +1533,16 @@
 	for(i=0; i<3; i++)
 	{
 		data.ray_dot_axis[i] = INPR( data.ray.direction, KDOP_AXES[i]);
+		data.idot_axis[i] = 1.0f / data.ray_dot_axis[i];
 
 		if(fabs(data.ray_dot_axis[i]) < FLT_EPSILON)
+		{
 			data.ray_dot_axis[i] = 0.0;
+		}
+		data.index[2*i] = data.idot_axis[i] < 0.0 ? 1 : 0;
+		data.index[2*i+1] = 1 - data.index[2*i];
+		data.index[2*i]	  += 2*i;
+		data.index[2*i+1] += 2*i;
 	}
 
 

Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.c
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.c	2009-06-11 18:19:08 UTC (rev 20815)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.c	2009-06-11 18:25:29 UTC (rev 20816)
@@ -177,8 +177,8 @@
 		//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 );
+//		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;
 		
@@ -284,7 +284,8 @@
 	}
 	
 	//Create raytree
-	raytree = re->raytree	= RE_rayobject_octree_create(re->r.ocres, faces);
+//	raytree = re->raytree	= RE_rayobject_octree_create(re->r.ocres, faces);
+	raytree = re->raytree	= RE_rayobject_bvh_create(faces);
 	face	= re->rayfaces	= (RayFace*)MEM_callocN(faces*sizeof(RayFace), "Render ray faces");
 	
 	for(obi=re->instancetable.first; obi; obi=obi->next)