[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [21600] branches/soc-2009-jaguarandi/ source/blender/render: *Added support to "BB hints" ( which works like a BB version of LCTS - longest common transversing subtree )
André Pinto
andresusanopinto at gmail.com
Wed Jul 15 19:38:00 CEST 2009
Revision: 21600
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21600
Author: jaguarandi
Date: 2009-07-15 19:38:00 +0200 (Wed, 15 Jul 2009)
Log Message:
-----------
*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.
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/raytrace/bvh.h
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_bvh.cpp
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c
branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.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-15 17:11:08 UTC (rev 21599)
+++ branches/soc-2009-jaguarandi/source/blender/render/extern/include/RE_raytrace.h 2009-07-15 17:38:00 UTC (rev 21600)
@@ -36,6 +36,7 @@
#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 @@
/* 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_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,7 +104,22 @@
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 @@
void *userdata;
+ RayHint *hint;
+
#ifdef RE_RAYCOUNTER
RayCounter *raycounter;
#endif
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-15 17:11:08 UTC (rev 21599)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject.h 2009-07-15 17:38:00 UTC (rev 21600)
@@ -98,6 +98,7 @@
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 @@
RE_rayobject_free_callback free;
RE_rayobject_merge_bb_callback bb;
RE_rayobject_cost_callback cost;
+ RE_rayobject_hint_bb_callback hint_bb;
} RayObjectAPI;
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h 2009-07-15 17:11:08 UTC (rev 21599)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/bvh.h 2009-07-15 17:38:00 UTC (rev 21600)
@@ -93,14 +93,13 @@
*/
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;
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_bvh.cpp
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_bvh.cpp 2009-07-15 17:11:08 UTC (rev 21599)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_bvh.cpp 2009-07-15 17:38:00 UTC (rev 21600)
@@ -199,7 +199,7 @@
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 );
}
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp 2009-07-15 17:11:08 UTC (rev 21599)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp 2009-07-15 17:38:00 UTC (rev 21600)
@@ -130,6 +130,7 @@
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 @@
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 @@
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 @@
// (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;
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-15 17:11:08 UTC (rev 21599)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject.c 2009-07-15 17:38:00 UTC (rev 21600)
@@ -414,6 +414,20 @@
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)
{
Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.c
===================================================================
--- branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.c 2009-07-15 17:11:08 UTC (rev 21599)
+++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayshade.c 2009-07-15 17:38:00 UTC (rev 21600)
@@ -624,9 +624,7 @@
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 @@
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 @@
vec[2]-= vec[2];
}
- VECCOPY(isec.start, ship->co);
VECCOPY(isec.vec, vec );
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list