diff options
Diffstat (limited to 'source/blender/render/intern/raytrace/reorganize.h')
-rw-r--r-- | source/blender/render/intern/raytrace/reorganize.h | 188 |
1 files changed, 75 insertions, 113 deletions
diff --git a/source/blender/render/intern/raytrace/reorganize.h b/source/blender/render/intern/raytrace/reorganize.h index 68b2b22ecdd..1930e5bb32b 100644 --- a/source/blender/render/intern/raytrace/reorganize.h +++ b/source/blender/render/intern/raytrace/reorganize.h @@ -66,17 +66,15 @@ void reorganize_find_fittest_parent(Node *tree, Node *node, std::pair<float,Node std::queue<Node*> q; q.push(tree); - while(!q.empty()) - { + while (!q.empty()) { Node *parent = q.front(); q.pop(); - if(parent == node) continue; - if(node_fits_inside(node, parent) && RE_rayobject_isAligned(parent->child) ) - { + if (parent == node) continue; + if (node_fits_inside(node, parent) && RE_rayobject_isAligned(parent->child) ) { float pcost = bb_area(parent->bb, parent->bb+3); cost = std::min( cost, std::make_pair(pcost,parent) ); - for(Node *child = parent->child; child; child = child->sibling) + for (Node *child = parent->child; child; child = child->sibling) q.push(child); } } @@ -89,28 +87,23 @@ void reorganize(Node *root) std::queue<Node*> q; q.push(root); - while(!q.empty()) - { + while (!q.empty()) { Node * node = q.front(); q.pop(); - if( RE_rayobject_isAligned(node->child) ) - { - for(Node **prev = &node->child; *prev; ) - { + if (RE_rayobject_isAligned(node->child)) { + for (Node **prev = &node->child; *prev; ) { assert( RE_rayobject_isAligned(*prev) ); q.push(*prev); std::pair<float,Node*> best(FLT_MAX, root); reorganize_find_fittest_parent( root, *prev, best ); - if(best.second == node) - { + if (best.second == node) { //Already inside the fitnest BB prev = &(*prev)->sibling; } - else - { + else { Node *tmp = *prev; *prev = (*prev)->sibling; @@ -123,8 +116,7 @@ void reorganize(Node *root) } } - if(node != root) - { + if (node != root) { } } } @@ -137,29 +129,24 @@ void reorganize(Node *root) template<class Node> void remove_useless(Node *node, Node **new_node) { - if( RE_rayobject_isAligned(node->child) ) - { + if ( RE_rayobject_isAligned(node->child) ) { - for(Node **prev = &node->child; *prev; ) - { + for (Node **prev = &node->child; *prev; ) { Node *next = (*prev)->sibling; remove_useless(*prev, prev); - if(*prev == NULL) + if (*prev == NULL) *prev = next; - else - { + else { (*prev)->sibling = next; prev = &((*prev)->sibling); } } } - if(node->child) - { - if(RE_rayobject_isAligned(node->child) && node->child->sibling == 0) + if (node->child) { + if (RE_rayobject_isAligned(node->child) && node->child->sibling == 0) *new_node = node->child; } - else if(node->child == NULL) - { + else if (node->child == NULL) { *new_node = NULL; } } @@ -171,18 +158,16 @@ void remove_useless(Node *node, Node **new_node) template<class Node> void pushup(Node *parent) { - if(is_leaf(parent)) return; + if (is_leaf(parent)) return; float p_area = bb_area(parent->bb, parent->bb+3); Node **prev = &parent->child; - for(Node *child = parent->child; RE_rayobject_isAligned(child) && child; ) - { + for (Node *child = parent->child; RE_rayobject_isAligned(child) && child; ) { const float c_area = bb_area(child->bb, child->bb + 3); const int nchilds = count_childs(child); float original_cost = ((p_area != 0.0f)? (c_area / p_area)*nchilds: 1.0f) + 1; float flatten_cost = nchilds; - if(flatten_cost < original_cost && nchilds >= 2) - { + if (flatten_cost < original_cost && nchilds >= 2) { append_sibling(child, child->child); child = child->sibling; *prev = child; @@ -192,15 +177,14 @@ void pushup(Node *parent) // child = *prev; tot_pushup++; } - else - { + else { *prev = child; prev = &(*prev)->sibling; child = *prev; } } - for(Node *child = parent->child; RE_rayobject_isAligned(child) && child; child = child->sibling) + for (Node *child = parent->child; RE_rayobject_isAligned(child) && child; child = child->sibling) pushup(child); } @@ -210,30 +194,27 @@ void pushup(Node *parent) template<class Node, int SSize> void pushup_simd(Node *parent) { - if(is_leaf(parent)) return; + if (is_leaf(parent)) return; int n = count_childs(parent); Node **prev = &parent->child; - for(Node *child = parent->child; RE_rayobject_isAligned(child) && child; ) - { + for (Node *child = parent->child; RE_rayobject_isAligned(child) && child; ) { int cn = count_childs(child); - if(cn-1 <= (SSize - (n%SSize) ) % SSize && RE_rayobject_isAligned(child->child) ) - { + if (cn-1 <= (SSize - (n%SSize) ) % SSize && RE_rayobject_isAligned(child->child) ) { n += (cn - 1); append_sibling(child, child->child); child = child->sibling; *prev = child; } - else - { + else { *prev = child; prev = &(*prev)->sibling; child = *prev; } } - for(Node *child = parent->child; RE_rayobject_isAligned(child) && child; child = child->sibling) + for (Node *child = parent->child; RE_rayobject_isAligned(child) && child; child = child->sibling) pushup_simd<Node,SSize>(child); } @@ -248,19 +229,17 @@ void pushdown(Node *parent) Node **s_child = &parent->child; Node * child = parent->child; - while(child && RE_rayobject_isAligned(child)) - { + while (child && RE_rayobject_isAligned(child)) { Node *next = child->sibling; Node **next_s_child = &child->sibling; //assert(bb_fits_inside(parent->bb, parent->bb+3, child->bb, child->bb+3)); - for(Node *i = parent->child; RE_rayobject_isAligned(i) && i; i = i->sibling) - if(child != i && bb_fits_inside(i->bb, i->bb+3, child->bb, child->bb+3) && RE_rayobject_isAligned(i->child)) - { + for (Node *i = parent->child; RE_rayobject_isAligned(i) && i; i = i->sibling) + if (child != i && bb_fits_inside(i->bb, i->bb+3, child->bb, child->bb+3) && RE_rayobject_isAligned(i->child)) { // todo optimize (should the one with the smallest area?) // float ia = bb_area(i->bb, i->bb+3) -// if(child->i) +// if (child->i) *s_child = child->sibling; child->sibling = i->child; i->child = child; @@ -286,18 +265,17 @@ void pushdown(Node *parent) template<class Node> float bvh_refit(Node *node) { - if(is_leaf(node)) return 0; - if(is_leaf(node->child)) return 0; + if (is_leaf(node)) return 0; + if (is_leaf(node->child)) return 0; float total = 0; - for(Node *child = node->child; child; child = child->sibling) + for (Node *child = node->child; child; child = child->sibling) total += bvh_refit(child); float old_area = bb_area(node->bb, node->bb+3); INIT_MINMAX(node->bb, node->bb+3); - for(Node *child = node->child; child; child = child->sibling) - { + for (Node *child = node->child; child; child = child->sibling) { DO_MIN(child->bb, node->bb); DO_MAX(child->bb+3, node->bb+3); } @@ -347,32 +325,27 @@ struct OVBVHNode int best_cutsize; void set_cut(int cutsize, OVBVHNode ***cut) { - if(cutsize == 1) - { + if (cutsize == 1) { **cut = this; *cut = &(**cut)->sibling; } - else - { - if(cutsize > MAX_CUT_SIZE) - { - for(OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) - { + else { + if (cutsize > MAX_CUT_SIZE) { + for (OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) { child->set_cut( 1, cut ); cutsize--; } assert(cutsize == 0); } else - for(OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) + for (OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) child->set_cut( child->get_cut_size( cutsize ), cut ); } } void optimize() { - if(RE_rayobject_isAligned(this->child)) - { + if (RE_rayobject_isAligned(this->child)) { //Calc new childs { OVBVHNode **cut = &(this->child); @@ -381,7 +354,7 @@ struct OVBVHNode } //Optimize new childs - for(OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) + for (OVBVHNode *child = this->child; child && RE_rayobject_isAligned(child); child = child->sibling) child->optimize(); } } @@ -415,8 +388,7 @@ struct VBVH_optimalPackSIMD //Fetch childs and needed data { float parent_area = bb_area(node->bb, node->bb+3); - for(Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) - { + for (Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) { this->child[nchilds] = child; this->child_hit_prob[nchilds] = (parent_area != 0.0f)? bb_area(child->bb, child->bb+3) / parent_area: 1.0f; nchilds++; @@ -427,36 +399,35 @@ struct VBVH_optimalPackSIMD //Build DP table to find minimum cost to represent this node with a given cutsize - int bt [MAX_OPTIMIZE_CHILDS+1][MAX_CUT_SIZE+1]; //backtrace table - float cost[MAX_OPTIMIZE_CHILDS+1][MAX_CUT_SIZE+1]; //cost table (can be reduced to float[2][MAX_CUT_COST]) + int bt [MAX_OPTIMIZE_CHILDS + 1][MAX_CUT_SIZE + 1]; //backtrace table + float cost[MAX_OPTIMIZE_CHILDS + 1][MAX_CUT_SIZE + 1]; //cost table (can be reduced to float[2][MAX_CUT_COST]) - for(int i=0; i<=nchilds; i++) - for(int j=0; j<=MAX_CUT_SIZE; j++) - cost[i][j] = INFINITY; + for (int i = 0; i <= nchilds; i++) { + for (int j = 0; j <= MAX_CUT_SIZE; j++) { + cost[i][j] = INFINITY; + } + } cost[0][0] = 0; - for(int i=1; i<=nchilds; i++) - for(int size=i-1; size/*+(nchilds-i)*/<=MAX_CUT_SIZE; size++) - for(int cut=1; cut+size/*+(nchilds-i)*/<=MAX_CUT_SIZE; cut++) - { - float new_cost = cost[i-1][size] + child_hit_prob[i-1]*child[i-1]->get_cost(cut); - if(new_cost < cost[i][size+cut]) - { - cost[i][size+cut] = new_cost; - bt[i][size+cut] = cut; + for (int i = 1; i<=nchilds; i++) { + for (int size = i - 1; size/*+(nchilds-i)*/<=MAX_CUT_SIZE; size++) { + for (int cut = 1; cut+size/*+(nchilds-i)*/<=MAX_CUT_SIZE; cut++) { + float new_cost = cost[i - 1][size] + child_hit_prob[i - 1] * child[i - 1]->get_cost(cut); + if (new_cost < cost[i][size+cut]) { + cost[i][size+cut] = new_cost; + bt[i][size+cut] = cut; + } + } } } //Save the ways to archieve the minimum cost with a given cutsize - for(int i = nchilds; i <= MAX_CUT_SIZE; i++) - { + for (int i = nchilds; i <= MAX_CUT_SIZE; i++) { node->cut_cost[i-1] = cost[nchilds][i]; - if(cost[nchilds][i] < INFINITY) - { + if (cost[nchilds][i] < INFINITY) { int current_size = i; - for(int j=nchilds; j>0; j--) - { + for (int j=nchilds; j>0; j--) { child[j-1]->cut_size[i-1] = bt[j][current_size]; current_size -= bt[j][current_size]; } @@ -468,26 +439,22 @@ struct VBVH_optimalPackSIMD void calc_costs(Node *node) { - if( RE_rayobject_isAligned(node->child) ) - { + if ( RE_rayobject_isAligned(node->child) ) { int nchilds = 0; - for(Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) - { + for (Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) { calc_costs(child); nchilds++; } - for(int i=0; i<MAX_CUT_SIZE; i++) + for (int i=0; i<MAX_CUT_SIZE; i++) node->cut_cost[i] = INFINITY; //We are not allowed to look on nodes with with so many childs - if(nchilds > MAX_CUT_SIZE) - { + if (nchilds > MAX_CUT_SIZE) { float cost = 0; float parent_area = bb_area(node->bb, node->bb+3); - for(Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) - { + for (Node *child = node->child; child && RE_rayobject_isAligned(child); child = child->sibling) { cost += ((parent_area != 0.0f)? ( bb_area(child->bb, child->bb+3) / parent_area ): 1.0f) * child->get_cost(1); } @@ -495,16 +462,13 @@ struct VBVH_optimalPackSIMD node->cut_cost[0] = cost; node->best_cutsize = nchilds; } - else - { + else { calc_best calc(node); //calc expected cost if we optimaly pack this node - for(int cutsize=nchilds; cutsize<=MAX_CUT_SIZE; cutsize++) - { + for (int cutsize=nchilds; cutsize<=MAX_CUT_SIZE; cutsize++) { float m = node->get_cost(cutsize) + testcost(cutsize); - if(m < node->cut_cost[0]) - { + if (m < node->cut_cost[0]) { node->cut_cost[0] = m; node->best_cutsize = cutsize; } @@ -512,24 +476,22 @@ struct VBVH_optimalPackSIMD } assert(node->cut_cost[0] != INFINITY); } - else - { + else { node->cut_cost[0] = 1.0f; - for(int i=1; i<MAX_CUT_SIZE; i++) + for (int i = 1; i < MAX_CUT_SIZE; i++) node->cut_cost[i] = INFINITY; } } Node *transform(Node *node) { - if(RE_rayobject_isAligned(node->child)) - { + if (RE_rayobject_isAligned(node->child)) { static int num = 0; bool first = false; - if(num == 0) { num++; first = true; } + if (num == 0) { num++; first = true; } calc_costs(node); - if((G.debug & G_DEBUG) && first) printf("expected cost = %f (%d)\n", node->cut_cost[0], node->best_cutsize ); + if ((G.debug & G_DEBUG) && first) printf("expected cost = %f (%d)\n", node->cut_cost[0], node->best_cutsize ); node->optimize(); } return node; |