Revision: 21666
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=21666
Author: jaguarandi
Date: 2009-07-17 21:09:42 +0200 (Fri, 17 Jul 2009)
Log Message:
-----------
Another try with building better trees (this should never make worst trees)
Expected number of BB tests should reduce a bit (depending on the scene)
Modified Paths:
--------------
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
Added Paths:
-----------
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h
Modified:
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
2009-07-17 18:35:49 UTC (rev 21665)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/rayobject_vbvh.cpp
2009-07-17 19:09:42 UTC (rev 21666)
@@ -38,6 +38,7 @@
#include "rayobject.h"
};
+#include "reorganize.h"
#include "bvh.h"
#include <queue>
@@ -146,9 +147,9 @@
//assert(bb_fits_inside(parent->bb, parent->bb+3, child->bb,
child->bb+3));
for(Node *i = parent->child; RayObject_isAligned(i) && i; i =
i->sibling)
- if(child != i && bb_fits_inside(i->bb, i->bb+3, child->bb,
child->bb+3))
+ if(child != i && bb_fits_inside(i->bb, i->bb+3, child->bb,
child->bb+3) && RayObject_isAligned(i->child))
{
-// todo optimize (hsould the one with the smallest area
+// todo optimize (should the one with the smallest area?)
// float ia = bb_area(i->bb, i->bb+3)
// if(child->i)
*s_child = child->sibling;
@@ -167,8 +168,65 @@
pushdown( i );
}
+template<class Node>
+int count_childs(Node *parent)
+{
+ int n = 0;
+ for(Node *i = parent->child; i; i = i->sibling)
+ {
+ n++;
+ if(!RayObject_isAligned(i))
+ break;
+ }
+
+ return n;
+}
+
+template<class Node>
+void append_sibling(Node *node, Node *sibling)
+{
+ while(node->sibling)
+ node = node->sibling;
+
+ node->sibling = sibling;
+}
+
+template<class Node>
+void pushup(Node *parent)
+{
+ float p_area = bb_area(parent->bb, parent->bb+3);
+ Node **prev = &parent->child;
+ for(Node *child = parent->child; RayObject_isAligned(child) && child; )
+ {
+ float c_area = bb_area(child->bb, child->bb+3) ;
+ int nchilds = count_childs(child);
+ float original_cost = (c_area / p_area)*nchilds + 1;
+ float flatten_cost = nchilds;
+ if(flatten_cost < original_cost && nchilds >= 2)
+ {
+ append_sibling(child, child->child);
+ child = child->sibling;
+ *prev = child;
+
+// *prev = child->child;
+// append_sibling( *prev, child->sibling );
+// child = *prev;
+ tot_pushup++;
+ }
+ else
+ {
+ *prev = child;
+ prev = &(*prev)->sibling;
+ child = *prev;
+ }
+ }
+
+ for(Node *child = parent->child; RayObject_isAligned(child) && child;
child = child->sibling)
+ pushup(child);
+}
+
template<class Tree, class Node, class Builder>
-Node *bvh_rearrange(Tree *tree, Builder *builder, float *cost)
+Node *bvh_rearrange(Tree *tree, Builder *builder)
{
int size = rtbuild_size(builder);
@@ -176,61 +234,31 @@
{
Node *node = bvh_new_node(tree);
INIT_MINMAX(node->bb, node->bb+3);
- rtbuild_merge_bb(builder, node->bb, node->bb+3);
-
+ rtbuild_merge_bb(builder, node->bb, node->bb+3);
node->child = (BVHNode*)builder->begin[0];
-
- *cost =
RE_rayobject_cost((RayObject*)node->child)+RAY_BB_TEST_COST;
return node;
}
else
{
Node *node = bvh_new_node(tree);
- float parent_area;
-
+
INIT_MINMAX(node->bb, node->bb+3);
rtbuild_merge_bb(builder, node->bb, node->bb+3);
- parent_area = bb_area( node->bb, node->bb+3 );
Node **child = &node->child;
-
- std::queue<Builder> childs;
- childs.push(*builder);
-
- *cost = 0;
-
- while(!childs.empty())
+
+ int nc = rtbuild_split(builder, 2);
+ assert(nc == 2);
+ for(int i=0; i<nc; i++)
{
- Builder b = childs.front();
- childs.pop();
+ Builder tmp;
+ rtbuild_get_child(builder, i, &tmp);
- float hit_prob = rtbuild_area(&b) / parent_area;
- if(hit_prob > 1.0f / 2.0f && rtbuild_size(&b) > 1)
- {
- //The expected number of BB test is smaller if
we directly add the 2 childs of this node
- int nc = rtbuild_split(&b, 2);
- assert(nc == 2);
- for(int i=0; i<nc; i++)
- {
- Builder tmp;
- rtbuild_get_child(&b, i, &tmp);
- childs.push(tmp);
- }
- tot_pushup++;
-
- }
- else
- {
- float tcost;
- *child = bvh_rearrange<Tree,Node,Builder>(tree,
&b, &tcost);
- child = &((*child)->sibling);
-
- *cost += tcost*hit_prob + RAY_BB_TEST_COST;
- }
+ *child = bvh_rearrange<Tree,Node,Builder>(tree, &tmp);
+ child = &((*child)->sibling);
}
- assert(child != &node->child);
+
*child = 0;
-
return node;
}
}
@@ -246,9 +274,13 @@
BLI_memarena_use_malloc(obj->node_arena);
- obj->root = bvh_rearrange<BVHTree,BVHNode,RTBuilder>( obj,
obj->builder, &obj->cost );
+ obj->root = bvh_rearrange<BVHTree,BVHNode,RTBuilder>( obj, obj->builder
);
+ reorganize(obj->root);
+ remove_useless(obj->root, &obj->root);
+ pushup(obj->root);
pushdown(obj->root);
-// obj->cost = 1.0;
+// obj->root = memory_rearrange(obj->root);
+ obj->cost = 1.0;
rtbuild_free( obj->builder );
obj->builder = NULL;
@@ -336,14 +368,16 @@
void bfree(BVHTree *tree)
{
- if(tot_pushup + tot_pushdown + tot_hints)
+ if(tot_pushup + tot_pushdown + tot_hints + tot_moves)
{
printf("tot pushups: %d\n", tot_pushup);
printf("tot pushdowns: %d\n", tot_pushdown);
+ printf("tot moves: %d\n", tot_moves);
printf("tot hints created: %d\n", tot_hints);
tot_pushup = 0;
tot_pushdown = 0;
tot_hints = 0;
+ tot_moves = 0;
}
bvh_free(tree);
}
Added:
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h
===================================================================
---
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h
(rev 0)
+++
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h
2009-07-17 19:09:42 UTC (rev 21666)
@@ -0,0 +1,138 @@
+/**
+ * $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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 <algorithm>
+#include <queue>
+
+template<class Node>
+bool node_fits_inside(Node *a, Node *b)
+{
+ return bb_fits_inside(b->bb, b->bb+3, a->bb, a->bb+3);
+}
+
+template<class Node>
+void reorganize_find_fittest_parent(Node *tree, Node *node,
std::pair<float,Node*> &cost)
+{
+ std::queue<Node*> q;
+ q.push(tree);
+
+ while(!q.empty())
+ {
+ Node *parent = q.front();
+ q.pop();
+
+ if(parent == node) continue;
+ if(node_fits_inside(node, parent) &&
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)
+ q.push(child);
+ }
+ }
+}
+
+static int tot_moves = 0;
+template<class Node>
+void reorganize(Node *root)
+{
+ std::queue<Node*> q;
+
+ q.push(root);
+ while(!q.empty())
+ {
+ Node * node = q.front();
+ q.pop();
+
+ if( RayObject_isAligned(node->child) )
+ {
+ for(Node **prev = &node->child; *prev; )
+ {
+ assert( 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)
+ {
+ //Already inside the fitnest BB
+ prev = &(*prev)->sibling;
+ }
+ else
+ {
+ Node *tmp = *prev;
+ *prev = (*prev)->sibling;
+
+ tmp->sibling = best.second->child;
+ best.second->child = tmp;
+
+ tot_moves++;
+ }
+
+
+ }
+ }
+ if(node != root)
+ {
+ }
+ }
+}
+
+/*
+ * Prunes useless nodes from trees:
+ * erases nodes with total ammount of primitives = 0
+ * prunes nodes with only one child (except if that child is a primitive)
+ */
+template<class Node>
+void remove_useless(Node *node, Node **new_node)
+{
+ if( RayObject_isAligned(node->child) )
+ {
+
+ for(Node **prev = &node->child; *prev; )
+ {
+ Node *next = (*prev)->sibling;
+ remove_useless(*prev, prev);
+ if(*prev == 0)
+ *prev = next;
+ else
+ {
+ (*prev)->sibling = next;
+ prev = &((*prev)->sibling);
+ }
+ }
+ }
+ if(node->child)
+ {
+ if(RayObject_isAligned(node->child) && node->child->child == 0)
+ *new_node = node->child;
+ }
+ else if(node->child == 0)
+ *new_node = 0;
+}
Property changes on:
branches/soc-2009-jaguarandi/source/blender/render/intern/raytrace/reorganize.h
___________________________________________________________________
Name: svn:keywords
+ Author Date Id Revision
Name: svn:eol-style
+ native
_______________________________________________
Bf-blender-cvs mailing list
Bf-blender-cvs@blender.org
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
