diff options
| author | Brecht Van Lommel <brechtvanlommel@pandora.be> | 2011-02-05 16:41:29 +0300 |
|---|---|---|
| committer | Brecht Van Lommel <brechtvanlommel@pandora.be> | 2011-02-05 16:41:29 +0300 |
| commit | 04299657a7eaee212b983b27bed6b66793f7a985 (patch) | |
| tree | 02dc6e965d8ef08135234da893a85ece7ef7ac2c /source/blender/render/intern/raytrace | |
| parent | 90cf78eb5409a77c912b90fb812a4391e31897ae (diff) | |
Raytrace modifications from the Render Branch.
These should not have any effect on render results, except in some cases with
you have overlapping faces, where the noise seems to be slightly reduced.
There are some performance improvements, for simple scenes I wouldn't expect
more than 5-10% to be cut off the render time, for sintel scenes we got about
50% on average, that's with millions of polygons on intel quad cores. This
because memory access / cache misses were the main bottleneck for those scenes,
and the optimizations improve that.
Interal changes:
* Remove RE_raytrace.h, raytracer is now only used by render engine again.
* Split non-public parts rayobject.h into rayobject_internal.h, hopefully
makes it clearer how the API is used.
* Added rayintersection.h to contain some of the stuff from RE_raytrace.h
* Change Isect.vec/labda to Isect.dir/dist, previously vec was sometimes
normalized and sometimes not, confusing... now dir is always normalized
and dist contains the distance.
* Change VECCOPY and similar to BLI_math functions.
* Force inlining of auxiliary functions for ray-triangle/quad intersection,
helps a few percentages.
* Reorganize svbvh code so all the traversal functions are in one file
* Don't do test for root so that push_childs can be inlined
* Make shadow a template parameter so it doesn't need to be runtime checked
* Optimization in raytree building, was computing bounding boxes more often
than necessary.
* Leave out logf() factor in SAH, makes tree build quicker with no
noticeable influence on raytracing on performance?
* Set max childs to 4, simplifies traversal code a bit, but also seems
to help slightly in general.
* Store child pointers and child bb just as fixed arrays of size 4 in nodes,
nearly all nodes have this many children, so overall it actually reduces
memory usage a bit and avoids a pointer indirection.
Diffstat (limited to 'source/blender/render/intern/raytrace')
16 files changed, 2291 insertions, 459 deletions
diff --git a/source/blender/render/intern/raytrace/bvh.h b/source/blender/render/intern/raytrace/bvh.h index c31d1213b99..dd23967297a 100644 --- a/source/blender/render/intern/raytrace/bvh.h +++ b/source/blender/render/intern/raytrace/bvh.h @@ -26,12 +26,16 @@ * * ***** END GPL LICENSE BLOCK ***** */ -#include "rayobject.h" + +#include "MEM_guardedalloc.h" + +#include "BLI_math.h" + #include "raycounter.h" -#include "rayobject_rtbuild.h" +#include "rayintersection.h" +#include "rayobject.h" #include "rayobject_hint.h" - -#include "BLI_utildefines.h" +#include "rayobject_rtbuild.h" #include <assert.h> @@ -45,21 +49,49 @@ #ifdef __SSE__ inline int test_bb_group4(__m128 *bb_group, const Isect *isec) { - const __m128 tmin0 = _mm_setzero_ps(); - const __m128 tmax0 = _mm_load1_ps(&isec->labda); - - const __m128 tmin1 = _mm_max_ps(tmin0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[0]], _mm_load1_ps(&isec->start[0]) ), _mm_load1_ps(&isec->idot_axis[0])) ); - const __m128 tmax1 = _mm_min_ps(tmax0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[1]], _mm_load1_ps(&isec->start[0]) ), _mm_load1_ps(&isec->idot_axis[0])) ); - const __m128 tmin2 = _mm_max_ps(tmin1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[2]], _mm_load1_ps(&isec->start[1]) ), _mm_load1_ps(&isec->idot_axis[1])) ); - const __m128 tmax2 = _mm_min_ps(tmax1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[3]], _mm_load1_ps(&isec->start[1]) ), _mm_load1_ps(&isec->idot_axis[1])) ); - const __m128 tmin3 = _mm_max_ps(tmin2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[4]], _mm_load1_ps(&isec->start[2]) ), _mm_load1_ps(&isec->idot_axis[2])) ); - const __m128 tmax3 = _mm_min_ps(tmax2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[5]], _mm_load1_ps(&isec->start[2]) ), _mm_load1_ps(&isec->idot_axis[2])) ); + const __m128 tmax0 = _mm_set_ps1(isec->dist); + + float start[3], idot_axis[3]; + copy_v3_v3(start, isec->start); + copy_v3_v3(idot_axis, isec->idot_axis); + + const __m128 tmin1 = _mm_max_ps(tmin0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[0]], _mm_set_ps1(start[0]) ), _mm_set_ps1(idot_axis[0])) ); + const __m128 tmax1 = _mm_min_ps(tmax0, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[1]], _mm_set_ps1(start[0]) ), _mm_set_ps1(idot_axis[0])) ); + const __m128 tmin2 = _mm_max_ps(tmin1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[2]], _mm_set_ps1(start[1]) ), _mm_set_ps1(idot_axis[1])) ); + const __m128 tmax2 = _mm_min_ps(tmax1, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[3]], _mm_set_ps1(start[1]) ), _mm_set_ps1(idot_axis[1])) ); + const __m128 tmin3 = _mm_max_ps(tmin2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[4]], _mm_set_ps1(start[2]) ), _mm_set_ps1(idot_axis[2])) ); + const __m128 tmax3 = _mm_min_ps(tmax2, _mm_mul_ps( _mm_sub_ps( bb_group[isec->bv_index[5]], _mm_set_ps1(start[2]) ), _mm_set_ps1(idot_axis[2])) ); return _mm_movemask_ps(_mm_cmpge_ps(tmax3, tmin3)); } #endif +/* + * 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] + */ +static int rayobject_bb_intersect_test(const Isect *isec, const float *_bb) +{ + const float *bb = _bb; + + 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]; + + RE_RC_COUNT(isec->raycounter->bb.test); + + if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return 0; + if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return 0; + if(t1x > isec->dist || t1y > isec->dist || t1z > isec->dist) return 0; + RE_RC_COUNT(isec->raycounter->bb.hit); + + return 1; +} /* bvh tree generics */ template<class Tree> static int bvh_intersect(Tree *obj, Isect *isec); @@ -108,7 +140,7 @@ static float bvh_cost(Tree *obj) /* bvh tree nodes generics */ template<class Node> static inline int bvh_node_hit_test(Node *node, Isect *isec) { - return RE_rayobject_bb_intersect_test(isec, (const float*)node->bb); + return rayobject_bb_intersect_test(isec, (const float*)node->bb); } @@ -133,7 +165,7 @@ static inline 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,bool TEST_ROOT> +template<class Node,int MAX_STACK_SIZE,bool TEST_ROOT,bool SHADOW> static int bvh_node_stack_raycast(Node *root, Isect *isec) { Node *stack[MAX_STACK_SIZE]; @@ -158,7 +190,7 @@ static int bvh_node_stack_raycast(Node *root, Isect *isec) else { hit |= RE_rayobject_intersect( (RayObject*)node, isec); - if(hit && isec->mode == RE_RAY_SHADOW) return hit; + if(SHADOW && hit) return hit; } } return hit; diff --git a/source/blender/render/intern/raytrace/rayobject.cpp b/source/blender/render/intern/raytrace/rayobject.cpp index c267b89fc2c..dd4932f0bd9 100644 --- a/source/blender/render/intern/raytrace/rayobject.cpp +++ b/source/blender/render/intern/raytrace/rayobject.cpp @@ -22,135 +22,90 @@ * * The Original Code is: all of this file. * - * Contributor(s): Andr Pinto. + * Contributor(s): André Pinto. * * ***** END GPL LICENSE BLOCK ***** */ + #include <assert.h> +#include "MEM_guardedalloc.h" + #include "BLI_math.h" #include "BLI_utildefines.h" - - #include "DNA_material_types.h" -#include "RE_raytrace.h" - -#include "render_types.h" +#include "rayintersection.h" #include "rayobject.h" #include "raycounter.h" +#include "render_types.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] - */ -int RE_rayobject_bb_intersect_test(const Isect *isec, const float *_bb) -{ - const float *bb = _bb; - - 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]; - - RE_RC_COUNT(isec->raycounter->bb.test); - - if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return 0; - if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return 0; - if(t1x > isec->labda || t1y > isec->labda || t1z > isec->labda) return 0; - RE_RC_COUNT(isec->raycounter->bb.hit); - - return 1; -} +/* RayFace + note we force always inline here, because compiler refuses to otherwise + because function is too long. Since this is code that is called billions + of times we really do want to inline. */ -/* 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) +MALWAYS_INLINE RayObject* rayface_from_coords(RayFace *rayface, void *ob, void *face, float *v1, float *v2, float *v3, float *v4) { - float co1[3], co2[3], co3[3], co4[3]; - float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22; - float m0, m1, m2, divdet, det, det1; - float u1, v, u2; + rayface->ob = ob; + rayface->face = face; + + copy_v3_v3(rayface->v1, v1); + copy_v3_v3(rayface->v2, v2); + copy_v3_v3(rayface->v3, v3); - VECCOPY(co1, face->v1->co); - VECCOPY(co2, face->v2->co); - if(face->v4) + if(v4) { - VECCOPY(co3, face->v4->co); - VECCOPY(co4, face->v3->co); + copy_v3_v3(rayface->v4, v4); + rayface->quad = 1; } else { - VECCOPY(co3, face->v3->co); + rayface->quad = 0; } - t00= co3[0]-co1[0]; - t01= co3[1]-co1[1]; - t02= co3[2]-co1[2]; - t10= co3[0]-co2[0]; - t11= co3[1]-co2[1]; - t12= co3[2]-co2[2]; - - x0= t11*r2-t12*r1; - x1= t12*r0-t10*r2; - x2= t10*r1-t11*r0; - - divdet= t00*x0+t01*x1+t02*x2; + return RE_rayobject_unalignRayFace(rayface); +} - m0= rx1-co3[0]; - m1= ry1-co3[1]; - m2= rz1-co3[2]; - det1= m0*x0+m1*x1+m2*x2; - - if(divdet!=0.0f) { - u1= det1/divdet; +MALWAYS_INLINE void rayface_from_vlak(RayFace *rayface, ObjectInstanceRen *obi, VlakRen *vlr) +{ + rayface_from_coords(rayface, obi, vlr, vlr->v1->co, vlr->v2->co, vlr->v3->co, vlr->v4 ? vlr->v4->co : 0); - if(u1<ISECT_EPSILON) { - det= t00*(m1*r2-m2*r1); - det+= t01*(m2*r0-m0*r2); - det+= t02*(m0*r1-m1*r0); - v= det/divdet; + if(obi->transform_primitives) + { + mul_m4_v3(obi->mat, rayface->v1); + mul_m4_v3(obi->mat, rayface->v2); + mul_m4_v3(obi->mat, rayface->v3); - if(v<ISECT_EPSILON && (u1 + v) > -(1.0f+ISECT_EPSILON)) { - return 1; - } - } + if(RE_rayface_isQuad(rayface)) + mul_m4_v3(obi->mat, rayface->v4); } +} - if(face->v4) { +RayObject* RE_rayface_from_vlak(RayFace *rayface, ObjectInstanceRen *obi, VlakRen *vlr) +{ + return rayface_from_coords(rayface, obi, vlr, vlr->v1->co, vlr->v2->co, vlr->v3->co, vlr->v4 ? vlr->v4->co : 0); +} - t20= co3[0]-co4[0]; - t21= co3[1]-co4[1]; - t22= co3[2]-co4[2]; +/* VlakPrimitive */ - divdet= t20*x0+t21*x1+t22*x2; - if(divdet!=0.0f) { - u2= det1/divdet; - - if(u2<ISECT_EPSILON) { - det= t20*(m1*r2-m2*r1); - det+= t21*(m2*r0-m0*r2); - det+= t22*(m0*r1-m1*r0); - v= det/divdet; - - if(v<ISECT_EPSILON && (u2 + v) >= -(1.0f+ISECT_EPSILON)) { - return 2; - } - } - } - } - return 0; +RayObject* RE_vlakprimitive_from_vlak(VlakPrimitive *face, struct ObjectInstanceRen *obi, struct VlakRen *vlr) +{ + face->ob = obi; + face->face = vlr; + + return RE_rayobject_unalignVlakPrimitive(face); } -static inline int vlr_check_intersect(Isect *is, ObjectInstanceRen *obi, VlakRen *vlr) +/* Checks for ignoring faces or materials */ + +MALWAYS_INLINE int vlr_check_intersect(Isect *is, ObjectInstanceRen *obi, VlakRen *vlr) { /* for baking selected to active non-traceable materials might still * be in the raytree */ - if(!(vlr->mat->mode & MA_TRACEBLE)) + if(!(vlr->flag & R_TRACEBLE)) return 0; /* I know... cpu cycle waste, might do smarter once */ @@ -160,7 +115,7 @@ static inline int vlr_check_intersect(Isect *is, ObjectInstanceRen *obi, VlakRen return (is->lay & obi->lay); } -static inline int vlr_check_intersect_solid(Isect *is, ObjectInstanceRen* obi, VlakRen *vlr) +MALWAYS_INLINE int vlr_check_intersect_solid(Isect *is, ObjectInstanceRen* obi, VlakRen *vlr) { /* solid material types only */ if (vlr->mat->material_type == MA_TYPE_SURFACE) @@ -169,168 +124,223 @@ static inline int vlr_check_intersect_solid(Isect *is, ObjectInstanceRen* obi, V return 0; } -static inline int vlr_check_bake(Isect *is, ObjectInstanceRen* obi, VlakRen *vlr) +MALWAYS_INLINE int vlr_check_bake(Isect *is, ObjectInstanceRen* obi, VlakRen *vlr) { return (obi->obr->ob != is->userdata); } -static inline int rayface_check_cullface(RayFace *face, Isect *is) -{ - float nor[3]; - - /* don't intersect if the ray faces along the face normal */ - if(face->quad) normal_quad_v3( nor,face->v1, face->v2, face->v3, face->v4); - else normal_tri_v3( nor,face->v1, face->v2, face->v3); - - return (INPR(nor, is->vec) < 0); -} +/* Ray Triangle/Quad Intersection */ -/* ray - triangle or quad intersection */ -/* this function shall only modify Isect if it detects an hit */ -static int intersect_rayface(RayObject *hit_obj, RayFace *face, Isect *is) +MALWAYS_INLINE int isec_tri_quad(float start[3], float dir[3], RayFace *face, float uv[2], float *lambda) { - float co1[3],co2[3],co3[3],co4[3]={0}; - float x0,x1,x2,t00,t01,t02,t10,t11,t12,t20,t21,t22,r0,r1,r2; - float m0, m1, m2, divdet, det1; - float labda, u, v; - short ok=0; - - if(is->orig.ob == face->ob && is->orig.face == face->face) - return 0; - - /* check if we should intersect this face */ - if(is->check == RE_CHECK_VLR_RENDER) - { - if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face ) == 0) - return 0; - } - else if(is->check == RE_CHECK_VLR_NON_SOLID_MATERIAL) - { - if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face ) == 0) - return 0; - if(vlr_check_intersect_solid(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0) - return 0; - } - else if(is->check == RE_CHECK_VLR_BAKE) { - if(vlr_check_bake(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face ) == 0) - return 0; - } + float co1[3], co2[3], co3[3], co4[3]; + float t0[3], t1[3], x[3], r[3], m[3], u, v, divdet, det1, l; + int quad; - if(is->skip & RE_SKIP_CULLFACE) - { - if(rayface_check_cullface(face, is) == 0) - return 0; - } + quad= RE_rayface_isQuad(face); - RE_RC_COUNT(is->raycounter->faces.test); + copy_v3_v3(co1, face->v1); + copy_v3_v3(co2, face->v2); + copy_v3_v3(co3, face->v3); - //Load coords - VECCOPY(co1, face->v1); - VECCOPY(co2, face->v2); - if(RE_rayface_isQuad(face)) - { - VECCOPY(co3, face->v4); - VECCOPY(co4, face->v3); - } - else - { - VECCOPY(co3, face->v3); - } + copy_v3_v3(r, dir); - t00= co3[0]-co1[0]; - t01= co3[1]-co1[1]; - t02= co3[2]-co1[2]; - t10= co3[0]-co2[0]; - t11= co3[1]-co2[1]; - t12= co3[2]-co2[2]; - - r0= is->vec[0]; - r1= is->vec[1]; - r2= is->vec[2]; - - x0= t12*r1-t11*r2; - x1= t10*r2-t12*r0; - x2= t11*r0-t10*r1; + /* intersect triangle */ + sub_v3_v3v3(t0, co3, co2); + sub_v3_v3v3(t1, co3, co1); - divdet= t00*x0+t01*x1+t02*x2; + cross_v3_v3v3(x, r, t1); + divdet= dot_v3v3(t0, x); - m0= is->start[0]-co3[0]; - m1= is->start[1]-co3[1]; - m2= is->start[2]-co3[2]; - det1= m0*x0+m1*x1+m2*x2; + sub_v3_v3v3(m, start, co3); + det1= dot_v3v3(m, x); - if(divdet!=0.0f) { - + if(divdet != 0.0f) { divdet= 1.0f/divdet; - u= det1*divdet; - if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) { - float cros0, cros1, cros2; - - cros0= m1*t02-m2*t01; - cros1= m2*t00-m0*t02; - cros2= m0*t01-m1*t00; - v= divdet*(cros0*r0 + cros1*r1 + cros2*r2); + v= det1*divdet; - if(v<ISECT_EPSILON && (u + v) > -(1.0f+ISECT_EPSILON)) { - labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12); + if(v < RE_RAYTRACE_EPSILON && v > -(1.0f+RE_RAYTRACE_EPSILON)) { + float cros[3]; - if(labda>-ISECT_EPSILON && labda<is->labda) { - ok= 1; + cross_v3_v3v3(cros, m, t0); + u= divdet*dot_v3v3(cros, r); + + if(u < RE_RAYTRACE_EPSILON && (v + u) > -(1.0f+RE_RAYTRACE_EPSILON)) { + l= divdet*dot_v3v3(cros, t1); + + /* check if intersection is within ray length */ + if(l > -RE_RAYTRACE_EPSILON && l < *lambda) { + uv[0]= u; + uv[1]= v; + *lambda= l; + return 1; } } } } - if(ok==0 && RE_rayface_isQuad(face)) { - - t20= co3[0]-co4[0]; - t21= co3[1]-co4[1]; - t22= co3[2]-co4[2]; + /* intersect second triangle in quad */ + if(quad) { + copy_v3_v3(co4, face->v4); + sub_v3_v3v3(t0, co3, co4); + divdet= dot_v3v3(t0, x); - divdet= t20*x0+t21*x1+t22*x2; - if(divdet!=0.0f) { + if(divdet != 0.0f) { divdet= 1.0f/divdet; - u = det1*divdet; + v = det1*divdet; - if(u<ISECT_EPSILON && u>-(1.0f+ISECT_EPSILON)) { - float cros0, cros1, cros2; - cros0= m1*t22-m2*t21; - cros1= m2*t20-m0*t22; - cros2= m0*t21-m1*t20; - v= divdet*(cros0*r0 + cros1*r1 + cros2*r2); + if(v < RE_RAYTRACE_EPSILON && v > -(1.0f+RE_RAYTRACE_EPSILON)) { + float cros[3]; + + cross_v3_v3v3(cros, m, t0); + u= divdet*dot_v3v3(cros, r); - if(v<ISECT_EPSILON && (u + v) >-(1.0f+ISECT_EPSILON)) { - labda= divdet*(cros0*t10 + cros1*t11 + cros2*t12); + if(u < RE_RAYTRACE_EPSILON && (v + u) > -(1.0f+RE_RAYTRACE_EPSILON)) { + l= divdet*dot_v3v3(cros, t1); - if(labda>-ISECT_EPSILON && labda<is->labda) { - ok= 2; + if(l >- RE_RAYTRACE_EPSILON && l < *lambda) { + uv[0]= u; + uv[1]= -(1.0f + v + u); + *lambda= l; + return 2; } } } } } + return 0; +} + +/* Simpler yes/no Ray Triangle/Quad Intersection */ + +MALWAYS_INLINE int isec_tri_quad_neighbour(float start[3], float dir[3], RayFace *face) +{ + float co1[3], co2[3], co3[3], co4[3]; + float t0[3], t1[3], x[3], r[3], m[3], u, v, divdet, det1; + int quad; + + quad= RE_rayface_isQuad(face); + + copy_v3_v3(co1, face->v1); + copy_v3_v3(co2, face->v2); + copy_v3_v3(co3, face->v3); + + negate_v3_v3(r, dir); /* note, different than above function */ + + /* intersect triangle */ + sub_v3_v3v3(t0, co3, co2); + sub_v3_v3v3(t1, co3, co1); + + cross_v3_v3v3(x, r, t1); + divdet= dot_v3v3(t0, x); + + sub_v3_v3v3(m, start, co3); + det1= dot_v3v3(m, x); + + if(divdet != 0.0f) { + divdet= 1.0f/divdet; + v= det1*divdet; + + if(v < RE_RAYTRACE_EPSILON && v > -(1.0f+RE_RAYTRACE_EPSILON)) { + float cros[3]; + + cross_v3_v3v3(cros, m, t0); + u= divdet*dot_v3v3(cros, r); + + if(u < RE_RAYTRACE_EPSILON && (v + u) > -(1.0f+RE_RAYTRACE_EPSILON)) + return 1; + } + } + + /* intersect second triangle in quad */ + if(quad) { + copy_v3_v3(co4, face->v4); + sub_v3_v3v3(t0, co3, co4); + divdet= dot_v3v3(t0, x); + + if(divdet != 0.0f) { + divdet= 1.0f/divdet; + v = det1*divdet; + + if(v < RE_RAYTRACE_EPSILON && v > -(1.0f+RE_RAYTRACE_EPSILON)) { + float cros[3]; + + cross_v3_v3v3(cros, m, t0); + u= divdet*dot_v3v3(cros, r); + + if(u < RE_RAYTRACE_EPSILON && (v + u) > -(1.0f+RE_RAYTRACE_EPSILON)) + return 2; + } + } + } + + return 0; +} + +/* RayFace intersection with checks and neighbour verifaction included, + Isect is modified if the face is hit. */ + +MALWAYS_INLINE int intersect_rayface(RayObject *hit_obj, RayFace *face, Isect *is) +{ + float dist, uv[2]; + int ok= 0; + + /* avoid self-intersection */ + if(is->orig.ob == face->ob && is->orig.face == face->face) + return 0; + + /* check if we should intersect this face */ + if(is->check == RE_CHECK_VLR_RENDER) + { + if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0) + return 0; + } + else if(is->check == RE_CHECK_VLR_NON_SOLID_MATERIAL) + { + if(vlr_check_intersect(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0) + return 0; + if(vlr_check_intersect_solid(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0) + return 0; + } + else if(is->check == RE_CHECK_VLR_BAKE) { + if(vlr_check_bake(is, (ObjectInstanceRen*)face->ob, (VlakRen*)face->face) == 0) + return 0; + } + + /* ray counter */ + RE_RC_COUNT(is->raycounter->faces.test); + + dist= is->dist; + ok= isec_tri_quad(is->start, is->dir, face, uv, &dist); + if(ok) { - /* when a shadow ray leaves a face, it can be little outside the edges of it, causing - intersection to be detected in its neighbour face */ + /* when a shadow ray leaves a face, it can be little outside the edges + of it, causing intersection to be detected in its neighbour face */ if(is->skip & RE_SKIP_VLR_NEIGHBOUR) { - if(labda < 0.1f && is->orig.ob == face->ob) + if(dist < 0.1f && is->orig.ob == face->ob) { VlakRen * a = (VlakRen*)is->orig.face; VlakRen * b = (VlakRen*)face->face; - /* so there's a shared edge or vertex, let's intersect ray with face - itself, if that's true we can safely return 1, otherwise we assume - the intersection is invalid, 0 */ + /* so there's a shared edge or vertex, let's intersect ray with + face itself, if that's true we can safely return 1, otherwise + we assume the intersection is invalid, 0 */ if(a->v1==b->v1 || a->v2==b->v1 || a->v3==b->v1 || a->v4==b->v1 || a->v1==b->v2 || a->v2==b->v2 || a->v3==b->v2 || a->v4==b->v2 || a->v1==b->v3 || a->v2==b->v3 || a->v3==b->v3 || a->v4==b->v3 - || (b->v4 && (a->v1==b->v4 || a->v2==b->v4 || a->v3==b->v4 || a->v4==b->v4))) - if(!intersection2((VlakRen*)a, -r0, -r1, -r2, is->start[0], is->start[1], is->start[2])) - { - return 0; + || (b->v4 && (a->v1==b->v4 || a->v2==b->v4 || a->v3==b->v4 || a->v4==b->v4))) { + /* create RayFace from original face, transformed if necessary */ + RayFace origface; + ObjectInstanceRen *ob= (ObjectInstanceRen*)is->orig.ob; + rayface_from_vlak(&origface, ob, (VlakRen*)is->orig.face); + + if(!isec_tri_quad_neighbour(is->start, is->dir, &origface)) + { + return 0; + } } } } @@ -338,8 +348,8 @@ static int intersect_rayface(RayObject *hit_obj, RayFace *face, Isect *is) RE_RC_COUNT(is->raycounter->faces.hit); is->isect= ok; // which half of the quad - is->labda= labda; - is->u= u; is->v= v; + is->dist= dist; + is->u= uv[0]; is->v= uv[1]; is->hit.ob = face->ob; is->hit.face = face->face; @@ -352,51 +362,18 @@ static int intersect_rayface(RayObject *hit_obj, RayFace *face, Isect *is) return 0; } -RayObject* RE_rayface_from_vlak(RayFace *rayface, ObjectInstanceRen *obi, VlakRen *vlr) -{ - return RE_rayface_from_coords(rayface, obi, vlr, vlr->v1->co, vlr->v2->co, vlr->v3->co, vlr->v4 ? vlr->v4->co : 0 ); -} - -RayObject* RE_rayface_from_coords(RayFace *rayface, void *ob, void *face, float *v1, float *v2, float *v3, float *v4) -{ - rayface->ob = ob; - rayface->face = face; - - VECCOPY(rayface->v1, v1); - VECCOPY(rayface->v2, v2); - VECCOPY(rayface->v3, v3); - if(v4) - { - VECCOPY(rayface->v4, v4); - rayface->quad = 1; - } - else - { - rayface->quad = 0; - } - - return RE_rayobject_unalignRayFace(rayface); -} - -RayObject* RE_vlakprimitive_from_vlak(VlakPrimitive *face, struct ObjectInstanceRen *obi, struct VlakRen *vlr) -{ - face->ob = obi; - face->face = vlr; - return RE_rayobject_unalignVlakPrimitive(face); -} - +/* Intersection */ int RE_rayobject_raycast(RayObject *r, Isect *isec) { int i; + RE_RC_COUNT(isec->raycounter->raycast.test); - /* Setup vars used on raycast */ - isec->dist = len_v3(isec->vec); - + /* setup vars used on raycast */ for(i=0; i<3; i++) { - isec->idot_axis[i] = 1.0f / isec->vec[i]; + isec->idot_axis[i] = 1.0f / isec->dir[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]; @@ -406,7 +383,7 @@ int RE_rayobject_raycast(RayObject *r, Isect *isec) } #ifdef RT_USE_LAST_HIT - /* Last hit heuristic */ + /* last hit heuristic */ if(isec->mode==RE_RAY_SHADOW && isec->last_hit) { RE_RC_COUNT(isec->raycounter->rayshadow_last_hit.test); @@ -433,6 +410,7 @@ int RE_rayobject_raycast(RayObject *r, Isect *isec) #endif return 1; } + return 0; } @@ -447,103 +425,93 @@ int RE_rayobject_intersect(RayObject *r, Isect *i) //TODO optimize (useless copy to RayFace to avoid duplicate code) VlakPrimitive *face = (VlakPrimitive*) RE_rayobject_align(r); RayFace nface; - RE_rayface_from_vlak(&nface, face->ob, face->face); - - if(face->ob->transform_primitives) - { - mul_m4_v3(face->ob->mat, nface.v1); - mul_m4_v3(face->ob->mat, nface.v2); - mul_m4_v3(face->ob->mat, nface.v3); - if(RE_rayface_isQuad(&nface)) - mul_m4_v3(face->ob->mat, nface.v4); - } + rayface_from_vlak(&nface, face->ob, face->face); return intersect_rayface(r, &nface, i); } else if(RE_rayobject_isRayAPI(r)) { - r = RE_rayobject_align( r ); - return r->api->raycast( r, i ); + r = RE_rayobject_align(r); + return r->api->raycast(r, i); + } + else { + assert(0); + return 0; } - else assert(0); - return 0; /* wont reach this, quiet compilers */ } +/* Building */ + void RE_rayobject_add(RayObject *r, RayObject *o) { - r = RE_rayobject_align( r ); - return r->api->add( r, o ); + r = RE_rayobject_align(r); + return r->api->add(r, o); } void RE_rayobject_done(RayObject *r) { - r = RE_rayobject_align( r ); - r->api->done( r ); + r = RE_rayobject_align(r); + r->api->done(r); } void RE_rayobject_free(RayObject *r) { - r = RE_rayobject_align( r ); - r->api->free( r ); + r = RE_rayobject_align(r); + r->api->free(r); } +float RE_rayobject_cost(RayObject *r) +{ + if(RE_rayobject_isRayFace(r) || RE_rayobject_isVlakPrimitive(r)) + { + return 1.0f; + } + else if(RE_rayobject_isRayAPI(r)) + { + r = RE_rayobject_align(r); + return r->api->cost(r); + } + else { + assert(0); + return 1.0f; + } +} + +/* Bounding Boxes */ + void RE_rayobject_merge_bb(RayObject *r, float *min, float *max) { if(RE_rayobject_isRayFace(r)) { RayFace *face = (RayFace*) RE_rayobject_align(r); - DO_MINMAX( face->v1, min, max ); - DO_MINMAX( face->v2, min, max ); - DO_MINMAX( face->v3, min, max ); - if(RE_rayface_isQuad(face)) DO_MINMAX( face->v4, min, max ); + DO_MINMAX(face->v1, min, max); + DO_MINMAX(face->v2, min, max); + DO_MINMAX(face->v3, min, max); + if(RE_rayface_isQuad(face)) DO_MINMAX(face->v4, min, max); } else if(RE_rayobject_isVlakPrimitive(r)) { VlakPrimitive *face = (VlakPrimitive*) RE_rayobject_align(r); RayFace nface; - RE_rayface_from_vlak(&nface, face->ob, face->face); - - if(face->ob->transform_primitives) - { - mul_m4_v3(face->ob->mat, nface.v1); - mul_m4_v3(face->ob->mat, nface.v2); - mul_m4_v3(face->ob->mat, nface.v3); - if(RE_rayface_isQuad(&nface)) - mul_m4_v3(face->ob->mat, nface.v4); - } - - DO_MINMAX( nface.v1, min, max ); - DO_MINMAX( nface.v2, min, max ); - DO_MINMAX( nface.v3, min, max ); - if(RE_rayface_isQuad(&nface)) DO_MINMAX( nface.v4, min, max ); - } - else if(RE_rayobject_isRayAPI(r)) - { - r = RE_rayobject_align( r ); - r->api->bb( r, min, max ); - } - else assert(0); -} + rayface_from_vlak(&nface, face->ob, face->face); -float RE_rayobject_cost(RayObject *r) -{ - if(RE_rayobject_isRayFace(r) || RE_rayobject_isVlakPrimitive(r)) - { - return 1.0; + DO_MINMAX(nface.v1, min, max); + DO_MINMAX(nface.v2, min, max); + DO_MINMAX(nface.v3, min, max); + if(RE_rayface_isQuad(&nface)) DO_MINMAX(nface.v4, min, max); } else if(RE_rayobject_isRayAPI(r)) { - r = RE_rayobject_align( r ); - return r->api->cost( r ); + r = RE_rayobject_align(r); + r->api->bb(r, min, max); } else - { assert(0); - return 1.0; /* XXX, better default value? */ - } } +/* Hints */ + void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max) { if(RE_rayobject_isRayFace(r) || RE_rayobject_isVlakPrimitive(r)) @@ -552,60 +520,30 @@ void RE_rayobject_hint_bb(RayObject *r, RayHint *hint, float *min, float *max) } else if(RE_rayobject_isRayAPI(r)) { - r = RE_rayobject_align( r ); - return r->api->hint_bb( r, hint, min, max ); + r = RE_rayobject_align(r); + return r->api->hint_bb(r, hint, min, max); } - else assert(0); + else + assert(0); } +/* RayObjectControl */ + int RE_rayobjectcontrol_test_break(RayObjectControl *control) { if(control->test_break) - return control->test_break( control->data ); + return control->test_break(control->data); return 0; } - -/* - * Empty raytree - */ -static int RE_rayobject_empty_intersect(RayObject *o, Isect *is) +void RE_rayobject_set_control(RayObject *r, void *data, RE_rayobjectcontrol_test_break_callback test_break) { - return 0; -} - -static void RE_rayobject_empty_free(RayObject *o) -{ -} - -static void RE_rayobject_empty_bb(RayObject *o, float *min, float *max) -{ - return; -} - -static float RE_rayobject_empty_cost(RayObject *o) -{ - return 0.0; + if(RE_rayobject_isRayAPI(r)) + { + r = RE_rayobject_align(r); + r->control.data = data; + r->control.test_break = test_break; + } } -static void RE_rayobject_empty_hint_bb(RayObject *o, RayHint *hint, float *min, float *max) -{} - -static RayObjectAPI empty_api = -{ - RE_rayobject_empty_intersect, - NULL, //static void RE_rayobject_instance_add(RayObject *o, RayObject *ob); - NULL, //static void RE_rayobject_instance_done(RayObject *o); - RE_rayobject_empty_free, - RE_rayobject_empty_bb, - RE_rayobject_empty_cost, - RE_rayobject_empty_hint_bb -}; - -static RayObject empty_raytree = { &empty_api, {0, 0} }; - -RayObject *RE_rayobject_empty_create() -{ - return RE_rayobject_unalignRayAPI( &empty_raytree ); -} diff --git a/source/blender/render/intern/raytrace/rayobject_blibvh.cpp b/source/blender/render/intern/raytrace/rayobject_blibvh.cpp new file mode 100644 index 00000000000..7d59cc2df30 --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_blibvh.cpp @@ -0,0 +1,168 @@ +/** + * $Id: rayobject_blibvh.cpp 29491 2010-06-16 18:57:23Z blendix $ + * + * ***** 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 "BLI_kdopbvh.h" +#include "BLI_math.h" +#include "BLI_utildefines.h" + +#include "rayintersection.h" +#include "rayobject.h" + +static int RE_rayobject_blibvh_intersect(RayObject *o, Isect *isec); +static void RE_rayobject_blibvh_add(RayObject *o, RayObject *ob); +static void RE_rayobject_blibvh_done(RayObject *o); +static void RE_rayobject_blibvh_free(RayObject *o); +static void RE_rayobject_blibvh_bb(RayObject *o, float *min, float *max); + +static float RE_rayobject_blibvh_cost(RayObject *o) +{ + //TODO calculate the expected cost to raycast on this structure + return 1.0; +} + +static void RE_rayobject_blibvh_hint_bb(RayObject *o, RayHint *hint, float *min, float *max) +{ + return; +} + +static RayObjectAPI bvh_api = +{ + RE_rayobject_blibvh_intersect, + RE_rayobject_blibvh_add, + RE_rayobject_blibvh_done, + RE_rayobject_blibvh_free, + RE_rayobject_blibvh_bb, + RE_rayobject_blibvh_cost, + RE_rayobject_blibvh_hint_bb +}; + +typedef struct BVHObject +{ + RayObject rayobj; + RayObject **leafs, **next_leaf; + BVHTree *bvh; + float bb[2][3]; +} BVHObject; + +RayObject *RE_rayobject_blibvh_create(int size) +{ + BVHObject *obj= (BVHObject*)MEM_callocN(sizeof(BVHObject), "BVHObject"); + assert(RE_rayobject_isAligned(obj)); /* RayObject API assumes real data to be 4-byte aligned */ + + obj->rayobj.api = &bvh_api; + obj->bvh = BLI_bvhtree_new(size, 0.0, 4, 6); + obj->next_leaf = obj->leafs = (RayObject**)MEM_callocN(size*sizeof(RayObject*), "BVHObject leafs"); + + INIT_MINMAX(obj->bb[0], obj->bb[1]); + return RE_rayobject_unalignRayAPI((RayObject*) obj); +} + +struct BVHCallbackUserData +{ + Isect *isec; + RayObject **leafs; +}; + +static void bvh_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) +{ + struct BVHCallbackUserData *data = (struct BVHCallbackUserData*)userdata; + Isect *isec = data->isec; + RayObject *face = data->leafs[index]; + + if(RE_rayobject_intersect(face,isec)) + { + hit->index = index; + + if(isec->mode == RE_RAY_SHADOW) + hit->dist = 0; + else + hit->dist = isec->dist; + } +} + +static int RE_rayobject_blibvh_intersect(RayObject *o, Isect *isec) +{ + BVHObject *obj = (BVHObject*)o; + BVHTreeRayHit hit; + float dir[3]; + struct BVHCallbackUserData data; + data.isec = isec; + data.leafs = obj->leafs; + + copy_v3_v3(dir, isec->dir); + + hit.index = 0; + hit.dist = isec->dist; + + return BLI_bvhtree_ray_cast(obj->bvh, isec->start, dir, 0.0, &hit, bvh_callback, (void*)&data); +} + +static void RE_rayobject_blibvh_add(RayObject *o, RayObject *ob) +{ + BVHObject *obj = (BVHObject*)o; + float min_max[6]; + INIT_MINMAX(min_max, min_max+3); + RE_rayobject_merge_bb(ob, min_max, min_max+3); + + DO_MIN(min_max , obj->bb[0]); + DO_MAX(min_max+3, obj->bb[1]); + + BLI_bvhtree_insert(obj->bvh, obj->next_leaf - obj->leafs, min_max, 2); + *(obj->next_leaf++) = ob; +} + +static void RE_rayobject_blibvh_done(RayObject *o) +{ + BVHObject *obj = (BVHObject*)o; + BLI_bvhtree_balance(obj->bvh); +} + +static void RE_rayobject_blibvh_free(RayObject *o) +{ + BVHObject *obj = (BVHObject*)o; + + if(obj->bvh) + BLI_bvhtree_free(obj->bvh); + + if(obj->leafs) + MEM_freeN(obj->leafs); + + MEM_freeN(obj); +} + +static void RE_rayobject_blibvh_bb(RayObject *o, float *min, float *max) +{ + BVHObject *obj = (BVHObject*)o; + DO_MIN(obj->bb[0], min); + DO_MAX(obj->bb[1], max); +} + diff --git a/source/blender/render/intern/raytrace/rayobject_empty.cpp b/source/blender/render/intern/raytrace/rayobject_empty.cpp new file mode 100644 index 00000000000..abd54ab9fab --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_empty.cpp @@ -0,0 +1,75 @@ +/** + * $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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 1990-1998 NeoGeo BV. + * All rights reserved. + * + * Contributors: 2004/2005 Blender Foundation, full recode + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include "MEM_guardedalloc.h" + +#include "rayobject.h" + +/* + * Empty raytree + */ + +static int RE_rayobject_empty_intersect(RayObject *o, Isect *is) +{ + return 0; +} + +static void RE_rayobject_empty_free(RayObject *o) +{ +} + +static void RE_rayobject_empty_bb(RayObject *o, float *min, float *max) +{ + return; +} + +static float RE_rayobject_empty_cost(RayObject *o) +{ + return 0.0; +} + +static void RE_rayobject_empty_hint_bb(RayObject *o, RayHint *hint, float *min, float *max) +{} + +static RayObjectAPI empty_api = +{ + RE_rayobject_empty_intersect, + NULL, //static void RE_rayobject_instance_add(RayObject *o, RayObject *ob); + NULL, //static void RE_rayobject_instance_done(RayObject *o); + RE_rayobject_empty_free, + RE_rayobject_empty_bb, + RE_rayobject_empty_cost, + RE_rayobject_empty_hint_bb +}; + +static RayObject empty_raytree = { &empty_api, {0, 0} }; + +RayObject *RE_rayobject_empty_create() +{ + return RE_rayobject_unalignRayAPI( &empty_raytree ); +} + diff --git a/source/blender/render/intern/raytrace/rayobject_hint.h b/source/blender/render/intern/raytrace/rayobject_hint.h index 1ea59d00bac..adb7d652276 100644 --- a/source/blender/render/intern/raytrace/rayobject_hint.h +++ b/source/blender/render/intern/raytrace/rayobject_hint.h @@ -26,6 +26,7 @@ * * ***** END GPL LICENSE BLOCK ***** */ + #ifndef RE_RAYTRACE_RAYOBJECT_HINT_H #define RE_RAYTRACE_RAYOBJECT_HINT_H @@ -68,3 +69,4 @@ inline int hint_test_bb(HintFrustum &obj, float *Nmin, float *Nmax) */ #endif + diff --git a/source/blender/render/intern/raytrace/rayobject_instance.cpp b/source/blender/render/intern/raytrace/rayobject_instance.cpp new file mode 100644 index 00000000000..c0adae71c1f --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_instance.cpp @@ -0,0 +1,208 @@ +/** + * $Id: rayobject_instance.cpp 29542 2010-06-18 09:45:46Z blendix $ + * + * ***** 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 "BLI_math.h" +#include "BLI_utildefines.h" + +#include "rayintersection.h" +#include "rayobject.h" + +#define RE_COST_INSTANCE (1.0f) + +static int RE_rayobject_instance_intersect(RayObject *o, Isect *isec); +static void RE_rayobject_instance_free(RayObject *o); +static void RE_rayobject_instance_bb(RayObject *o, float *min, float *max); +static float RE_rayobject_instance_cost(RayObject *o); + +static void RE_rayobject_instance_hint_bb(RayObject *o, RayHint *hint, float *min, float *max) +{} + +static RayObjectAPI instance_api = +{ + RE_rayobject_instance_intersect, + NULL, //static void RE_rayobject_instance_add(RayObject *o, RayObject *ob); + NULL, //static void RE_rayobject_instance_done(RayObject *o); + RE_rayobject_instance_free, + RE_rayobject_instance_bb, + RE_rayobject_instance_cost, + RE_rayobject_instance_hint_bb +}; + +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], void *ob, void *target_ob) +{ + InstanceRayObject *obj= (InstanceRayObject*)MEM_callocN(sizeof(InstanceRayObject), "InstanceRayObject"); + assert( RE_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; + + copy_m4_m4(obj->target2global, transform); + invert_m4_m4(obj->global2target, obj->target2global); + + return RE_rayobject_unalignRayAPI((RayObject*) obj); +} + +static int RE_rayobject_instance_intersect(RayObject *o, Isect *isec) +{ + InstanceRayObject *obj = (InstanceRayObject*)o; + float start[3], dir[3], idot_axis[3], dist; + int changed = 0, i, res; + + // TODO - this is disabling self intersection on instances + if(isec->orig.ob == obj->ob && obj->ob) + { + changed = 1; + isec->orig.ob = obj->target_ob; + } + + // backup old values + copy_v3_v3(start, isec->start); + copy_v3_v3(dir, isec->dir); + copy_v3_v3(idot_axis, isec->idot_axis); + dist = isec->dist; + + // transform to target coordinates system + mul_m4_v3(obj->global2target, isec->start); + mul_mat3_m4_v3(obj->global2target, isec->dir); + isec->dist *= normalize_v3(isec->dir); + + // update idot_axis and bv_index + for(i=0; i<3; i++) + { + isec->idot_axis[i] = 1.0f / isec->dir[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]; + } + + // raycast + res = RE_rayobject_intersect(obj->target, isec); + + // map dist into original coordinate space + if(res == 0) + { + isec->dist = dist; + } + else + { + // note we don't just multiply dist, because of possible + // non-uniform scaling in the transform matrix + float vec[3]; + + mul_v3_v3fl(vec, isec->dir, isec->dist); + mul_mat3_m4_v3(obj->target2global, vec); + + isec->dist = len_v3(vec); + isec->hit.ob = obj->ob; + +#ifdef RT_USE_LAST_HIT + // TODO support for last hit optimization in instances that can jump + // directly to the last hit face. + // For now it jumps directly to the last-hit instance root node. + isec->last_hit = RE_rayobject_unalignRayAPI((RayObject*) obj); +#endif + } + + // restore values + copy_v3_v3(isec->start, start); + copy_v3_v3(isec->dir, dir); + copy_v3_v3(isec->idot_axis, idot_axis); + + if(changed) + isec->orig.ob = obj->ob; + + // restore bv_index + for(i=0; i<3; 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]; + } + + return res; +} + +static void RE_rayobject_instance_free(RayObject *o) +{ + InstanceRayObject *obj = (InstanceRayObject*)o; + MEM_freeN(obj); +} + +static float RE_rayobject_instance_cost(RayObject *o) +{ + InstanceRayObject *obj = (InstanceRayObject*)o; + return RE_rayobject_cost(obj->target) + RE_COST_INSTANCE; +} + +static void RE_rayobject_instance_bb(RayObject *o, float *min, float *max) +{ + //TODO: + // *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], t[3]; + int i, j; + INIT_MINMAX(m, M); + RE_rayobject_merge_bb(obj->target, m, M); + + //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]; + mul_m4_v3(obj->target2global, t); + DO_MINMAX(t, min, max); + } +} + diff --git a/source/blender/render/intern/raytrace/rayobject_internal.h b/source/blender/render/intern/raytrace/rayobject_internal.h new file mode 100644 index 00000000000..6067be07c50 --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_internal.h @@ -0,0 +1,128 @@ + +#ifndef RE_RAYOBJECT_INTERNAL_H +#define RE_RAYOBJECT_INTERNAL_H + +#ifdef __cplusplus +extern "C" { +#endif + +/* RayObjectControl + * + * This class is intended as a place holder for control, configuration of the + * rayobject like: + * - stop building (TODO maybe when porting build to threads this could be + * implemented with some thread_cancel function) + * - max number of threads and threads callback to use during build + * ... + */ + +typedef int (*RE_rayobjectcontrol_test_break_callback)(void *data); + +typedef struct RayObjectControl { + void *data; + RE_rayobjectcontrol_test_break_callback test_break; +} RayObjectControl; + +/* Returns true if for some reason a heavy processing function should stop + * (eg.: user asked to stop during a tree a build) + */ + +int RE_rayobjectcontrol_test_break(RayObjectControl *c); + +/* RayObject + + A ray object is everything where we can cast rays like: + * a face/triangle + * an octree + * a bvh tree + * an octree of bvh's + * a bvh of bvh's + + + All types of RayObjects can be created by implementing the + callbacks of the RayObject. + + Due to high computing time evolved with casting on faces + there is a special type of RayObject (named RayFace) + which won't use callbacks like other generic nodes. + + In order to allow a mixture of RayFace+RayObjects, + all RayObjects must be 4byte aligned, allowing us to use the + 2 least significant bits (with the mask 0x03) to define the + type of RayObject. + + This leads to 4 possible types of RayObject: + + addr&3 - type of object + 0 Self (reserved for each structure) + 1 RayFace (tri/quad primitive) + 2 RayObject (generic with API callbacks) + 3 VlakPrimitive + (vlak primitive - to be used when we have a vlak describing the data + eg.: on render code) + + 0 means it's reserved and has it own meaning inside each ray acceleration structure + (this way each structure can use the allign offset to determine if a node represents a + RayObject primitive, which can be used to save memory) + */ + +/* used to test the type of ray object */ +#define RE_rayobject_isAligned(o) ((((intptr_t)o)&3) == 0) +#define RE_rayobject_isRayFace(o) ((((intptr_t)o)&3) == 1) +#define RE_rayobject_isRayAPI(o) ((((intptr_t)o)&3) == 2) +#define RE_rayobject_isVlakPrimitive(o) ((((intptr_t)o)&3) == 3) + +/* used to align a given ray object */ +#define RE_rayobject_align(o) ((RayObject*)(((intptr_t)o)&(~3))) + +/* used to unalign a given ray object */ +#define RE_rayobject_unalignRayFace(o) ((RayObject*)(((intptr_t)o)|1)) +#define RE_rayobject_unalignRayAPI(o) ((RayObject*)(((intptr_t)o)|2)) +#define RE_rayobject_unalignVlakPrimitive(o) ((RayObject*)(((intptr_t)o)|3)) + +/* + * This rayobject represents a generic object. With it's own callbacks for raytrace operations. + * It's suitable to implement things like LOD. + */ + +struct RayObject { + struct RayObjectAPI *api; + struct RayObjectControl control; +}; + +typedef int (*RE_rayobject_raycast_callback)(RayObject *, struct Isect *); +typedef void (*RE_rayobject_add_callback)(RayObject *raytree, RayObject *rayobject); +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 *, struct RayHint *, float *, float *); + +typedef struct RayObjectAPI { + RE_rayobject_raycast_callback raycast; + RE_rayobject_add_callback add; + RE_rayobject_done_callback done; + RE_rayobject_free_callback free; + RE_rayobject_merge_bb_callback bb; + RE_rayobject_cost_callback cost; + RE_rayobject_hint_bb_callback hint_bb; +} RayObjectAPI; + +/* + * Returns the expected cost of raycast on this node, primitives have a cost of 1 + */ +float RE_rayobject_cost(RayObject *r); + +/* + * This function differs from RE_rayobject_raycast + * RE_rayobject_intersect does NOT perform last-hit optimization + * So this is probably a function to call inside raytrace structures + */ +int RE_rayobject_intersect(RayObject *r, struct Isect *i); + +#ifdef __cplusplus +} +#endif + +#endif + diff --git a/source/blender/render/intern/raytrace/rayobject_octree.cpp b/source/blender/render/intern/raytrace/rayobject_octree.cpp new file mode 100644 index 00000000000..0fd43dfe5ef --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_octree.cpp @@ -0,0 +1,1080 @@ +/** + * $Id: rayobject_octree.cpp 29491 2010-06-16 18:57:23Z blendix $ + * + * ***** 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 1990-1998 NeoGeo BV. + * All rights reserved. + * + * Contributors: 2004/2005 Blender Foundation, full recode + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/* IMPORTANT NOTE: this code must be independent of any other render code + to use it outside the renderer! */ + +#include <math.h> +#include <string.h> +#include <stdlib.h> +#include <float.h> +#include <assert.h> + +#include "MEM_guardedalloc.h" + +#include "DNA_material_types.h" + +#include "BLI_math.h" +#include "BLI_utildefines.h" + +#include "rayintersection.h" +#include "rayobject.h" + +/* ********** structs *************** */ +#define BRANCH_ARRAY 1024 +#define NODE_ARRAY 4096 + +typedef struct Branch +{ + struct Branch *b[8]; +} Branch; + +typedef struct OcVal +{ + short ocx, ocy, ocz; +} OcVal; + +typedef struct Node +{ + struct RayFace *v[8]; + struct OcVal ov[8]; + struct Node *next; +} Node; + +typedef struct Octree { + RayObject rayobj; + + struct Branch **adrbranch; + struct Node **adrnode; + float ocsize; /* ocsize: mult factor, max size octree */ + float ocfacx,ocfacy,ocfacz; + float min[3], max[3]; + int ocres; + int branchcount, nodecount; + + /* during building only */ + char *ocface; + + RayFace **ro_nodes; + int ro_nodes_size, ro_nodes_used; + +} Octree; + +static int RE_rayobject_octree_intersect(RayObject *o, Isect *isec); +static void RE_rayobject_octree_add(RayObject *o, RayObject *ob); +static void RE_rayobject_octree_done(RayObject *o); +static void RE_rayobject_octree_free(RayObject *o); +static void RE_rayobject_octree_bb(RayObject *o, float *min, float *max); + +/* + * This function is not expected to be called by current code state. + */ +static float RE_rayobject_octree_cost(RayObject *o) +{ + return 1.0; +} + +static void RE_rayobject_octree_hint_bb(RayObject *o, RayHint *hint, float *min, float *max) +{ + return; +} + +static RayObjectAPI octree_api = +{ + RE_rayobject_octree_intersect, + RE_rayobject_octree_add, + RE_rayobject_octree_done, + RE_rayobject_octree_free, + RE_rayobject_octree_bb, + RE_rayobject_octree_cost, + RE_rayobject_octree_hint_bb +}; + +/* **************** ocval method ******************* */ +/* within one octree node, a set of 3x15 bits defines a 'boundbox' to OR with */ + +#define OCVALRES 15 +#define BROW16(min, max) (((max)>=OCVALRES? 0xFFFF: (1<<(max+1))-1) - ((min>0)? ((1<<(min))-1):0) ) + +static void calc_ocval_face(float *v1, float *v2, float *v3, float *v4, short x, short y, short z, OcVal *ov) +{ + float min[3], max[3]; + int ocmin, ocmax; + + copy_v3_v3(min, v1); + copy_v3_v3(max, v1); + DO_MINMAX(v2, min, max); + DO_MINMAX(v3, min, max); + if(v4) { + DO_MINMAX(v4, min, max); + } + + ocmin= OCVALRES*(min[0]-x); + ocmax= OCVALRES*(max[0]-x); + ov->ocx= BROW16(ocmin, ocmax); + + ocmin= OCVALRES*(min[1]-y); + ocmax= OCVALRES*(max[1]-y); + ov->ocy= BROW16(ocmin, ocmax); + + ocmin= OCVALRES*(min[2]-z); + ocmax= OCVALRES*(max[2]-z); + ov->ocz= BROW16(ocmin, ocmax); + +} + +static void calc_ocval_ray(OcVal *ov, float xo, float yo, float zo, float *vec1, float *vec2) +{ + int ocmin, ocmax; + + if(vec1[0]<vec2[0]) { + ocmin= OCVALRES*(vec1[0] - xo); + ocmax= OCVALRES*(vec2[0] - xo); + } else { + ocmin= OCVALRES*(vec2[0] - xo); + ocmax= OCVALRES*(vec1[0] - xo); + } + ov->ocx= BROW16(ocmin, ocmax); + + if(vec1[1]<vec2[1]) { + ocmin= OCVALRES*(vec1[1] - yo); + ocmax= OCVALRES*(vec2[1] - yo); + } else { + ocmin= OCVALRES*(vec2[1] - yo); + ocmax= OCVALRES*(vec1[1] - yo); + } + ov->ocy= BROW16(ocmin, ocmax); + + if(vec1[2]<vec2[2]) { + ocmin= OCVALRES*(vec1[2] - zo); + ocmax= OCVALRES*(vec2[2] - zo); + } else { + ocmin= OCVALRES*(vec2[2] - zo); + ocmax= OCVALRES*(vec1[2] - zo); + } + ov->ocz= BROW16(ocmin, ocmax); +} + +/* ************* octree ************** */ + +static Branch *addbranch(Octree *oc, Branch *br, short ocb) +{ + int index; + + if(br->b[ocb]) return br->b[ocb]; + + oc->branchcount++; + index= oc->branchcount>>12; + + if(oc->adrbranch[index]==NULL) + oc->adrbranch[index]= (Branch*)MEM_callocN(4096*sizeof(Branch), "new oc branch"); + + if(oc->branchcount>= BRANCH_ARRAY*4096) { + printf("error; octree branches full\n"); + oc->branchcount=0; + } + + return br->b[ocb]= oc->adrbranch[index]+(oc->branchcount & 4095); +} + +static Node *addnode(Octree *oc) +{ + int index; + + oc->nodecount++; + index= oc->nodecount>>12; + + if(oc->adrnode[index]==NULL) + oc->adrnode[index]= (Node*)MEM_callocN(4096*sizeof(Node),"addnode"); + + if(oc->nodecount> NODE_ARRAY*NODE_ARRAY) { + printf("error; octree nodes full\n"); + oc->nodecount=0; + } + + return oc->adrnode[index]+(oc->nodecount & 4095); +} + +static int face_in_node(RayFace *face, short x, short y, short z, float rtf[][3]) +{ + static float nor[3], d; + float fx, fy, fz; + + // init static vars + if(face) { + normal_tri_v3( nor,rtf[0], rtf[1], rtf[2]); + d= -nor[0]*rtf[0][0] - nor[1]*rtf[0][1] - nor[2]*rtf[0][2]; + return 0; + } + + fx= x; + fy= y; + fz= z; + + if((fx)*nor[0] + (fy)*nor[1] + (fz)*nor[2] + d > 0.0f) { + if((fx+1)*nor[0] + (fy )*nor[1] + (fz )*nor[2] + d < 0.0f) return 1; + if((fx )*nor[0] + (fy+1)*nor[1] + (fz )*nor[2] + d < 0.0f) return 1; + if((fx+1)*nor[0] + (fy+1)*nor[1] + (fz )*nor[2] + d < 0.0f) return 1; + + if((fx )*nor[0] + (fy )*nor[1] + (fz+1)*nor[2] + d < 0.0f) return 1; + if((fx+1)*nor[0] + (fy )*nor[1] + (fz+1)*nor[2] + d < 0.0f) return 1; + if((fx )*nor[0] + (fy+1)*nor[1] + (fz+1)*nor[2] + d < 0.0f) return 1; + if((fx+1)*nor[0] + (fy+1)*nor[1] + (fz+1)*nor[2] + d < 0.0f) return 1; + } + else { + if((fx+1)*nor[0] + (fy )*nor[1] + (fz )*nor[2] + d > 0.0f) return 1; + if((fx )*nor[0] + (fy+1)*nor[1] + (fz )*nor[2] + d > 0.0f) return 1; + if((fx+1)*nor[0] + (fy+1)*nor[1] + (fz )*nor[2] + d > 0.0f) return 1; + + if((fx )*nor[0] + (fy )*nor[1] + (fz+1)*nor[2] + d > 0.0f) return 1; + if((fx+1)*nor[0] + (fy )*nor[1] + (fz+1)*nor[2] + d > 0.0f) return 1; + if((fx )*nor[0] + (fy+1)*nor[1] + (fz+1)*nor[2] + d > 0.0f) return 1; + if((fx+1)*nor[0] + (fy+1)*nor[1] + (fz+1)*nor[2] + d > 0.0f) return 1; + } + + return 0; +} + +static void ocwrite(Octree *oc, RayFace *face, int quad, short x, short y, short z, float rtf[][3]) +{ + Branch *br; + Node *no; + short a, oc0, oc1, oc2, oc3, oc4, oc5; + + x<<=2; + y<<=1; + + br= oc->adrbranch[0]; + + if(oc->ocres==512) { + oc0= ((x & 1024)+(y & 512)+(z & 256))>>8; + br= addbranch(oc, br, oc0); + } + if(oc->ocres>=256) { + oc0= ((x & 512)+(y & 256)+(z & 128))>>7; + br= addbranch(oc, br, oc0); + } + if(oc->ocres>=128) { + oc0= ((x & 256)+(y & 128)+(z & 64))>>6; + br= addbranch(oc, br, oc0); + } + + oc0= ((x & 128)+(y & 64)+(z & 32))>>5; + oc1= ((x & 64)+(y & 32)+(z & 16))>>4; + oc2= ((x & 32)+(y & 16)+(z & 8))>>3; + oc3= ((x & 16)+(y & 8)+(z & 4))>>2; + oc4= ((x & 8)+(y & 4)+(z & 2))>>1; + oc5= ((x & 4)+(y & 2)+(z & 1)); + + br= addbranch(oc, br,oc0); + br= addbranch(oc, br,oc1); + br= addbranch(oc, br,oc2); + br= addbranch(oc, br,oc3); + br= addbranch(oc, br,oc4); + no= (Node *)br->b[oc5]; + if(no==NULL) br->b[oc5]= (Branch *)(no= addnode(oc)); + + while(no->next) no= no->next; + + a= 0; + if(no->v[7]) { /* node full */ + no->next= addnode(oc); + no= no->next; + } + else { + while(no->v[a]!=NULL) a++; + } + + no->v[a]= (RayFace*) RE_rayobject_align(face); + + if(quad) + calc_ocval_face(rtf[0], rtf[1], rtf[2], rtf[3], x>>2, y>>1, z, &no->ov[a]); + else + calc_ocval_face(rtf[0], rtf[1], rtf[2], NULL, x>>2, y>>1, z, &no->ov[a]); +} + +static void d2dda(Octree *oc, short b1, short b2, short c1, short c2, char *ocface, short rts[][3], float rtf[][3]) +{ + int ocx1,ocx2,ocy1,ocy2; + int x,y,dx=0,dy=0; + float ox1,ox2,oy1,oy2; + float labda,labdao,labdax,labday,ldx,ldy; + + ocx1= rts[b1][c1]; + ocy1= rts[b1][c2]; + ocx2= rts[b2][c1]; + ocy2= rts[b2][c2]; + + if(ocx1==ocx2 && ocy1==ocy2) { + ocface[oc->ocres*ocx1+ocy1]= 1; + return; + } + + ox1= rtf[b1][c1]; + oy1= rtf[b1][c2]; + ox2= rtf[b2][c1]; + oy2= rtf[b2][c2]; + + if(ox1!=ox2) { + if(ox2-ox1>0.0f) { + labdax= (ox1-ocx1-1.0f)/(ox1-ox2); + ldx= -1.0f/(ox1-ox2); + dx= 1; + } else { + labdax= (ox1-ocx1)/(ox1-ox2); + ldx= 1.0f/(ox1-ox2); + dx= -1; + } + } else { + labdax=1.0f; + ldx=0; + } + + if(oy1!=oy2) { + if(oy2-oy1>0.0f) { + labday= (oy1-ocy1-1.0f)/(oy1-oy2); + ldy= -1.0f/(oy1-oy2); + dy= 1; + } else { + labday= (oy1-ocy1)/(oy1-oy2); + ldy= 1.0f/(oy1-oy2); + dy= -1; + } + } else { + labday=1.0f; + ldy=0; + } + + x=ocx1; y=ocy1; + labda= MIN2(labdax, labday); + + while(TRUE) { + + if(x<0 || y<0 || x>=oc->ocres || y>=oc->ocres); + else ocface[oc->ocres*x+y]= 1; + + labdao=labda; + if(labdax==labday) { + labdax+=ldx; + x+=dx; + labday+=ldy; + y+=dy; + } else { + if(labdax<labday) { + labdax+=ldx; + x+=dx; + } else { + labday+=ldy; + y+=dy; + } + } + labda=MIN2(labdax,labday); + if(labda==labdao) break; + if(labda>=1.0f) break; + } + ocface[oc->ocres*ocx2+ocy2]=1; +} + +static void filltriangle(Octree *oc, short c1, short c2, char *ocface, short *ocmin, short *ocmax) +{ + int a, x, y, y1, y2; + + for(x=ocmin[c1];x<=ocmax[c1];x++) { + a= oc->ocres*x; + for(y=ocmin[c2];y<=ocmax[c2];y++) { + if(ocface[a+y]) { + y++; + while(ocface[a+y] && y!=ocmax[c2]) y++; + for(y1=ocmax[c2];y1>y;y1--) { + if(ocface[a+y1]) { + for(y2=y;y2<=y1;y2++) ocface[a+y2]=1; + y1=0; + } + } + y=ocmax[c2]; + } + } + } +} + +static void RE_rayobject_octree_free(RayObject *tree) +{ + Octree *oc= (Octree*)tree; + +#if 0 + printf("branches %d nodes %d\n", oc->branchcount, oc->nodecount); + printf("raycount %d \n", raycount); + printf("ray coherent %d \n", coherent_ray); + printf("accepted %d rejected %d\n", accepted, rejected); +#endif + if(oc->ocface) + MEM_freeN(oc->ocface); + + if(oc->adrbranch) { + int a= 0; + while(oc->adrbranch[a]) { + MEM_freeN(oc->adrbranch[a]); + oc->adrbranch[a]= NULL; + a++; + } + MEM_freeN(oc->adrbranch); + oc->adrbranch= NULL; + } + oc->branchcount= 0; + + if(oc->adrnode) { + int a= 0; + while(oc->adrnode[a]) { + MEM_freeN(oc->adrnode[a]); + oc->adrnode[a]= NULL; + a++; + } + MEM_freeN(oc->adrnode); + oc->adrnode= NULL; + } + oc->nodecount= 0; + + MEM_freeN(oc); +} + + +RayObject *RE_rayobject_octree_create(int ocres, int size) +{ + Octree *oc= (Octree*)MEM_callocN(sizeof(Octree), "Octree"); + assert( RE_rayobject_isAligned(oc) ); /* RayObject API assumes real data to be 4-byte aligned */ + + oc->rayobj.api = &octree_api; + + oc->ocres = ocres; + + oc->ro_nodes = (RayFace**)MEM_callocN(sizeof(RayFace*)*size, "octree rayobject nodes"); + oc->ro_nodes_size = size; + oc->ro_nodes_used = 0; + + + return RE_rayobject_unalignRayAPI((RayObject*) oc); +} + + +static void RE_rayobject_octree_add(RayObject *tree, RayObject *node) +{ + Octree *oc = (Octree*)tree; + + assert( RE_rayobject_isRayFace(node) ); + assert( oc->ro_nodes_used < oc->ro_nodes_size ); + oc->ro_nodes[ oc->ro_nodes_used++ ] = (RayFace*)RE_rayobject_align(node); +} + +static void octree_fill_rayface(Octree *oc, RayFace *face) +{ + float ocfac[3], rtf[4][3]; + float co1[3], co2[3], co3[3], co4[3]; + short rts[4][3]; + short ocmin[3], ocmax[3]; + char *ocface= oc->ocface; // front, top, size view of face, to fill in + int a, b, c, oc1, oc2, oc3, oc4, x, y, z, ocres2; + + ocfac[0]= oc->ocfacx; + ocfac[1]= oc->ocfacy; + ocfac[2]= oc->ocfacz; + + ocres2= oc->ocres*oc->ocres; + + copy_v3_v3(co1, face->v1); + copy_v3_v3(co2, face->v2); + copy_v3_v3(co3, face->v3); + if(face->v4) + copy_v3_v3(co4, face->v4); + + for(c=0;c<3;c++) { + rtf[0][c]= (co1[c]-oc->min[c])*ocfac[c] ; + rts[0][c]= (short)rtf[0][c]; + rtf[1][c]= (co2[c]-oc->min[c])*ocfac[c] ; + rts[1][c]= (short)rtf[1][c]; + rtf[2][c]= (co3[c]-oc->min[c])*ocfac[c] ; + rts[2][c]= (short)rtf[2][c]; + if(RE_rayface_isQuad(face)) { + rtf[3][c]= (co4[c]-oc->min[c])*ocfac[c] ; + rts[3][c]= (short)rtf[3][c]; + } + } + + for(c=0;c<3;c++) { + oc1= rts[0][c]; + oc2= rts[1][c]; + oc3= rts[2][c]; + if(!RE_rayface_isQuad(face)) { + ocmin[c]= MIN3(oc1,oc2,oc3); + ocmax[c]= MAX3(oc1,oc2,oc3); + } + else { + oc4= rts[3][c]; + ocmin[c]= MIN4(oc1,oc2,oc3,oc4); + ocmax[c]= MAX4(oc1,oc2,oc3,oc4); + } + if(ocmax[c]>oc->ocres-1) ocmax[c]=oc->ocres-1; + if(ocmin[c]<0) ocmin[c]=0; + } + + if(ocmin[0]==ocmax[0] && ocmin[1]==ocmax[1] && ocmin[2]==ocmax[2]) { + ocwrite(oc, face, RE_rayface_isQuad(face), ocmin[0], ocmin[1], ocmin[2], rtf); + } + else { + + d2dda(oc, 0,1,0,1,ocface+ocres2,rts,rtf); + d2dda(oc, 0,1,0,2,ocface,rts,rtf); + d2dda(oc, 0,1,1,2,ocface+2*ocres2,rts,rtf); + d2dda(oc, 1,2,0,1,ocface+ocres2,rts,rtf); + d2dda(oc, 1,2,0,2,ocface,rts,rtf); + d2dda(oc, 1,2,1,2,ocface+2*ocres2,rts,rtf); + if(!RE_rayface_isQuad(face)) { + d2dda(oc, 2,0,0,1,ocface+ocres2,rts,rtf); + d2dda(oc, 2,0,0,2,ocface,rts,rtf); + d2dda(oc, 2,0,1,2,ocface+2*ocres2,rts,rtf); + } + else { + d2dda(oc, 2,3,0,1,ocface+ocres2,rts,rtf); + d2dda(oc, 2,3,0,2,ocface,rts,rtf); + d2dda(oc, 2,3,1,2,ocface+2*ocres2,rts,rtf); + d2dda(oc, 3,0,0,1,ocface+ocres2,rts,rtf); + d2dda(oc, 3,0,0,2,ocface,rts,rtf); + d2dda(oc, 3,0,1,2,ocface+2*ocres2,rts,rtf); + } + /* nothing todo with triangle..., just fills :) */ + filltriangle(oc, 0,1,ocface+ocres2,ocmin,ocmax); + filltriangle(oc, 0,2,ocface,ocmin,ocmax); + filltriangle(oc, 1,2,ocface+2*ocres2,ocmin,ocmax); + + /* init static vars here */ + face_in_node(face, 0,0,0, rtf); + + for(x=ocmin[0];x<=ocmax[0];x++) { + a= oc->ocres*x; + for(y=ocmin[1];y<=ocmax[1];y++) { + if(ocface[a+y+ocres2]) { + b= oc->ocres*y+2*ocres2; + for(z=ocmin[2];z<=ocmax[2];z++) { + if(ocface[b+z] && ocface[a+z]) { + if(face_in_node(NULL, x, y, z, rtf)) + ocwrite(oc, face, RE_rayface_isQuad(face), x,y,z, rtf); + } + } + } + } + } + + /* same loops to clear octree, doubt it can be done smarter */ + for(x=ocmin[0];x<=ocmax[0];x++) { + a= oc->ocres*x; + for(y=ocmin[1];y<=ocmax[1];y++) { + /* x-y */ + ocface[a+y+ocres2]= 0; + + b= oc->ocres*y + 2*ocres2; + for(z=ocmin[2];z<=ocmax[2];z++) { + /* y-z */ + ocface[b+z]= 0; + /* x-z */ + ocface[a+z]= 0; + } + } + } + } +} + +static void RE_rayobject_octree_done(RayObject *tree) +{ + Octree *oc = (Octree*)tree; + int c; + float t00, t01, t02; + int ocres2 = oc->ocres*oc->ocres; + + INIT_MINMAX(oc->min, oc->max); + + /* Calculate Bounding Box */ + for(c=0; c<oc->ro_nodes_used; c++) + RE_rayobject_merge_bb( RE_rayobject_unalignRayFace(oc->ro_nodes[c]), oc->min, oc->max); + + /* Alloc memory */ + oc->adrbranch= (Branch**)MEM_callocN(sizeof(void *)*BRANCH_ARRAY, "octree branches"); + oc->adrnode= (Node**)MEM_callocN(sizeof(void *)*NODE_ARRAY, "octree nodes"); + + oc->adrbranch[0]=(Branch *)MEM_callocN(4096*sizeof(Branch), "makeoctree"); + + /* the lookup table, per face, for which nodes to fill in */ + oc->ocface= (char*)MEM_callocN( 3*ocres2 + 8, "ocface"); + memset(oc->ocface, 0, 3*ocres2); + + for(c=0;c<3;c++) { /* octree enlarge, still needed? */ + oc->min[c]-= 0.01f; + oc->max[c]+= 0.01f; + } + + t00= oc->max[0]-oc->min[0]; + t01= oc->max[1]-oc->min[1]; + t02= oc->max[2]-oc->min[2]; + + /* this minus 0.1 is old safety... seems to be needed? */ + oc->ocfacx= (oc->ocres-0.1)/t00; + oc->ocfacy= (oc->ocres-0.1)/t01; + oc->ocfacz= (oc->ocres-0.1)/t02; + + oc->ocsize= sqrt(t00*t00+t01*t01+t02*t02); /* global, max size octree */ + + for(c=0; c<oc->ro_nodes_used; c++) + { + octree_fill_rayface(oc, oc->ro_nodes[c]); + } + + 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 ); + printf("%f %f - %f\n", oc->min[2], oc->max[2], oc->ocfacz ); +} + +static void RE_rayobject_octree_bb(RayObject *tree, float *min, float *max) +{ + Octree *oc = (Octree*)tree; + DO_MINMAX(oc->min, min, max); + DO_MINMAX(oc->max, min, max); +} + +/* check all faces in this node */ +static int testnode(Octree *oc, Isect *is, Node *no, OcVal ocval) +{ + short nr=0; + + /* return on any first hit */ + if(is->mode==RE_RAY_SHADOW) { + + for(; no; no = no->next) + for(nr=0; nr<8; nr++) + { + RayFace *face = no->v[nr]; + OcVal *ov = no->ov+nr; + + if(!face) break; + + if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) ) + { + if( RE_rayobject_intersect( RE_rayobject_unalignRayFace(face),is) ) + return 1; + } + } + } + else + { /* else mirror or glass or shadowtra, return closest face */ + int found= 0; + + for(; no; no = no->next) + for(nr=0; nr<8; nr++) + { + RayFace *face = no->v[nr]; + OcVal *ov = no->ov+nr; + + if(!face) break; + + if( (ov->ocx & ocval.ocx) && (ov->ocy & ocval.ocy) && (ov->ocz & ocval.ocz) ) + { + if( RE_rayobject_intersect( RE_rayobject_unalignRayFace(face),is) ) + found= 1; + } + } + + return found; + } + + return 0; +} + +/* find the Node for the octree coord x y z */ +static Node *ocread(Octree *oc, int x, int y, int z) +{ + Branch *br; + int oc1; + + x<<=2; + y<<=1; + + br= oc->adrbranch[0]; + + if(oc->ocres==512) { + oc1= ((x & 1024)+(y & 512)+(z & 256))>>8; + br= br->b[oc1]; + if(br==NULL) { + return NULL; + } + } + if(oc->ocres>=256) { + oc1= ((x & 512)+(y & 256)+(z & 128))>>7; + br= br->b[oc1]; + if(br==NULL) { + return NULL; + } + } + if(oc->ocres>=128) { + oc1= ((x & 256)+(y & 128)+(z & 64))>>6; + br= br->b[oc1]; + if(br==NULL) { + return NULL; + } + } + + oc1= ((x & 128)+(y & 64)+(z & 32))>>5; + br= br->b[oc1]; + if(br) { + oc1= ((x & 64)+(y & 32)+(z & 16))>>4; + br= br->b[oc1]; + if(br) { + oc1= ((x & 32)+(y & 16)+(z & 8))>>3; + br= br->b[oc1]; + if(br) { + oc1= ((x & 16)+(y & 8)+(z & 4))>>2; + br= br->b[oc1]; + if(br) { + oc1= ((x & 8)+(y & 4)+(z & 2))>>1; + br= br->b[oc1]; + if(br) { + oc1= ((x & 4)+(y & 2)+(z & 1)); + return (Node *)br->b[oc1]; + } + } + } + } + } + + return NULL; +} + +static int cliptest(float p, float q, float *u1, float *u2) +{ + float r; + + if(p<0.0f) { + if(q<p) return 0; + else if(q<0.0f) { + r= q/p; + if(r>*u2) return 0; + else if(r>*u1) *u1=r; + } + } + else { + if(p>0.0f) { + if(q<0.0f) return 0; + else if(q<p) { + r= q/p; + if(r<*u1) return 0; + else if(r<*u2) *u2=r; + } + } + else if(q<0.0f) return 0; + } + return 1; +} + +/* extensive coherence checks/storage cancels out the benefit of it, and gives errors... we + need better methods, sample code commented out below (ton) */ + +/* + +in top: static int coh_nodes[16*16*16][6]; +in makeoctree: memset(coh_nodes, 0, sizeof(coh_nodes)); + +static void add_coherence_test(int ocx1, int ocx2, int ocy1, int ocy2, int ocz1, int ocz2) +{ + short *sp; + + sp= coh_nodes[ (ocx2 & 15) + 16*(ocy2 & 15) + 256*(ocz2 & 15) ]; + sp[0]= ocx1; sp[1]= ocy1; sp[2]= ocz1; + sp[3]= ocx2; sp[4]= ocy2; sp[5]= ocz2; + +} + +static int do_coherence_test(int ocx1, int ocx2, int ocy1, int ocy2, int ocz1, int ocz2) +{ + short *sp; + + sp= coh_nodes[ (ocx2 & 15) + 16*(ocy2 & 15) + 256*(ocz2 & 15) ]; + if(sp[0]==ocx1 && sp[1]==ocy1 && sp[2]==ocz1 && + sp[3]==ocx2 && sp[4]==ocy2 && sp[5]==ocz2) return 1; + return 0; +} + +*/ + +/* return 1: found valid intersection */ +/* starts with is->orig.face */ +static int RE_rayobject_octree_intersect(RayObject *tree, Isect *is) +{ + Octree *oc= (Octree*)tree; + Node *no; + OcVal ocval; + 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; + + /* clip with octree */ + if(oc->branchcount==0) return 0; + + /* do this before intersect calls */ +#if 0 + is->facecontr= NULL; /* to check shared edge */ + is->obcontr= 0; + is->faceisect= is->isect= 0; /* shared edge, quad half flag */ + is->userdata= oc->userdata; +#endif + + copy_v3_v3( start, is->start ); + madd_v3_v3v3fl( end, is->start, is->dir, is->dist ); + ldx= is->dir[0]*is->dist; + olabda = is->dist; + u1= 0.0f; + u2= 1.0f; + + /* clip with octree cube */ + if(cliptest(-ldx, start[0]-oc->min[0], &u1,&u2)) { + if(cliptest(ldx, oc->max[0]-start[0], &u1,&u2)) { + ldy= is->dir[1]*is->dist; + if(cliptest(-ldy, start[1]-oc->min[1], &u1,&u2)) { + if(cliptest(ldy, oc->max[1]-start[1], &u1,&u2)) { + ldz = is->dir[2]*is->dist; + 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) { + end[0] = start[0]+u2*ldx; + end[1] = start[1]+u2*ldy; + end[2] = start[2]+u2*ldz; + } + + if(u1>0.0f) { + start[0] += u1*ldx; + start[1] += u1*ldy; + start[2] += u1*ldz; + } + } + } + } + } + } + } + + if(c1==0) return 0; + + /* reset static variables in ocread */ + //ocread(oc, oc->ocres, 0, 0); + + /* setup 3dda to traverse octree */ + 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; + + ocx1= (int)ox1; + ocy1= (int)oy1; + ocz1= (int)oz1; + ocx2= (int)ox2; + ocy2= (int)oy2; + ocz2= (int)oz2; + + if(ocx1==ocx2 && ocy1==ocy2 && ocz1==ocz2) { + no= ocread(oc, ocx1, ocy1, ocz1); + if(no) { + /* exact intersection with node */ + 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); + 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; + + /* calc labda en ld */ + dox= ox1-ox2; + doy= oy1-oy2; + doz= oz1-oz2; + + if(dox<-FLT_EPSILON) { + ldx= -1.0f/dox; + labdax= (ocx1-ox1+1.0f)*ldx; + dx= 1; + } else if(dox>FLT_EPSILON) { + ldx= 1.0f/dox; + labdax= (ox1-ocx1)*ldx; + dx= -1; + } else { + labdax=1.0f; + ldx=0; + dx= 0; + } + + if(doy<-FLT_EPSILON) { + ldy= -1.0f/doy; + labday= (ocy1-oy1+1.0f)*ldy; + dy= 1; + } else if(doy>FLT_EPSILON) { + ldy= 1.0f/doy; + labday= (oy1-ocy1)*ldy; + dy= -1; + } else { + labday=1.0f; + ldy=0; + dy= 0; + } + + if(doz<-FLT_EPSILON) { + ldz= -1.0f/doz; + labdaz= (ocz1-oz1+1.0f)*ldz; + dz= 1; + } else if(doz>FLT_EPSILON) { + ldz= 1.0f/doz; + labdaz= (oz1-ocz1)*ldz; + dz= -1; + } else { + labdaz=1.0f; + ldz=0; + dz= 0; + } + + xo=ocx1; yo=ocy1; zo=ocz1; + labdao= ddalabda= MIN3(labdax,labday,labdaz); + + vec2[0]= ox1; + vec2[1]= oy1; + vec2[2]= oz1; + + /* this loop has been constructed to make sure the first and last node of ray + are always included, even when ddalabda==1.0f or larger */ + + while(TRUE) { + + no= ocread(oc, xo, yo, zo); + if(no) { + + /* calculate ray intersection with octree node */ + copy_v3_v3(vec1, vec2); + // dox,y,z is negative + vec2[0]= ox1-ddalabda*dox; + vec2[1]= oy1-ddalabda*doy; + vec2[2]= oz1-ddalabda*doz; + calc_ocval_ray(&ocval, (float)xo, (float)yo, (float)zo, vec1, vec2); + + //is->dist = (u1+ddalabda*(u2-u1))*olabda; + if( testnode(oc, is, no, ocval) ) + found = 1; + + if(is->dist < (u1+ddalabda*(u2-u1))*olabda) + return found; + } + + + labdao= ddalabda; + + /* traversing ocree nodes need careful detection of smallest values, with proper + exceptions for equal labdas */ + eqval= (labdax==labday); + if(labday==labdaz) eqval += 2; + if(labdax==labdaz) eqval += 4; + + if(eqval) { // only 4 cases exist! + if(eqval==7) { // x=y=z + xo+=dx; labdax+=ldx; + yo+=dy; labday+=ldy; + zo+=dz; labdaz+=ldz; + } + else if(eqval==1) { // x=y + if(labday < labdaz) { + xo+=dx; labdax+=ldx; + yo+=dy; labday+=ldy; + } + else { + zo+=dz; labdaz+=ldz; + } + } + else if(eqval==2) { // y=z + if(labdax < labday) { + xo+=dx; labdax+=ldx; + } + else { + yo+=dy; labday+=ldy; + zo+=dz; labdaz+=ldz; + } + } + else { // x=z + if(labday < labdax) { + yo+=dy; labday+=ldy; + } + else { + xo+=dx; labdax+=ldx; + zo+=dz; labdaz+=ldz; + } + } + } + else { // all three different, just three cases exist + eqval= (labdax<labday); + if(labday<labdaz) eqval += 2; + if(labdax<labdaz) eqval += 4; + + if(eqval==7 || eqval==5) { // x smallest + xo+=dx; labdax+=ldx; + } + else if(eqval==2 || eqval==6) { // y smallest + yo+=dy; labday+=ldy; + } + else { // z smallest + zo+=dz; labdaz+=ldz; + } + + } + + ddalabda=MIN3(labdax,labday,labdaz); + if(ddalabda==labdao) break; + /* to make sure the last node is always checked */ + if(labdao>=1.0f) break; + } + } + + /* reached end, no intersections found */ + return 0; +} + + + diff --git a/source/blender/render/intern/raytrace/rayobject_qbvh.cpp b/source/blender/render/intern/raytrace/rayobject_qbvh.cpp index c510af540db..e8a118d3349 100644 --- a/source/blender/render/intern/raytrace/rayobject_qbvh.cpp +++ b/source/blender/render/intern/raytrace/rayobject_qbvh.cpp @@ -26,7 +26,11 @@ * * ***** END GPL LICENSE BLOCK ***** */ + #include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" + #include "vbvh.h" #include "svbvh.h" #include "reorganize.h" @@ -60,10 +64,10 @@ void bvh_done<QBVHTree>(QBVHTree *obj) BLI_memarena_use_malloc(arena2); BLI_memarena_use_align(arena2, 16); - //Build and optimize the tree - //TODO do this in 1 pass (half memory usage during building) + //Build and optimize the tree + //TODO do this in 1 pass (half memory usage during building) VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1, &obj->rayobj.control).transform(obj->builder); - + if(RE_rayobjectcontrol_test_break(&obj->rayobj.control)) { BLI_memarena_free(arena1); @@ -71,28 +75,32 @@ void bvh_done<QBVHTree>(QBVHTree *obj) return; } - pushup_simd<VBVHNode,4>(root); + pushup_simd<VBVHNode,4>(root); + obj->root = Reorganize_SVBVH<VBVHNode>(arena2).transform(root); - //Cleanup - BLI_memarena_free(arena1); + //Free data + BLI_memarena_free(arena1); - rtbuild_free( obj->builder ); - obj->builder = NULL; - obj->node_arena = arena2; - obj->cost = 1.0; -} + obj->cost = 1.0; + rtbuild_free(obj->builder); + obj->builder = NULL; +} template<int StackSize> int intersect(QBVHTree *obj, Isect* isec) { //TODO renable hint support - if(RE_rayobject_isAligned(obj->root)) - return bvh_node_stack_raycast<SVBVHNode,StackSize,false>( obj->root, isec); + if(RE_rayobject_isAligned(obj->root)) { + if(isec->mode == RE_RAY_SHADOW) + return svbvh_node_stack_raycast<StackSize,true>(obj->root, isec); + else + return svbvh_node_stack_raycast<StackSize,false>(obj->root, isec); + } else - return RE_rayobject_intersect( (RayObject*) obj->root, isec ); + return RE_rayobject_intersect((RayObject*)obj->root, isec); } template<class Tree> @@ -132,13 +140,11 @@ RayObjectAPI* bvh_get_api(int maxstacksize) return 0; } - RayObject *RE_rayobject_qbvh_create(int size) { return bvh_create_tree<QBVHTree,DFS_STACK_SIZE>(size); } - #else RayObject *RE_rayobject_qbvh_create(int size) diff --git a/source/blender/render/intern/raytrace/rayobject_raycounter.cpp b/source/blender/render/intern/raytrace/rayobject_raycounter.cpp new file mode 100644 index 00000000000..a355d4b5a06 --- /dev/null +++ b/source/blender/render/intern/raytrace/rayobject_raycounter.cpp @@ -0,0 +1,88 @@ +/** + * $Id: rayobject_raycounter.cpp 29491 2010-06-16 18:57:23Z blendix $ + * + * ***** 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 "rayobject.h" +#include "raycounter.h" + +#ifdef RE_RAYCOUNTER + +void RE_RC_INFO(RayCounter *info) +{ + printf("----------- Raycast counter --------\n"); + printf("Rays total: %llu\n", info->raycast.test ); + printf("Rays hit: %llu\n", info->raycast.hit ); + printf("\n"); + printf("BB tests: %llu\n", info->bb.test ); + printf("BB hits: %llu\n", info->bb.hit ); + printf("\n"); + printf("SIMD BB tests: %llu\n", info->simd_bb.test ); + printf("SIMD BB hits: %llu\n", info->simd_bb.hit ); + printf("\n"); + printf("Primitives tests: %llu\n", info->faces.test ); + printf("Primitives hits: %llu\n", info->faces.hit ); + printf("------------------------------------\n"); + printf("Shadow last-hit tests per ray: %f\n", info->rayshadow_last_hit.test / ((float)info->raycast.test) ); + printf("Shadow last-hit hits per ray: %f\n", info->rayshadow_last_hit.hit / ((float)info->raycast.test) ); + printf("\n"); + printf("Hint tests per ray: %f\n", info->raytrace_hint.test / ((float)info->raycast.test) ); + printf("Hint hits per ray: %f\n", info->raytrace_hint.hit / ((float)info->raycast.test) ); + printf("\n"); + printf("BB tests per ray: %f\n", info->bb.test / ((float)info->raycast.test) ); + printf("BB hits per ray: %f\n", info->bb.hit / ((float)info->raycast.test) ); + printf("\n"); + printf("SIMD tests per ray: %f\n", info->simd_bb.test / ((float)info->raycast.test) ); + printf("SIMD hits per ray: %f\n", info->simd_bb.hit / ((float)info->raycast.test) ); + printf("\n"); + printf("Primitives tests per ray: %f\n", info->faces.test / ((float)info->raycast.test) ); + printf("Primitives hits per ray: %f\n", info->faces.hit / ((float)info->raycast.test) ); + printf("------------------------------------\n"); +} + +void RE_RC_MERGE(RayCounter *dest, RayCounter *tmp) +{ + dest->faces.test += tmp->faces.test; + dest->faces.hit += tmp->faces.hit; + + dest->bb.test += tmp->bb.test; + dest->bb.hit += tmp->bb.hit; + + dest->simd_bb.test += tmp->simd_bb.test; + dest->simd_bb.hit += tmp->simd_bb.hit; + + dest->raycast.test += tmp->raycast.test; + dest->raycast.hit += tmp->raycast.hit; + + dest->rayshadow_last_hit.test += tmp->rayshadow_last_hit.test; + dest->rayshadow_last_hit.hit += tmp->rayshadow_last_hit.hit; + + dest->raytrace_hint.test += tmp->raytrace_hint.test; + dest->raytrace_hint.hit += tmp->raytrace_hint.hit; +} + +#endif diff --git a/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp b/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp index 79bb3b9260f..cdaaebc7f92 100644 --- a/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp +++ b/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp @@ -22,23 +22,23 @@ * * The Original Code is: all of this file. * - * Contributor(s): Andr Pinto. + * Contributor(s): André Pinto. * * ***** END GPL LICENSE BLOCK ***** */ + #include <assert.h> #include <math.h> #include <stdlib.h> #include <algorithm> #include "rayobject_rtbuild.h" + #include "MEM_guardedalloc.h" #include "BLI_math.h" #include "BLI_utildefines.h" - - static bool selected_node(RTBuilder::Object *node) { return node->selected; @@ -94,13 +94,22 @@ void rtbuild_free(RTBuilder *b) void rtbuild_add(RTBuilder *b, RayObject *o) { + float bb[6]; + assert( b->primitives.begin + b->primitives.maxsize != b->primitives.end ); + + INIT_MINMAX(bb, bb+3); + RE_rayobject_merge_bb(o, bb, bb+3); + + /* skip objects with zero bounding box, they are of no use, and + will give problems in rtbuild_heuristic_object_split later */ + if(len_squared_v3v3(bb, bb+3) == 0.0f) + return; + copy_v3_v3(b->primitives.end->bb, bb); + copy_v3_v3(b->primitives.end->bb+3, bb+3); b->primitives.end->obj = o; b->primitives.end->cost = RE_rayobject_cost(o); - - INIT_MINMAX(b->primitives.end->bb, b->primitives.end->bb+3); - RE_rayobject_merge_bb(o, b->primitives.end->bb, b->primitives.end->bb+3); for(int i=0; i<3; i++) { @@ -333,8 +342,8 @@ int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds) { if(i == size-1) { - VECCOPY(sweep[i].bb, obj[i]->bb); - VECCOPY(sweep[i].bb+3, obj[i]->bb+3); + copy_v3_v3(sweep[i].bb, obj[i]->bb); + copy_v3_v3(sweep[i].bb+3, obj[i]->bb+3); sweep[i].cost = obj[i]->cost; } else @@ -365,8 +374,12 @@ int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds) //Worst case heuristic (cost of each child is linear) float hcost, left_side, right_side; - left_side = bb_area(sweep_left.bb, sweep_left.bb+3)*(sweep_left.cost+logf((float)i)); - right_side= bb_area(sweep[i].bb, sweep[i].bb+3)*(sweep[i].cost+logf((float)size-i)); + // not using log seems to have no impact on raytracing perf, but + // makes tree construction quicker, left out for now to test (brecht) + // left_side = bb_area(sweep_left.bb, sweep_left.bb+3)*(sweep_left.cost+logf((float)i)); + // right_side= bb_area(sweep[i].bb, sweep[i].bb+3)*(sweep[i].cost+logf((float)size-i)); + left_side = bb_area(sweep_left.bb, sweep_left.bb+3)*(sweep_left.cost); + right_side= bb_area(sweep[i].bb, sweep[i].bb+3)*(sweep[i].cost); hcost = left_side+right_side; assert(left_side >= 0); diff --git a/source/blender/render/intern/raytrace/rayobject_svbvh.cpp b/source/blender/render/intern/raytrace/rayobject_svbvh.cpp index 647c5771e4f..c10da3ad8c0 100644 --- a/source/blender/render/intern/raytrace/rayobject_svbvh.cpp +++ b/source/blender/render/intern/raytrace/rayobject_svbvh.cpp @@ -26,8 +26,11 @@ * * ***** END GPL LICENSE BLOCK ***** */ + #include "MEM_guardedalloc.h" +#include "BLI_utildefines.h" + #include "vbvh.h" #include "svbvh.h" #include "reorganize.h" @@ -75,7 +78,8 @@ void bvh_done<SVBVHTree>(SVBVHTree *obj) //Build and optimize the tree if(0) { - VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1,&obj->rayobj.control).transform(obj->builder); + VBVHNode *root = BuildBinaryVBVH<VBVHNode>(arena1, &obj->rayobj.control).transform(obj->builder); + if(RE_rayobjectcontrol_test_break(&obj->rayobj.control)) { BLI_memarena_free(arena1); @@ -86,11 +90,11 @@ void bvh_done<SVBVHTree>(SVBVHTree *obj) reorganize(root); remove_useless(root, &root); bvh_refit(root); - + pushup(root); pushdown(root); pushup_simd<VBVHNode,4>(root); - + obj->root = Reorganize_SVBVH<VBVHNode>(arena2).transform(root); } else @@ -98,6 +102,7 @@ void bvh_done<SVBVHTree>(SVBVHTree *obj) //Finds the optimal packing of this tree using a given cost model //TODO this uses quite a lot of memory, find ways to reduce memory usage during building OVBVHNode *root = BuildBinaryVBVH<OVBVHNode>(arena1,&obj->rayobj.control).transform(obj->builder); + if(RE_rayobjectcontrol_test_break(&obj->rayobj.control)) { BLI_memarena_free(arena1); @@ -108,15 +113,13 @@ void bvh_done<SVBVHTree>(SVBVHTree *obj) VBVH_optimalPackSIMD<OVBVHNode,PackCost>(PackCost()).transform(root); obj->root = Reorganize_SVBVH<OVBVHNode>(arena2).transform(root); } - //Free data BLI_memarena_free(arena1); obj->node_arena = arena2; obj->cost = 1.0; - - + rtbuild_free( obj->builder ); obj->builder = NULL; } @@ -125,8 +128,12 @@ template<int StackSize> int intersect(SVBVHTree *obj, Isect* isec) { //TODO renable hint support - if(RE_rayobject_isAligned(obj->root)) - return bvh_node_stack_raycast<SVBVHNode,StackSize,false>( obj->root, isec); + if(RE_rayobject_isAligned(obj->root)) { + if(isec->mode == RE_RAY_SHADOW) + return svbvh_node_stack_raycast<StackSize,true>(obj->root, isec); + else + return svbvh_node_stack_raycast<StackSize,false>(obj->root, isec); + } else return RE_rayobject_intersect( (RayObject*) obj->root, isec ); } @@ -172,6 +179,7 @@ RayObject *RE_rayobject_svbvh_create(int size) { return bvh_create_tree<SVBVHTree,DFS_STACK_SIZE>(size); } + #else RayObject *RE_rayobject_svbvh_create(int size) diff --git a/source/blender/render/intern/raytrace/rayobject_vbvh.cpp b/source/blender/render/intern/raytrace/rayobject_vbvh.cpp index b2104a2d557..df5842db2bf 100644 --- a/source/blender/render/intern/raytrace/rayobject_vbvh.cpp +++ b/source/blender/render/intern/raytrace/rayobject_vbvh.cpp @@ -22,29 +22,33 @@ * * The Original Code is: all of this file. * - * Contributor(s): Andr Pinto. + * Contributor(s): André Pinto. * * ***** END GPL LICENSE BLOCK ***** */ + int tot_pushup = 0; int tot_pushdown = 0; int tot_hints = 0; - #include <assert.h> -#include "rayobject.h" -#include "rayobject_rtbuild.h" -#include "RE_raytrace.h" -#include "BLI_memarena.h" + #include "MEM_guardedalloc.h" + #include "BKE_global.h" #include "BLI_math.h" +#include "BLI_memarena.h" +#include "BLI_utildefines.h" + +#include "rayintersection.h" +#include "rayobject.h" +#include "rayobject_rtbuild.h" #include "reorganize.h" #include "bvh.h" #include "vbvh.h" -#include "svbvh.h" + #include <queue> #include <algorithm> @@ -126,8 +130,12 @@ template<int StackSize> int intersect(VBVHTree *obj, Isect* isec) { //TODO renable hint support - if(RE_rayobject_isAligned(obj->root)) - return bvh_node_stack_raycast<VBVHNode,StackSize,false>( obj->root, isec); + if(RE_rayobject_isAligned(obj->root)) { + if(isec->mode == RE_RAY_SHADOW) + return bvh_node_stack_raycast<VBVHNode,StackSize,false,true>( obj->root, isec); + else + return bvh_node_stack_raycast<VBVHNode,StackSize,false,false>( obj->root, isec); + } else return RE_rayobject_intersect( (RayObject*) obj->root, isec ); } diff --git a/source/blender/render/intern/raytrace/reorganize.h b/source/blender/render/intern/raytrace/reorganize.h index c8fbd1cfe94..4e2dce32136 100644 --- a/source/blender/render/intern/raytrace/reorganize.h +++ b/source/blender/render/intern/raytrace/reorganize.h @@ -26,18 +26,18 @@ * * ***** END GPL LICENSE BLOCK ***** */ + +#include <float.h> +#include <math.h> #include <stdio.h> + #include <algorithm> -#include <math.h> -#include <vector> #include <queue> - -#include "BLI_utildefines.h" +#include <vector> #include "BKE_global.h" #ifdef _WIN32 -#undef INFINITY #define INFINITY FLT_MAX // in mingw math.h: (1.0F/0.0F). This generates compile error, though. #endif @@ -302,7 +302,7 @@ float bvh_refit(Node *node) * with the purpose to reduce the expected cost (eg.: number of BB tests). */ #include <vector> -#define MAX_CUT_SIZE 16 +#define MAX_CUT_SIZE 4 /* svbvh assumes max 4 children! */ #define MAX_OPTIMIZE_CHILDS MAX_CUT_SIZE struct OVBVHNode diff --git a/source/blender/render/intern/raytrace/svbvh.h b/source/blender/render/intern/raytrace/svbvh.h index 11511fccb89..832058870dd 100644 --- a/source/blender/render/intern/raytrace/svbvh.h +++ b/source/blender/render/intern/raytrace/svbvh.h @@ -26,6 +26,7 @@ * * ***** END GPL LICENSE BLOCK ***** */ + #ifdef __SSE__ #ifndef RE_RAYTRACE_SVBVH_H @@ -33,56 +34,132 @@ #include "bvh.h" #include "BLI_memarena.h" -#include "BLI_utildefines.h" #include "BKE_global.h" #include <stdio.h> #include <algorithm> struct SVBVHNode { + float child_bb[24]; + SVBVHNode *child[4]; int nchilds; - - //Array of bb, array of childs - float *child_bb; - SVBVHNode **child; }; -template<> -inline int bvh_node_hit_test<SVBVHNode>(SVBVHNode *node, Isect *isec) +static int svbvh_bb_intersect_test_simd4(const Isect *isec, const __m128 *bb_group) +{ + const __m128 tmin0 = _mm_setzero_ps(); + const __m128 tmax0 = _mm_set_ps1(isec->dist); + + const __m128 start0 = _mm_set_ps1(isec->start[0]); + const __m128 start1 = _mm_set_ps1(isec->start[1]); + const __m128 start2 = _mm_set_ps1(isec->start[2]); + const __m128 sub0 = _mm_sub_ps(bb_group[isec->bv_index[0]], start0); + const __m128 sub1 = _mm_sub_ps(bb_group[isec->bv_index[1]], start0); + const __m128 sub2 = _mm_sub_ps(bb_group[isec->bv_index[2]], start1); + const __m128 sub3 = _mm_sub_ps(bb_group[isec->bv_index[3]], start1); + const __m128 sub4 = _mm_sub_ps(bb_group[isec->bv_index[4]], start2); + const __m128 sub5 = _mm_sub_ps(bb_group[isec->bv_index[5]], start2); + const __m128 idot_axis0 = _mm_set_ps1(isec->idot_axis[0]); + const __m128 idot_axis1 = _mm_set_ps1(isec->idot_axis[1]); + const __m128 idot_axis2 = _mm_set_ps1(isec->idot_axis[2]); + const __m128 mul0 = _mm_mul_ps(sub0, idot_axis0); + const __m128 mul1 = _mm_mul_ps(sub1, idot_axis0); + const __m128 mul2 = _mm_mul_ps(sub2, idot_axis1); + const __m128 mul3 = _mm_mul_ps(sub3, idot_axis1); + const __m128 mul4 = _mm_mul_ps(sub4, idot_axis2); + const __m128 mul5 = _mm_mul_ps(sub5, idot_axis2); + const __m128 tmin1 = _mm_max_ps(tmin0, mul0); + const __m128 tmax1 = _mm_min_ps(tmax0, mul1); + const __m128 tmin2 = _mm_max_ps(tmin1, mul2); + const __m128 tmax2 = _mm_min_ps(tmax1, mul3); + const __m128 tmin3 = _mm_max_ps(tmin2, mul4); + const __m128 tmax3 = _mm_min_ps(tmax2, mul5); + + return _mm_movemask_ps(_mm_cmpge_ps(tmax3, tmin3)); +} + +static int svbvh_bb_intersect_test(const Isect *isec, const float *_bb) { + const float *bb = _bb; + + 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]; + + RE_RC_COUNT(isec->raycounter->bb.test); + + if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return 0; + if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return 0; + if(t1x > isec->dist || t1y > isec->dist || t1z > isec->dist) return 0; + + RE_RC_COUNT(isec->raycounter->bb.hit); + return 1; } -template<> -inline void bvh_node_push_childs<SVBVHNode>(SVBVHNode *node, Isect *isec, SVBVHNode **stack, int &stack_pos) +static bool svbvh_node_is_leaf(const SVBVHNode *node) { - int i=0; - while(i+4 <= node->nchilds) - { - int res = test_bb_group4( (__m128*) (node->child_bb+6*i), isec ); - RE_RC_COUNT(isec->raycounter->simd_bb.test); - - if(res & 1) { stack[stack_pos++] = node->child[i+0]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } - if(res & 2) { stack[stack_pos++] = node->child[i+1]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } - if(res & 4) { stack[stack_pos++] = node->child[i+2]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } - if(res & 8) { stack[stack_pos++] = node->child[i+3]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } - - i += 4; - } - while(i < node->nchilds) + return !RE_rayobject_isAligned(node); +} + +template<int MAX_STACK_SIZE, bool SHADOW> +static int svbvh_node_stack_raycast(SVBVHNode *root, Isect *isec) +{ + SVBVHNode *stack[MAX_STACK_SIZE], *node; + int hit = 0, stack_pos = 0; + + stack[stack_pos++] = root; + + while(stack_pos) { - if(RE_rayobject_bb_intersect_test(isec, (const float*)node->child_bb+6*i)) - stack[stack_pos++] = node->child[i]; - i++; + node = stack[--stack_pos]; + + if(!svbvh_node_is_leaf(node)) + { + int nchilds= node->nchilds; + + if(nchilds == 4) { + float *child_bb= node->child_bb; + int res = svbvh_bb_intersect_test_simd4(isec, ((__m128*) (child_bb))); + SVBVHNode **child= node->child; + + RE_RC_COUNT(isec->raycounter->simd_bb.test); + + if(res & 1) { stack[stack_pos++] = child[0]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } + if(res & 2) { stack[stack_pos++] = child[1]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } + if(res & 4) { stack[stack_pos++] = child[2]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } + if(res & 8) { stack[stack_pos++] = child[3]; RE_RC_COUNT(isec->raycounter->simd_bb.hit); } + } + else { + float *child_bb= node->child_bb; + SVBVHNode **child= node->child; + int i; + + for(i=0; i<nchilds; i++) + if(svbvh_bb_intersect_test(isec, (float*)child_bb+6*i)) + stack[stack_pos++] = child[i]; + } + } + else + { + hit |= RE_rayobject_intersect((RayObject*)node, isec); + if(SHADOW && hit) break; + } } + + return hit; } + template<> inline void bvh_node_merge_bb<SVBVHNode>(SVBVHNode *node, float *min, float *max) { if(is_leaf(node)) { - RE_rayobject_merge_bb( (RayObject*)node, min, max); + RE_rayobject_merge_bb((RayObject*)node, min, max); } else { @@ -156,15 +233,13 @@ struct Reorganize_SVBVH { SVBVHNode *node = (SVBVHNode*)BLI_memarena_alloc(arena, sizeof(SVBVHNode)); node->nchilds = nchilds; - node->child_bb = (float*)BLI_memarena_alloc(arena, sizeof(float)*6*nchilds); - node->child= (SVBVHNode**)BLI_memarena_alloc(arena, sizeof(SVBVHNode*)*nchilds); return node; } void copy_bb(float *bb, const float *old_bb) { - std::copy( old_bb, old_bb+6, bb ); + std::copy(old_bb, old_bb+6, bb); } void prepare_for_simd(SVBVHNode *node) @@ -174,7 +249,7 @@ struct Reorganize_SVBVH { float vec_tmp[4*6]; float *res = node->child_bb+6*i; - std::copy( res, res+6*4, vec_tmp); + std::copy(res, res+6*4, vec_tmp); for(int j=0; j<6; j++) { @@ -231,7 +306,7 @@ struct Reorganize_SVBVH { float bb[6]; INIT_MINMAX(bb, bb+3); - RE_rayobject_merge_bb( (RayObject*)o_child, bb, bb+3); + RE_rayobject_merge_bb((RayObject*)o_child, bb, bb+3); copy_bb(node->child_bb+i*6, bb); break; } @@ -240,7 +315,7 @@ struct Reorganize_SVBVH copy_bb(node->child_bb+i*6, o_child->bb); } } - assert( i == 0 ); + assert(i == 0); prepare_for_simd(node); @@ -251,3 +326,4 @@ struct Reorganize_SVBVH #endif #endif //__SSE__ + diff --git a/source/blender/render/intern/raytrace/vbvh.h b/source/blender/render/intern/raytrace/vbvh.h index a5ca093de2a..06188ede8c6 100644 --- a/source/blender/render/intern/raytrace/vbvh.h +++ b/source/blender/render/intern/raytrace/vbvh.h @@ -26,12 +26,13 @@ * * ***** END GPL LICENSE BLOCK ***** */ -#include <assert.h> +#include <assert.h> #include <algorithm> -#include "rayobject_rtbuild.h" + #include "BLI_memarena.h" -#include "BLI_utildefines.h" + +#include "rayobject_rtbuild.h" /* * VBVHNode represents a BVHNode with support for a variable number of childrens @@ -167,12 +168,11 @@ struct BuildBinaryVBVH Node *node = create_node(); - INIT_MINMAX(node->bb, node->bb+3); - rtbuild_merge_bb(builder, node->bb, node->bb+3); - Node **child = &node->child; int nc = rtbuild_split(builder); + INIT_MINMAX(node->bb, node->bb+3); + assert(nc == 2); for(int i=0; i<nc; i++) { @@ -180,6 +180,8 @@ struct BuildBinaryVBVH rtbuild_get_child(builder, i, &tmp); *child = _transform(&tmp); + DO_MIN((*child)->bb, node->bb); + DO_MAX((*child)->bb+3, node->bb+3); child = &((*child)->sibling); } |