*Added support to "BB hints" (which works like a BB version of LCTS - longest common...
authorAndre Susano Pinto <andresusanopinto@gmail.com>
Wed, 15 Jul 2009 17:38:00 +0000 (17:38 +0000)
committerAndre Susano Pinto <andresusanopinto@gmail.com>
Wed, 15 Jul 2009 17:38:00 +0000 (17:38 +0000)
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.

source/blender/render/extern/include/RE_raytrace.h
source/blender/render/intern/include/rayobject.h
source/blender/render/intern/raytrace/bvh.h
source/blender/render/intern/raytrace/rayobject_bvh.cpp
source/blender/render/intern/raytrace/rayobject_vbvh.cpp
source/blender/render/intern/source/rayobject.c
source/blender/render/intern/source/rayshade.c

index 4d0c0b1a88c1862e27ee919c2b8cbbd2e8d3b92b..beae1b84b0409448ee8697d0d7069834352d0176 100644 (file)
@@ -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
index 16ebc537ef972aad75d0be27456569acf6064178..6f8debead19e6bc6e93fb9f184b92ed9acfeb1f9 100644 (file)
@@ -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;
 
index d9277f9a5839deb5317ade3fd0991e934ad39228..8f7e611168479ed6935ee41aac5b93744a2ea5d6 100644 (file)
@@ -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;
index 2c2a260df982e76d7f5c776feff59dae4f0adda8..435c49cdc42eb75f6f1101e5feaac0fb852714b5 100644 (file)
@@ -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 );
 }
index 305de145a7284beedaa15af3d0d14db6a9ebd151..ce3218c25fa493ceb06f53cba301edae0e9d79f1 100644 (file)
@@ -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;
index 949b7afb5a037beda81f475d45de2ca7806cddef..2e63dc78c0eccebeec52689376f0e8577d90d523 100644 (file)
@@ -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)
 {
index 52edd7a7e276226eb01a5739f35b64c93508929b..66f564d4364e828254ca71c72a8b6725c6cd432d 100644 (file)
@@ -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;