Revision: 21413 http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21413 Author: jaguarandi Date: 2009-07-07 21:07:53 +0200 (Tue, 07 Jul 2009)
Log Message: ----------- made rtbuild object_heuristic_spliter faster I think its something like: old was: 4*nlogn + 3*(n*6) new is: (2*nlogn + 3*(n*6)) * f, with f<1 Still missing changing the sorting function to an introsort instead of qsort Other options like bucketing sort may be worth trying (for very large trees) Modified Paths: -------------- branches/soc-2009-jaguarandi/source/blender/blenkernel/BKE_utildefines.h branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bih.c branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_blibvh.c branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c Modified: branches/soc-2009-jaguarandi/source/blender/blenkernel/BKE_utildefines.h =================================================================== --- branches/soc-2009-jaguarandi/source/blender/blenkernel/BKE_utildefines.h 2009-07-07 18:58:11 UTC (rev 21412) +++ branches/soc-2009-jaguarandi/source/blender/blenkernel/BKE_utildefines.h 2009-07-07 19:07:53 UTC (rev 21413) @@ -80,6 +80,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: branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h =================================================================== --- branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h 2009-07-07 18:58:11 UTC (rev 21412) +++ branches/soc-2009-jaguarandi/source/blender/render/intern/include/rayobject_rtbuild.h 2009-07-07 19:07:53 UTC (rev 21413) @@ -52,6 +52,8 @@ /* child partitions calculated during splitting */ int child_offset[RTBUILD_MAX_CHILDS+1]; + + int child_sorted_axis; /* -1 if not sorted */ } RTBuilder; Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bih.c =================================================================== --- branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bih.c 2009-07-07 18:58:11 UTC (rev 21412) +++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bih.c 2009-07-07 19:07:53 UTC (rev 21413) @@ -102,9 +102,8 @@ static void bih_bb(BIHTree *obj, float *min, float *max) { - //TODO only half operations needed - DO_MINMAX(obj->bb[0], min, max); - DO_MINMAX(obj->bb[1], min, max); + DO_MIN(obj->bb[0], min); + DO_MAX(obj->bb[1], max); } /* @@ -213,8 +212,8 @@ parent->bi[i][0] = cbb[parent->split_axis]; parent->bi[i][1] = cbb[parent->split_axis+3]; - DO_MINMAX(cbb , bb, bb+3); - DO_MINMAX(cbb+3, bb, bb+3); + DO_MIN(cbb , bb); + DO_MAX(cbb+3, bb+3); } for(; i<BIH_NCHILDS; i++) { Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_blibvh.c =================================================================== --- branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_blibvh.c 2009-07-07 18:58:11 UTC (rev 21412) +++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_blibvh.c 2009-07-07 19:07:53 UTC (rev 21413) @@ -110,8 +110,8 @@ INIT_MINMAX(min_max, min_max+3); RE_rayobject_merge_bb(ob, min_max, min_max+3); - DO_MINMAX(min_max , obj->bb[0], obj->bb[1]); - DO_MINMAX(min_max+3, obj->bb[0], obj->bb[1]); + DO_MIN(min_max , obj->bb[0]); + DO_MAX(min_max+3, obj->bb[1]); BLI_bvhtree_insert(obj->bvh, (int)ob, min_max, 2 ); } @@ -135,6 +135,6 @@ static void RayObject_blibvh_bb(RayObject *o, float *min, float *max) { BVHObject *obj = (BVHObject*)o; - DO_MINMAX( obj->bb[0], min, max ); - DO_MINMAX( obj->bb[1], min, max ); + DO_MIN( obj->bb[0], min ); + DO_MAX( obj->bb[1], max ); } Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c =================================================================== --- branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c 2009-07-07 18:58:11 UTC (rev 21412) +++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_bvh.c 2009-07-07 19:07:53 UTC (rev 21413) @@ -133,9 +133,8 @@ { if(RayObject_isAligned(node)) { - //TODO only half operations needed - DO_MINMAX(node->bb , min, max); - DO_MINMAX(node->bb+3, min, max); + DO_MIN(node->bb , min); + DO_MAX(node->bb+3, max); } else { Modified: branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c =================================================================== --- branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c 2009-07-07 18:58:11 UTC (rev 21412) +++ branches/soc-2009-jaguarandi/source/blender/render/intern/source/rayobject_rtbuild.c 2009-07-07 19:07:53 UTC (rev 21413) @@ -19,6 +19,7 @@ b->begin = begin; b->end = end; b->split_axis = 0; + b->child_sorted_axis = -1; for(i=0; i<RTBUILD_MAX_CHILDS; i++) b->child_offset[i] = 0; @@ -46,6 +47,7 @@ RTBuilder* rtbuild_get_child(RTBuilder *b, int child, RTBuilder *tmp) { rtbuild_init( tmp, b->begin + b->child_offset[child], b->begin + b->child_offset[child+1] ); + tmp->child_sorted_axis = b->child_sorted_axis; return tmp; } @@ -254,12 +256,14 @@ float bb_area(float *min, float *max) { - float sub[3]; + float sub[3], a; sub[0] = max[0]-min[0]; sub[1] = max[1]-min[1]; sub[2] = max[2]-min[2]; - return (sub[0]*sub[1] + sub[0]*sub[2] + sub[1]*sub[2])*2; + a = (sub[0]*sub[1] + sub[0]*sub[2] + sub[1]*sub[2])*2; + assert(a >= 0.0); + return a; } int rtbuild_heuristic_object_split(RTBuilder *b, int nchilds) @@ -274,7 +278,7 @@ else { float bcost = FLT_MAX; - int i, axis, baxis, boffset; + int i, axis, baxis, boffset, k, try_axis[3]; CostObject *cost = MEM_mallocN( sizeof(CostObject)*size, "RTBuilder.HeuristicObjectSplitter" ); float *acc_bb = MEM_mallocN( sizeof(float)*6*size, "RTBuilder.HeuristicObjectSplitterBB" ); @@ -285,8 +289,21 @@ RE_rayobject_merge_bb(b->begin[i], cost[i].bb, cost[i].bb+3); } - for(axis=0; axis<3; axis++) + if(b->child_sorted_axis >= 0 && b->child_sorted_axis < 3) { + try_axis[0] = b->child_sorted_axis; + try_axis[1] = (b->child_sorted_axis+1)%3; + try_axis[2] = (b->child_sorted_axis+2)%3; + } + else + { + try_axis[0] = 0; + try_axis[1] = 1; + try_axis[2] = 2; + } + + for(axis=try_axis[k=0]; k<3; axis=try_axis[++k]) + { float other_bb[6]; costobject_sort(cost, cost+size, axis); @@ -295,37 +312,54 @@ float *bb = acc_bb+i*6; if(i == size-1) { - INIT_MINMAX( bb, bb+3 ); + VECCOPY(bb, cost[i].bb); + VECCOPY(bb+3, cost[i].bb+3); } else { - VECCOPY( bb, bb+6 ); - VECCOPY( bb+3, bb+6+3 ); + bb[0] = MIN2(cost[i].bb[0], bb[6+0]); + bb[1] = MIN2(cost[i].bb[1], bb[6+1]); + bb[2] = MIN2(cost[i].bb[2], bb[6+2]); + + bb[3] = MAX2(cost[i].bb[3], bb[6+3]); + bb[4] = MAX2(cost[i].bb[4], bb[6+4]); + bb[5] = MAX2(cost[i].bb[5], bb[6+5]); } - RE_rayobject_merge_bb( cost[i].obj, bb, bb+3 ); } INIT_MINMAX(other_bb, other_bb+3); - DO_MINMAX( cost[0].bb, other_bb, other_bb+3 ); - DO_MINMAX( cost[0].bb+3, other_bb, other_bb+3 ); + DO_MIN( cost[0].bb, other_bb ); + DO_MAX( cost[0].bb+3, other_bb+3 ); for(i=1; i<size; i++) { //Worst case heuristic (cost of each child is linear) - float hcost = bb_area(other_bb, other_bb+3)*(i+log(i)) + bb_area(acc_bb+i*6, acc_bb+i*6+3)*(size-i+log(size-i)); - if(hcost < bcost) + float hcost, left_side, right_side; + + left_side = bb_area(other_bb, other_bb+3)*(i+logf(i)); + right_side= bb_area(acc_bb+i*6, acc_bb+i*6+3)*(size-i+logf(size-i)); + + if(left_side > bcost) break; //No way we can find a better heuristic in this axis + + hcost = left_side+right_side; + if( hcost < bcost + || (hcost == bcost && axis < baxis)) //this makes sure the tree built is the same whatever is the order of the sorting axis { bcost = hcost; baxis = axis; boffset = i; } - DO_MINMAX( cost[i].bb, other_bb, other_bb+3 ); - DO_MINMAX( cost[i].bb+3, other_bb, other_bb+3 ); + DO_MIN( cost[i].bb, other_bb ); + DO_MAX( cost[i].bb+3, other_bb+3 ); } + + if(baxis == axis) + { + for(i=0; i<size; i++) + b->begin[i] = cost[i].obj; + b->child_sorted_axis = axis; + } } - costobject_sort(cost, cost+size, baxis); - for(i=0; i<size; i++) - b->begin[i] = cost[i].obj; b->child_offset[0] = 0; b->child_offset[1] = boffset; _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org http://lists.blender.org/mailman/listinfo/bf-blender-cvs