[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [21282] branches/soc-2009-jaguarandi/ source/blender/render: *Added rayobject_bvh
André Pinto
andresusanopinto at gmail.com
Wed Jul 1 13:27:44 CEST 2009
Revision: 21282
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21282
Author: jaguarandi
Date: 2009-07-01 13:27:43 +0200 (Wed, 01 Jul 2009)
Log Message:
-----------
*Added rayobject_bvh
A bvh structure to use on the raytracer
Modified Paths:
--------------
branches/soc-2009-jaguarandi/source/blender/render/extern/include/RE_raytrace.h
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.c
Added Paths:
-----------
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
Modified: branches/soc-2009-jaguarandi/source/blender/render/extern/include/RE_raytrace.h
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/extern/include/RE_raytrace.h 2009-07-01 05:57:27 UTC (rev 21281)
+++ branches/soc-2009-jaguarandi/source/blender/render/extern/include/RE_raytrace.h 2009-07-01 11:27:43 UTC (rev 21282)
@@ -46,13 +46,15 @@
void RE_rayobject_free(RayObject *r);
/* RayObject constructors */
+
RayObject* RE_rayobject_octree_create(int ocres, int size);
-RayObject* RE_rayobject_blibvh_create(int size);
RayObject* RE_rayobject_instance_create(RayObject *target, float transform[][4], void *ob, void *target_ob);
-//RayObject* RayObject_derivedmesh_create(struct DerivedMesh*, void *ob);
-RayObject* RE_rayobject_mesh_create(struct Mesh*, void *ob);
+#define RE_rayobject_tree_create RE_rayobject_bvh_create
+RayObject* RE_rayobject_blibvh_create(int size); /* BLI_kdopbvh.c */
+RayObject* RE_rayobject_bvh_create(int size); /* rayobject_bvh.c */
+
/* Ray Intersection */
struct Isect
{
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h 2009-07-01 05:57:27 UTC (rev 21281)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h 2009-07-01 11:27:43 UTC (rev 21282)
@@ -123,6 +123,12 @@
*/
int RE_rayobject_intersect(RayObject *r, Isect *i);
+/*
+ * Returns distance ray must travel to hit the given bounding box
+ * BB should be in format [2][3]
+ */
+float RE_rayobject_bb_intersect(const Isect *i, const float *bb);
+
#define ISECT_EPSILON ((float)FLT_EPSILON)
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h 2009-07-01 05:57:27 UTC (rev 21281)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h 2009-07-01 11:27:43 UTC (rev 21282)
@@ -50,8 +50,8 @@
/* axis used (if any) on the split method */
int split_axis;
- /* links to child partitions calculated during splitting */
- RayObject **child[MAX_CHILDS+1];
+ /* child partitions calculated during splitting */
+ int child_offset[MAX_CHILDS+1];
} RTBuilder;
@@ -63,22 +63,9 @@
/* used during tree reorganization */
RTBuilder* rtbuild_get_child(RTBuilder *b, int child, RTBuilder *tmp);
-void rtbuild_mean_split(RTBuilder *b, int nchilds, int axis);
-void rtbuild_mean_split_largest_axis(RTBuilder *b, int nchilds);
-/*
-static BVHNode *bvh_rearrange(BVHTree *tree, RTBuilder *b)
-{
- int i;
- int nc = rtbuild_mean_split_largest_axis(b, BVH_NCHILDS);
- RTBuilder tmp;
-
- BVHNode *bvh = tree->next_node++;
+/* Calculates child partitions and returns number of efectively needed partitions */
+int rtbuild_mean_split(RTBuilder *b, int nchilds, int axis);
+int rtbuild_mean_split_largest_axis(RTBuilder *b, int nchilds);
- bvh->split_axis = tmp->split_axis;
- for(i=0; i<nc; i++)
- bvh->child[i] = bvh_rearrange( rtbuild_get_child(b, i, &tmp) );
-}
- */
-
#endif
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c 2009-07-01 05:57:27 UTC (rev 21281)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c 2009-07-01 11:27:43 UTC (rev 21282)
@@ -36,6 +36,34 @@
#include "render_types.h"
#include "rayobject.h"
+
+/*
+ * 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]
+ */
+float RE_rayobject_bb_intersect(const Isect *isec, const float *bb)
+{
+ float dist;
+
+ float t1x = (bb[isec->bv_index[0]] - isec->start[0]) * isec->idot_axis[0];
+ float t2x = (bb[isec->bv_index[1]] - isec->start[0]) * isec->idot_axis[0];
+ float t1y = (bb[isec->bv_index[2]] - isec->start[1]) * isec->idot_axis[1];
+ float t2y = (bb[isec->bv_index[3]] - isec->start[1]) * isec->idot_axis[1];
+ float t1z = (bb[isec->bv_index[4]] - isec->start[2]) * isec->idot_axis[2];
+ float t2z = (bb[isec->bv_index[5]] - isec->start[2]) * isec->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 > isec->labda || t1y > isec->labda || t1z > isec->labda) return FLT_MAX;
+
+ dist = t1x;
+ if (t1y > dist) dist = t1y;
+ if (t1z > dist) dist = t1z;
+ return dist;
+}
+
+
/* only for self-intersecting test with current render face (where ray left) */
static int intersection2(VlakRen *face, float r0, float r1, float r2, float rx1, float ry1, float rz1)
{
@@ -262,28 +290,43 @@
return 0;
}
-int RE_rayobject_raycast(RayObject *r, Isect *i)
+int RE_rayobject_raycast(RayObject *r, Isect *isec)
{
- RE_RC_COUNT(i->count->raycast.test);
+ int i;
+ RE_RC_COUNT(isec->count->raycast.test);
- i->dist = VecLength(i->vec);
+ /* Setup vars used on raycast */
+ isec->dist = VecLength(isec->vec);
- if(i->mode==RE_RAY_SHADOW && i->last_hit && RE_rayobject_intersect(i->last_hit, i))
+ for(i=0; i<3; i++)
{
- RE_RC_COUNT(i->count->raycast.hit);
- RE_RC_COUNT(i->count->rayshadow_last_hit_optimization );
+ isec->idot_axis[i] = 1.0f / isec->vec[i];
+
+ isec->bv_index[2*i] = isec->idot_axis[i] < 0.0 ? 1 : 0;
+ isec->bv_index[2*i+1] = 1 - isec->bv_index[2*i];
+
+ isec->bv_index[2*i] = i+3*isec->bv_index[2*i];
+ isec->bv_index[2*i+1] = i+3*isec->bv_index[2*i+1];
+ }
+
+
+ /* Last hit heuristic */
+ if(isec->mode==RE_RAY_SHADOW && isec->last_hit && RE_rayobject_intersect(isec->last_hit, isec))
+ {
+ RE_RC_COUNT(isec->count->raycast.hit);
+ RE_RC_COUNT(isec->count->rayshadow_last_hit_optimization );
return 1;
}
#ifdef RE_RAYCOUNTER
- if(RE_rayobject_intersect(r, i))
+ if(RE_rayobject_intersect(r, isec))
{
- RE_RC_COUNT(i->count->raycast.hit);
+ RE_RC_COUNT(isec->count->raycast.hit);
return 1;
}
return 0;
#else
- return RE_rayobject_intersect(r, i);
+ return RE_rayobject_intersect(r, isec);
#endif
}
Added: branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c (rev 0)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c 2009-07-01 11:27:43 UTC (rev 21282)
@@ -0,0 +1,200 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2009 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): André Pinto.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#include <assert.h>
+
+#include "MEM_guardedalloc.h"
+#include "BKE_utildefines.h"
+#include "BLI_arithb.h"
+#include "RE_raytrace.h"
+#include "rayobject_rtbuild.h"
+#include "rayobject.h"
+
+#define BVH_NCHILDS 2
+typedef struct BVHTree BVHTree;
+
+static int bvh_intersect(BVHTree *obj, Isect *isec);
+static void bvh_add(BVHTree *o, RayObject *ob);
+static void bvh_done(BVHTree *o);
+static void bvh_free(BVHTree *o);
+static void bvh_bb(BVHTree *o, float *min, float *max);
+
+static RayObjectAPI bvh_api =
+{
+ (RE_rayobject_raycast_callback) bvh_intersect,
+ (RE_rayobject_add_callback) bvh_add,
+ (RE_rayobject_done_callback) bvh_done,
+ (RE_rayobject_free_callback) bvh_free,
+ (RE_rayobject_merge_bb_callback)bvh_bb
+};
+
+typedef struct BVHNode BVHNode;
+struct BVHNode
+{
+ BVHNode *child[BVH_NCHILDS];
+ float bb[2][3];
+};
+
+struct BVHTree
+{
+ RayObject rayobj;
+
+ BVHNode *alloc, *next_node, *root;
+ RTBuilder *builder;
+
+};
+
+
+RayObject *RE_rayobject_bvh_create(int size)
+{
+ BVHTree *obj= (BVHTree*)MEM_callocN(sizeof(BVHTree), "BVHTree");
+ assert( RayObject_isAligned(obj) ); /* RayObject API assumes real data to be 4-byte aligned */
+
+ obj->rayobj.api = &bvh_api;
+ obj->builder = rtbuild_create( size );
+ obj->root = NULL;
+
+ return RayObject_unalignRayAPI((RayObject*) obj);
+}
+
+static void bvh_free(BVHTree *obj)
+{
+ if(obj->builder)
+ rtbuild_free(obj->builder);
+
+ if(obj->alloc)
+ MEM_freeN(obj->alloc);
+
+ MEM_freeN(obj);
+}
+
+
+static void bvh_merge_bb(BVHNode *node, float *min, float *max)
+{
+ if(RayObject_isAligned(node))
+ {
+ //TODO only half operations needed
+ DO_MINMAX(node->bb[0], min, max);
+ DO_MINMAX(node->bb[1], min, max);
+ }
+ else
+ {
+ RE_rayobject_merge_bb( (RayObject*)node, min, max);
+ }
+}
+
+static void bvh_bb(BVHTree *obj, float *min, float *max)
+{
+ bvh_merge_bb(obj->root, min, max);
+}
+
+/*
+ * Tree transverse
+ */
+static int dfs_raycast(BVHNode *node, Isect *isec)
+{
+ int hit = 0;
+ if(RE_rayobject_bb_intersect(isec, (const float*)node->bb) != FLT_MAX)
+ {
+ int i;
+ for(i=0; i<BVH_NCHILDS; i++)
+ if(RayObject_isAligned(node->child[i]))
+ {
+ hit = dfs_raycast(node->child[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ else
+ {
+ hit = RE_rayobject_intersect( (RayObject*)node->child[i], isec);
+ if(hit && isec->mode == RE_RAY_SHADOW) return hit;
+ }
+ }
+ return hit;
+}
+
+static int bvh_intersect(BVHTree *obj, Isect *isec)
+{
+ if(RayObject_isAligned(obj->root))
+ return dfs_raycast(obj->root, isec);
+ else
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list