Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/render/intern/raytrace/reorganize.h
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/render/intern/raytrace/reorganize.h')
-rw-r--r--source/blender/render/intern/raytrace/reorganize.h188
1 files changed, 113 insertions, 75 deletions
diff --git a/source/blender/render/intern/raytrace/reorganize.h b/source/blender/render/intern/raytrace/reorganize.h
index 1930e5bb32b..68b2b22ecdd 100644
--- a/source/blender/render/intern/raytrace/reorganize.h
+++ b/source/blender/render/intern/raytrace/reorganize.h
@@ -66,15 +66,17 @@ 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);
}
}
@@ -87,23 +89,28 @@ 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;
@@ -116,7 +123,8 @@ void reorganize(Node *root)
}
}
- if (node != root) {
+ if(node != root)
+ {
}
}
}
@@ -129,24 +137,29 @@ 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;
}
}
@@ -158,16 +171,18 @@ 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;
@@ -177,14 +192,15 @@ 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);
}
@@ -194,27 +210,30 @@ 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);
}
@@ -229,17 +248,19 @@ 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;
@@ -265,17 +286,18 @@ 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);
}
@@ -325,27 +347,32 @@ 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);
@@ -354,7 +381,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();
}
}
@@ -388,7 +415,8 @@ 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++;
@@ -399,35 +427,36 @@ 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];
}
@@ -439,22 +468,26 @@ 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);
}
@@ -462,13 +495,16 @@ 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;
}
@@ -476,22 +512,24 @@ 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;
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-12 14:10:32 +0300