Another try with building better trees (this should never make worst trees)
authorAndre Susano Pinto <andresusanopinto@gmail.com>
Fri, 17 Jul 2009 19:09:42 +0000 (19:09 +0000)
committerAndre Susano Pinto <andresusanopinto@gmail.com>
Fri, 17 Jul 2009 19:09:42 +0000 (19:09 +0000)
Expected number of BB tests should reduce a bit (depending on the scene)

source/blender/render/intern/raytrace/rayobject_vbvh.cpp
source/blender/render/intern/raytrace/reorganize.h [new file with mode: 0644]

index 8c2139fe6ca0e301fa7d6746898e60cbce54293b..17ed63e366969dca76116e761cc20554f1a1431d 100644 (file)
@@ -38,6 +38,7 @@ extern "C"
 #include "rayobject.h"
 };
 
+#include "reorganize.h"
 #include "bvh.h"
 #include <queue>
 
@@ -146,9 +147,9 @@ void pushdown(Node *parent)
                //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 @@ void pushdown(Node *parent)
                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 *bvh_rearrange(Tree *tree, Builder *builder, float *cost)
        {
                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;
 
+               *child = 0;
                return node;
        }
 }
@@ -246,9 +274,13 @@ void bvh_done<BVHTree>(BVHTree *obj)
        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 bvh_hint_bb(Tree *tree, LCTSHint *hint, float *min, float *max)
 
 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);
 }
diff --git a/source/blender/render/intern/raytrace/reorganize.h b/source/blender/render/intern/raytrace/reorganize.h
new file mode 100644 (file)
index 0000000..723c2b7
--- /dev/null
@@ -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;  
+}