Revision: 23649 http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=23649 Author: jaguarandi Date: 2009-10-06 04:56:11 +0200 (Tue, 06 Oct 2009)
Log Message: ----------- Merged Soc 2009 - raytrace optimization [0] from branch [1] at rev 23647 [0] - http://wiki.blender.org/index.php/User:Jaguarandi/SummerOfCode2009/ [1] - https://svn.blender.org/svnroot/bf-blender/branches/soc-2009-jaguarandi Revision Links: -------------- http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=23647 Modified Paths: -------------- trunk/blender/release/scripts/ui/buttons_scene.py trunk/blender/source/blender/blenkernel/BKE_utildefines.h trunk/blender/source/blender/blenlib/BLI_memarena.h trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c trunk/blender/source/blender/blenlib/intern/BLI_memarena.c trunk/blender/source/blender/editors/armature/meshlaplacian.c trunk/blender/source/blender/makesdna/DNA_scene_types.h trunk/blender/source/blender/makesrna/intern/rna_scene.c trunk/blender/source/blender/render/SConscript trunk/blender/source/blender/render/extern/include/RE_raytrace.h trunk/blender/source/blender/render/extern/include/RE_shader_ext.h trunk/blender/source/blender/render/intern/include/render_types.h trunk/blender/source/blender/render/intern/include/rendercore.h trunk/blender/source/blender/render/intern/source/pipeline.c trunk/blender/source/blender/render/intern/source/rayshade.c trunk/blender/source/blender/render/intern/source/rendercore.c trunk/blender/source/blender/render/intern/source/renderdatabase.c trunk/blender/source/blender/render/intern/source/shadeinput.c trunk/blender/source/blender/render/intern/source/volume_precache.c trunk/blender/source/blender/render/intern/source/volumetric.c trunk/blender/source/blender/windowmanager/intern/wm_init_exit.c Added Paths: ----------- trunk/blender/source/blender/render/intern/include/raycounter.h trunk/blender/source/blender/render/intern/include/rayobject.h trunk/blender/source/blender/render/intern/raytrace/ trunk/blender/source/blender/render/intern/raytrace/bvh.h trunk/blender/source/blender/render/intern/raytrace/rayobject.cpp trunk/blender/source/blender/render/intern/raytrace/rayobject_hint.h trunk/blender/source/blender/render/intern/raytrace/rayobject_qbvh.cpp trunk/blender/source/blender/render/intern/raytrace/rayobject_rtbuild.cpp trunk/blender/source/blender/render/intern/raytrace/rayobject_rtbuild.h trunk/blender/source/blender/render/intern/raytrace/rayobject_svbvh.cpp trunk/blender/source/blender/render/intern/raytrace/rayobject_vbvh.cpp trunk/blender/source/blender/render/intern/raytrace/reorganize.h trunk/blender/source/blender/render/intern/raytrace/svbvh.h trunk/blender/source/blender/render/intern/raytrace/vbvh.h trunk/blender/source/blender/render/intern/source/rayobject_blibvh.c trunk/blender/source/blender/render/intern/source/rayobject_instance.c trunk/blender/source/blender/render/intern/source/rayobject_octree.c trunk/blender/source/blender/render/intern/source/rayobject_raycounter.c Removed Paths: ------------- trunk/blender/source/blender/render/intern/source/raytrace.c Modified: trunk/blender/release/scripts/ui/buttons_scene.py =================================================================== --- trunk/blender/release/scripts/ui/buttons_scene.py 2009-10-06 02:45:42 UTC (rev 23648) +++ trunk/blender/release/scripts/ui/buttons_scene.py 2009-10-06 02:56:11 UTC (rev 23649) @@ -179,8 +179,13 @@ sub.itemR(rd, "free_image_textures") sub = col.column() sub.active = rd.render_raytracing - sub.itemL(text="Ray Tracing Octree:") - sub.itemR(rd, "octree_resolution", text="") + sub.itemL(text="Acceleration structure:") + sub.itemR(rd, "raytrace_structure", text="") + if rd.raytrace_structure == "OCTREE": + sub.itemR(rd, "octree_resolution", text="Resolution") + else: + sub.itemR(rd, "use_instances", text="Instances") + sub.itemR(rd, "use_local_coords", text="Local Coordinates") class SCENE_PT_post_processing(RenderButtonsPanel): __label__ = "Post Processing" Modified: trunk/blender/source/blender/blenkernel/BKE_utildefines.h =================================================================== --- trunk/blender/source/blender/blenkernel/BKE_utildefines.h 2009-10-06 02:45:42 UTC (rev 23648) +++ trunk/blender/source/blender/blenkernel/BKE_utildefines.h 2009-10-06 02:56:11 UTC (rev 23649) @@ -75,6 +75,14 @@ #define INIT_MINMAX2(min, max) { (min)[0]= (min)[1]= 1.0e30f; (max)[0]= (max)[1]= -1.0e30f; } +#define DO_MIN(vec, min) { if( (min)[0]>(vec)[0] ) (min)[0]= (vec)[0]; \ + if( (min)[1]>(vec)[1] ) (min)[1]= (vec)[1]; \ + if( (min)[2]>(vec)[2] ) (min)[2]= (vec)[2]; } \ + +#define DO_MAX(vec, max) { if( (max)[0]<(vec)[0] ) (max)[0]= (vec)[0]; \ + if( (max)[1]<(vec)[1] ) (max)[1]= (vec)[1]; \ + if( (max)[2]<(vec)[2] ) (max)[2]= (vec)[2]; } \ + #define DO_MINMAX(vec, min, max) { if( (min)[0]>(vec)[0] ) (min)[0]= (vec)[0]; \ if( (min)[1]>(vec)[1] ) (min)[1]= (vec)[1]; \ if( (min)[2]>(vec)[2] ) (min)[2]= (vec)[2]; \ Modified: trunk/blender/source/blender/blenlib/BLI_memarena.h =================================================================== --- trunk/blender/source/blender/blenlib/BLI_memarena.h 2009-10-06 02:45:42 UTC (rev 23648) +++ trunk/blender/source/blender/blenlib/BLI_memarena.h 2009-10-06 02:56:11 UTC (rev 23649) @@ -37,6 +37,10 @@ #ifndef BLI_MEMARENA_H #define BLI_MEMARENA_H +#ifdef __cplusplus +extern "C" { +#endif + /* A reasonable standard buffer size, big * enough to not cause much internal fragmentation, * small enough not to waste resources @@ -53,7 +57,14 @@ void BLI_memarena_use_malloc (struct MemArena *ma); void BLI_memarena_use_calloc (struct MemArena *ma); +void BLI_memarena_use_align(struct MemArena *ma, int align); + void* BLI_memarena_alloc (struct MemArena *ma, int size); +#ifdef __cplusplus +} #endif + +#endif + Modified: trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c =================================================================== --- trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2009-10-06 02:45:42 UTC (rev 23648) +++ trunk/blender/source/blender/blenlib/intern/BLI_kdopbvh.c 2009-10-06 02:56:11 UTC (rev 23649) @@ -52,6 +52,7 @@ { struct BVHNode **children; struct BVHNode *parent; // some user defined traversed need that + struct BVHNode *skip[2]; float *bv; // Bounding volume of all nodes, max 13 axis int index; // face, edge, vertex index char totnode; // how many nodes are used, used for speedup @@ -101,6 +102,8 @@ BVHTreeRay ray; float ray_dot_axis[13]; + float idot_axis[13]; + int index[6]; BVHTreeRayHit hit; } BVHRayCastData; @@ -353,7 +356,24 @@ } ////////////////////////////////////////////////////////////////////////////////////////////////////// +static void build_skip_links(BVHTree *tree, BVHNode *node, BVHNode *left, BVHNode *right) +{ + int i; + + node->skip[0] = left; + node->skip[1] = right; + + for (i = 0; i < node->totnode; i++) + { + if(i+1 < node->totnode) + build_skip_links(tree, node->children[i], left, node->children[i+1] ); + else + build_skip_links(tree, node->children[i], left, right ); + left = node->children[i]; + } +} + /* * BVHTree bounding volumes functions */ @@ -939,6 +959,7 @@ for(i = 0; i < tree->totbranch; i++) tree->nodes[tree->totleaf + i] = branches_array + i; + build_skip_links(tree, tree->nodes[tree->totleaf], NULL, NULL); //bvhtree_info(tree); } @@ -1405,6 +1426,7 @@ * raycast is done by performing a DFS on the BVHTree and saving the closest hit */ + //Determines the distance that the ray must travel to hit the bounding volume of the given node static float ray_nearest_hit(BVHRayCastData *data, float *bv) { @@ -1443,13 +1465,40 @@ return low; } +//Determines the distance that the ray must travel to hit the bounding volume of the given node +//Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe +//[http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9] +// +//TODO this doens't has data->ray.radius in consideration +static float fast_ray_nearest_hit(const BVHRayCastData *data, const BVHNode *node) +{ + const float *bv = node->bv; + float dist; + + float t1x = (bv[data->index[0]] - data->ray.origin[0]) * data->idot_axis[0]; + float t2x = (bv[data->index[1]] - data->ray.origin[0]) * data->idot_axis[0]; + float t1y = (bv[data->index[2]] - data->ray.origin[1]) * data->idot_axis[1]; + float t2y = (bv[data->index[3]] - data->ray.origin[1]) * data->idot_axis[1]; + float t1z = (bv[data->index[4]] - data->ray.origin[2]) * data->idot_axis[2]; + float t2z = (bv[data->index[5]] - data->ray.origin[2]) * data->idot_axis[2]; + + if(t1x > t2y || t2x < t1y || t1x > t2z || t2x < t1z || t1y > t2z || t2y < t1z) return FLT_MAX; + if(t2x < 0.0 || t2y < 0.0 || t2z < 0.0) return FLT_MAX; + if(t1x > data->hit.dist || t1y > data->hit.dist || t1z > data->hit.dist) return FLT_MAX; + + dist = t1x; + if (t1y > dist) dist = t1y; + if (t1z > dist) dist = t1z; + return dist; +} + static void dfs_raycast(BVHRayCastData *data, BVHNode *node) { int i; //ray-bv is really fast.. and simple tests revealed its worth to test it //before calling the ray-primitive functions - float dist = ray_nearest_hit(data, node->bv); + float dist = fast_ray_nearest_hit(data, node); if(dist >= data->hit.dist) return; if(node->totnode == 0) @@ -1483,6 +1532,37 @@ } } +static void iterative_raycast(BVHRayCastData *data, BVHNode *node) +{ + while(node) + { + float dist = fast_ray_nearest_hit(data, node); + if(dist >= data->hit.dist) + { + node = node->skip[1]; + continue; + } + + if(node->totnode == 0) + { + if(data->callback) + data->callback(data->userdata, node->index, &data->ray, &data->hit); + else + { + data->hit.index = node->index; + data->hit.dist = dist; + VECADDFAC(data->hit.co, data->ray.origin, data->ray.direction, dist); + } + + node = node->skip[1]; + } + else + { + node = node->children[0]; + } + } +} + int BLI_bvhtree_ray_cast(BVHTree *tree, const float *co, const float *dir, float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata) { int i; @@ -1503,9 +1583,16 @@ for(i=0; i<3; i++) { data.ray_dot_axis[i] = INPR( data.ray.direction, KDOP_AXES[i]); + data.idot_axis[i] = 1.0f / data.ray_dot_axis[i]; if(fabs(data.ray_dot_axis[i]) < FLT_EPSILON) + { data.ray_dot_axis[i] = 0.0; + } + data.index[2*i] = data.idot_axis[i] < 0.0 ? 1 : 0; + data.index[2*i+1] = 1 - data.index[2*i]; + data.index[2*i] += 2*i; + data.index[2*i+1] += 2*i; } @@ -1518,7 +1605,10 @@ } if(root) + { dfs_raycast(&data, root); +// iterative_raycast(&data, root); + } if(hit) Modified: trunk/blender/source/blender/blenlib/intern/BLI_memarena.c =================================================================== --- trunk/blender/source/blender/blenlib/intern/BLI_memarena.c 2009-10-06 02:45:42 UTC (rev 23648) +++ trunk/blender/source/blender/blenlib/intern/BLI_memarena.c 2009-10-06 02:56:11 UTC (rev 23649) @@ -45,6 +45,7 @@ int bufsize, cursize; int use_calloc; + int align; LinkNode *bufs; }; @@ -52,6 +53,7 @@ MemArena *BLI_memarena_new(int bufsize) { MemArena *ma= MEM_callocN(sizeof(*ma), "memarena"); ma->bufsize= bufsize; + ma->align = 8; return ma; } @@ -64,6 +66,11 @@ ma->use_calloc= 0; } +void BLI_memarena_use_align(struct MemArena *ma, int align) { + /* align should be a power of two */ + ma->align = align; +} + void BLI_memarena_free(MemArena *ma) { BLI_linklist_free(ma->bufs, (void(*)(void*)) MEM_freeN); MEM_freeN(ma); @@ -77,16 +84,28 @@ /* ensure proper alignment by rounding * size up to multiple of 8 */ - size= PADUP(size, 8); + size= PADUP(size, ma->align); if (size>ma->cursize) { - ma->cursize= (size>ma->bufsize)?size:ma->bufsize; + unsigned char *tmp; + + if(size > ma->bufsize - (ma->align - 1)) + { + ma->cursize = PADUP(size+1, ma->align); + } + else ma->cursize = ma->bufsize; + if(ma->use_calloc) ma->curbuf= MEM_callocN(ma->cursize, "memarena calloc"); else ma->curbuf= MEM_mallocN(ma->cursize, "memarena malloc"); BLI_linklist_prepend(&ma->bufs, ma->curbuf); + + /* align alloc'ed memory (needed if align > 8) */ + tmp = (unsigned char*)PADUP( (intptr_t) ma->curbuf, ma->align); + ma->cursize -= (tmp - ma->curbuf); + ma->curbuf = tmp; } ptr= ma->curbuf; @@ -95,3 +114,4 @@ return ptr; } + Modified: trunk/blender/source/blender/editors/armature/meshlaplacian.c =================================================================== --- trunk/blender/source/blender/editors/armature/meshlaplacian.c 2009-10-06 02:45:42 UTC (rev 23648) +++ trunk/blender/source/blender/editors/armature/meshlaplacian.c 2009-10-06 02:56:11 UTC (rev 23649) @@ -105,8 +105,9 @@ float *p; /* values from all p vectors */ float *mindist; /* minimum distance to a bone for all vertices */ - RayTree *raytree; /* ray tracing acceleration structure */ - MFace **vface; /* a face that the vertex belongs to */ + RayObject *raytree; /* ray tracing acceleration structure */ + RayFace *faces; /* faces to add to the ray tracing struture */ + MFace **vface; /* a face that the vertex belongs to */ } heat; #ifdef RIGID_DEFORM @@ -394,75 +395,41 @@ #define DISTANCE_EPSILON 1e-4f /* Raytracing for vertex to bone visibility */ - -static LaplacianSystem *HeatSys = NULL; - -static void heat_ray_coords_func(RayFace *face, float **v1, float **v2, float **v3, float **v4) -{ @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org http://lists.blender.org/mailman/listinfo/bf-blender-cvs